leetcode 做题思路快查

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. 反转字符串中的单词151. 反转字符串中的单词151. 反转字符串中的单词

        思路1：python api， split, reverse

14. 最长公共前缀

155. 最小栈

        使用辅助栈，记录最小元素

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. 删除有序数组中的重复项

        考虑到a[], m; b[], n; 对a采用逆序的将a, b 中的元素放入a. 这样就不需要额外空间；