leetcode 做题思路快查
58. 最后一个单词的长度
考虑从字符串size() - 1处倒序的定义两个指针；多的空格用while(j > 0 && s[j] == ' ') j--跳过； 考虑"a" "_"这两个场景
s45. 跳跃游戏 II
思路：动态规划，f[i] = 0...i-1跳到i的最少步数；外层循环 0..len-1, 内层循环 0..i -1 (0..i - 1)跳跃到i的最少步数； 更新条件是 j + a[j] >= i(能到达i)
s53. 最大子数组和
思路: 关键是当前子数组和
// 当前子数组和currentSum = max(currentSum + nums[l], nums[l]);maxSum = max(maxSum, currentSum);128. 最长连续序列
arr = 1 2 3 4 100 200;
A. for将元素加入hash_set; B.对于每个x, x-1不在hash_set则x是bengin节点，begin_vev = 1 , 100 , 200; C. 对于bengin_vec中，如果x++在hash_set，则序列长度++
151. 反转字符串中的单词
思路1：python api， split, reverse；
思路2：考虑从字符串size() - 1处倒序的定义两个指针；多的空格用while(s[j] == ' ') j--跳过；
14. 最长公共前缀
155. 最小栈
思路：使用第2个辅助栈，记录最小元素
20. 有效的括号
21. 合并两个有序链表
141. 环形链表
快慢指针fast, slow； 如果slow==fast
146. LRU 缓存1
42. 接雨水
1. 单调递减栈【3， 2】， 如果遇见4比2大，那么3，2， 4中间可以取雨水
92. 反转链表 II
206. 反转链表
思路：头插法
100. 相同的树
思路1: 递归
104. 二叉树的最大深度
思路1：最简单的思路递归 1 + max(depth(node->left), depth(node->right))
思路2：使用栈实现递归，stk.push(root); while(!stk.empty) {}
200. 岛屿数量
1. 上下左右DFS，2. 遍历过的标记为2
17. 电话号码的字母组合
思路：回溯DFS
23. 合并 K 个升序链表
思路1： 分治法
思路2：大顶堆，需要实现大顶堆的排序方法
struct Status {int val;ListNode *ptr;bool operator < (const Status &rhs) const {return val > rhs.val;}};priority_queue <Status> q;3. 无重复字符的最长子串 tag 滑动窗口
//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {//当前考虑的元素while (l <= r && check()) {//区间[left,right]不符合题意//扩展左边界}//区间[left,right]符合题意，统计相关信息
}5. 最长回文子串
题目：s=babad 输出 aba
思路：f(i,j) = 1， s[i:j] 为回文；
初始化f(i,i)=1; 状态转移 f(i-1, j+1) = f(i,j) & s[i] == s[j];
边界条件， i - 1 > 0, j + 1 < n
循环：外循环，枚举字串长度， 内循环，枚举左边界
215. 数组中的第K个最大元素
思路1：使用堆来求解，建立大顶堆，再将头部元素pop出来. priority_queue<int> pQ;
思路2：快排后取值
67. 二进制求和
思路：大数字求和，需要考虑进位；
121. 买卖股票的最佳时机
输入：[7,1,5,3,6,4]， 输出 5
思路：变量A记录下标i天以前最低的股价，变量B = arr[i] - A, 对B求最大
189. 轮转数组
思路：旋转2次；1 2 3 4 5 ==> 3 2 1, 5 4 ==> 4 5 1 2 3
26. 删除有序数组中的重复项
思路：定义slow, fast；slow指向要更新的元素，fast指向检查的元素，如果fast == fast - 1 => slow++ = fast++;
X.合并两个有序数组
考虑到a[], m; b[], n; 对a采用逆序的将a, b 中的元素放入a. 这样就不需要额外空间；