入手

没思路就先暴力看看怎么做 再思考如何减少时间复杂度

数据处理

在对数据做是否满足要求判断时,每次操作都要改变原始数据的情况

如:查字符串时, 每次要做拼接或删除

  • 先暴力思考,如果认为不超时可以做
  • 否则找逻辑

对于循环类型的,每次变化数组长度不变,或是前后拼接,可以找到规律后利用 取模 来做到无需变化数组得到每次变化 如 对串 aabbc 每次取一部分拼接查找拼接后某索引对应的字符 aabbc bcaab caabb 就可以用取模运算 如查找第二位的值

	idx = 2; 每次取k位拼接到后面
	第一次取3,第二个的索引为原来的5
	第二次取1,第二个索引为原来的1  
	
	找到规律 idx = (idx + k) % n;
	就不用改变串来查找

判断时间复杂度高的数据计算类型

如果每次读取,查询再计算出结果的时间复杂度过大

  • 试试预处理 通过先处理可能出现的数据,再每次查询的方式做 例如打表

01串改画图

例子-组合数应用

对字符的思考改为对图论的思考,有时可以简化问题

分情况讨论

想不明白就分情况思考 一般可以理清楚思路