力扣100二刷——图论、回溯
第二次刷题不在idea写代码，而是直接在leetcode网站上写，“逼”自己掌握常用的函数。
| 标志 | 掌握程度 | 解释 | 办法 |
|---|---|---|---|
| ⭐ | Fully 完全掌握 | 看到题目就有思路，编程也很流利 | |
| ⭐⭐ | Basically 基本掌握 | 需要稍作思考，或者看到提示方法后能解答 | |
| ⭐⭐⭐ | Slightly 稍微掌握 | 需要看之前写过的代码才能想起怎么做 | 多做 |
| ⭐⭐⭐⭐ | absolutely no 完全没有掌握 | 需要看题解才知道怎么做 | 背 |
| ⭐⭐⭐⭐⭐ | 有难度的高频题 | 需要看题解才知道怎么做，而且过几天就忘了这道题怎么做了 | 背背 |
| 51 | ⭐⭐⭐ | Medium | 图论 | 200/岛屿数量 | 递归，三个参数：岛与数组、i、j 遍历原始数组，遇到格子的值为‘1’则调用递归函数 递归结束条件：格子索引超过边界、格子的值为‘0’ 将当前格子周围的格子的索引传入递归函数 | |
|---|---|---|---|---|---|---|
| 52 | ⭐⭐⭐ | Medium | 图论 | 994/腐烂的橘子 | BFS广度优先搜索，和二叉树的层序遍历思路是一样的 遍历数组，维护一个队列来存放初始数组中腐烂的橘子索引Deque<int[]> queue = new ArrayDeque<>();，并统计新鲜橘子的个数fresh 当队列不为空且fresh>0时，ans++ 每一轮‘感染’之后，更新队列的长度length，当length > 0时 3.1 弹出队头元素 3.2 将该元素周围的新鲜橘子（1）加入到队列中，并将其变为 2，且fresh-- 根据fresh 是否 > 0返回结果 | |
| 53 | ⭐⭐⭐ | Medium | 图论 | 207/课程表 | BFS广度优先搜索 准备工作： 维护一个degree数组，表示每个课程的入度 维护一个表示依赖关系的哈希表，key为被依赖的课程，value为依赖key的课 维护一个入度为0的队列，先将所有入度为0的课程加入队列 BFS，当课程数 > 0 并且 队列不为空时： 弹出队头课程，课程数-- 从map中找到依赖该课程的课程列表，并将他们的入度 -1，如果入度变为0，则入队 根据课程数是否 > 0 返回结果 | |
| 54 | Medium | 图论 | 208/实现Trie（前缀树） | |||
| 55 | ⭐⭐⭐ | Medium | 回溯 | 46/全排列 | DFS+回溯，递归函数参数：原始数组、当前层数 维护isUsed数组记录元素是否被使用过，item集合、ans集合记录结果 每次递归，从0开始遍历数组 如果元素没被使用过，则将其加入item数组，并更新isUsed 将原始数组、当前层数+1传入递归函数 回溯操作，移除item的最后一个元素、还原isUsed 结束递归操作：当当前层数等于数组长度时，将item的拷贝版本加入到ans中 ans.add(new ArrayList(item)); | |
| 56 | ⭐⭐⭐ | Medium | 回溯 | 78/子集 | DFS+回溯，递归函数参数：原始数组、当前索引index 和上题不同的是，每次递归遍历数组不是从0开始，而是从当前index开始 将原始数组和当前正在遍历的索引 i + 1传入递归函数 | |
| 57 | ⭐⭐⭐ | Medium | 回溯 | 17/电话号码的字母组合 | DFS+回溯：递归函数参数：原始数组、当前索引index 准备工作，先将数组到字母的映射保存到map中 每层递归代表一个数字，输入几个数字，就是求这几个数组对应的字母之间的全排列 每次递归，先根据index对应的数字在map中找到对应的字母，字母字符串就是当前层所要遍历的 将index + 1传入递归函数 递归结束条件：index等于数字数 | |
| 58 | ⭐⭐⭐ | Medium | 回溯 | 39/组合总和 | DFS+回溯： 其实这道题就是78/子集的升级版，要在子集中 寻找sum = target的集合 注意：回溯时，不但要更新 item，还要更新sum 递归结束条件：当前总和 ≥ 目标和，注意等于的时候，将当前 item 添加进 ans | |
| 59 | ⭐⭐⭐ | Medium | 回溯 | 22/括号生成 | DFS+回溯： 递归传入参数：括号对数 n，左括号数量，右括号数量 左括号数量 < n 时，添加左括号到temp，并将新的左括号数量传入递归函数，回溯（更新temp） 右括号数量 < 左括号数量时，添加右括号到temp，并将新的右括号数量传入递归函数，回溯（更新temp） 递归结束条件：右括号数量 = n | |
| 60 | ⭐⭐⭐⭐ | Medium | 回溯 | 79/单词搜索 | DFS+回溯： 依次将矩阵的元素（行列）以及当前遍历的字符位置传入递归函数 递归函数中，对当前元素判断是否与当前字符相等，不等则直接返回false 元素行列超出范围也返回false 以上条件都不满足，说明元素与当前字符相等，将当前元素更新为 ‘\0’，继续遍历下一个元素，回溯（将当前元素还原，word.charAt(index)） | |
| 61 | ⭐⭐⭐⭐ | Medium | 回溯 | 131/分割回文串 | DFS+回溯：递归参数：当前子串起始位置left 在字符串长度 n 的范围内，将子串结束位置right 从 left 开始遍历 判断 s.subString(left, right + 1)是否为回文，这里另写一个函数 如果是回文的话，则添加子串到item，并将right + 1传入递归函数，达到分割的目的，回溯（更新item） 递归结束条件：right = n | |
| 62 | Hard | 回溯 | 51/N皇后 |
图片版：
