我们可以从中学到什么
第一次遇见这种题,不知道从哪下手;估计以后做多了,就有思路了
打表是一种典型的用空间换时间的技巧,一般指将所有可能需要用到的结果事先计算出来,这样后面需要用到时就可以直接查表获得
原本循环查询的时间复杂度是O(n),打表查询的话时间复杂度是O(1)
步骤:
1:先枚举年,在枚举月
2:看一年的12个月中,13号落在在周几
3:如果是闰年,2月+ 1
java代码
import java.util.Scanner;
public class Main{
static int[] month = {0,31,28,31,30,31,30,31,31,30,31,30,31}; //打表
static int[] weekday = new int[7]; //以星期几为索引,存储出现的次数
public static void main(String[] args){
Scanner in =new Scanner(System.in);
int n = in.nextInt();
int days = 0;
for(int year = 1900; year < 1900 + n; year ++) //枚举年
{
for(int i = 1; i <= 12; i ++) //枚举月
{
weekday[(days + 12) % 7] ++; //13号周几+1
days += month[i]; //跳转到下个月
if(i == 2)
{
if(year % 100 != 0 && year % 4 == 0 || year % 400 == 0) days++;
}
}
}
for(int i = 5, j = 0; j < 7; i = (i + 1)%7, j++) //j代表循环次数,i输出周六~周四
{
System.out.print(weekday[i] + " ");
}
}
}