20天leetcodeHot100 刷题笔记

day1 4.17

1.两数之和 *

• 在整数数组中找出和为给定值的两个元素下标

1. 两趟循环肯定可以找出来但是O(n^2)
2. 为了加快寻找使用hash表 (k,v) = (数组值, 数组下标)
3. 遍历新元素的时候,检查表中有没有对应的k,有就return, 没有就将这个元素加入

283.移动零 **

• 将数组的零元素移到末尾, 同时保证非0元素相对位置, 且要求不能复制数组

1. 超时的做法, 每次遍历找到最右侧的0, 然后与其右边交换位置, 直到所有0都到最右边 循环太多次
2. 用一个指针记录非0的位置, 遍历一次数组, 把所有非0的都填到这个指针记录的位置
3. 剩下的就是填0

160.相交链表 *

• 数据结构期末考手写过, 找出两个链表是否有相交节点

1. 法1, 结合hash表, 先遍历其中一个链表, 将其中信息记录下来(k,v) = (listNode, listNode.val), 再遍历另一个链表, 如果hash表中有对应的key直接返回
2. 法2, 两个链表, 两个指针分别遍历, 遍历完的从另一个链表的头再开始遍历, 这样两个指针走完一趟, 恰好消除了长度差, 若第二趟再相遇就是交点

94.二叉树的中序遍历 *

• 返回二叉树的中序遍历

1. 递归法很简单, 注意中序遍历是, 左-根-右
2. 迭代法, 用一个栈来模拟递归的过程, 先一直找到最左边的子节点, 这个过程一直入栈, 然后进行出栈并把当前出栈节点加入ans, 遍历该节点的右节点

121.买卖股票的最佳时机 **

• 给定一个数组表示未来n天的股票价格, 决定在哪一天买入和哪一天卖出获取最大利润, 返回最大利润值

1. 法1, 结合题目过程进行贪心, 每次找第i小的作为买入天, 然后再该天后面找最大的作为卖出天, 计算一个利润, 循环找n次, 在网站上会超时
2. 法2, 对于方法1的简化, 只要遍历一次就好, 遍历的过程中, 记录一个最小值, 当前遍历到的减去最小值, 计算一个利润, 同时维护最大值, 遍历完得到的就是最大利润

day2 4.18

20.有效的括号 *

• 判断字符串的括号是否匹配

1. 用栈进行判断, 读到左括号就入栈, 读到右括号, 先看栈顶是不是对应的左括号, 若是就出栈, 不是就直接return false, 最后看栈是否为空, 非空return false
2. 可以提前判断字符串长度是否为偶数

70.爬楼梯 *

• 爬n阶楼梯, 每次可以爬1级或2级, 返回有多少种爬楼梯方式

1. 法1, 递归思想, 最后一步只有两种情况, 要么走1步(climb(n-1)), 要么走2步(climb(n-2)), 递归会超时
2. 法2, 根据递归思想写出迭代的解法, 也就是动态规划的思想

35.搜索插入位置 *

• 在排序后的数组中找出目标值的位置, 如果不存在, 返回应该插入的位置

1. 二分法, 关键就是边界条件的处理

104.二叉树的最大深度 *

• 返回一个二叉树的最大深度

1. 递归, 深度优先遍历, 访问一个节点的左和右的深度, 求他们的最大值

206.反转链表 *

• 输入单链表的头节点, 返回翻转后的链表

1. 链表的常规操作, 记录一个当前节点, 前一个节点, 后一个节点, 调整节点的指针指向
2. 注意最后一个节点可能没被链接上, 要仔细考虑
3. 还要考虑只有一个头节点的情况
4. 递归解法, 先把除了head之外的所有节点反转得到newHead, 那么这时候就得到一个newHead, 和一个head指向反转后的最后一个节点, 调整指针, 使这个head被丢出去就可以了

public ListNode reverseList(ListNode head) {
   //head->1 -> 2 -> 3 -> 4 -> 5  
  if (head == null || head.next == null) {
        return head;
    }
    //                  HEAD->1 
    //                        ↓
    //newHead->5 -> 4 -> 3 -> 2
    ListNode newHead = reverseList(head.next);


    //                 HEAD-> 1 
    //                        ↑↓
    //newHead->5 -> 4 -> 3 -> 2
    head.next.next = head;


     //                 HEAD->1 
    //                        ↑
    //newHead->5 -> 4 -> 3 -> 2
    head.next = null;


    //newHead->5 -> 4 -> 3 -> 2 ->1
    return newHead;
}

day3 4.19

49.字母异位词分组 **

• 给定一个字符串数组, 将其中的字母异位词组合在一起

1. 遍历这个字符串数组, 每次将遍历到的字符串排序, 作为key, 检查hashmap(k,v)=(String,List)里有没有对应的key
2. 若有, 则将其value的list增加上当前排序前的字符串
3. 若没有, 则添加这个key
4. 最后遍历hashmap的value即可

234.回文链表 *

• 给定单链表的表头, 判断是否是回文链表

1. 将原始链表复制到数组上, 然后对数组进行是否回文的判断
2. 利用递归法, 递归到最小情况后返回的过程其实就是从后往前遍历, 利用一个全局变量来记录从前往后遍历的节点.

200.岛屿数量 *

• 给定一个二维数组, 0表示水, 1表示陆地, 判断其中岛屿的数目

1. 建立一个二维辅助数组, 表示这个地方有没有被遍历过
2. 搜索整个图, 遇到1, 如果当前没被遍历过, ans+1且进行遍历这个地方的所有相邻区域, 辅助数组对应位置设为true

搬运liweiwei和liuyubobo大佬的一段话：棋盘上的搜索问题，不能，也没有必要在输入的 board 上修改，必须使用标准的做法：建立 visited 布尔数组辅助完成题目给出的任务。

136.只出现一次的数字 **

• 在给定的数组中, 找出只出现过一次的元素下标

1. 方法1, 用hashMap加快搜索, 遍历数组, 若hasMap中没有key就将当前数作为key存入, 若有则删去, 最后hashMap中只剩下一个key, 就是答案

2. 题目原本要求不使用额外空间, 不需要额外空间的方法，就往位运算上想

3. 交换律：a ^ b ^ c <=> a ^ c ^ b

4. 任何数于0异或为任何数 0 ^ n => n

5. 相同的数异或为0: n ^ n => 0

6. 2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3

73.矩阵置零 *

• 给定一个矩阵, 若一个元素为0, 则将该行该列都设为0

1. 使用一个大小为n+m的辅助数组来记录当前行和列是否需要置0, 前n表示行, 后m表示列
2. 第一次遍历矩阵, 若遍历到0, 把辅助数组对应的行和列的位置设为true
3. 第二次遍历进行填0

day4 4.20

53.最大子数组和 **

• 找出数组中连续的具有最大和的子数组

1. 应该意识到只有负数会使这个子数组和减小, 遍历一遍数组过程中, 更新当前的最大值, 且如果当前和已经小于0, 就没有继续下去的必要, 重新开始一个子数组计算

最开始的领导在这条路往后招收人才，遇到好的就收，遇到不好的也收毕竟要看看后面有没有特别好的可以抵消不好的影响，直至归零，这时不得已只能换个领导往后招收人才，同时历史的记录者记录了在这条路出现的巅峰。

56.合并区间 *

• 合并所有重叠的区间, 返回不重叠的区间数组

1. 先对原始区间进行排序, 然后按从小到大去决定要不要合并区间就可以了

141.环形链表 *

• 给定链表的头, 判断这个链表有没有环

1. 方法1, 用hashMap存储访问过的节点, 当再次访问到相同节点就是有环
2. 方法2, 快慢指针, 快指针一次走两步, 慢指针一次走一步, 若快指针走到null, 就是没有环, 若二者相遇就是有环

142.环形链表2 **

• 给定链表的头, 判断这个链表有没有环, 并输出环的第一个节点

1. 方法1, 用hashMap存储访问过的节点, 当再次访问到相同节点就是有环, 不用改
2. 方法2, slow指针和fast指针相遇的时候, 假设fast已经在环内走了n圈, 记入环前有a个节点, 相遇处距离环开头b, 距环结束c, 则 fast指针共走过了 a + (n-1) *(b+c) + b = a + nb + (n-1)c
3. 因为fast指针走的速度是slow的两倍, 距离也是两倍, 有a + nb + (n-1)c = 2(a + b), 得到a = (n-1)(b + c) - b
4. 即若有一个节点现在从头开始走, 到入环, slow指针刚好走n-1圈 - b, 也到达入环点, 他们将在入环点相遇

128.最长连续序列 **

• 给定未排序的整数数组, 找出数字连续的最长序列

1. 使用hashMap(k,v)=(数组中的数, 当前数的最长连续值), 遍历数组的过程中, 若当前数已经在hashMap中跳过
2. 在hashMap中找当前数的前一个元素和后一个元素是否存在, put(当前数, 1 + pre + next)
3. 维护这个连续数的左右两个边界, 即当前数-pre 和当前数+next
4. 在这个过程中记录最大值

day5 4.21

3.无重复字符的最长子串 **

• 找出字符串中没有重复字符的最长子字符串

1. 方法1, 最普通的遍历, 耗时
2. 方法2, 滑动窗口, 其实就是队列, 当没有重复元素的时候, 一直入队, 出现重复元素, 就把那个重复元素之前的都出队, 记录这个过程中的最长队列长度
3. 具体实现, 不用队列, 这个出队太麻烦, 使用hashMap(字符, 在字符串中的下标), 并记录队列的最左端元素的下标
4. 当访问到字符在hashMap中时, 更新一下队列的最左端, 相当于出队, 然后在把这个字符放进去hashMap, 相当于入队
5. 若不在hashMap中, 直接把这个字符放进去就可以
6. 计算一下队列长度, 也就是当前下标-左端, 同时更新一下最大值

226.翻转二叉树 *

• 给定二叉树的根节点, 返回左右翻转后的二叉树

1. 先翻转当前节点的左右子节点, 然后递归对当前节点的左右子节点调用翻转

101.对称二叉树 **

• 给定二叉树的根节点, 检查其是否是轴对称的

1. 注意递归是分为直接递归和间接递归, 这题输入是一个根节点, 无法在这个函数上直接递归, 要构造一个用来判断左子树的左子树是否等于右子树的右子树, 的辅助函数进行递归

day6 4.24

11.盛最多水的容器 **

• 给定一个数组, 表示木板的高度, 找出两块木板的组合成的容器能装最多的水, 既要考虑高度也要考虑面积

1. 第一次看到题有点无从下手, 看提示后找到思路
2. 重点在于木桶定律, 我每次只移动短的边, 才有可能找到最大值
3. 这种题常见就是遍历一遍记录最大值

解题思路 双指针法：使用两个指针，一个指向数组的起始位置（left），另一个指向数组的末尾位置（right）。 计算面积：计算当前两个指针所指向的线段与x轴构成的容器的面积，面积由较短的那条线的高度和两个指针之间的距离决定。 移动指针：为了寻找可能更大的面积，移动较短的那条线的指针向内侧移动一位，因为移动较长的线的指针不会增加容器的高度，而移动较短的线的指针有可能找到更高的线，从而增加面积。 更新最大面积：在每次移动指针后，计算新的面积，并更新最大面积。 重复步骤：重复上述过程，直到两个指针相遇。

15.三数之和 **

• 给定整数数组, 输出其中满足三个数之和为0的三个数字的列表

1. 尝试使用先给数组排序, 然后从头和尾向中间进行查找, 但处理不清楚头尾指针该如何移动, 找不全
2. 尝试递归全部展开, 超时
3. 要按照固定的顺序从小到大遍历数组, 再遍历到i的时候, 再从i+1, 和length-1 开始由两端向中间遍历, 注意去除重复值

169.多数元素 **

• 找出数组中个数超过 n/2 的元素

1. 想象一个选举的场景, 和自己相同的数字会投票给他, 不同的会投-1, 当前候选人选票小于0时更换候选人
2. 因为题目要求多数元素个数超过 n/2 最后肯定会剩下一个多数元素

543.二叉树的直径 **

• 找出二叉树上两个节点之间的最长长度

1. 方法1, 将树的直径看作左右子树的深度之和 再加上 1或2, 当只有左子树或右子树的时候加1, 两个都有加2
2. 但因为可能不是经过根节点, 所以要递归遍历一下所有子节点, 记录一个最大值
3. 方法2, 再求左右子树深度的时候就把这个最大值记录了, 减少一趟的遍历过程, 也不用考虑加1还是加2的问题, 因为再计算深度的时候就考虑了根是否有左右节点

day7 4.25

155.最小栈 **

• 设计一个能在常数时间内找到最小元素的栈

1. 为了方便获得最小值, 栈中元素除了要记录自己的值外, 还要记录当前的最小值
2. 用数组去模拟栈, 数组存储的是节点, 每个节点还会记录以他为栈顶时的最小值
3. push和pop的时候维护一下全局的最小值

21.合并两个有序链表 *

• 将两个升序链表合并为一个新的链表

1. 分别遍历两个链表, 用一个统一的node去遍历, 若a链表当前节点小于b链表当前节点, node.next = a

74.搜索二维矩阵 *

• 在m*n的矩阵中, 矩阵从左到右从上到下递增, 给出矩阵中是否含有目标元素

1. 先把这个矩阵每一行的最后一个元素提取出来存到一个数组中, 对这个数组进行二分查找, 可以找出目标在哪一行
2. 再对这一行元素进行二分查找
3. 方法2 从矩阵的右上角看, 是一棵二叉搜索树, 若当前节点小于target, row++, 若当前节点大于target, col--

994.腐烂的橘子 **

• 在给定的m*n网络中, 有若干好橘子和坏橘子, 坏橘子会每分钟感染周围四个方向的橘子, 输出最后全部都是坏橘子的时间, 不可能返回-1

1. 广度优先搜索BFS: 刚开始, 把所有腐烂的橘子加入队列中, 开始传染
2. 每次传染需要遍历的相邻节点为这个橘子的上下左右四个橘子, 若为好橘子, 就把他传染, 并把他加入队列, 作为下一次传染的源头
3. 直到队列为空, 也就是不再有传染源头, 或者好橘子全部被传染

BFS 可以看成是层序遍历。从某个结点出发，BFS 首先遍历到距离为 1 的结点，然后是距离为 2、3、4…… 的结点。因此，BFS 可以用来求最短路径问题。BFS 先搜索到的结点，一定是距离最近的结点。

day8 4.26

42.接雨水 ***

• 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

1. 基本思想, 对于每一个柱子, 他当前所在位置能接多少雨水取决于, 他左边的最大高度, 他右边的最大高度, 和自身高度, 为Math.min(左边最大高度, 右边最大高度) - 自身高度
2. 使用双指针分别指向左边和右边, 维护左右的最大高度, 当左边最大高度更小时, 左指针加1, 当右边最大高度更小时, 右指针减1

560.和为K的子数组 **

• 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

1. 方法1 去遍历左指针之后的所有元素, 若加起来的和等于k, 结果加1, 遍历一遍后移动左指针
2. 方法2 维护一个前缀和的哈希表(k,v)=(当前前缀和, 等于当前前缀和元素的数量), 当前的元素看他前面的前缀和, 有多少个等于 当前前缀和 - k 的元素, 也就是在哈希表中查询一下

2.两数相加 *

• 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表

1. 基本的链表操作, 分别遍历两条链表, 维护一下进位, 注意若一条链表到头, 若还有进位要继续处理另一条链表

day9 4.27

102.二叉树的层序遍历 *

• 对二叉树进行按层次遍历

1. 使用队列进行按层次遍历, 还需要一个额外的队列来记录当前是第几层

19.删除链表的倒数第N个节点 *

• 删除链表的倒数第N个节点, 返回删除后的链表的头节点

1. 设立两个指针, 一个从头指针之前开始, 这是一个虚拟的头节点, 因为为了应对删除头节点的情况
2. 另一个先走N步
3. 开始遍历, 当先走的指针走到头时, 后走的指向的就是倒数第N+1个, 然后进行删除即可

54.螺旋矩阵 *

• 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

1. 维护一下螺旋移动指针的操作即可

364.字符串解码 **

• 给定一个编码后的字符串, 返回他解码后的字符串
• 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次

1. 用一个栈去记录中括号的位置和这次重复的次数, 找到最外层的中括号, 然后递归调用decode函数
2. 将递归得到的结果重复k次, 添加到结果字符串中

739.每日温度 *

• 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替

1. 方法1, 用栈去记录当前还有多少没找到升温的天, 遍历一次数组, 遍历到新的元素的时候, 看当前元素是否比栈顶元素大, 若大的话就出栈, 且设置ans, 要一直遍历到栈为空或遇到小于栈顶元素的时候

day10 4.28

207.课程表 **

• 给定课程的先修关系, 判断能否完成所有课程的学习

1. 图的拓扑排序
2. 先用邻接矩阵表示图
3. 初始化每个节点的入度
4. 从图中任选一个入度为0的节点, 删去, 同时删去他的出边, 更新其他节点的入度
5. 以此循环, 直到所有节点删去, 输出true, 或者只有入度不为0的节点, 输出false

108.将有序数组转化为二叉搜索树 **

• 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树
• 二叉搜索树: 左子树的键值小于根, 右子树的键值大于根
• 平衡: |hl - hr| <= 1

1. 给定数组已经按照升序排列, 也就是二叉树的中序遍历
2. 按照中序遍历的顺序, 每次先找到当前数组的中间值,作为根, 分为左子树和右子树, 递归去建树
3. 因为每次都取中间的值作为根, 可以有效保证树是平衡的

98.验证二叉搜索树 **

• 给你一个二叉树, 验证他是否是有效的二叉搜索树

1. 通过递归中序遍历, 来检查前一个节点值是否小于后一个节点
2. 若过程中发现有左子树或右子树不符合有效二叉搜索树就return false

189.轮转数组 *

• 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数

1. 方法1, 用一个新数组, 去直接找转k次后的数组应该长什么样, 也就是后length-k 最先放入, 其他的在依次放入

day11 4.29

230.二叉搜索树中第K小的元素 *

• 给定一个二叉搜索树，找到其中的第K小的元素

1. 计算左有多少个节点，来决定下一步要去哪一边寻找第k小节点
2. 若左子树有m个节点， 且m>=k, 则递归调用kthSmallest(root.left, k)
3. 若m < k, 则递归调用kthSmallest(root.right, k - leftChildCount -1)

238.除自身以外数组的乘积 *

• 计算整数数组中, 除当前元素外其他所有元素的乘积

1. 计算每个位置的前缀积和后缀积
2. 当前位置除自身外的乘积就是当前位置的前缀积 * 后缀积

118.杨辉三角 *

• 给定一个非负整数n, 生成杨辉三角的前n行

1. 通过递归由n-1行生成第n行
2. 再生成过程中直接把这一行加入答案里

198.打家劫舍 **

• 每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警, 求出在不触发警报的情况能得到的最多现金

1. 设置两个变量记录, 偷到前前个房屋的金额prev, 偷到前个房屋的金额cur
2. 那下一次要不要偷当前房屋取决于 max(prev + nums[i], cur)
3. 一直更新cur和prev即可

24.两两交换链表中的节点 *

• 给你一个链表，两两交换其中相邻的节点

1. 基本的链表操作
2. 用三条指针, 分别表示前一个节点(不动), 当前节点, 和下一个节点
3. 每次交换当前节点和下一个节点
4. 注意要把交换后的节点之前重新连接起来

day12 4.30

46.全排列 *

• 给定一个不含重复数字的数组, 返回其所有可能的全排列

1. 递归
2. 基本条件是数组只有一个元素, 那他的全排列就是自身
3. 如果数组大于一个元素, 他的全排列也就是第1个元素和剩下的n-1个元素的全排列
4. 以此来建立递归关系, 遍历一次, 每次将第i个元素和第一个元素交换, 进行剩下n-1个元素的全排列, 再交换回来, 继续下一个元素的遍历

215.数组中的第K个最大元素 **

• 返回数组的第K个最大元素

1. 堆排序算法
2. 建堆过程：自底向上，先将元素放到最后一个节点，然后进行上滤，看他的根节点是否小于当前节点，若小于就交换两个节点
3. 找第K个最大元素过程：堆的删除算法，自顶向下，每次都是取出并删除根节点，然后将最后一个节点放到根节点，然后把他下滤
4. 下滤过程：先找出当前节点的左右节点中最大的节点，若他大于当前节点，就进行交换，然后继续进行，直到遍历到最后一个节点

day13 5.5

347.前K个高频元素 *

• 找出数组中出现频率前K高的元素

1. 写过215之后, 掌握了堆就简单了, 唯一不同在于堆里面既要存放这个元素的值也要存放这个元素出现的频率

day14 5.7

438.找到字符串中所有的字母异位词 **

• 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。

1. 方法1: 参考3.无重复字符的最长子串,和49.字母异位词分组, 将字符串排序后进行比较来判断是否是字母异位词, 但这样排序次数过多, 体现不太出来滑动窗口的优势
2. 方法2: 对于字母异位词, 只要其中的每个字母的数量相等, 那么他们就是字母异位词, 维护一个长26的int数组, 来记录窗口的每个字母数目, 滑动过程中, 队列头的字符所对应的int数组-1, 队列尾的字符所对应的int数组+1

293.滑动窗口的最大值 ***

• 给你一个整数数组, 上面有一个长为k的滑动窗口, 返回滑动过程中窗口的最大值

1. 单调队列, 在移动滑动窗口时, 维护一个单调的队列结构
2. 向右移动窗口, 将队列里面小于这个元素的全部出队, 将这个元素的下标入队, 同时检查队首元素, 是否已经超出窗口范围, 若超出窗口范围队首也要出队
3. 总是输出当前的队首元素就是答案

48.旋转图像 **

• 给定一个n*n的二维矩阵, 将其顺时针旋转90度

1. 方法1, 结合数学的坐标系, 看作是相对与中心点的旋转, 找出每个点想对于中心点的左边(x,y), 顺时针旋转90度变为(y,-x), 再转化回绝对坐标
2. 方法2, 矩阵先进行转置, 再对每一行进行逆序

240.搜索二维矩阵II *

• 和74.搜索二维矩阵相比, 矩阵不再按蛇型递增, 而是每一行递增, 每一列也递增

1. 方法都和74的类似
2. 方法1, 从第一行开始, 每行进行二分查找, 找到最后的位置为边界, 下一行限制在边界的左侧进行二分查找
3. 方法2, 从右上角看, 看作一棵二叉搜索树

day15 5.8

78.子集 *

• 给你一个数组, 返回他的所有的子集的集合

1. 递归, 有n个元素的子集, 看为n-1个元素的子集, 再在其每个子集加上第n个元素得到的集合

17.电话号码的字母组合 *

• 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母

1. 和78.子集类似的思路

55.跳跃游戏 **

• 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false

1. 贪心计算一下最远能跳到的地方, 若在倒数第二个下标时, 最远能跳到的地方还大于0, 则能跳到终点
2. 遍历数组维护这个最远能跳到的位置(相对于当前下标的距离), 每走一步这个最大值-1, 同时看当前的值是否大于最大值, 若大于就替换

45.跳跃游戏II **

• 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标, 数组中的每个元素代表你在该位置可以跳跃的最大长度, 返回跳到最后一个下标的最小跳跃数

1. 维护一个这次跳跃的最远位置(能跳到的绝对位置)和下一步跳跃的最远位置(能跳到的绝对位置)
2. 若当前位置已经等于这次跳跃的最远距离,说明必须要进行一次跳跃了, 此时更新这次跳跃的最远距离
3. 在遍历过程中还要不断更新下一步跳跃的最远位置

day16 5.9

114.二叉树展开为链表 **

• 将一个二叉树按先序遍历的顺序展开为链表

1. 展开过程其实就是将左子树接到右节点, 将原来的右子树接到左子树的最右边的节点, 一直向右遍历这棵树
2. 方法2, 因为是按先序遍历过程展开为链表, 自然可以想到在先序遍历过程中将当前节点的下一个节点连接为之后要遍历的节点即可, 但是这样会发生丢失子节点的过程, 为了避免丢失子节点, 采取倒过来的先序遍历

199.二叉树的右视图 *

• 给定一个二叉树的根, 想象站在二叉树的右边, 返回看到的节点

1. 按层次遍历, 输出每一层的最后一个节点

105.从前序与中序遍历序列构造二叉树 *

• 由树的前序和中序遍历构造出二叉树

1. 由前序遍历确定根节点, 在中序遍历中找到这个根节点, 分为左右两个子树, 递归建立左右两个子树

day17 5.10

437.路径总和III **

• 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目. 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）

1. 先序遍历, 记录每一个节点的前缀和, 和到当前节点的路径长 cur, 若之前记录的前缀和中存在 cur-targetSum, 则就是存在到targetSum的路径
2. 在遍历过程中维护前缀和, 到一个新的路径后要去除原来的路径的前缀和

236.二叉树的最近公共祖先 *

• 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

1. 如果这两个节点都在二叉树的左子树, 那么就去左子树找公共祖先, 若两个节点分别位于左右两个子树, 那么根节点就是公共祖先, 若都在右子树就去右子树寻找
2. 以此建立递归

279.完全平方数 **

• 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量

1. 动态规划问题, 找出状态转移的方程, 由上一个状态推导出下一状态, 也是递归的思想, 但一般用一个dp数组来代替递归
2. 对于整数 i, 完全平方数肯定小于 sqrt(i), 我们遍历 1~sqrt(i), 找到一个j, 使得 i-j^2 的完全平方数dp[i-j^2]最少, 那么整数i的完全平方数的数量最少就是 1 + dp[i-j^2]

322.零钱兑换 *

• 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1

1. 动态规划和279完全平方数类似, 只不过找的不是完全平方数, 而是硬币的面值
2. 注意和279不同, 是存在无法凑成总金额的情况

139.单词拆分 **

• 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

1. 对于一个字符串, 考虑其被字典中的word切分为前后两部分, 若前后两部分都能由字典中单词拼出, 那么这个字符串也自然能被字典中单词拼出
2. 注意要枚举出这个字符串的每一个含有word的位置

day18 5.11

300.最长递增子序列 **

• 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度

1. 动态规划, dp[i] 表示以nums[i]结尾的最长递增子序列
2. 容易知道刚开始dp[]数组的每个元素都为1
3. 从小开始计算dp
4. 以nums[i]结尾的最长递增子序列, 等于以nums[j]结尾, 再考虑能否加上当前第i个元素(若nums[i] > nums[j] 则可以加1)
5. 最后dp数组中的最大值就是答案

152.乘积最大子数组 **

• 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

1. 注意是连续的子数组, 那么第i个子数组的最大乘积 = Math.max(第i-1个子数组的最大乘积 * 当前第i个数, 当前第i个数)
2. 但要注意负数的情况, 若之前的乘积为负, 再乘上一个负数, 负负得正, 可能会大于正数的最大值
3. 所以除了维护最大乘积还要记录一个最小乘积, 根据当前第i个数的正负来判断最大值可能在哪里

62.不同路径 *

• 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
• 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
• 问总共有多少条不同的路径？

1. 因为只能向下走或向右走, 到(i,j) 只能从(i-1,j) 和(i,j-1)走过来, 和爬楼梯问题类似
2. 注意边界条件, 也就是第0行和第0列, 都要初始化为1, 即只能一直向右或一直向下走

34.在排序数组中查找元素的第一个和最后一个元素 *

• 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

1. 用二分查找找到元素在数组中的位置
2. 从这个位置开始向前和向后遍历, 找到左右边界即可
3. 当然也可以直接在二分查找的时候, 去找这个左右边界

33.搜索旋转排序数组 *

• 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
• 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

1. 可以先找到旋转的地方, 再对两个小数组分别进行二分查找
2. 方法2: 二分查找的过程, 将原数组分成了两边, 必然有一边是排好序的, 而另一边是被旋转的, 如果在排好序的那一边就直接进行二分查找, 若再被旋转的这一边, 则再次进行这样的切分

day19 5.12

208.实现Trie(前缀树) *

• 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

1. 实现一个森林即可, 森林中的树的根表示字符串的第一个字符, 因为都是小写字母, 可以用TreeNode[26] 来表示森林和每一个节点
2. 维护这个森林结构, 相同字符的一直向下遍历, 若出现不同字符就生长出子节点
3. 还需要记录当前节点是否是一个字符串的终结

39.组合总和 **

• 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

1. 每次选择数组中的一个元素作为候选, target-candiate作为目标, 从当前元素所在位置开始(包括当前元素), 继续再剩余的数组中找有无target

22.括号生成 **

• 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

1. 合法的括号组合永远都是左括号数等于右扩号数
2. 再生成括号组合的时候, 如果左括号数小于n, 则加一个左括号, 如果右括号数小于左扩号数, 则加一个右扩号
3. 若当前生成的字符串, 左括号数=右括号数=n, 则将其加到答案中

day20 5.15

复习