解题之道 | 如何根据数据范围和算法复杂度猜测解题思路？

---

写在前面

• 发了个如何Knight选手怎么才能上到Guardian?的讨论，大佬刘好念说了个根据数据范围猜解题思路的技巧，也正好看到有人问怎么才能去猜，因此发个帖总结下自己想到的，欢迎大家补充讨论~

---

力扣题目需要的运算次数

• 根据过往做题经验，解力扣的题目需要的计算次数一般要控制在$10^6$这个量级才可以不出现TLE

---

算法与数据范围

• 可以根据各种算法的复杂度和题目我的数据量去估计会不会TLE

---

算法的复杂度与数据范围的量级

• $O(1)$：对于一些需要脑筋急转弯或者使用各种数学知识直接计算或者等复杂度在$O(1)$的算法，数据范围$n$基本不受限制
• $O(logn)$：对于二分查找等复杂度为$O(logn)$的算法，数据范围$n$一般可以在$10^9$这个量级内
• $O(n)$：对于单调栈、单调队列、差分数组、BFS、DFS、贪心、哈希、前缀和、一维动态规划等复杂度为$O(n)$的算法，$n$一般可以在$10^6$这个量级内
• $O(nlogn)$：对于快速排序、（堆）优先队列、图、分治、字典树、线段树、并查集等复杂度为$O(nlogn)$的算法，数据范围$n$一般可以在$10^5$这个量级内
• $O(n^2)$：对于二维动态规划等复杂度为$O(n^2)$的算法，数据范围$n$一般可以在$10^3$这个量级内
• $O(n^3)$：对于三维动态规划等复杂度为$O(n^3)$，数据范围$n$一般可以在$10^2$这个量级内
• $O(2^n)$：对于状态压缩等复杂度为$O(2^n)$的算法，数据范围$n$一般可以在$16$内（$2^{16}=65536$）

---

根据题目内容可能的解题思路 刘好念秘籍

还有几点：

• 如果求最值又有约束，可能是二分。
• 如果数据量为10^5，复杂度为O(nlogn)，可能要固定枚举一个值，然后二分另外一个值（可能还有贪心）；
• 题目中提到了字符串、数据范围为16或者12可能是状态压缩、动态规划；
• 关于网格的问题，数据小可能是DFS、BFS，数据大可能是动态规划；
• 关于日期的，可能是动态规划；
• 关于字符串内连续字符（字符位置相关）的，可能双指针；
• 明显先进先出、先进后出的，队列、栈模拟；
• 关于约数、素数的，可能先用O(nlogn)的复杂度将各个数字分解为质数之积；
• 关于与或非位运算的，可能状态压缩，或者总结规律（脑筋急转弯）；
• 关于区间操作的，可能树状数组、线段树；
• 关于节点之间连接关系的，可能并查集，拓扑排序；
• 关于二叉树父子关系的，可能树上动态规划；

一点点补充吧，不全，不一定有用；

---

总结

• 根据算法的复杂度和数据范围估算其是否控制在$10^6$这个量级，一般超出范围很容易就TLE