跳到主要内容

LeetCode 1~50

5、最长回文子串​

dp[i][j]=dp[i+1][j−1]&&s[i]==s[j]dp[i][j] = dp[i+1][j-1] \&\& s[i] == s[j]

11、盛最多水的容器​

15、三数之和​

题目大意是从数组中选3个数使其和为0，找出所有不重复的组合。本题主要难点在于，怎么保证组合的不重复？

由于结果与数组顺序无关，可以先将数组排序。先考虑2个数的情况，即从数组中找2个数使其和为指定值，可以参考两数之和的解法。为了避免组合重复，每次添加组合前先判断是否与之前最后一个组合重复（为什么？因为数组是有序的）。

对于三数之和，遍历数组，将问题转化为两数之和，然后利用两数之和的结果，得到三数组合结果，同样通过判断之前最后一个组合的的第3个数是否重复来对组合进行判重。

17、电话号码的字母组合​

全排列，可以用递归解决。

19、删除链表的倒数第N个节点​

常规链表题，注意一些边界情况：

  • 删除的是头节点

22、括号生成​

回溯法，注意恢复现场。

31、下一个排列​

从后往前，找到数减小的位置，假设 nums[i-1] < nums[i]，在 [i, n-1] 区间找 >nums[i-1] 的最小值 nums[j]，然后将 nums[j] 与 nums[i-1] 交换，然后将 [i, n-1] 区间排序即可。

如果没有数减小的位置，说明是最后一个，那么将数组排序即可。

33、搜索旋转排序数组​

二分法

思路很容易，但不容易写对。

34、在排序数组中查找元素的第一个和最后一个位置​

二分法的三种模板

TODO：补充代码

39、组合总和​

回溯法，如何判重是难点。