2020年9月刷题日志
9.29
遍历二叉树我还是太菜，今儿个只是非递归的后序遍历我看题解都看了半天
题目
145. 二叉树的后序遍历
难度中等
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1]进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路
老样子，两种解法，一种python写，另一种java写
-
普通递归
-
思想就是写一个递归函数，先遍历左子树，再遍历后子树，最后再把结点值放到答案里。
-
不用理解后序遍历的本质就能写出来的方法
-
非递归解法
-
利用栈去存储需要遍历的结点
-
基本思想就是，先一直向左下遍历，当遍历不下去的时候，再看看右下还有没有
-
每次记录结点值得时候保证遍历的这个结点右下角没了，或者右下角全部被记录过了
-
讲不太清。。。直接看代码吧
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def postOrder(root):
if not root:
return
postOrder(root.left)
postOrder(root.right)
res.append(root.val)
return
postOrder(root)
return res
import java.util.LinkedList;
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// stk用来暂存遍历的结点
Deque<TreeNode> stk= new LinkedList<>();
// ans用来存放后序遍历的结果
List<Integer> ans = new ArrayList<>();
stk.push(root);
// prev用来记录上一个遍历完成的结点
TreeNode prev = null;
while(!stk.isEmpty()||root!=null){
// 先把左子树遍历完
while(root!=null){
stk.push(root);
root = root.left;
}
root = stk.pop();
if(root.right == null || root.right == prev){
// 当右子树为空或者右子树已经记录时 记录当前结点的值
ans.add(root.val);
prev = root;
root = null;
}else{
// 右子树非空且没被记录过，就继续遍历右子树
stk.push(root);
root = root.right;
}
}
return ans;
}
}
9.28
题目
117. 填充每个节点的下一个右侧节点指针 II
难度中等
给定一个二叉树
struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为
NULL。初始状态下，所有 next 指针都被设置为
NULL。进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。提示：
- 树中的节点数小于
6000-100 <= node.val <= 100
思路
这次的二叉树要用bfs来解
I am so 菜 that I 看题解
老样子，有两种思路，一种用python实现，一种用java实现
空间复杂度O(N)
- 利用队列进行层序遍历
- 每次在遍历某一层的时候，设计pre结点来存储上一个遍历的结点（也就是左边最近的结点）
- 将pre.next设置为当前结点
- 将pre设置为当前结点
- 继续向右遍历
- 向右遍历的同时要把自己的左右子节点放到队列里
空间复杂度O(1)
-
假设我们已经遍历完第二层，那么此时计算第三层结点的右侧指针时我们可以借助第二层
-
我们从第二层的最左边结点向右遍历
-
假设第二层最左边的结点为cur
-
去判断cur.left和cur.right
-
用上面的思路，利用pre结点来设置cur.left.next和cur.right.next
-
然后遍历cur.next，直到遍历完该层
-
再把cur设置为第三层最左边的结点继续
代码
from queue import Queue
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return
# 利用队列实现二叉树的层序遍历
queue = Queue()
queue.put(root)
while not queue.empty():
# level表示这一层的总结点数
level = queue.qsize()
pre = Node()
for i in range(level):
node = queue.get()
# pre为空表示这个结点是这层第一个结点
if pre:
pre.next = node
# 此时的这个节点为下一个结点的pre
pre = node
if node.left:
queue.put(node.left)
if node.right:
queue.put(node.right)
return root
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root == null){
return null;
}
Node cur = root;
// cur来记录每层的最左边的结点
while(cur!=null){
// dummy结点方便我们遍历下一层
Node dummy = new Node();
Node pre = dummy;
while(cur!=null){
// 去判断cur的左右子结点
if(cur.left != null){
// 当子节点存在时，就更新pre.next结点和pre结点
pre.next = cur.left;
pre = cur.left;
}
if(cur.right != null){
pre.next = cur.right;
pre = cur.right;
}
cur = cur.next;
}
cur = dummy.next;
}
return root;
}
}
9.27
困
题目
235. 二叉搜索树的最近公共祖先
难度简单
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
通过次数89,309
提交次数136,007
思路
参考了官方题解知道了两种解法
解法1
- 分别找到根节点到达p的路径path_q和根节点到达q的路径path_q
- 从头开始遍历两个路径，当path_q[i] != path_p[i]时，遍历的上一个结点就是分叉点
解法2
- 从root开始遍历整棵树
- 如果root.val<p.val且root.val<q.val，就往root的右边去找分叉点
- 如果root.val>p.val且root.val>q.val，就往root的左边去找分叉点
- 如果都不满足，说明此时p在root的左子树，q在root的右子树，root就是分叉点
代码
- java写的解法1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pathToP = getPath(root, p);
List<TreeNode> pathToQ = getPath(root, q);
TreeNode ans = new TreeNode();
for(int i = 0;i<pathToP.size() && i<pathToQ.size();i++){
if (pathToP.get(i)==pathToQ.get(i)){
ans = pathToP.get(i);
}else{
break;
}
}
return ans;
}
private List<TreeNode> getPath(TreeNode root, TreeNode target){
List<TreeNode> path = new ArrayList<>();
while(root!=target){
path.add(root);
if(root.val>target.val){
root = root.left;
}else{
root = root.right;
}
}
path.add(root);
return path;
}
}
- python用的是解法2
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while True:
cur = root.val
if cur<p.val and cur<q.val:
root = root.right
elif cur>p.val and cur>q.val:
root = root.left
else:
return root
9.26
托福考完了，总分估计不太行，不过估计也不准备考第二次了吧
考试真的紧张死，然后还是碰到了听力加试，结果没想到听力比阅读高
来刷题放松一下吧
题目
113. 路径总和 II
难度中等
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和
sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:
[ [5,4,11,2], [5,8,4,5] ]
思路
老回溯法了
还是比较轻松的，虽然提交的时候WA了四次
或者说叫dfs？
- 向下遍历
- 如果是空结点，直接return
- 如果不是叶节点，自动继续向下遍历，同时在已遍历的路径中加入该结点的值，目标值减去该结点的值
- 如果是叶节点，同时节点值就等于当前需要的target，就把这条路径放到答案里
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
ans = []
if not root:
return ans
def isLeave(root):
if root and not root.left and not root.right:
return True
else:
return False
def findPath(path, target, root):
if not root:
return
if not isLeave(root):
findPath(path+[root.val], target-root.val, root.left)
findPath(path+[root.val], target-root.val, root.right)
elif root.val == target:
ans.append(path+[root.val])
findPath([], sum,root)
return ans
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while True:
cur = root.val
if cur<p.val and cur<q.val:
root = root.right
elif cur>p.val and cur>q.val:
root = root.left
else:
return root
9.24
大概是放弃出国了，但是周六托福还得好好考啊，毕竟是2k块钱呢呜呜呜
今天不知道是睡多了还是什么，头很痛
题目
501. 二叉搜索树中的众数
难度简单197
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如： 给定 BST
[1,null,2,2],1 \ 2 / 2
返回[2].提示：如果众数超过1个，不需考虑输出顺序
**进阶：**你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
代码
没能实现常数空间，只是用了中序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def findMode(self, root: TreeNode) -> List[int]:
answer = []
last = 0
cnt = 0
maxCount = 0
def inorder(root):
nonlocal last, cnt, maxCount, answer
if not root:
return 0
if root.left:
inorder(root.left)
if root.val == last:
cnt += 1
else:
cnt = 1
if cnt == maxCount:
answer.append(root.val)
elif cnt>maxCount:
maxCount = cnt
answer=[root.val]
last = root.val
if root.right:
inorder(root.right)
inorder(root)
return answer
9.23
好累，痒痒鼠好非
题目
617. 合并二叉树
难度简单497
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7注意: 合并必须从两个树的根节点开始。
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1:
return t2
if not t2:
return t1
cur = TreeNode(t1.val + t2.val)
left = self.mergeTrees(t1.left,t2.left)
right = self.mergeTrees(t1.right, t2.right)
cur.left, cur.right = left, right
return cur
9.21
周六考托福啦，这周就不写题解了，直接上代码吧
题目
538. 把二叉搜索树转换为累加树
难度简单
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 原始二叉搜索树: 5 / \ 2 13 输出: 转换为累加树: 18 / \ 20 13
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
def addKids(root):
nonlocal total
if root:
addKids(root.right)
total += root.val
root.val = total
addKids(root.left)
total = 0
addKids(root)
return root
9.20
又是美好的周日，双休日就多刷点题吧（不过题解我就懒得多写了）
题目
78. 子集
难度中等759
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
题解
经典老番
- 数组
- 所有可能的子集
dfs嘛，这道题甚至还不用剪枝
看到不重复就知道dfs函数里面肯定有一个参数去决定循环开始的位置
直接上代码
代码
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(nums, path, begin):
res.append(path)
if len(path) == len(nums):
return
for i in range(begin, len(nums)):
dfs(nums, path + [nums[i]], i+1)
dfs(nums, [], 0)
return res
改成java改的我头大，果然还是太菜了
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
dfs(nums, res, 0, path);
return res;
}
private void dfs(int[] nums, List<List<Integer>> res, int begin, ArrayList<Integer> path){
res.add(new ArrayList<>(path));
if(nums.length == path.size()){
return;
}
for(int i = begin;i<nums.length;i++){
path.add(nums[i]);
dfs(nums, res, i+1, path);
path.remove(path.size()-1);
}
}
}
9.19
leetcode的周六，i了i了
题目
404. 左叶子之和
难度简单
计算给定二叉树的所有左叶子之和。
示例：
3 / \ 9 20 / \ 15 7 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
题解
- 遍历所有节点
- 把所有自己本身是左子节点且自己没有子节点的节点加起来
总结：万能的dfs
这边用了一个flag位去判断该节点是不是左子节点，这么写的话递归过程比较好理解
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
def findAndAdd(root, flag):
if not root:
return 0
if flag and root and not root.left and not root.right:
return root.val
return findAndAdd(root.left, True) + findAndAdd(root.right, False)
return findAndAdd(root, False)
// java就是单纯的翻译一遍上面的代码
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return add(root, false);
}
private int add(TreeNode root, boolean flag){
if(root == null){
return 0;
}
if(flag && root.left == null && root.right == null){
return root.val;
}
return add(root.left, true)+add(root.right, false);
}
}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
dfs(nums, res, 0, path);
return res;
}
private void dfs(int[] nums, List<List<Integer>> res, int begin, ArrayList<Integer> path){
res.add(new ArrayList<>(path));
if(nums.length == path.size()){
return;
}
for(int i = begin;i<nums.length;i++){
path.add(nums[i]);
dfs(nums, res, i+1, path);
path.remove(path.size()-1);
}
}
}
9.18
人在图书馆 很困 想睡 晚安
题目
47. 全排列 II
难度中等
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
题解
跟组合一样，这道题还是老方法，回溯法
不断地递归去求排列的可能性
区别在于剪枝的方法
if not used[i]:
if i>0 and nums[i] == nums[i-1] and not used[i-1]:
continue
就拿题目里的[1, 1, 2]来举例说明吧
- 一开始我选第一个1
- 接下来我选1
- 由于只剩下一个2，所以构成[1,1,2]
- 接下来我选2
- 由于只剩下一个1，所以构成[1,2,1]
- 接下来我选1
- 一开始我选第二个1
- 这时我们知道其实这种条件下是跟上面一摸一样的，因为两个数字相同嘛
- 那么这种就没有必要继续递归求解
- 这种条件具体就是指
- 我现在选的这个数字已经在上一个分支里出现过
- 也就是nums[i] == nums[i-1]
- 同时我还要保证这个分支里，没有继续选上一个数 not used[i-1]
代码
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
if len(nums) == 0:
return []
def dfs(nums, depth, used, path,res):
if depth == len(nums):
res.append(path.copy())
return
for i in range(len(nums)):
if not used[i]:
if i>0 and nums[i] == nums[i-1] and not used[i-1]:
continue
path.append(nums[i])
used[i] = 1
dfs(nums, depth+1, used, path, res)
used[i] = 0
path.pop()
res = []
used = [0 for i in range(len(nums))]
dfs(nums, 0, used, [], res)
return res
9.17
人傻了，到图书馆一看，发现是困难题
看完题目，发现是图论，得，咱直接看题解好了
685. 冗余连接 II
难度困难
在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。
输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以
边组成的二维数组。 每一个边的元素是一对[u, v]，用以表示有向图中连接顶点u和顶点v的边，其中u是v的一个父节点。返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
示例 1:
输入: [[1,2], [1,3], [2,3]] 输出: [2,3] 解释: 给定的有向图如下: 1 / \ v v 2-->3示例 2:
输入: [[1,2], [2,3], [3,4], [4,1], [1,5]] 输出: [4,1] 解释: 给定的有向图如下: 5 <- 1 -> 2 ^ | | v 4 <- 3注意:
- 二维数组大小的在3到1000范围内。
- 二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。
题解
看完weiwei大佬的题解，发现自己好菜
题目的意思就是说现在给了你很多根边，要求是删除一根边，让剩下边拼到一块儿就是一个有根树
那怎么需要删除的边呢？
说到底无非就是
- 删一条边
- 看剩下的边能不能成树
那大佬总结出来怎么删的边的可能性有
- 删掉一条入度为2的边，看还会不会构成回路
- 删掉一条入度为1的边，看还会不会构成回路
那么具体要做的看上去有两件事
- 统计每条边的入度
- 判断删掉某条边后，是否会构成回路
那么判断回路还需要用到一种算法，叫做并查集。
可以参考这篇文章，特别好懂
https://blog.csdn.net/qq_41593380/article/details/81146850
简单来说并查集就是用来快速查找某个点的根节点
代码
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int len = edges.length;
// 先记录所有点的入度
int[] inDegree = new int[len+1];
for(int[] edge:edges){
inDegree[edge[1]]++;
}
for(int i = len-1;i >= 0;i--){
if(inDegree[edges[i][1]] == 2){
// 尝试删除入度为2的边
if(!judgeCircle(edges,len,i)){
// 删除该边后如果不形成环，说明就是要删除的那条变
return edges[i];
}
}
}
for(int i = len-1;i>=0;i--){
if(inDegree[edges[i][1]] == 1){
// 尝试删除入度为1的边
if(!judgeCircle(edges,len,i)){
// 同理，删除后不成环就返回边
return edges[i];
}
}
}
return new int[0];
}
private boolean judgeCircle(int[][] edges, int len, int remove){
UnionFind unionFind = new UnionFind(len+1);
// 尝试删除某条边之后 判断是否成环
for(int i = 0;i<len;i++){
if (i == remove){
continue;
}
if(!unionFind.union(edges[i][0], edges[i][1])){
// 如果合并失败，说明edges[i][0]和edges[i][1]在一个联通分量离
return true;
}
}
return false;
}
private class UnionFind{
private int[] parent;
public UnionFind(int n){
parent = new int[n];
for(int i = 0;i<n;i++){
parent[i] = i;
}
}
public int find(int x){
while(x!=parent[x]){
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public boolean union(int x, int y){
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY){
return false;
}
parent[rootX] = rootY;
return true;
}
}
}
9.16
ohhhhh，又是简单题，赶快刷完去刷托福了
题目
226. 翻转二叉树
难度简单
翻转一棵二叉树。
示例：
输入：
4 / \ 2 7 / \ / \ 1 3 6 9输出：
4 / \ 7 2 / \ / \ 9 6 3 1
题解
思路很简单，用一个递归函数去把每个节点的左子树和右子树交换一下就完事儿了
唯一需要提的就是python的代码会跟java的有点不一样
python属于自顶向下的，java属于自底向上的。
因为python可以直接root.left, root.right = root.right, root.left
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return root;
}else{
TreeNode left = invertTree(root.right);
TreeNode right = invertTree(root.left);
root.left = left;
root.right = right;
}
return root;
}
}
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
def reverse(root):
if not root:
return
root.left, root.right = root.right, root.left
reverse(root.left)
reverse(root.right)
reverse(root)
return root
9.15
今天是困难题，有点懵
不过幸好今天没课
题目
37. 解数独
难度困难
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。- 数字
1-9在每一列只能出现一次。- 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。空白格用
'.'表示。
一个数独。
答案被标成红色。
Note:
- 给定的数独序列只包含数字
1-9和字符'.'。- 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9形式的。
题解
首先确定我们的方法，回溯法
基本思路就是
- 根据当前的棋盘，在一个空格内填入可能的数字
- 在填入一个可能的解后，继续在下一个空格内填入可能的数字
- 若填入当前数字后发现没有下一个能填入的数字，就退回上一步，在该空格内填另一个可能的数字（回溯法的关键思想）
- 直到将所有空格填满
我们根据数独的三个规则找到填入数字的可能性
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
如何快速判断某一个格子能填几呢？针对三个规则，定义三个数组
- row数组，用来检查每行的数字的出现情况
row[i][j]=1代表了第i+1行出现过j+1这个数字
- col数组，用来检查每列的数字的出现情况
col[i][j]=1代表了第i+1列出现过j+1这个数字
- block数组，用来检查九个九宫格内数字的出现情况
block[i/3][j/3][k]=1代表了第i/3行,第j/3的九宫格内出现过k+1这个数字
如何知道哪些空格需要填呢？
- 建立一个动态数组spaces，一开始遍历棋盘找到所有空格，以
[i,j]的格式放入spaces中
解数独具体的流程
- 遍历一遍当前棋盘，初始化row,col,block,spaces数组
- 对整个棋盘进行递归求解
- 如果此时已经没有空格可以填入，则退出循环，找到解
- 否则就找到需要填的空格，尝试将1-9其中满足规则的填入空格并更新三个数组
- 在调用递归函数之后，要把当前填入的整个数字给去掉，并还原三个数组
代码
class Solution {
// row[i][j] 用来记录第i+1行有没有出现过j+1这个数字
private int[][] row = new int[9][9];
// col[i][j] 用来记录第i+1列有没有出现过j+1这个数字
private int[][] col = new int[9][9];
// block[i][j][k] 用来记录第i+1行第j+1列的这个九宫格内是否出现过k+1这个数字
private int[][][] block = new int[3][3][9];
// spaces中的第i个数组[i,j]用来存储的是第i+1行，j+1列这个方格是否为空
private List<int[]> spaces = new ArrayList<>();
// valid用来判断数独是否已经完成
private boolean valid = false;
public void solveSudoku(char[][] board) {
for(int i = 0;i<9;i++){
for(int j = 0;j<9;j++){
if(board[i][j] == '.'){
spaces.add(new int[]{i,j});
}else{
int num = board[i][j] - '1';
row[i][num] = col[j][num] = block[i/3][j/3][num] = 1;
}
}
}
dfs(board,0);
}
private void dfs(char[][] board, int index){
if(index == spaces.size()){
valid = true;
return;
}else{
int cur_i = spaces.get(index)[0];
int cur_j = spaces.get(index)[1];
for(int num = 1; num <= 9 && !valid;num++){
if(row[cur_i][num-1]==0 && col[cur_j][num-1]==0 && block[cur_i/3][cur_j/3][num-1]==0){
row[cur_i][num-1] = col[cur_j][num-1] = block[cur_i/3][cur_j/3][num-1] = 1;
board[cur_i][cur_j] = (char)(num+ '0');
dfs(board, index+1);
row[cur_i][num-1] = col[cur_j][num-1] = block[cur_i/3][cur_j/3][num-1] = 0;
}
}
}
}
}
9.14
三天的数模竞赛终于结束了，头发掉光，疯狂爆痘，人快猝死了
算是见到了凌晨三点的苏大，24小时内只吃了一顿饭，已经没空去饿了
努力了 尝试了 尽力了 也可以说这次就算理想不结果也是问心无愧了
终于又回到了leetcode的怀抱
在研究了三天热学，整数规划，机理模型，从数学建模到语文建模后
今天的ta用美好的二叉树来欢迎我，我简直感动到热泪盈眶
题目
94. 二叉树的中序遍历
难度中等
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]进阶: 递归算法很简单，你可以通过迭代算法完成吗？
题解1
首先用递归来解，很简单
中序遍历就是写一个递归，然后在递归函数内对结点的处理顺序就是先左结点，再父节点，最后右结点
代码1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
ans = []
def inorder(root):
if not root:
return
inorder(root.left)
ans.append(root.val)
inorder(root.right)
inorder(root)
return ans
题解2
然后用java写一个非递归的
参考了官方题解，简单来说就是用stack来模拟递归
代码2
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stk = new LinkedList<>();
while(!stk.isEmpty() || root!=null){
while(root != null){
stk.push(root);
root = root.left;
}
root = stk.pop();
ans.add(root.val);
root = root.right;
}
return ans;
}
}
9.10
题目
40. 组合总和 II
难度中等
给定一个数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
题解
总体上跟昨天的每日一题差不多
思路都是利用dfs或者说回溯法，逐个可能性递归求解
唯一的区别就是，昨天是可以重复的，今天是不能重复的
- java我使用的依然是昨天的方法，只是更改了一下每次递归时begin的位置，昨天是从原数字开始，今天从原数字后面一个开始递归（因为每个数字只能用一次）
- python的话我尝试了使用哈希表（字典）来记录数字出现的次数，然后在遍历时候先把数组去重。最后在回溯的时候去增删这个数字出现的次数，来保证每个数字不会被重复使用
代码
import java.nio.file.Path;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(candidates);
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, target, 0, ans, path);
return ans;
}
public void dfs(int[] candidates, int target, int begin, List<List<Integer>> ans, Deque<Integer> path){
if(target == 0){
ans.add(new ArrayList<>(path));
}else{
for(int i = begin;i<candidates.length;i++){
if(candidates[i] > target){
break;
}else if(i > begin && candidates[i] == candidates[i-1]){
continue;
}else{
path.addLast(candidates[i]);
dfs(candidates, target-candidates[i], i+1, ans, path);
path.removeLast();
}
}
}
}
}
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
candidates_set = list(set(candidates))
dic = dict()
for i in candidates_set:
dic[i] = candidates.count(i)
def dfs(nums, target, begin):
if target == 0:
ans.append(nums)
else:
for i in range(begin,len(candidates_set)):
num = candidates_set[i]
if not dic[num]:
continue
elif num>target:
return
else:
dic[num] -= 1
dfs(nums+[num],target-num,i)
dic[num] += 1
dfs([], target,0)
return ans
9.9
题目
39. 组合总和
难度中等884
给定一个无重复元素的数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的数字可以无限制重复被选取。说明：
- 所有数字（包括
target）都是正整数。- 解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]示例 2：
输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]提示：
1 <= candidates.length <= 301 <= candidates[i] <= 200candidate中的每个元素都是独一无二的。1 <= target <= 500
题解
一看题目就知道，深搜肯定好用
那么首先要考虑的是递归函数的参数也就是，dfs(?)
-
首先肯定得有一个列表去存放目前为止已经被加起来的数，那就先设定为nums吧
-
同时为了避免每次递归时都要求一次数组nums的和，还得有一个变量存储当前nums的和，就叫它cur_sum吧
-
假设我们就用这两个显然的参数来写递归
- 考虑出递归的条件，很简单，有两种
- cur_sum > target
- cur_sum == target
- 其中第一种情况因为此时不管再怎么往nums里加数字都不可能成立，所以直接return
- 第二种情况，nums数组属于题目要求的组合，就把nums数组放到ans数组中，然后return
- 考虑出递归的条件，很简单，有两种
-
除此之外，就是cur_sum < target了
-
这个时候很容易想到，去遍历一遍candidates数组中所有的数字，添加到nums数组里试一下就好了
-
此时可以有一个剪枝的小办法，先判断cur_sum加上这个数字是不是小于等于target
-
如果小于等于，就继续搜
-
反之，就不用dfs了
-
-
但是这样操作下来有一个问题
- 例如candidates = [2, 3], target = 8
- 那么最后答案中会出现[2,2,3], [2,3,2], [3,2,2]
- 为什么呢？因为我们每次深搜的时候都是把整个nums数组遍历一遍，自然会出现不同顺序同样数字的组合
- 怎么解决呢？
-
增加一个变量begin，用来存储每次遍历开始的位置
- 用这个变量来保证每次我遍历数组，去尝试各个可能性的时候都是从至少当前数字开始往后
- 由于题目给的candidates是从小到大排序的，所以就绝对不会出现[2,3,2]这种组合了
-
代码
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
# 存放答案
def dfs(nums,cur_sum, begin):
# 递归深搜
if cur_sum > target:
return
elif cur_sum == target:
ans.append(nums)
else:
for i in range(begin,len(candidates)):
cur_num = candidates[i]
if cur_sum+cur_num <= target:
dfs(nums+[cur_num], cur_sum+cur_num, i)
return
dfs([],0,0)
return ans
9.8
又到了愉快（并不）的刷题时间啦
77. 组合
难度中等
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
题解1
一种解法是比较巧妙的结合了数学归纳法，评论里的大佬是真滴强
- 利用C(m,n) = C(m-1,n) + C(m-1,n-1)，使用递归的方式
代码1
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
if k>n or k == 0:
return []
if k == 1:
return [[i] for i in range(1,n+1)]
if k == n:
return [i for i in range(1,n+1)]
answer = self.combine(n-1,k)
for i in self.combine(n-1,k-1):
i.append(n)
answer.append(i)
return answer
题解2
这种解法就非常朴实无华，总结就是dfs加剪枝
-
举个例子，例如n=5，k=3
-
现在我的path中存放了1，2，那么我要怎么找到第三个数呢？
-
通过循环，begin值设为3，然后递增1，每次循环的时候把对应的值加到path中，最后在回溯的时候要把这个加进去的值remove掉
-
会有一个什么样的过程呢？
- i = begin = 3
- path.add(3)
- 此时执行dfs
- 发现path的长度等于3，所以res.add(path)
- 然后这个时候又回到path.add(3)之后
- 因为3已经被用过了，就把3remove掉，继续循环
- 这一次 i = 4，重复以上步骤
-
可能有点难理解，直接看代码好了
代码2
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public List<List<Integer>> combine(int n, int k) {
// res存放结果，path存放在递归过程中的临时数组
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> path = new ArrayDeque<>();
if(k<=0 || k>n){
return res;
}
dfs(n, k, 1, path, res);
return res;
}
private void dfs(int n, int k,int begin, Deque<Integer> path, List<List<Integer>> res){
if(path.size() == k){
// 当path中有k个元素时就把path加入到结果中
res.add(new ArrayList<>(path));
}else{
// 这里处理剪枝时可以注意到i<=n其实是一个过于宽泛的条件
// 例如n=15，k=4，path里已经有了两个数，接下来还要选择两个数
// 搜索的起点begin值最大就是14，最后一个被选的是[14,15]
// 也就是说i<=15条件过大，应该是i<=14,这里的14 = n-(k-path里已经有的元素数) + 1
for(int i = begin;i<=n-(k-path.size())+1;i++){
path.addLast(i);
dfs(n, k, i+1, path, res);
// 每次回溯都需要把那个加进去的值删掉再继续循环
path.removeLast();
}
}
}
}
9.7
开学第一天哦，题目不算难噢（好尬）
题目
347. 前 K 个高频元素
难度中等
给定一个非空的整数数组，返回其中出现频率前 *k* 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]示例 2:
输入: nums = [1], k = 1 输出: [1]提示：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
题解
首先题目要求返回的是出现频率的前k个元素，那这个出现频率首先肯定得求出来对不对。
那么题目还要求时间复杂度要由于N log N，那么直接用两层循环去求每个元素的次数（python里的count方法）肯定是不满足的。（是N²了）
那就用字典嘛，或者说哈希表。
dic[i]=x，这里的i是nums数组中的数字，x是i在数组nums中出现的总次数。
循环一遍nums，遇到一个i就把dic[i]+1。
求出了出现次数之后怎么办呢，要找到前k个。
这里就有两种方法了
-
一种是死办法，把所有的数字根据出现次数，直接排序，虽然是 N log N不过也能通过呢。（代码见下python）
-
一种是稍微巧妙一点的办法，建小顶堆，也就是说堆顶的那个元素的值一定是堆中最小的。
- 把哈希表中所有的键值对一个一个丢到堆里。
- 如果堆里面装的个数小于k（题目中要求返回出现次数排序前k个的元素），就直接丢到堆里
- 如果堆的个数等于k了，就检查这个键对应value是否比堆顶的value大，如果更大，就把堆顶的丢掉，把新的一个键值对塞进堆里
- 要注意，塞进去的同时要能够保证堆顶的值一直是最小的
代码
python是纯自己写，但是java的由于学术不精，只会语法，库和包都不会用，就剽的大佬的。
python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
dic = dict()
for i in nums:
if not dic.get(i):
dic[i] = 1
else:
dic[i] += 1
nums = list(set(nums))
nums.sort()
cnts = []
for i in nums:
if dic[i]:
cnts.append([i,dic[i]])
cnts.sort(key = lambda d:d[1], reverse = True)
ans = [(cnts[i][0]) for i in range(k)]
return ans
java
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap();
for(int num : nums){
if (map.containsKey(num)){
map.put(num, map.get(num)+1);
}else{
map.put(num,1);
}
}
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a, Integer b){
return map.get(a)-map.get(b);
}
});
for(Integer key : map.keySet()){
if (pq.size() < k){
pq.add(key);
} else if (map.get(key) > map.get(pq.peek())){
pq.remove();
pq.add(key);
}
}
int[] res = new int[k];
int i = 0;
while(!pq.isEmpty()){
res[i++] = pq.remove();
}
return res;
}
}
9.6
题目
107. 二叉树的层次遍历 II
难度简单
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如： 给定二叉树
[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7返回其自底向上的层次遍历为：
[ [15,7], [9,20], [3] ]
题解
看到难度是简单就松了一口气
果不其然， 今天的题目也算是对一年前的数据结构的复习吧，还记得当时老师只要求画图，不要求具体的代码
这次就来试试看吧
一看到二叉树就想到了递归
由于个人对于dfs比较熟悉，就直接写了一个dfs递归解法
- 用res来存储最终结果
- 当遍历到新的一层的时候（也就是depth>=res数组的长度的时候），就往res里append一个空列表用于存储新的一层的结点值
- 同时往该结点对应那一层的列表里（res[depth]）append结点的值
- 对该结点的左子节点和右子节点重复以上工作
代码
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
res = []
def dfs(root, depth):
if not root:
return
if len(res)<depth+1:
res.append([])
res[depth].append(root.val)
dfs(root.left, depth+1)
dfs(root.right, depth+1)
dfs(root,0)
return res[::-1]
9.5
又到新学期啦（上学期啥都没学就过去了，暑假也跟飞一样地过去了）
事不宜迟开始刷题吧，毕竟不管是为了实习，还是为了读研，还是为了申请出国的项目，刷题都是血赚。
题目
60. 第k个排列
难度中等
给出集合
[1,2,3,…,*n*]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。
说明：
- 给定 n 的范围是 [1, 9]。
- 给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3 输出: "213"示例 2:
输入: n = 4, k = 9 输出: "2314"
题解
给定两个数字，一个n是数字的位数，一个k意思是返回所有排序中第k大的那个排序。
思路也不难理解，位数从大到小开始考虑。
举个例子就能明白，就拿示例二来讲。
输入: n = 4, k = 9
输出: "2314"
-
n=4，k=9，我们第一个要考虑的是千位数；
-
由于是从小到大的全排列，而且我们有1 2 3 4，这四个数字；
-
那么很显然全排列中一开始一定是一些1XXX，然后是2XXX，然后是3XXX，最后是4XXX，其中每个数字开头的排列数肯定是相同的；
-
每个数字开头有多少种排列呢？
- 1XXX有 $3!=3\times2\times1=6$种
- 同样2XXX，3XXX，4XXX也都是每个6种
-
有了这个，加上k=9，我们就知道，我们要找的排列肯定是2开头的，因为(9/6)向上取整=2
-
当我们找到这个千位数字之后，我们就要继续找百位数了，方法跟千位数一样。循环n次即获得最终答案。
-
有一个点需要注意的就是，我们用一个数组nums去存储我们排列中可能的数字，当取用其中一个数字之后，要把它在数组中删掉
代码
部分命名习惯及语法可能有所欠缺，望指出。
class Solution:
def getPermutation(self, n: int, k: int) -> str:
def fac(n):
res = 1
for i in range(1,n+1):
res *= i
return res
nums = [i for i in range(1,n+1)]
res = ""
for i in range(n-1,-1,-1):
# 1.找出对应位数-1的阶乘
# 2.比如找n = 3, k = 3时，一开始就是 (3-1)! = 2
# 说明有2个百位为1的，2个百位为2的，2个百位为3的数字
# 3.因为我们要找的是第3个，按小到大排就是百位为2的
# 4.然后我们就把第2个数字就nums数组中删掉
# 5.后面的数字从第一步开始重复，直到nums数组为空
cur_fac = fac(i)
ind = math.ceil(k/cur_fac)
if k>cur_fac:
k %= cur_fac
cur_num = nums[ind-1]
res += str(cur_num)
nums.remove(cur_num)
return res
执行结果：
执行用时：32 ms, 在所有 Python3 提交中击败了98.22%的用户
内存消耗：13.7 MB, 在所有 Python3 提交中击败了46.33%的用户