1、枚举
对所有可能的情况进行枚举。面对枚举类型的题目,在想到思路的时候,要习惯于分析一下这种方法的复杂度是多少,结合题目的数据量分析这样的方法是否可行,然后再动手写代码,节约时间。
计算机1000MS,大约可进行10^7次运算。所以,常见的代码时间复杂度,1秒内可接受的数据量如下表:
复杂度 | 数据量 |
---|---|
O(n!) | 10 |
O(2^n) | 20 |
O(n^3) | 200 |
O(n^2) | 3000 |
O(nlogn) | 10^6 |
O(n) | 10^7 |
O(n^(1/2)) | 10^14 |
O(logn) | > 10^20 |
上表中,数据量就是n
最多能取值多少,不会导致超时错误。
2、模拟
只需利用程序实现题目的要求。模拟总共可分为3大类,分别是图形排版、日期问题、其他模拟,学习基本的做题思路之后,多加练习,那么这类题目就不会有太多困难。
- 图形排版:这种问题如果字符阵列的规律不太容易通过从上到下、从左到右的输出直接打印出来,那么思路是通过构造一个二维的字符数组,先根据题面要求画图形,总结规律并转换成数学公式,比如
h+2*i
这种,然后构造出图形保存到二维数组中,最后按顺序输出二维数组内容即可。如果图形可以直接打印出来的话,那么也要抽象出图形,标记边长、坐标什么的,总结出数学公式。 - 日期问题:一个公式,包含3个关键变量,日期A,天数,日期B,一般都是给你其中的两个变量,求另外一个变量,这类问题注意预处理(用空间换时间) 的概念,定义一个
dayTable[row][month]
数组,保存平年、闰年每个月的天数(PS:平年共365天/年,闰年366天/年),接着写一个判断是不是闰年的函数,如果是闰年,2月有29天,愉快编写主函数。 - 其他模拟:五花八门,只需根据题面要求进行模拟即可。同样可以采用预处理,用空间换时间的办法,简洁高效。