入手
没思路就先暴力看看怎么做 再思考如何减少时间复杂度
数据处理
在对数据做是否满足要求判断时,每次操作都要改变原始数据的情况
如:查字符串时, 每次要做拼接或删除
- 先暴力思考,如果认为不超时可以做
- 否则找逻辑
对于循环类型的,每次变化数组长度不变,或是前后拼接,可以找到规律后利用 取模 来做到无需变化数组得到每次变化 如 对串 aabbc 每次取一部分拼接查找拼接后某索引对应的字符 aabbc → bcaab → caabb 就可以用取模运算 如查找第二位的值
idx = 2; 每次取k位拼接到后面
第一次取3,第二个的索引为原来的5
第二次取1,第二个索引为原来的1
找到规律 idx = (idx + k) % n;
就不用改变串来查找
判断时间复杂度高的数据计算类型
如果每次读取,查询再计算出结果的时间复杂度过大
- 试试预处理 通过先处理可能出现的数据,再每次查询的方式做 例如打表
01串改画图
对字符的思考改为对图论的思考,有时可以简化问题
分情况讨论
想不明白就分情况思考 一般可以理清楚思路