这是小川的第415次更新,第448篇原创

看题和准备

今天介绍的是LeetCode算法题中Easy级别的第266题(顺位题号是1185)。给定日期,返回该日期的星期几。输入为三个整数,分别代表日,月和年。

以下列值之一返回答案:{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}

例如:

输入:day = 31, month = 8, year = 2019
输出:"Saturday"

输入:day = 18, month = 7, year = 1999
输出:"Sunday"

输入:day = 15, month = 8, year = 1993
输出:"Sunday"

约束

  • 给定的日期是1971年至2100年之间的有效日期。

第一种解法

题目要求我们计算给定日期是星期几,直接调用Calendar类的API,如果是面试不建议这么做。

public String dayOfTheWeek(int day, int month, int year) {
    String[] week = {"Sunday", "Monday", "Tuesday", "Wednesday",
            "Thursday", "Friday", "Saturday"};
    Calendar cal = Calendar.getInstance();
    cal.set(year, month-1, day);
    int i = cal.get(Calendar.DAY_OF_WEEK)-1;
    if (i<0) {
        i = 0;
    }
    return week[i];
}


第二种解法

第一步,先算出从1971年距离当前年份的前一年总共有多少天,平年加365天,闰年加366天。

第二步,再计算给的月份的前几个月的天数之和,闰年2月有29天。

第三步,再加上给的天数减去1天,因为题目给的示例中星期天是第一天。

第四步,将最后得到的天数再加上5天,因为1971年1月1日是星期五,然后对7取余。

public String dayOfTheWeek2(int day, int month, int year) {
    String[] week = {"Sunday", "Monday", "Tuesday", "Wednesday",
            "Thursday", "Friday", "Saturday"};
    int[] dayOfMonth = {31,28,31,30,31,30,31,31,30,31,30,31};
    int total = 0;
    for (int i=1971; i<year; i++) {
        if (i%4 == 0) {
            total++;
        }
        total += 365;
    }
    if (year%4 == 0) {
        dayOfMonth[1] = 29;
    }
    for (int j=0; j<month-1; j++) {
        total += dayOfMonth[j];
    }
    total += day - 1;
    return week[(total + 5)%7];
}


第三种解法

利用蔡勒公式来解。

w =  (c/4- 2*c + y + y/4 + 26*(m + 1)/10 + d - 1) % 7;
  • c:代表世纪,是年份的前两位,比如1971,c就为19。

  • y:是年份的后两位,比如1971,y就是71。

  • m:代表月,3<= m <= 14,某年的1、2月要看作上一年的13、14月来计算,比如2003年1月1日,要看作2002年的13月1日来计算。

  • d:代表日。

  • w:计算结果,代表星期几。

有一点需要注意,利用蔡勒公式算出来的数,有可能为负数,因此需要加上7,再取余一次,才能当作索引去字符串数组里取值。

public String dayOfTheWeek3(int day, int month, int year) {
    String[] week = { "Sunday", "Monday", "Tuesday", 
            "Wednesday", "Thursday", "Friday", "Saturday" };
    //如果月份小于3月,则月份加12,年份减1
    if (month < 3) {
        month += 12;
        year -= 1;
    }
    int J = year / 100; // 世纪,年份前两位
    int K = year % 100; // 年份,年份后两位
    int h = (K + K / 4 + J / 4 - 2 * J +
             26 * (month + 1) / 10 + day - 1) % 7;
    // h算出来可能为负数,需要补7后再取一次余
    return week[(h + 7) % 7];
}


第四种解法

利用基姆拉尔森公式来计算。

Week = (Day + 2*Month + 3*(Month+1)/5 + Year + Year/4 - Year/100 + Year/400) % 7;

如果月份小于3月,则月份加12,年份减1。对于星期几,在基姆拉尔森公式里,星期一是排在第一位,星期天排在最后一位。

public String dayOfTheWeek4(int day, int month, int year) {
    String[] week = {"Monday", "Tuesday", "Wednesday", 
            "Thursday", "Friday", "Saturday", "Sunday"};
    if (month < 3) {
        month += 12;
        year -= 1;
    }
    int w = (day + 2*month + 3*(month+1)/5 + 
            year + year/4 - year/100 + year/400) % 7;
    return week[w];
}


小结

算法专题目前已更新LeetCode算法题文章272+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、在看就是对我最大的回报和支持!

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!