LeetCodeHot100_0x07
LeetCodeHot100_0x07
49. 二叉树的最近公共祖先（不会）
求解思路： 这题不看答案真想不明白，官解的思路还是太巧妙了。具体的先认识一下如何判断某个节点是p、q祖先，需要任意满足以下两种情况之一：
- p、q分居两边，那么必定存在一个节点，它的左子树中存在p/q ，右子树中存在q/p
- p、q同侧，那么必然是p是q的祖先或 q是p的祖先，也就是说根节点是p / q，且子树中存在 p / q即可。
那么如何设计搜索逻辑呢？从根节点出发，首先是判断当前根节点具不具备成为祖宗的潜力：也就是符合上述两种情况：所以我们可以定义一个Boolean类型的DFS方法，分别递归它的左子树和右子树判断是否存在p / q。
通过以上，祖先是找到了，但是如何确保是最近祖先呢？这就归功于递归的回溯特性了。回溯确保能从最底层逐级往上判断，那么最近祖先肯定先被扫描记录到，以确保找到的祖先就是最近祖先。
class Solution {
public TreeNode res;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 思路描述：
// 求p q 的最近公共祖先分解：存在最小一棵树使得：
//1. 左子树中存在p/q 右子树存在 q/p
//2. p/q 全在一边，那么p / q 其中之一是树根节点
// 进行dfs深搜判断（题目确保q/p不同）
// 搜左子树判断是否存在 p/q，定义为 lson
// 搜右子树判断是否存在 p/q，定义为 rson
// 如果lson && rson符合 证明符合第一种情况，这个树根节点可能是解
// 如果树根节点等于 p/q 且lson / rson 存在真，证明符合第二种情况，这个树根可能是解
// 那要如何确保最近呢？—— 根节点必然是祖先，但是不是最近的
// dfs的回溯特性，确保了我们是从最底层开始向上推导的，也就是说，一定能确保最近的祖先会先被res记录到
dfs(root,p,q);
return res;
}
public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return false;
boolean lson = dfs(root.left,p,q); // 判断左子树中是否存在p/q
boolean rson = dfs(root.right,p,q); // 判断右子树中是否存在p/q
// 判断是否符合情况1 或 情况2
if(lson && rson || (root.val == p.val || root.val == q.val) && (lson || rson)) res = root;
// 如果子树存在lson / rson 或 根节点是 p/q 这三种情况之一，都证明了root下符合要求
return lson || rson || (root.val == p.val || root.val == q.val);
}
}
50. 二叉树中的最大路径和
求解思路： 求最大路径和 与 求最大长度有什么区别么？其实没有，这题我们一样可以参照树的直径思路，遍历每一个节点，以该节点为树根，求出左子树最大和 与 右子树最大和 + 当前树根值。
当然注意一点，如果左子树最大和小于0，那就没必要左子树了（树根+右子树），因为这是个累赘，不可能是最优解。右子树同理。
class Solution {
private int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
// 和二叉树直径思路应该类似？遍历每一个节点，然后把左右最大路径相加，再更新最大值
solve(root);
return res;
}
public int solve(TreeNode root) {
if(root == null) return 0;
int LMax = solve(root.left);
int RMax = solve(root.right);
res = Math.max(res,LMax + RMax + root.val);
int ans = Math.max(LMax,RMax) + root.val;
return ans > 0 ? ans : 0; // 小于零的必然不可能成为最优
}
}
51. 岛屿数量
求解思路： 这题实质上就是让你判断图中有几块陆地，几个连通块。所以我们可以遍历图，当发现一块陆地时，我们上下左右不断扩张，将周围都是陆地的位置全部利用标记数组标记起来。简化一下我们不用另开标记数组，直接改地图：当遍历到陆地，拿水把它覆盖了，也是一种标记方式。
class Solution {
public int numIslands(char[][] grid) {
// 求连通块数量
int m = grid.length;
int n = grid[0].length;
int isLandCount = 0;
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(grid[i][j] == '1') { // 发现一篇陆地，放水去淹
infect(grid,i,j);
isLandCount ++;
}
}
}
return isLandCount;
}
// 淹水函数
public void infect(char[][] grid,int x,int y) {
// 越界不淹,有水不淹
if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0')
return ;
grid[x][y] = '0'; // 淹水
infect(grid,x+1,y); // 向右淹
infect(grid,x,y+1); // 向下淹
infect(grid,x-1,y); // 向左淹
infect(grid,x,y-1); // 向上淹
}
}
52. 腐烂的橘子
求解思路： 这题和上一题类似，都是有一个感染过程。然而这题要求给出最小感染时间，翻译翻译就是最小路径。对于图论中的最小路径问题，基本上要请出我们的BFS算法了。这题一样。我们完全可以定义一个队列存储腐烂橘子，然后进行感染。在感染更新图时，第一层被感染的橘子标记为3，第二层感染的橘子标记为4。即在发起感染的橘子的值基础上加1。最后答案就再遍历一遍，如果还存在新鲜橘子说明无法完全感染，否则在被感染橘子中找到值最大的，再减去2就是答案。
class Solution {
public int orangesRotting(int[][] grid) {
// 利用数组本身标记扩散时间，利用队列进行层次感染
Queue<int[]> queue = new LinkedList<>();
int m = grid.length;
int n = grid[0].length;
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
//第一遍遍历：将烂橘子加入队列
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(grid[i][j] == 2) {
queue.offer(new int[]{i,j});
}
}
}
// 开始感染橘子
while(!queue.isEmpty()) {
// 取出烂橘子
int[] point = queue.poll();
int x = point[0], y = point[1];
// 四个方向进行感染
for(int i=0;i<4;i++) {
int u = x + dx[i];
int v = y + dy[i];
if(u >= 0 && u < m && v >= 0 && v < n && grid[u][v] == 1) {
grid[u][v] = grid[x][y] + 1; // 感染
queue.offer(new int[]{u,v}); // 入队
}
}
}
// 第二遍遍历，判断答案
int maxTime = 0;
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(grid[i][j] == 1) return -1; // 还有新鲜橘子（那你不寄了么）
if(grid[i][j] >= 2) {
maxTime = Math.max(maxTime,grid[i][j] - 2); // 更新最大时间（3表示第一层感染的，减去基准2）
}
}
}
return maxTime;
}
}
53. 课程表
求解思路： 首先清楚什么是拓扑，按照拓扑排序的思路，每一次将指向自己次数为0的课程取出来【这些课程就是达到选修条件的】，然后将与这些课程相关的课程的指向次数-1【因为已经修了】。然后如果发现出现了指向为0的课程，就可以继续重复上述操作。
根据描述，可以感觉到这题跟层序遍历思路类似，都需要借助队列将每一层指向为0的元素存储，然后弹出。
这题的关键在于如何用良好的结构将课程间的关系存储起来，然后用队列去处理。
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 只要课程被指向一次就+1
List<List<Integer>> edges = new ArrayList<>();
int[] coursesCnt = new int[numCourses];
//1. 先把拓扑结构创建好
for(int i=0;i<numCourses;i++) {
edges.add(new ArrayList<Integer>());
}
//2. 将拓扑数据存入，指向边次数存入
for(int[] courses : prerequisites) {
// 按要求将没门课程的先序课程存入，并记录指向的次数
edges.get(courses[1]).add(courses[0]);
++coursesCnt[courses[0]];
}
//3. 创建队列
Queue<Integer> queue = new LinkedList<>();
for(int i=0;i<numCourses;i++) {
// 指向为0的课程可以达修的要求了
if(coursesCnt[i] == 0) queue.offer(i);
}
//4. 操作队列
int isVisited = 0; // 已经修完的课程
while(!queue.isEmpty()) {
isVisited ++;
int u = queue.poll(); // 取出指向为0的课程，将它直接关联的课程的指向都-1
for(int v : edges.get(u)) {
--coursesCnt[v];
if(coursesCnt[v] == 0) {
queue.offer(v); // 把指向为0的课程又加入到队列中
}
}
}
//5. 判断是否所有的课程都修完了
if(isVisited == numCourses) return true;
return false;
}
}
54. 实现Tire前缀树(模板)
求解思路： 定义一个数组存放孩子单词节点，并声明一个布尔变量isEnd用来标记结尾。只有标记了结尾的单词才是真正存进Tire的单词，其他路径上的单词只是前缀。
- 插入时逐个遍历单词，将字母插入到节点该插入的位置，并更新节点位置，然后字母插入完成后将对应节点的isEnd标记为true
- 查找时也是逐个遍历单词，然后依次判断该字母是否存在于Tire中，最后遍历完后，还需要判断一下末尾字母有没有isEnd = true。
- 查找前缀和查找思路一致，只是少了个isEnd判断
class Trie {
// 定义属性
private Trie[] children;
private boolean isEnd;
// 初始化方法
public Trie() {
children = new Trie[26];
isEnd = false;
}
// 插入
public void insert(String word) {
// this指向当前实例对象
Trie node = this;
for(int i=0; i<word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if(node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index]; // 指向下一个节点
}
node.isEnd = true;
}
// 查找
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
// 判断前缀
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
// 查找前缀
private Trie searchPrefix(String prefix) {
Trie node = this;
for(int i=0;i<prefix.length();i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if(node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
55. 全排列
求解思路： 递归解法
- 递归终止条件：长度达到数组大小，证明所有元素都参与了排列，计入答案中
- 递归思路：遍历数组，判断当前位置是否使用，没有就尝试使用，并进入下一层递归，最后回溯删除。
class Solution {
List<List<Integer>> res = new ArrayList<>();
boolean[] visited;
public List<List<Integer>> permute(int[] nums) {
// 标记数组初始化
visited = new boolean[nums.length];
// dfs回溯
dfs(nums, new ArrayList<>());
return res;
}
private void dfs(int[] nums, List<Integer> path) {
// 如果将所有元素都选择了，可以作为一个答案
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
// 遍历寻找没有被使用的元素
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
// 将元素加入列表，并标记
visited[i] = true;
path.add(nums[i]);
// 进入下一层调用
dfs(nums, path);
// 递归
path.remove(path.size() - 1);
visited[i] = false;
}
}
}
}
56. 子集
求解思路： 每种元素只有两种选择，只要遍历一遍，让每个元素做出自己的选择，就是其中一个子集。用递归把所有结果记录下来。
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> arr = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
// 每种元素只有两种选择：加入或者不加入
// 每轮只需要遍历一遍，让每个元素都做出自己的选择就可以了
// 一共需要做出n^2种选择，用递归再合适不可了。
// 进行dfs
dfs(nums,0);
return res;
}
public void dfs(int[] nums, int setup) {
if(setup == nums.length) {
res.add(new ArrayList<Integer>(arr));
return;
}
arr.add(nums[setup]); // 加
dfs(nums,setup + 1);
arr.remove(arr.size()-1); // 不加
dfs(nums,setup + 1);
}
}
57. 电话号码的字母组合
求解思路： 求所有组合。可以这么考虑，例如234，2有三种选择、3有三种选择、4有三种选择。那么我们可以首先遍历digits，遍历到2、3、4.然后对于每一个，我们实现存好对应的映射字母表，再遍历字母表。从字母表种选择其中一个字母作为一种组合。每个元素也是只有选和不选两种选择。
class Solution {
// 存储哈希
char[][] s = new char[][] {
{'a','b','c'}, // 2
{'d','e','f'}, // 3
{'g','h','i'}, // 4
{'j','k','l'}, // 5
{'m','n','o'}, // 6
{'p','q','r','s'},// 7
{'t','u','v'}, // 8
{'w','x','y','z'} // 9
};
// 存储答案
List<String> res = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if(digits.length() == 0) return res; // 非空判断
dfs(digits,0,new StringBuilder()); // 递归回溯：目标字符串，枚举到的位数，中间字符串
return res;
}
public void dfs(String digits, int setup, StringBuilder sb) {
if(sb.length() == digits.length()) { // 枚举到了最后一个完，那么一个答案就出来了
res.add(sb.toString());
return;
}
for(char ch : s[digits.charAt(setup)-'2']) { // 找到当前位置的数值对应映射的哈希字母表
sb.append(ch); // 加入
dfs(digits,setup+1,sb); // 进入下一层
sb.deleteCharAt(sb.length() - 1); // 回溯
}
}
}
58. 组合总和
求解思路： 首先进行排序，方便后续剪枝。思路是这样的：允许重复使用元素，也就是说下一层dfs可以从当前元素开始（这个很重要）
所以我们在设计DFS时，一样从第一个元素开始尝试，只要当前target小于目标值，就可以尝试将当前元素加入，然后递归下一层时同样从这个元素开始继续进行尝试。当然也要有回溯删除元素。
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(candidates,target,0,new ArrayList<Integer>());
return res;
}
public void dfs(int[] candidates,int target,int start, ArrayList<Integer> ans) {
if(target == 0) {
res.add(new ArrayList<>(ans));
return;
}
for(int i=start;i<candidates.length;i++) {
if(target < candidates[i]) break; // 剪枝，后面不合适了
ans.add(candidates[i]); // 尝试加入
dfs(candidates,target-candidates[i],i,ans); // 加入后递归到下一层需要从i继续开始尝试
ans.remove(ans.size() - 1); // 回溯
}
}
}
59. 括号生成
求解思路：
- 思路：记录左括号和右括号的使用数量
- 递归出口条件：左括号和右括号数量为n
- 递归方案：无脑添加左括号，无脑补充右括号，不行就回溯
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
// 给定一个n，让你生成含n对且有效的括号数量？？？？？？
// 看到题目我直接一整个放弃摆烂了好吧！
// 诶，好像又有点思路了！
// 诶诶诶好像过了
// 666 甜菜出院
// 思路:
// 1.记录当前用了多少个左括号和右括号
// 2.如果左括号和右括号都用了N个，就可以存入一种方案
// 3.无脑添加左括号
// 4.无脑匹配右括号
// 5. 回溯回溯回溯！！！
dfs(0,0,n, new StringBuilder());
return res;
}
public void dfs(int l,int r,int n,StringBuilder str) {
if(l==n && r==n) {
res.add(str.toString());
return;
}
if(l < n) {
dfs(l + 1,r,n,str.append('('));
str.deleteCharAt(str.length() - 1); // 回溯
}
if(r < l) {
dfs(l, r+1,n,str.append(')'));
str.deleteCharAt(str.length() - 1); // 回溯
}
}
}
60. 总结
LeetCodeHot100_0x07主要是关于搜索和递归的题目，前后也是跨了好多天才做完，这次纯粹是懒大王了。回顾一下每一题的思路吧：
- 二叉树的最近公共祖先
经典面试、递归- 明确公共祖先主要满足两种情况：
- 当前节点的左右子树分别存在 p / q
- 当前节点就是p / q,且左子树或右子树中存在另一个
- 递归终止条件：为空
- 明确递归思路
- 定义布尔类型的DFS，用于判断当前节点左子树和右子树分别满不满足存在p/q
- 定义左子树 lson，右子树rlon，那么翻译符合的两种条件有：
- lson == true && rson == true ||
- (root.val == p || root.val == q) && (lson == true || rson == true) )
- 明确公共祖先主要满足两种情况：
- 二叉树的最大路径和
递归、贪心- 这题本质上和二叉树的最大直径思路是一样的，只是把左右子树最大深度变形成最大路径和
- 所以我们参考二叉树直径的思路：
- （1）遍历每一个节点
- （2）计算左子树最大和、计算右子树最大和
递归计算 - （3）判断左、右子树最大和是否大于0 ，小于0的没有加入到答案的机会
贪心思维
- 递归函数的设计：
- 递归终止条件：为空返回0
- 递归返回值： 返回 （左子树最大节点 与 右子树最大节点的较大值 + 当前节点值 ）再与0比较，返回较大值
- 递归思路：递归左子树计算Lmax，递归右子树计算Rmax，作为返回值的计算条件
- 岛屿数量
图、搜索、模板、DFS- 这题算是图论里面最基础的一个模型了。为了判断有几块岛屿，我们可以采取以下策略：
- （1）遍历图，找到一块陆地
- （2）以这块陆地出发，上下左右去尽可能把相连的陆地全部找到
- （3）将这些陆地标记为已使用，表明这一堆陆地等效为一整块陆地
- 这题算是图论里面最基础的一个模型了。为了判断有几块岛屿，我们可以采取以下策略：
- 腐烂橘子
图论、搜索、BFS、队列- 这题是图论的另一类模板题，强调广度搜索，具体解题策略如下：
- （1）第一遍 遍历图，找到所有在0时刻腐烂的橘子，将它们的坐标加入队列结构中
- （2）第二遍 遍历队列，获取到x时刻的烂橘子，然后立马对上下左右进行扩展一层的搜索
- （3）如果发现新鲜橘子，将它变成腐烂橘子，并标记腐烂时刻为x+1，最后将它加入腐烂橘子队列
- （4）循环上述步骤，直到所有腐烂橘子全部出队为止
- （5）第三遍 遍历图，判断图中还存不存在新鲜橘子，如果还有，说明它可以避免感染。
- 这题是图论的另一类模板题，强调广度搜索，具体解题策略如下：
- 课程表
拓扑序列、队列- 这题要你判断能否将所有课程修完，并且在修课前，要将所有的先修课程完成。这个实际上是考察拓扑序列的问题，所以我们的解题策略描述如下：
- （1）构建入度，将课程的入度情况存储起来
- （2）定义队列，将初始构建入度为0的课程加入到队列中
- （3）遍历队列，逐个取出课程，将所有依附于它的课程入度-1，记录已完成课程数量+1
- （4）判断入队，如果存在新的入度为0的课程，可以将它继续加入到队列
- （5）结果判断， 如果已完成课程数量小于课程数组长度，说明修不完。
- 这题要你判断能否将所有课程修完，并且在修课前，要将所有的先修课程完成。这个实际上是考察拓扑序列的问题，所以我们的解题策略描述如下：
- 实现Tire前缀树
模板、前缀树、数据结构- 这题就是实现前缀树的系列方法，定义好Tire的数据结构：children + isEnd
- 实现添加：遍历 + 结尾标记true
- 实现前缀判断：遍历判断children有没有
- 实现单词判断: 遍历前缀判断 + 结尾标记是否为true
- 这题就是实现前缀树的系列方法，定义好Tire的数据结构：children + isEnd
- 全排列
dfs- 这题递归的经典例题，全排列的思路比较简单,简称试错原理：
- （1）遍历数组，判断当前元素是否使用过？
- （2）没使用过，尝试加入ans中，并跳入下一层递归
- （3）回溯处理，将当前元素从ans中删除
- 这题递归的经典例题，全排列的思路比较简单,简称试错原理：
- 子集
dfs- 这题也是经典例题了，和上题稍微不同的是这题的每一个元素都有两种选择：即选或不选
- （1）遍历数组，选择当前元素，加入ans，进入下一层递归
- （2）删除元素，表示不选择当前元素，进入下一层递归
- 这题也是经典例题了，和上题稍微不同的是这题的每一个元素都有两种选择：即选或不选
- 电话号码的组合
哈希、递归- 这题在递归思想的基础上多了一步数据映射处理的步骤。先将电话号码与26个字母连城哈希映射。接着进行DFS，DFS思路如下：
- （1）遍历字符串，获取每一位数值
- （2）根据数值，找到与之映射的字母表
- （3）接着就是类似全排列的思路，尝试加入，递归下一层，回溯
- 这题在递归思想的基础上多了一步数据映射处理的步骤。先将电话号码与26个字母连城哈希映射。接着进行DFS，DFS思路如下：
- 组合总和
sort、dfs- 这题指出元素可以重复使用，要求写出所有组合之和符合目标值的方案，既然可以重复使用，那就要避免不要形成无限递归，具体策略如下:
- （1）将原数组进行排序，便于后续进行递归终止判断
- （2）遍历数组，从默认start = 0位置开始
- （3）判断终止，判断当前剩下的大小与当前元素大小比较，如果任然小于当前元素，那么后面的也一定不符合了，可以直接终止。
- （4）如果可以继续，那尝试将该元素加入，并将start更新成当前元素位置，以进入下一层递归
- （5）如果不合适，回溯
- 这题指出元素可以重复使用，要求写出所有组合之和符合目标值的方案，既然可以重复使用，那就要避免不要形成无限递归，具体策略如下:
- 括号生成
贪心、dfs- 这题看到题目差点放弃，感觉很抽象，但实际想想，其实遵循两个原则就秒了：
- （1）无脑放左括号，直到数量到达n
- （2）无脑补右括号，直到数量等于左括号数量
- 你就写吧，这两个无脑条件直接秒杀
- 这题看到题目差点放弃，感觉很抽象，但实际想想，其实遵循两个原则就秒了：