空间换时间的常用技巧:

  1. 记录出现次数或出现位置(哈希表可以看成是O(1)复杂度)
  2. 查表法(打表)

字符串

  1. 分隔字符串
  2. 统计单词数
  3. 回文

除前缀后,后缀后也是可以用的,比如:https://leetcode-cn.com/problems/shifting-letters/

二叉树的中序遍历,一定是将所有结点按从小到大的顺序输出。


构造并查集时如果没有直接提供整数型编号,比如对一堆字符串建立并查集,可以先将每个字符串映射成唯一的数字,使用map<string, int>配合自增来实现。

涉及单链表插入问题,可以先给链表补一个空的头结点,以方便处理在头结点这前进行插入的情况。

涉及链表插入,原则一定是先补全待插入结点的指针域,再调整前后结点的指针域。

贪心:

https://leetcode-cn.com/problems/advantage-shuffle/

一定是每一步都有当前的最优解才可以用贪心算法,如果不到最后一步都不知道哪个是最优秀解,贪心就失效了,比如这题:https://leetcode-cn.com/problems/maximum-score-from-performing-multiplication-operations/,这里,每次选从左右里选一个,貌似可以用贪心拿到每次的最优解,但是其实是错误的,有可能上一步的最优解把下一步更优的解排除了,所以不到最后一步,都无法确定哪个是最优的,也就不能应用贪心算法来求解。

并查集合:

https://leetcode-cn.com/problems/number-of-provinces/

对于并查集来说,刚建好的集合有些路径可能是没压缩的,所以在执行查找时可以顺便执行一次压缩,而且查找时的路径压缩是针对整条路径上的点进行压缩,而不单单是末端结点。

快速幂:

https://leetcode-cn.com/problems/count-good-numbers/

前缀和:

https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/

滑动窗口:

https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/

单调栈:

https://leetcode-cn.com/problems/daily-temperatures/

双指针:

https://leetcode-cn.com/problems/reverse-only-letters/


  • 无标签