leetcode解题报告

宋正兵 更新 on 2021-08-06

1、二叉树专题

总结

  • 掌握二叉树递归与非递归遍历

模板

模板整理来源

作者:gre-z
链接:https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian–2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

前序遍历模板(递归)

1
2
3
4
5
6
7
8
public static void preOrderRecur(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.value + " ");
preOrderRecur(root.left);
preOrderRecur(root.right);
}

前序遍历模板(迭代)

首先我们应该创建一个 Stack 用来存放节点,首先我们想要打印根节点的数据,此时 Stack 里面的内容为空,所以我们优先将头结点加入 Stack ,然后打印。

之后我们应该先打印左子树,然后右子树。所以先加入Stack 的就是右子树,然后左子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void preOrderIteration(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tempNode = stack.pop();
System.out.print(tempNode.value + " ");
if (tempNode.right != null) {
stack.push(tempNode.right);
}
if (tempNode.left != null) {
stack.push(tempNode.left);
}
}
}

中序遍历模板(递归)

1
2
3
4
5
6
7
8
public static void preOrderRecur(TreeNode root) {
if (root == null) {
return;
}
preOrderRecur(root.left);
System.out.print(root.value + " ");
preOrderRecur(root.right);
}

中序遍历模板(迭代)

  1. 创建一个 Stack ,然后按 左 中 右的顺序输出节点。
  2. 尽可能的将这个节点的左子树压入 Stack ,此时栈顶的元素是最左侧的元素,其目的是找到一个最小单位的子树(也就是最左侧的一个节点),并且在寻找的过程中记录了来源,才能返回上层,同时在返回上层的时候已经处理完毕左子树了。
  3. 当处理完最小单位的子树时,返回到上层处理了中间节点。(如果把整个左中右的遍历都理解成子树的话,就是处理完 左子树->中间(就是一个节点)->右子树)
  4. 如果有右节点,其也要进行中序遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void inOrderIteration(TreeNode root) {
if (root == null) {
return;
}
TreeNode tempNode = root;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || tempNode != null) {
while (tempNode != null) {
stack.push(tempNode);
tempNode = tempNode.left;
}
tempNode = stack.pop();
System.out.print(tempNode.value + " ");
tempNode = tempNode.right;
}
}
1
2
3
4
5
6
7
8
9
10
11
栈S;
p= root;
while(p || S不空){
while(p){
p入S;
p = p的左子树;
}
p = S.top 出栈;
访问p;
p = p的右子树;
}

后续遍历模板(递归)

1
2
3
4
5
6
7
8
public static void postOrderRecur(TreeNode root) {
if (root == null) {
return;
}
postOrderRecur(root.left);
postOrderRecur(root.right);
System.out.print(root.value + " ");
}

后续遍历模板1(迭代)

  1. 前序遍历的过程 是 中左右。
  2. 将其转化成 中右左。也就是压栈的过程中优先压入左子树,在压入右子树。
  3. 然后将这个结果返回来,这里是利用栈的先进后出倒序打印。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void postOrderIteration(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode tempNode = stack1.pop();
stack2.push(tempNode);
if (tempNode.left != null) {
stack1.push(tempNode.left);
}
if (tempNode.right != null) {
stack1.push(tempNode.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().value + " ");
}
}

改进,利用LinkedList,直接头插

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void postOrderIteration(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
List<Integer> resList = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tempNode = stack.pop();
resList.add(0, tempNode.val);
if (tempNode.left != null) {
stack.push(tempNode.left);
}
if (tempNode.right != null) {
stack.push(tempNode.right);
}
}
// 打印 resList
}

后续遍历模板2(迭代)

  1. 用一个指针 cur 标记当前退出的节点是什么。
  2. 后序遍历的过程中在遍历完左子树跟右子树 cur 都会回到根结点。所以当前不管是从左子树还是右子树回到根结点都不应该再操作了,应该退回上层。
  3. 如果是从右边再返回根结点,应该回到上层。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void postOrderIteration2(TreeNode root) { 
if (root == null) {
return;
}
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
TreeNode peek = stack.peek();
if (peek.left != null && peek.left != cur && peek.right != cur) {
stack.push(peek.left);
} else if (peek.right != null && peek.right != cur) {
stack.push(peek.right);
} else {
System.out.print(stack.pop().val + " ");
cur = peek;
}
}
}

层次遍历模板 BFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public void bfs(Node root) {
Queue<Node> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
Node tempNode = queue.poll();
// visit
for(遍历所有tempNode的相邻节点nextNode) {
if (nextNode节点有效 && visited[nextNode]==0) {
visited[nextNode] = 1;
queue.offer(nextNode);
}
}
}
}
}

层次遍历模板 BFS模板 可以确定遍历到哪一层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public void bfs(Node root) {
Queue<Node> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
}
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
Node tempNode = queue.poll();
size--;
// visit
for(遍历所有tempNode的相邻节点nextNode) {
if (nextNode节点有效 && visited[nextNode]==0) {
visited[nextNode] = 1;
queue.offer(nextNode);
}
}
}
level++;
}
}
}

144. 二叉树的前序遍历

二叉树的前序遍历

递归 根左右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
List<Integer> list = new LinkedList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
preOrder(root);
return list;
}
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
}

迭代 栈是先进后出,所以先入栈右子树,再入栈左子树,出栈的时候正好是先左子树后右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> output = new LinkedList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if (root == null) {
return output;
}
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tempNode = stack.pop();
output.add(tempNode.val);
if (tempNode.right != null) {
stack.push(tempNode.right);
}
if (tempNode.left != null) {
stack.push(tempNode.left);
}
}
return output;
}
}

94. 二叉树的中序遍历

二叉树的中序遍历

递归 左根右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
List<Integer> output = new LinkedList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
MidOrder(root);
return output;
}
public void MidOrder(TreeNode root) {
if (root == null) {
return;
}
MidOrder(root.left);
output.add(root.val);
MidOrder(root.right);
}
}

迭代 利用栈实现,先找到二叉树的最左叶子节点对其访问,然后退回上一个节点访问,如果有右子树则对其右子树同样地进行找到最左叶子节点操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> output = new LinkedList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode tempNode = root;
while (tempNode != null || !stack.isEmpty()) {
while (tempNode != null) {
stack.push(tempNode);
tempNode = tempNode.left;
}
tempNode = stack.pop();
output.add(tempNode.val);
tempNode = tempNode.right;
}
return output;
}
}

145. 二叉树的后序遍历

二叉树的后序遍历

递归 左右根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
List<Integer> output = new LinkedList<Integer>();
public List<Integer> postorderTraversal(TreeNode root) {
afterOrder(root);
return output;
}
public void afterOrder(TreeNode root) {
if (root == null) {
return;
}
afterOrder(root.left);
afterOrder(root.right);
output.add(root.val);
}
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> output = new LinkedList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if (root == null) {
return output;
}
// cur 记录上一次访问对象
TreeNode cur = root;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tempNode = stack.peek();
if (tempNode.left != null && tempNode.left != cur && tempNode.right != cur) {
// 左子树不为空,且左子树未被访问(防止左子树访问后退回父节点又访问左子树)
// 且右子树不为空(防止左右子树都访问后退回父节点又接着访问)
stack.push(tempNode.left);
} else if (tempNode.right != null && tempNode.right != cur) {
// 右子树不为空且右子树未被访问
stack.push(tempNode.right);
} else {
tempNode = stack.pop();
output.add(tempNode.val);
cur = tempNode;
}
}
return output;
}
}

102. 二叉树的层序遍历

二叉树的层序遍历

给定一个二叉树,返回按照 层序遍历 得到的节点值

用一个队列记录一层的元素,然后扫描这一层的元素,并把下一层的元素添加到队列中,同时将本层的元素添加到 List 集合中去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> resList = new LinkedList<List<Integer>>();
if (root != null) {
queue.add(root);
}
while (! queue.isEmpty()) {
int size = queue.size();
LinkedList<Integer> tempList = new LinkedList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode tempNode = queue.poll();
tempList.add(tempNode.val);
if (tempNode.left != null) {
queue.add(tempNode.left);
}
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
resList.add(tempList);
}
return resList;
}
}

107. 二叉树的层次遍历 II

二叉树的层次遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

同102类似,利用队列进行层次遍历,不同的是在插入时使用头插的方法记录每一层的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> resList = new LinkedList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();

if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> tempList = new LinkedList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode tempNode = queue.poll();
tempList.add(tempNode.val);
if (tempNode.left != null) {
queue.add(tempNode.left);
}
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
// 头插
resList.add(0, tempList);
}
return resList;
}
}

103. 二叉树的锯齿形层次遍历

二叉树的锯齿形层次遍历

层序遍历的变形,定义一个变量来记录当前层次的遍历是从左往右还是从右往左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> output = new LinkedList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if (root == null) {
return output;
}
queue.add(root);
boolean sequence = true;
while (! queue.isEmpty()) {
int size = queue.size();
List<Integer> tempList = new LinkedList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode tempNode = queue.poll();
if (sequence) {
tempList.add(tempNode.val);
} else {
tempList.add(0, tempNode.val);
}

if (tempNode.left != null) {
queue.add(tempNode.left);
}
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
output.add(tempList);
sequence = !sequence;
}
return output;
}
}

104. 二叉树的最大深度

二叉树的最大深度

给定一个二叉树,找出其最大深度。

思路1:递归。 已知左右子树的深度为 lr ,那么该二叉树的最大深度为
$$
max(l,r) + 1
$$
而左子树和右子树的最大深度又可以以同样的方式进行计算。递归在访问到空节点时退出。

1
2
3
4
5
6
7
8
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}

思路2:层次遍历。 需要作一点的改变是,得记录每一层节点的个数,只有在遍历完当前层次的节点过后,才能算作进入下一层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int depth = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode temp = queue.poll();
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
size--;
}
depth++;
}
return depth;
}
}

110. 平衡二叉树

平衡二叉树

判断一棵二叉树是否是高度平衡的二叉树。

高度平衡二叉树的定义:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

自顶向下: 首先计算左右子树的高度,如果左右子树的高度差是否不超过 1,再分别递归地遍历左右子节点,并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right);
}
public static int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}

自底向上:

自顶向下对于同一个节点,函数 maxDepth 会被重复调用,会导致时间复杂度高。使用自底向上的做法,对每个节点只会调用函数 maxDepth 一次。

对于当前遍历到的节点,先递归地判断其左右子树是否平衡,再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定是非负整数),否则返回 -1。如果存在一棵子树不平衡,则整个二叉树一定不平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean isBalanced(TreeNode root) {
return maxDepth1(root) >= 0;
}
public static int maxDepth1(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = maxDepth1(root.left);
int rightHeight = maxDepth1(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
}

124. 二叉树中的最大路径和

二叉树中的最大路径和

给一颗非空的二叉树,返回其最大路径和。

主要使用递归的思想。完成一个函数 maxGain(node) ,计算二叉树中的一个节点的最大贡献值,即以该节点为根节点的子树中寻找以该节点为起点的一条路径,使得该路径上的节点值之和最大。

具体而言,计算如下:

  • 空节点的最大贡献为0
  • 非空节点的最大贡献等于节点值与其子节点中的最大贡献值之和

使用全局变量 maxSum 来存储最大路径和,在递归过程中更新它的值。

节点的贡献值是节点所在的路径!对于当前节点的贡献值是节点值+MAX(左节点的最大贡献,右节点的最大贡献)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}

public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时,才会选取对应子节点
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
int priceNewpath = node.val + leftGain + rightGain;
// 更新答案
maxSum = Math.max(maxSum, priceNewpath);
// 返回节点的最大贡献值
return node.val + Math.max(leftGain, rightGain);
}
}

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

二叉树的最近公共祖先

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

祖先的定义: 若节点 p 在节点 root 的左(右)子树中,或 p = root ,则称 rootp 的祖先。

最近公共祖先的定义: 设节点 root 为节点 p, q 的某公共祖先,若其左子节点 root.left 和右子节点 root.right 都不是 p, q 的公共祖先,则称 root 是 “最近的公共祖先”。

根据以上定义,若 rootp, q最近公共祖先 ,则只可能为以下情况之一:

  • pq 在root的子树中,且分列 root异侧 (即分别在左、右子树中);
  • p = root ,且 qroot 的左或右子树中;
  • q = root ,且 proot 的左或右子树中;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 越过叶子节点 或 找到其中一个节点
if (root == null || root.val == p.val || root.val == q.val) {
return root;
}

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);


// 左、右子树都不为空,则表明 p 和 q 在 root 的异侧,该节点是最近公共祖先
if (left != null && right != null) {
return root;
} else if (left != null) {
// left != null && right == null
// p 和 q 都不在 root 的右侧,直接返回 left
return left;
} else if (right != null) {
// left == null && right != null
return right;
} else {
// 同时为空,说明 root 的左右子树都不包含 p 和 q
return null;
}
}
}

98. 验证二叉搜索树

验证二叉搜索树

假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

给定一个二叉树,判断其是否是一个有效的二叉搜索树

中序遍历递归 利用 pre 变量记录中序遍历中的前一个值大小。因为中序遍历的顺序是左根右,遍历时,判断当前节点是否大于中序遍历的前一个节点,如果大于,说明满足 BST,继续遍历;否则直接返回 false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// 访问左子树
if (!isValidBST(root.left)) {
return false;
}
// 访问当前节点:如果当前节点小于等于中序遍历的前一个节点,说明不满足BST,返回 false;否则继续遍历。
if (root.val <= pre) {
return false;
}
pre = root.val;
// 访问右子树
return isValidBST(root.right);
}
}

中序遍历迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
long pre = Long.MIN_VALUE;
TreeNode tempNode = root;
while(tempNode != null || !stack.isEmpty()) {
while (tempNode != null) {
stack.push(tempNode);
tempNode = tempNode.left;
}
tempNode = stack.pop();
if (pre >= tempNode.val) {
return false;
}
pre = tempNode.val;
tempNode = tempNode.right;
}
return true;
}
}

701. 二叉搜索树中的插入操作

二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
}

450. 删除二叉搜索树中的节点

删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

按照二叉搜索树的规则去寻找需要删除的节点,找到后可以分为三种情况:

  • 若待删除节点为叶子节点:直接删除该节点
  • 若待删除节点有右子树:用该节点的后继节点来替代,且删除后继节点
  • 若待删除节点只有左子树:用该节点的前驱节点来替代,且删除前驱节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return root;
}
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
// 如果是叶子节点,直接删除
if (isLeaf(root)) {
root = null;
} else if (root.right != null) {
// 如果有右子树,找到后继节点,替换并删除后继节点
root.val = aftereNode(root);
root.right = deleteNode(root.right, root.val);
} else {
// 如果没有右子树,有左子树,找到前驱节点,替换并删除前驱节点
root.val = beforeNode(root);
root.left = deleteNode(root.left, root.val);
}
}

return root;
}
// 判断是否为叶子节点
boolean isLeaf(TreeNode root) {
if (root.left == null && root.right == null) {
return true;
}
return false;
}
// 找到前驱节点的值
int beforeNode(TreeNode root) {
TreeNode tempNode = root.left;
while (tempNode.right != null) {
tempNode = tempNode.right;
}
return tempNode.val;
}
// 找到后继节点的值
int aftereNode(TreeNode root) {
TreeNode tempNode = root.right;
while (tempNode.left != null) {
tempNode = tempNode.left;
}
return tempNode.val;
}
}

2、链表

  • null 异常处理
  • 哑巴节点
  • 快慢指针
  • 插入一个节点到排序列表
  • 从一个链表中移除一个节点
  • 翻转链表
  • 合并两个链表
  • 找到链表的中间节点

83. 删除排序链表中的重复元素

删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode temp = head;
while (temp != null && temp.next != null) {
if (temp.val == temp.next.val) {
temp.next = temp.next.next;
} else {
temp = temp.next;
}
}
return head;
}
}

82. 删除排序链表中的重复元素 II

删除排序链表中的重复元素 II

给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

双指针

建立两个指针 pretempNodepre 记录的是上一个不同值的链表元素,当 tempNode 指向下一个与 pre 指向元素值不相同时,判断两个指针所指向元素是否相邻(即 pre.next == tempNode )。

  • 如果相邻表示 *->1->2 这种情况,pre 所指向的 1 能够被插入输出链表
  • 如果不相邻表示 *->1->1->2 这种情况,pre 所指向的 1 不能被插入输出链表,直接更新 pre 指针的位置到 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public ListNode deleteDuplicates(ListNode head) {
// 建立一个虚拟头结点
ListNode output = new ListNode(-1);
// 定义一个尾巴,用于尾插法
ListNode tail = output;
ListNode pre = head, tempNode = head;
while (tempNode != null) {
while (tempNode != null && pre.val == tempNode.val) {
tempNode = tempNode.next;
}
if (pre.next == tempNode) {
// pre 和 tempNode 是邻近节点
// 说明 pre 和 tempNode 的节点值不同,pre 可以放入output链表
tail.next = pre;
tail = tail.next;
tail.next = null;
}
pre = tempNode;
}
return output.next;
}
}

递归

递归地处理链表头,确保没有重复的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
if (head.val == head.next.val) {
// 链表的开头就出现重复,while中消除链表头之后的重复,直到第一个不重复
// 传递第一个不重复的链表节点,变相的删除了重复的链表头。
while (head != null && head.next != null && head.val == head.next.val) {
head.next = head.next.next;
}
return deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
return head;
}
}
}

206. 反转链表

反转链表

反转一个单链表

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public ListNode reverseList(ListNode head) {
ListNode output = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = output;
output = curr;
curr = nextTemp;
}
return output;
}
}

递归

假设链表为 1->2->3 当前走到了 2 ,此时

tempNode = 3

head = 2->3

于是 head.next.next = head 表示 2->3->2head.next = null 就变成了 3->2 实现了反转。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode tempNode = reverseList(head.next);
head.next.next = head;
head.next = null;
return tempNode;
}
}

92. 反转链表 II

反转链表 II

反转从位置 mn 的链表。请使用一趟扫描完成反转。

将链表分为三个部分,需要反转之前,需要反转,需要反转之后。分别用指针 preNode 记录第 m-1 个元素,即第一个需要反转的元素的前一个元素,用来作为反转元素链表的头指针使用;需要反转的元素才用头插法,插到 preNode 所指向元素的后面,且利用指针 tailNode 记录元素反转过后被放到末尾的元素,反转完所有待反转元素后,再用 tailNode 连接反转部分和需要反转之后的部分。

例如: 1->2->3->4->5->NULL,m=2,n=4 ,此时 preNode 指向元素 1tailNode 指向元素 2,等到反转完所有元素后, tailNode 将指向元素 5

添加哑元节点的目的是为了方便处理第一个节点就需要反转的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 添加哑元节点,处理第一个节点就要反转的情况
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
// 指向第 left-1 个元素,作为反转元素的头
ListNode preNode = dummyNode;
for (int i = 1; i < left; i++) {
preNode = preNode.next;
}
// 记录反转后的尾巴元素,以便和第 right+1 个元素连接起来
ListNode tailNode = preNode.next;
ListNode curNode = preNode.next;
for (int i = left; i <= right; i++) {
ListNode tempNode = curNode.next;
curNode.next = preNode.next;
preNode.next = curNode;
curNode = tempNode;
}
// 将反转的尾巴元素指向后面不需要反转的元素
tailNode.next = curNode;
return dummyNode.next;
}
}

21. 合并两个有序链表

合并两个有序链表

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

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}

}
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);

ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}

// 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 == null ? l2 : l1;

return prehead.next;
}
}

86. 分隔链表

分隔链表

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。 保留两个分区中每个节点的初试相对位置。

模拟

记录第一个大于或等于 x 的元素的前一个元素为 pointNode ,往后遍历,每次发现小于 x 的元素时,先把该元素从当前位置取出,再将该元素插入到 pointNode 的后面,为了保证每个节点的初试相对位置, pointNode 相应的往后移动一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode output = new ListNode(Integer.MIN_VALUE);
output.next = head;
ListNode curNode = output;
ListNode preNode = output;

// 找到第一个大于或等于 x 的元素的前一个,并用 pointNode 标记
while (curNode != null && curNode.val < x) {
preNode = curNode;
curNode = curNode.next;
}
ListNode pointNode = preNode;

// 往后遍历,发现小于 x 的元素,那么往前插入到 pointNode 的后面,为了符合题目,每次插入pointNode应当往后移一位
while (curNode != null) {
ListNode tempNode = curNode.next;

if (curNode.val < x) {
// 需要插入,此时的preNode不改变
preNode.next = curNode.next;
curNode.next = pointNode.next;
pointNode.next = curNode;
pointNode = pointNode.next;
} else {
preNode = curNode;
}
curNode = tempNode;
}

return output.next;
}
}

拆分再拼接

将链表拆分为小于 x 的一部分,和大于等于 x 的一部分,然后再将两部分拼接起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public ListNode partition(ListNode head, int x) {
// 链表less记录小于x的元素
ListNode less = new ListNode(0);
ListNode ptr1 = less;
// 链表greatOrEqual记录大于等于x的元素
ListNode greatOrEqual = new ListNode(0);
ListNode ptr2 = greatOrEqual;
while (head != null) {
if (head.val < x) {
ptr1.next = new ListNode(head.val);
ptr1 = ptr1.next;
} else {
ptr2.next = new ListNode(head.val);
ptr2 = ptr2.next;
}
head = head.next;
}
// 拼接两段链表
ptr1.next = greatOrEqual.next;
return less.next;
}
}

148. 排序链表

排序链表

O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

递归 但是空间不满足常数级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/* 知识点1:归并排序的整体思想
* 知识点2:找到一个链表的中间节点的方法
* 知识点3:合并两个已排好序的链表为一个新的有序链表
*/
class Solution {
public ListNode sortList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode slow = head; //慢指针
ListNode fast = head.next; //快指针

while(fast!=null && fast.next!=null){ //快慢指针找到链表中点
slow = slow.next; //慢指针走一步
fast = fast.next.next; //快指针走两步
}
ListNode rightHead = slow.next; //链表第二部分的头节点
slow.next = null; //cut 链表

ListNode left = sortList(head); //递归排序前一段链表
ListNode right = sortList(rightHead); //递归排序后一段链表
return merge(left,right);
}
public ListNode merge(ListNode h1,ListNode h2){ //合并两个有序链表
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
while(h1!=null && h2!=null){
if(h1.val < h2.val){
p.next = h1;
h1 = h1.next;
}else{
p.next = h2;
h2 = h2.next;
}
p = p.next;
}
p.next = h1 == null ? h2 : h1;
return dummy.next;
}
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public ListNode sortList(ListNode head) {
int length = getLength(head);
ListNode dummy = new ListNode(-1);
dummy.next = head;

for(int step = 1; step < length; step*=2){ //依次将链表分成1块,2块,4块...
//每次变换步长,pre指针和cur指针都初始化在链表头
ListNode pre = dummy;
ListNode cur = dummy.next;
while(cur!=null){
ListNode h1 = cur; //第一部分头 (第二次循环之后,cur为剩余部分头,不断往后把链表按照步长step分成一块一块...)
ListNode h2 = split(h1,step); //第二部分头
cur = split(h2,step); //剩余部分的头
ListNode temp = merge(h1,h2); //将一二部分排序合并
pre.next = temp; //将前面的部分与排序好的部分连接
while(pre.next!=null){
pre = pre.next; //把pre指针移动到排序好的部分的末尾
}
}
}
return dummy.next;
}
public int getLength(ListNode head){
//获取链表长度
int count = 0;
while(head!=null){
count++;
head=head.next;
}
return count;
}
public ListNode split(ListNode head,int step){
//断链操作 返回第二部分链表头
if(head==null) return null;
ListNode cur = head;
for(int i=1; i<step && cur.next!=null; i++){
cur = cur.next;
}
ListNode right = cur.next;
cur.next = null; //切断连接
return right;
}
public ListNode merge(ListNode h1, ListNode h2){
//合并两个有序链表
ListNode head = new ListNode(-1);
ListNode p = head;
while(h1!=null && h2!=null){
if(h1.val < h2.val){
p.next = h1;
h1 = h1.next;
}
else{
p.next = h2;
h2 = h2.next;
}
p = p.next;
}
p.next = h1 == null ? h2 : h1;
return head.next;
}
}

143. 重排链表

重排链表

给定一个单链表 L: L0→L1→…→Ln-1→Ln,将其重新排列后变为 L0→Ln→L1→Ln-1→L2→Ln-2→…

快慢指针 将链表分为前半部分和后半部分,对后半部分进行翻转,再将两个链表进行交替插入即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return ;
}
// 快、慢指针 slow 和 fast
ListNode slow = head;
ListNode fast = head.next;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// 从中间切断,得到前半部分链表 l1 和后半部分链表 l2
ListNode l1 = head;
ListNode l2 = slow.next;
slow.next = null;

// 翻转后半部分链表 l2
l2 = reverse(l2);
// l1 和 l2 一人插入一次
head = merge(l1, l2);
}

ListNode reverse(ListNode head) {
// 头插法
ListNode output = new ListNode(-1);
while (head != null) {
ListNode nextNode = head.next;
head.next = output.next;
output.next = head;
head = nextNode;
}
return output.next;
}

ListNode merge(ListNode head1, ListNode head2) {
ListNode output = new ListNode(-1);
ListNode curNode = output;
boolean flag = true;
while (head1 != null && head2 != null) {
if (flag) {
flag = false;
curNode.next = head1;
head1 = head1.next;
} else {
flag = true;
curNode.next = head2;
head2 = head2.next;
}
curNode = curNode.next;
}
curNode.next = head1 == null ? head2 : head1;
return output.next;
}
}

141. 环形链表

环形链表

给定一个链表,判断是否有环。

进阶:空间复杂度 O(1) 内解决

哈希表 但是不满足空间复杂度 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<ListNode> hashSet = new HashSet<ListNode>();
while (head != null) {
// hashSet 中已经存在该元素
if (!hashSet.add(head)) {
return true;
}
head = head.next;
}
return false;
}
}

快慢指针 快指针每次移动 2 位,慢指针每次移动 1 位,如果是循环的链表,那么快慢指针一定会在某个位置相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}

142. 环形链表 II

环形链表 II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

首先判断链表是否有环,如果有环再寻找入环的第一个节点。

假设使用快慢指针判断是否有环,那么当有环的情况下,快慢指针重合的地方一定是在环内部(节点 B)。假设慢指针一共移动了 a + b 次,其中 a 是从 head 移动到入环的第一个节点 A 的步数, b 是从入环的第一个节点 A 移动到快慢指针重合的节点 B 的步数。快指针移动的步数是慢指针的两倍,所以慢指针再移动 a + b 次又能够回到节点 B。如果慢指针只移动 a 次就能回到入环的第一个节点 A,但是对于 a 的值是未知的。于是定义一个entranceNode 指针,让它和慢指针同步走,移动 a 次,它们相遇的地方必然是入环的第一个节点 A

DmliFowkvJhMOVn.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}

// 查看是否有环
ListNode slow = head;
ListNode fast = head;
boolean hasCycle = false;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}

if (hasCycle) {
// 找到环的入口
ListNode entranceNode = head;
while (entranceNode != slow) {
entranceNode = entranceNode.next;
slow = slow.next;
}
return entranceNode;
} else {
return null;
}
}
}

234. 回文链表

回文链表

判断一个链表是否是回文链表

双指针 + 栈 例如 123321 后半部分入栈后从栈顶到栈底为 123 ,然后从 head 开始出栈比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}

ListNode slow = head;
ListNode fast = head.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

Stack<Integer> stack = new Stack<Integer>();
// 指向后半部分的开始节点
ListNode suffixNode = null;
if (getLength(head) % 2 == 0) {
suffixNode = slow.next;
} else {
suffixNode = slow.next.next;
}
while (suffixNode != null) {
stack.push(suffixNode.val);
suffixNode = suffixNode.next;
}
while (!stack.isEmpty()) {
if (head.val != stack.pop()) {
return false;
}
head = head.next;
}
return true;
}

public int getLength(ListNode head) {
int length = 0;
while (head != null) {
head = head.next;
length++;
}
return length;
}
}

反转链表 + 双指针 空间复杂度 O(1) 时间复杂度 O(n)

  1. 找到前半部分链表的尾节点。
  2. 反转后半部分链表。
  3. 判断是否为回文。
  4. 恢复链表。
  5. 返回结果。

138. 复制带随机指针的链表

复制带随机指针的链表

思路:

第一遍复制节点的 valnextrandom 暂时为空,并将源节点和克隆节点形成映射存放在一个 HashMap 中。

第二遍利用 HashMap,将克隆节点对应的 nextrandom 从 HashMap中找出来。比如 curNode 和 curNode.next,它们都在 HashMap 中存放了克隆的节点,于是第二遍复制时把 curNode.next 的克隆节点连接到 curNode 的克隆节点后面即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public Node copyRandomList(Node head) {
// 先创建一个链表,用Map映射当前的node和新的node
Map<Node, Node> map = new HashMap<>();
// 遍历链表,将原节点作为key,拷贝节点作为value保存在map中
Node curNode = head;
while (curNode != null) {
map.put(curNode, new Node(curNode.val));
curNode = curNode.next;
}
// 复制链表
curNode = head;
while (curNode != null) {
map.get(curNode).next = map.get(curNode.next);
map.get(curNode).random = map.get(curNode.random);
curNode = curNode.next;
}
return map.get(head);
}

3、栈和队列

  • 熟悉栈的使用场景
    • 后入先出,保存临时值
    • 利用栈DFS深度搜索
  • 熟悉队列的使用场景
    • 利用队列BFS广度搜索

155. 最小栈

最小栈

用链表来模拟队列,栈顶元素为链表头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MinStack {

/** initialize your data structure here. */
// 用链表来模拟队列,栈顶元素为链表头
private Node head;
public MinStack() {}

public void push(int x) {
if (head == null) {
head = new Node(x, x);
} else {
head = new Node(x, Math.min(x, head.min), head);
}
}

public void pop() {
head = head.next;
}

public int top() {
return head.val;
}

public int getMin() {
return head.min;
}
class Node {
int val;
int min;
Node next;
Node(int val, int min) {
this.val = val;
this.min = min;
this.next = null;
}
Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}

150. 逆波兰表达式求值

逆波兰表达式求值

输入: [“2”, “1”, “+”, “3”, “*”]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

思路:
通过栈保存原来的元素,遇到表达式弹出运算,再推入结果,重复这个过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int evalRPN(String[] tokens) {
int left, right;//left放左操作数,right放右操作数
//依次遍历逆波兰式字符串,数字进栈,运算符,从栈中弹俩次
for (int i = 0; i < tokens.length; i++) {
String str = tokens[i];
//按照*/+-的优先级顺序
if (str.equals("*")) {
right = stack.pop();
left = stack.pop();
stack.push(left * right);//新运算数入栈
} else if (str.equals("/")) {
right = stack.pop();
left = stack.pop();
stack.push(left / right);//新操作数入栈
} else if (str.equals("+")) {
right = stack.pop();
left = stack.pop();
stack.push(left + right);//新操作数入栈
} else if (str.equals("-")) {
right = stack.pop();
left = stack.pop();
stack.push(left - right);//新操作数入栈
} else {
stack.push(Integer.valueOf(str));
}
}
return stack.pop();
}
}

394. 字符串解码

字符串解码

辅助栈,双栈

遇到左括号将数字存数字存到数字栈,字符串存到字符串栈,保存信息;遇到右括号数字栈取出数字 k ,重复复制当前的子字符串 k 次,再与字符串栈中的字符串合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public String decodeString(String s) {
Stack<Integer> stackMulti = new Stack<Integer>();
Stack<String> stackStr = new Stack<String>();
int multi = 0;
String res = new String();
for (Character c : s.toCharArray()) {
if (c == '[') {
// 左括号,将左括号左边的字符串存到字符串栈,把数字存到数字栈
stackMulti.push(multi);
stackStr.push(res);
multi = 0;
res = new String();
} else if (c == ']') {
// 右括号,数字栈取出一个数字k,重复当前子字符串k次,完成本轮解码
// 并于之前的子字符串合并,如"3[a2[c]]",比如本轮是完成"2[c]"
// 那么于之前的子字符串合并后就是"acc"
int k = stackMulti.pop();
String tempStr = new String();
for (int i = 0; i < k; i++) {
tempStr += res;
}
res = stackStr.pop() + tempStr;
} else if (Character.isDigit(c)) {
multi = multi * 10 + Integer.parseInt(c + "");
} else {
res += c;
}
}
return res;
}
}

94. 二叉树的中序遍历

二叉树的中序遍历

利用栈实现 ,先找到二叉树的最左叶子节点对其访问,然后退回上一个节点访问,如果有右子树则对其右子树同样地进行找到最左叶子节点操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> output = new LinkedList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode tempNode = root;
while (tempNode != null || !stack.isEmpty()) {
while (tempNode != null) {
stack.push(tempNode);
tempNode = tempNode.left;
}
tempNode = stack.pop();
output.add(tempNode.val);
tempNode = tempNode.right;
}
return output;
}
}

133. 克隆图

克隆图

给你无向连通图中一个节点的引用,请你返回该图的深拷贝(克隆)。

和138. 复制带随机指针的链表同理,利用hashMap保存克隆出来的节点,通过遍历的方式进行复制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private HashMap <Node, Node> visited = new HashMap <> ();
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}

// 如果该节点已经被访问过了,则直接从哈希表中取出对应的克隆节点返回
if (visited.containsKey(node)) {
return visited.get(node);
}

// 克隆节点,注意到为了深拷贝我们不会克隆它的邻居的列表
Node cloneNode = new Node(node.val, new ArrayList());
// 哈希表存储
visited.put(node, cloneNode);

// 遍历该节点的邻居并更新克隆节点的邻居列表
for (Node neighbor: node.neighbors) {
cloneNode.neighbors.add(cloneGraph(neighbor));
}
return cloneNode;
}
}

200. 岛屿数量(岛屿类问题通解)

岛屿数量

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public int numIslands(char[][] grid) {
int numIslands = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') {
numIslands++;
dfs(grid, r, c);
}
}
}
return numIslands;
}

void dfs(char[][] grid, int r, int c) {
// base case
if (!inArea(grid, r, c)) {
return;
}
// 如果不是岛屿
if (grid[r][c] != '1') {
return;
}
// 标记已经遍历过
grid[r][c] = '2';

dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}

boolean inArea(char[][] grid, int r, int c) {
return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}
}

岛屿类问题代码模板: 参考链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int[][] grid, int r, int c) {
// 判断 base case
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿,直接返回
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 将格子标记为「已遍历过」

// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}

84. 柱状图中最大的矩形(单调栈)

柱状图中最大的矩形

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。

暴力: 遍历数组,以当前 heights[i] 为高度从左往右寻找连续的高度大于等于 heights[i] 的序列,计算其面积并与 maxArea 比较,更新 maxArea

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
for (int i = 0; i < heights.length; i++) {
int width = 1;
for (int j = i + 1; j < heights.length; j++) {
if (heights[j] >= heights[i]) {
width++;
} else {
break;
}
}
for (int j = i - 1; j >= 0; j--) {
if (heights[j] >= heights[i]) {
width++;
} else {
break;
}
}
if (heights[i] * width > maxArea) {
maxArea = heights[i] * width;
}
}
return maxArea;
}
}

单调栈: 参考1参考2

维护一个单调增栈,为了便于计算面积,在原始数组的前后都添加一个0高度的柱子。

当第 i 个柱子进栈时,如果栈顶柱子(标记为 A )的高度低于或等于第 i 个柱子,则第 i 个柱子进栈;如果高于第 i 个柱子,则出栈,并计算以柱子 A 为高的矩形最大面积。

  • 高度 height:柱子 A 的高度;
  • 右边沿:正好是 i ,由于单调栈的性质,第 i 个柱子就是右边第一个矮于 A 的柱子;
  • 左边沿:单调栈中紧邻 A 的柱子(如果 A 已经出栈,那么左边沿就是 A 出栈后的栈顶);
  • 宽度 width右边沿 - 左边沿 - 1​

我们遍历每个柱体,若当前的柱体高度大于等于栈顶柱体的高度,就直接将当前柱体入栈,否则若当前的柱体高度小于栈顶柱体的高度,说明当前栈顶柱体找到了右边的第一个小于自身的柱体,那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了(且这个过程在 while 语句块中,会一直计算到柱子 i 前面比它矮的柱子)。

因此每次出栈后去更新矩形最大面积 maxArea = Math.max(maxArea, height * width); ,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> monotonicalStack = new Stack<Integer>();
int maxArea = 0;
// 原始数组前后添加高度为0的柱子
int[] newHeights = new int[heights.length + 2];
newHeights[0] = 0;
for (int i = 0; i < heights.length; i++) {
newHeights[i + 1] = heights[i];
}
newHeights[heights.length + 1] = 0;
// 维护单调栈
for (int i = 0; i < newHeights.length; i++) {
while (!monotonicalStack.isEmpty() && newHeights[i] < newHeights[monotonicalStack.peek()]) {
int height = newHeights[monotonicalStack.pop()];
int width = i - monotonicalStack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
monotonicalStack.push(i);
}
return maxArea;
}
}

单调栈模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] dailyTemperatures(int[] nums) {
// 存放答案的数组
int[] ans = new int[nums.length];
// 单调栈
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
// 比较个子高矮
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
// 满足出栈条件
stack.pop();
}
// 进栈
stack.push(i);
}
return ans;
}

类似题目739. 每日温度 - 力扣(LeetCode) (leetcode-cn.com)496. 下一个更大元素 I - 力扣(LeetCode) (leetcode-cn.com)42. 接雨水 - 力扣(LeetCode) (leetcode-cn.com)

232. 用栈实现队列

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(pushpoppeekempty)。

创建两个栈,栈A作为输入栈,栈B作为输出栈,用栈A和栈B实现先入先出队列。假设一组升序序列进入队列中,栈A中的元素从栈顶到栈底时逆序的,栈B中的元素从栈顶到栈底时正序的。(可以自己画图理解)

  • 入队 push:直接压入栈A;
  • 出队 pop:如果栈B为空,那么将栈A全部弹出压入栈B中,然后栈 B.pop();如果栈B不为空,直接栈 B.pop()
  • 队列顶端元素 peek:如果栈B为空,那么将栈A全部弹出压入栈B中,然后栈 B.peek();如果栈B不为空,直接栈 B.peek()
  • 队列是否为空 empty:当栈A和栈B都为空时,队列为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class MyQueue {
Stack<Integer> stackA; // 输入栈
Stack<Integer> stackB; // 输出栈

/** Initialize your data structure here. */
public MyQueue() {
stackA = new Stack<Integer>();
stackB = new Stack<Integer>();
}

/** Push element x to the back of queue. */
public void push(int x) {
stackA.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
// 如果b栈为空,则将a栈全部弹出并压入b栈中,然后b.pop()
if (stackB.isEmpty()) {
while (!stackA.isEmpty()) {
stackB.push(stackA.pop());
}
}
return stackB.pop();
}

/** Get the front element. */
public int peek() {
if (stackB.isEmpty()) {
while(!stackA.isEmpty()) {
stackB.push(stackA.pop());
}
}
return stackB.peek();
}

/** Returns whether the queue is empty. */
public boolean empty() {
return stackA.isEmpty() && stackB.isEmpty();
}
}

542. 01 矩阵(多源BFS问题)

01 矩阵

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。

寻找到最近的 0 的距离,转换到每个 0 元素到周围 1 的距离问题。

多源BFS: 首先把每个 0 入队,向周围扩散寻找 1,找到后记录走过的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public int[][] updateMatrix(int[][] matrix) {
// 上下左右
int[][] direction = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
int m = matrix.length, n = matrix[0].length;
// 首先将所有的 0 都入队,并且将 0 的位置设置成true,表示该位置是被访问过的
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<int[]>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
visited[i][j] = true;
queue.offer(new int[] {i, j});
}
}
}
// BFS
int distance = 1;
while (!queue.isEmpty()) {
int count = queue.size();
while (count > 0) {
int[] temp = queue.poll();
for (int i = 0; i < 4; i++) {
int x = temp[0] + direction[i][0];
int y = temp[1] + direction[i][1];
if (0 <= x && x < m && 0 <= y && y < n && !visited[x][y]) {
matrix[x][y] = distance;
visited[x][y] = true;
queue.offer(new int[] {x, y});
}
}
count--;
}
distance++;
}
return matrix;
}
}

4、二进制

常见二进制操作

异或 ^

1
2
a = 0 ^ a = a ^ 0
0 = a ^ a

由上可以推导出: a = a ^ b ^ b ,即相等的两个数异或值为0。

交换两个数

1
2
3
a = a ^ b
b = a ^ b
a = a ^ b

按位与 &

移除最后一个1

1
a = n & (n - 1)

获取最后一个1

1
diff = (n & (n - 1)) ^ n

136. 只出现一次的数字

只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

利用位运算的异或操作,两个相同的数字异或结果是0。因为整个数组只有一个元素只出现了一次,那么对整个数组进行异或操作,最后的答案就是只出现了一次的那个元素。

1
2
3
4
5
6
7
8
9
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res = res ^ num;
}
return res;
}
}

137. 只出现一次的数字 II

只出现一次的数字 II

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

按位求和

图片取自leetcode,把数的二进制每一位相加,然后对其每一位的和取余。

1607143013-YeZWjn-file_1607143013476.png

其他数字都出现了 3 次,只有目标数出现 1 次,那么每一位的 1的个数无非两种情况:

  • 3 的倍数(全为出现3次的数)
  • 3 的倍数 +1(包含出现一次的数)

这个 3 的倍数 +1 的情况就是我们目标数所在的那一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
// 统计第 i 位是 1 的数字的个数
for (int num : nums) {
if ((num >> i & 0x01) == 0x01) {
count++;
}
}
// 当取余为 1 的情况时,说明目标数在该位有 1
if (count % 3 == 1) {
res |= 1 << i;
}
}
return res;
}
}

位运算——卡诺图

如果能设计一个状态转换电路,使得一个数出现 3 次时能自动抵消为 0,最后剩下的就是只出现 1 次的数。

列出状态转移矩阵,由于无法直接观察得出所需执行操作的具体形式,画出卡诺图确定转移方程。

位运算——真值表达式

列出真值表,写出所需的真值表达式。

1
2
3
4
5
6
7
8
9
10
class Solution {
public int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int x : nums) {
b = ~a & (x ^ b);
a = ~b & (x ^ a);
}
return b;
}
}

260. 只出现一次的数字 III

只出现一次的数字 III

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

建立一个值到频率的映射关系的哈希表,返回频率为 1 的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int[] singleNumber(int[] nums) {
Map<Integer, Integer> hashmap = new HashMap();
for (int n : nums)
hashmap.put(n, hashmap.getOrDefault(n, 0) + 1);

int[] output = new int[2];
int idx = 0;
for (Map.Entry<Integer, Integer> item : hashmap.entrySet())
if (item.getValue() == 1) output[idx++] = item.getKey();

return output;
}

解法2

将问题转换成为“有一个数组每个数字都出现两次,有一个数字只出现了一次,求出该数字”。

将所有数字分成两组,使得:

  1. 两个只出现一次的数字在不同的组中
  2. 相同的数字会被分到相同的组中

记两个只出现了一次的数字为 a 和 b,那么所有数字异或的结果 xor 就等于 a 和 b 异或的结果。

我们知道,异或运算相同的两个数结果为 0,那么取 xor 的最后一个 1 (记 mask = xor ^ (xor & (xor - 1)),它表示数字 a 和 b 在这一位上一定不相同,据此我们就可以把所有数字分成两组。

  • 在 xor 的最后一个 1 上边,表示 a 和 b 在该位上不相等,那么可以根据这个点将 a 和 b 分到不同组中
  • 两个相同的数字的对应位都应该是相同的,一个被分到了某个组,另一个必然也被分到这一组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int n : nums) {
xor ^= n;
}
int mask = xor ^ (xor & (xor - 1));
int[] result = new int[2];
for (int n : nums) {
if ((mask & n) == 0) {
result[0] ^= n;
} else {
result[1] ^= n;
}
}
return result;
}
}

191. 位1的个数

位1的个数

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。java 没有无符号整数类型。

掩码 ,利用掩码挨位判断是否为 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int num = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
if ((n & mask << i) != 0) {
num++;
System.out.println(n & mask << i);
}
}
return num;
}
}

获取最后一个1

利用 n & (n-1) 反转 n 的最后一个 1。

假设 n = 0110 那么 n - 1 = 0101,此时 n & (n-1) = 0100,可以看到成功抹掉了最后一个 1。那么我们重复这个过程,直到 n = 0 停止,统计重复了多少次即可得出 n 有多少个 1。

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int num = 0;
while (n != 0) {
num++;
n = n & (n-1);
}
return num;
}
}

338. 比特位计数

比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

可以看作是 191 的续,对每个数字都求一次就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int[] countBits(int num) {
int[] res = new int[num + 1];
for (int i = 0; i < num + 1; i++) {
res[i] = hammingWeight(i);
}
return res;
}

public int hammingWeight(int n) {
int num = 0;
while (n != 0) {
num++;
n = n & (n - 1);
}
return num;
}
}

动态规划 待完善

190. 颠倒二进制位

颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

用一个变量 res 去存储结果,依次得到要转换数字的低位,然后依次保存到 res 中。res 每得到一位后进行左移腾出位置保存下一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int res = 0;
int count = 0;
while (count < 32) {
res <<= 1; //res 左移一位空出位置
res |= (n & 1); //得到的最低位加过来
n >>= 1;//原数字右移一位去掉已经处理过的最低位
count++;
}
return res;
}
}

分治

我们知道逆序一组数字 1,2,3,4,可以先 1,22,13,4 逆序为 4,3 得到 2,1,4,3,然后再把 2,13,4 逆序,得到原序列的逆序 4,3,2,1

32位的二进制位也是同理,可以被分为如下图所示的顺序:

image.png

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
n = (n >>> 16) | (n << 16);
n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
return n;
}
}

Integer自带的reverse函数 ,具体可以看这篇文章的分析。

1
2
3
4
5
6
7
8
public static int reverse(int i) {
i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
i = (i << 24) | ((i & 0xff00) << 8) |
((i >>> 8) & 0xff00) | (i >>> 24);
return i;
}

5、二分搜索

二分搜索模板

给定一个有序数组和目标值,找到第一次/最后一次/任何一次出现的索引,如果没有出现返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int binarySearch(int[] nums, int target) {
int mid, left = 0, right = nums.length - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (target == nums[mid]) {
return mid;
} else if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}

mid = left + (right-left)/2 可以防止 left+right 溢出(超出整数范围)。

704. 二分查找

二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int search(int[] nums, int target) {
int mid, left = 0, right = nums.length - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (target == nums[mid]) {
return mid;
} else if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}

}

35. 搜索插入位置

搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int searchInsert(int[] nums, int target) {
int mid, left = 0, right = nums.length - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (target == nums[mid]) {
return mid;
} else if (target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}

74. 搜索二维矩阵

搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

把 $m * n$ 的二维矩阵看作是一个长度为 $m * n$ 的数组,数组中的第 mid 个元素在二维矩阵中的位置是:

  • 行:row = mid / n
  • 列:col = mid % n

于是该问题就转换为了经典的二分搜索问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int mid, left = 0, right = m * n - 1;
while (left <= right) {
mid = left + (right - left) / 2;
int row = mid / n;
int col = mid % n;
if (target == matrix[row][col]) {
return true;
} else if (target < matrix[row][col]) {
right = mid - 1;
} else {
left = mid + 1;
}
}

return false;
}
}

278. 第一个错误的版本

第一个错误的版本

二分查找,如果 isBadVersion(mid) 返回 false,那么搜索空间确定为 [mid + 1, right],如果 isBadVersion(mid) 返回 true 那么搜索空间确定为 [left, mid - 1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int mid, left = 1, right = n;
while (left <= right) {
mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}

另一个模板

isBadVersion(mid) 返回 false,因此我们知道 mid 左侧(包括自身)的所有版本都是正确的。所以我们令 left = mid +1,把下一次的搜索空间变为 [mid + 1, right]。

isBadVersion(mid) 返回 true,因此我们知道 mid 右侧(不包括自身)的所有版本都不可能是第一个错误的版本。所以我们令 right = mid,把下一次的搜索空间变为 [left, mid]。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

153. 寻找旋转排序数组中的最小值

寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

充分利用升序排序的特点。

需要注意的是为什么比较 midright 而不比较 midleft

因为这是旋转前升序排列的数,左边小,右边大。我们要找的是最小值,肯定是偏向左找,目标值右边的情况会比较简单,容易区分,所以比较 midright 而不比较 midleft

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1; /* 左闭右闭区间,如果用右开区间则不方便判断右值 */
while (left < right) { /* 循环不变式,如果left == right,则循环结束 */
int mid = left + (right - left) / 2; /* 地板除,mid更靠近left */
if (nums[mid] > nums[right]) { /* 中值 > 右值,最小值在右半边,收缩左边界 */
left = mid + 1; /* 因为中值 > 右值,中值肯定不是最小值,左边界可以跨过mid */
} else if (nums[mid] < nums[right]) { /* 明确中值 < 右值,最小值在左半边,收缩右边界 */
right = mid; /* 因为中值 < 右值,中值也可能是最小值,右边界只能取到mid处 */
}
}
return nums[left]; /* 循环结束,left == right,最小值输出nums[left]或nums[right]均可 */
}
};

154. 寻找旋转排序数组中的最小值 II

寻找旋转排序数组中的最小值 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

二分法,不断缩小搜索空间。

需要注意的是为什么比较 midright 而不比较 midleft

因为这是旋转前升序排列的数,左边小,右边大。我们要找的是最小值,肯定是偏向左找,目标值右边的情况会比较简单,容易区分,所以比较 midright 而不比较 midleft

且因为有可能重复,所以重复的情况采用 right--,因为是升序的, right > left

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int findMin(int[] nums) {
int mid = 0, left = 0, right = nums.length - 1;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right--;
}
}
return nums[left];
}
}

33. 搜索旋转排序数组

搜索旋转排序数组

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。

请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

最先想到的 和 153 题类似,于是套用相似思想,进行模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public int search(int[] nums, int target) {
int mid, left = 0, right = nums.length - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (target == nums[mid]) {
return mid;
}
if (target == nums[left]) {
return left;
}
if (target == nums[right]) {
return right;
}
if (nums[left] < nums[mid]) {
// [left, mid] 升序,[mid + 1, right] 存在最小值
if (target < nums[mid]) {
// target 可能存在于 mid 的左右两边
if (target > nums[left]) {
// target 在 [left + 1, mid - 1]
left++;
right = mid - 1;
} else if (target < nums[left]){
// target 在 [mid + 1, right]
left = mid + 1;
} else {
// target == nums[left]
return left;
}
} else {
// target > nums[mid]
// target 可能存在于 [mid + 1, right]
left = mid + 1;
}
} else {
// nums[left] >= nums[mid]
// [mid, right] 升序,[left, mid] 存在最小值
if (target < nums[mid]) {
// target 可能在[left, mid - 1]
right = mid - 1;
} else {
// target > nums[mid]
// target 在 mid 左右都可能
if (target > nums[left]) {
// target 在 [left + 1, mid - 1]
left++;
right = mid - 1;
} else if (target < nums[left]) {
// target 在 [mid + 1, right]
left = mid + 1;
} else {
// target == nums[left]
return left;
}
}
}
}
return -1;
}
}

简洁版本 先确定 mid 和左段、右端的关系,接下来再判断 target 在 mid 的左边还是右边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public int search(int[] nums, int target) {
int mid, left = 0, right = nums.length - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (target == nums[mid]) {
return mid;
}
if (target == nums[left]) {
return left;
}
if (target == nums[right]) {
return right;
}
if (nums[left] < nums[mid]) {
// [left, mid] 升序,[mid + 1, right] 存在最小值
if (target > nums[left] && target < nums[mid]) {
// 说明 target 在 [left + 1, mid - 1]
right = mid - 1;
} else {
// target > nums[left] && target > nums[mid] ==> target 在 [mid + 1, right]
// target < nums[left] && target < nums[mid] ==> target 在 [mid + 1, right]
// target < nums[left] && target > nums[mid] ==> target 在 [mid + 1, right]
left = mid + 1;
}
} else {
// nums[left] > nums[mid]
// [mid, right] 升序,
if (target < nums[right] && target > nums[mid]) {
// 说明 target 在 [mid + 1, right - 1]
left = mid + 1;
} else {
// target < nums[right] && target < nums[mid] ==> target 在 [left, mid - 1]
// target > nums[right] && target < nums[mid] ==> target 在 [left, mid - 1]
// target > nums[right] && target > nums[mid] ==> target 在 [left, mid - 1]
right = mid - 1;
}
}
}
return -1;
}
}

81. 搜索旋转排序数组 II

搜索旋转排序数组 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。

思路

  • 第一类

    1011111101 这种。此种情况下 nums[left] == nums[right],分不清到底前面有序还是后面有序,此时 left++ 进行处理。相当于去掉了一个重复的干扰项。

  • 第二类

    2345671 这种,也就是 num[left] < nums[right],即 2 < 5,这种情况下前半部分有序。因此如果 nums[left] < target < nums[mid],则在前半部分找,否则去后半部分找。

  • 第三类

    6712345 这种,也就是 nums[left] > nums[mid],即 6 > 2,这种情况下,后半部分有序。因此如果 nums[mid] < target < nums[right],则在后半部分找,否则去前半部分找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public boolean search(int[] nums, int target) {
int mid, left = 0, right = nums.length - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (target == nums[mid]) {
return true;
}
if (target == nums[left]) {
return true;
}
if (target == nums[right]) {
return true;
}

if (nums[mid] < nums[left]) {
// [mid, right] 升序
if (target > nums[mid] && target < nums[right]) {
// target 在 [mid + 1, right]
left = mid + 1;
} else {
// target > nums[mid] && target > nums[right] ==> target 在 [left, mid - 1]
// target < nums[mid] ==> target 在 [left, mid - 1]
right = mid - 1;
}
} else if (nums[mid] > nums[left]) {
// [left, mid] 升序
if (target < nums[mid] && target > nums[left]) {
// target 在 [left, mid - 1]
right = mid - 1;
} else {
// target < nums[mid] && target < nums[left] ==> target 在 [mid + 1, right]
// target > nums[mid] ==> target 在 [mid + 1, right]
left = mid + 1;
}
} else {
// left == mid,left 可以排除
left++;
}
}
return false;
}
}

6、排序算法

十大经典排序算法

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static void mergeSort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, end, mid);
}
public static void merge(int[] array, int start, int end, int mid) {
int[] temp = new int[end - start + 1];
int p1 = start;
int p2 = mid + 1;
int k = 0;
while (p1 <= mid && p2 <= end) {
if (array[p1] < array[p2]) {
temp[k++] = array[p1++];
} else {
temp[k++] = array[p2++];
}
}
while (p1 <= mid) {
temp[k++] = array[p1++];
}
while (p2 <= end) {
temp[k++] = array[p2++];
}
for (int i = start; i <= end; i++) {
array[i] = temp[i - start];
}
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.Arrays;
public class Demo {
public static void main(String[] args) {
int[] array = {7, 6, 5, 3, 4, 2, 1};
heapSort(array);
System.out.println(Arrays.toString(array));
}

public static void heapSort(int[] array) {
// 1.构建大根堆
for (int i = array.length / 2 - 1; i >= 0; i--) {
// 从第一个非叶子结点开始,从下至上,从右至左调整结构
adjustHeap(array, i, array.length);
}
// 2.调整堆结构+交换堆顶元素与堆尾元素
for (int i = array.length - 1; i >= 0; i--) {
// 交换堆顶元素和堆尾元素
swap(array, 0, i);
// 重新对堆进行调整
adjustHeap(array, 0, i);
}
}

/**
* 调整大顶堆,仅仅在已经创建好的基础上,对第i个元素进行调整
*
* @param array
* @param i
* @param length
*/
public static void adjustHeap(int[] array, int i, int length) {
// 1.取出当前元素
int temp = array[i];
// 2.从第i个节点的左子节点开始,即第2*i+1处开始
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
// 如果右子节点大于左子节点,k指向右子节点
if (k + 1 < length && array[k] < array[k + 1]) {
k++;
}
// 如果子节点的值大于父节点,将子节点的值赋给父节点
if (array[k] > temp) {
array[i] = array[k];
i = k;
}
}
// 将temp放置到最终的位置
array[i] = temp;
}

public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}

7、动态规划

下面是矩阵dp

120. 三角形最小路径和

三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

自底向上 自底向上的优势是①可以规避边界问题,②出口 dp[0] 就是最终答案。

假设dp[i][j] 表示第 i 层第 j 个元素开始向下的最小路径和,那么有

dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]​

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[][] dp = new int[n + 1][n + 1];
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
}
}
return dp[0][0];
}
}

空间优化复杂度O(N)

在实际地推中,计算 dp[i][j] 只用到了 dp[i+1][j]dp[i+1][j+1],因此 dp 数组不需要定义成 N 行,只需要定义一行就够了。

在计算最底层 [4,1,8,3] 的时候,计算结果是

image.png

然后在计算上一层 [6,5,7] 的时候,当计算到 6 时我们只需要用到 dp[0]dp[1],然后将计算出来的结果更新到 dp[0]

image45505e2ffbc71442.png

计算 5 的时候,需要用到 dp[1]dp[2],然后将计算出来的结果更新到 dp[1]

可见,我们将空间优化到一维数组是完全可行的,每一行计算的时候更新一次 dp 数组。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n + 1];
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}

64. 最小路径和

最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

**说明:**每次只能向下或者向右移动一步。

在左边和上边添 0

1
2
3
4
0 0 0 0 
0 1 3 1
0 1 5 1
0 4 2 1

方便 dp 数组初始化。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int minPathSum(int[][] grid) {
int n = grid.length, m = grid[0].length;
int[][] dp = new int[n + 1][m + 1];
for (int row = 1; row <= n; row++) {
for (int col = 1; col <= m; col++) {
if (row == 1) {
// 第一行只能是往右走得到的最小路径和
dp[row][col] = dp[row][col - 1] + grid[row - 1][col - 1];
} else if (col == 1) {
// 第一列只能是往下走得到的最小路径和
dp[row][col] = dp[row - 1][col] + grid[row - 1][col - 1];
} else {
dp[row][col] = Math.min(dp[row - 1][col], dp[row][col - 1]) + grid[row - 1][col - 1];
}
}
}
return dp[n][m];
}
}

62. 不同路径

不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];

// 第一行都只能从左边过来,所以只有一条路
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
// 第一列都只能从上边过来,所以只有一条路
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}

// dp[row][col] 可以来自它的左边或者是上边,所以它的路径等于左边的路径与上边的路径之和
// dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
for (int row = 1; row < m; row++) {
for (int col = 1; col < n; col++) {
dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
}
}
return dp[m - 1][n -1];
}
}

63. 不同路径 II【滚动数组优化空间复杂度】

不同路径 II

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

二维数组动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid[0][0] == 1) {
return 0;
}
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = 1;

// 第一行的格子,只能来自左边
// 如果当前格子有障碍物,那么它将没办法到达
// 如果当前格子没有障碍物,那么它只能从左边到达(此时依赖左边的所有格子之中有没有障碍物),所以路径数等于它左边的格子
for (int i = 1; i < n; i++) {
if (obstacleGrid[0][i] == 1) {
dp[0][i] = 0;
} else {
dp[0][i] = dp[0][i - 1];
}
}

// 第一列的格子,只能来自上边
// 如果当前格子有障碍物,那么它将没办法到达
// 如果当前格子没有障碍物,那么它只能从上边到达(此时依赖上边的所有格子之中有没有障碍物),所以路径数等于它上边的格子
for (int i = 1; i < m; i++) {
if (obstacleGrid[i][0] == 1) {
dp[i][0] = 0;
} else {
dp[i][0] = dp[i - 1][0];
}
}

// 中间的格子则来自左边或上边
// 如果有障碍物,那就没办法到达
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
}
return dp[m - 1][n - 1];
}
}

利用滚动数组优化空间复杂度

简单的理解就是让数组滚动起来,每次都使用固定的几个存储空间,来达到压缩,节省存储空间的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length, m = obstacleGrid[0].length;
int[] dp = new int[m];
dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
continue;
}
if (j - 1 >= 0 && obstacleGrid[i][j] == 0) {
dp[j] = dp[j] + dp[j - 1];
}
}
}
return dp[m - 1];
}
}

下面是序列dp

70. 爬楼梯

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

**注意:**给定 n 是一个正整数。

第 n 个台阶只能从第 n-1 或者 n-2 个上来。到第 n-1 个台阶的走法 + 第 n-2 个台阶的走法 = 到第 n 个台阶的走法,已经知道了第 1 个和第 2 个台阶的走法,一路加上去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}

if (n == 2) {
return 2;
}

int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int temp = b;
b = a + b;
a = temp;
}
return b;
}
}

55. 跳跃游戏

跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

动态规划

dp[i] 能否到达取决于 dp[0] ~ dp[i - 1] 之中有没有 nums[j] + j ≥ i 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[0] = true;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] == true && nums[j] + j >= i) {
dp[i] = true;
break;
}
}
}
return dp[n - 1];
}
}

贪心

对于每一个可以到达的位置 x,它使得 x+1,x+2,⋯,x+nums[x] 这些连续的位置都可以到达。

依次遍历数组中的每一个位置,维护最远可以到达的位置。对于当前遍历到的位置 x,如果它在最远可以到达的位置的范围内,那么我们就可以从起点通过若干次跳跃到达该位置,因此我们可以用 x + nums[x] 来更新最远可以到达的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean canJump(int[] nums) {
int longestLocation = 0, n = nums.length;
for (int i = 0; i < n; i++) {
if (i <= longestLocation) {
longestLocation = Math.max(longestLocation, i + nums[i]);
if (longestLocation >= n - 1) {
return true;
}
}
}
return false;
}
}

45. 跳跃游戏 II

跳跃游戏 II

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

动态规划

dp[i] 保存到达该位置 i 所需要的最少跳跃次数。初始 dp[0] = 0,其余位置为 Integer.MAX_VALUE

假设当前遍历到第 i 个元素,那么第 i 个元素能够跳跃到达的位置为 [i + 1, i + nums[i]],那么到达 [i + 1, i + nums[i]] 这些元素的跳跃次数为 dp[j] = Math.min(dp[j], dp[i] + 1), j = [i + 1, i + nums[i]]。即通过遍历每一个位置,来更新当前位置所能到达位置 j 处所需要的最少的跳跃次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n];

dp[0] = 0;
for (int i = 1; i < n; i++) {
dp[i] = Integer.MAX_VALUE;
}

for (int i = 0; i < n; i++) {
for (int j = i; j < n && j <= i + nums[i]; j++) {
dp[j] = Math.min(dp[j], dp[i] + 1);
}
}

return dp[n - 1];
}
}

贪心

当前所在位置为 i,选择第i个元素能到达的位置 [i + 1, i + nums[i]] 中,再跳一次能到达的最远位置。即下一个跳跃落点的位置最好是它能跳的越远越好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int step = 0, end = 0, maxPosition = 0;
// 在边界正好为最后一个位置的情况下,就没有必要再跳了
for (int i = 0; i < n - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
step++;
}
}
return step;
}
}

132. 分割回文串 II

分割回文串 II

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回符合要求的最少分割次数。

1、首先进行预处理,标记 preDp[i][j] 表示字符串子序列 [i, j] 是否是回文串;

2、动态规划:

dp[i] 表示 [0, i] 所需要的最少分割次数,假设 [0, i] 内某处 j[j, i] 是回文串,那么可以理解为在 j - 1j 处切一刀,将 [0, i] 分割为 [0, j - 1][j, i],此时可以得出状态转移方程:

dp[i] = min(dp[i], dp[j - 1] + 1),其中 dp[j - 1] 表示 [0, j - 1] 所需要的最小分割次数, +1 表示加上切的 j - 1j 处的这一刀,与 dp[i] 比较是因为这一轮会一直计算 dp[i] 的值,更新保留一个最小值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public int minCut(String s) {
int n = s.length();
boolean[][] preDp = new boolean[n][n];

for (int i = 0; i < s.length(); i++) {
prePro(preDp, s, i, i);
prePro(preDp, s, i, i + 1);
}


// dp[i] 表示 [0, i] 切割成符合要求的最少分割次数
// 当 [j, i] 是回文子串时,从 j - 1 和 j 中间切一刀分为 [0, j - 1] 和 [j, i]
// 那么 dp[i] = dp[j - 1] + 1, dp[j - 1] 表示 [0, j - 1] 切割成符合要求的最少分割次数,1 表示切 j - 1 和 j 中间的这一刀。
// 同时 dp[i] 更新时也需要和 dp[i] 本身的值作比较,找到最少的切割次数
int[] dp = new int[n];
Arrays.fill(dp, n);
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (preDp[j][i] == true) {
if (j == 0) {
dp[i] = 0;
} else{
dp[i] = Math.min(dp[i], dp[j - 1] + 1);
}
}
}
}
// System.out.println(preDp[0][1] + " " + dp[1]);
return dp[n - 1];
}

void prePro(boolean[][] preDp, String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
preDp[left][right] = true;
left--;
right++;
}
}
}

300. 最长递增子序列

最长递增子序列

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

子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

动态规划

dp[i] 表示以第 i 个元素结尾的子序列中,最长严格递增子序列的长度是 dp[i]。假设有 nums[j] < nums[i]dp[j]dp[0] ~ dp[i - 1] 中最大的一个。于是有

dp[i] = max(dp[j]) + 1,其中 0 ≤ j < inums[j] < nums[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length, maxLength = 1;
int[] dp = new int[n];

for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
}

139. 单词拆分

单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

dp[i] 表示前 i 个元素(s[0...i-1])能不能被拆分为字典中出现的单词。

假设当前已经知道了 dp[0]、dp[1]、...、dp[i-2] 的情况,现在遍历到第 i 个元素的时候有:

存在第 j 个元素(0 ≤ j < i),dp[i] = dp[j] && check(s[j...i - 1]),遍历所有 j 可能的取值,当能够被拆分时退出遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];

dp[0] = true;

for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (wordDict.contains(s.substring(j, i)) && dp[j]) {
dp[i] = true;
break;
}
}
}

return dp[n];
}

}

下面时双序列DP

1143. 最长公共子序列

最长公共子序列

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

遍历两个字符串:
1、若 当前两个字符 相等:
当前状态 = 两个元素的前一个状态 + 1
2、若 当前两个字符 不等:
当前状态 = 两个元素任一元素的前一个状态 的 最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length(), m = text2.length();
int[][] dp = new int[n + 1][m + 1];

dp[0][0] = 0;

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[n][m];
}
}

72. 编辑距离

编辑距离

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

插入一个字符
删除一个字符
替换一个字符

dp[i][j] 表示 word1 的前 i 个字符(word1[0, i - 1]) 转换到 word2 的前 j 个字符(word2[0, j - 1])所需要的次数。

那么状态的转移只有:

  • 插入一个字符:word1="a" word2="ab",此时需要插入一个字符 dp[i][j] = dp[i][j-1] + 1
  • 删除一个字符:word1="ab" word2="a",此时需要删除一个字符 dp[i][j] = dp[i-1][j] + 1
  • 替换一个字符:word1="ab" word2="ac",此时需要替换一个字符 dp[i][j] = dp[i-1][j-1] + 1

这三种状态的转移选择其中所需要操作次数最小的去更新 dp[i][j]

word1[i] == word2[j] 时,dp[i][j] = dp[i-1][j-1]

且需要单独考虑 word1 或者 word2 为空的情况,此时需要对不为空的字符串中的所有字符进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public int minDistance(String word1, String word2) {
// 分为增删改三个动作
// dp[i][j] 表示 word1 的前 i 个字符转换到 word2 的前 j 个字符所需要的次数
// 增:word1="a" word2="ab",此时需要插入一个字符 dp[i][j] = dp[i][j-1] + 1
// 删:word1="ab" word2="a",此时需要删除一个字符 dp[i][j] = dp[i-1][j] + 1
// 改:word1="ab" word2="ac",此时需要替换一个字符 dp[i][j] = dp[i-1][j-1] + 1
// word1 或者 word2 为空的情况单独考虑,此时需要所有元素都进行操作
// 如果word1 的第 i 个字符转换到 word2 的第 j 个字符相等,那么 dp[i][j] = dp[i-1][j-1]
int n = word1.length(), m = word2.length();


int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= m; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= n ; i++) {
for (int j = 1; j <= m; j++) {

if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
}
}
}
return dp[n][m];
}
}

背包和零钱兑换问题

322. 零钱兑换

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

你可以认为每种硬币的数量是无限的。

首先定义:

  • F(S) 是组成金额 S 所需的最少硬币数量
  • [c0...cn-1] 是可选的 n 枚硬币面额值

假设我们知道 F(S),即组成金额 S 所需最少的金币数,最后一枚硬币的面值是 C。那么可以得到转移方程:F(S) = F(S-C) + 1

但是我们不知道最后一枚硬币的面值是多少,所以我们需要枚举每个硬币面额值 c0,c1,...,cn-1 并选择其中的最小值。
$$
F(S) = min \ F(S-c_{i}) + 1 \subject \ to \ S - c_{i} \geq 0
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int coinChange(int[] coins, int amount) {
// F[S] = F[S-C] + 1
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
// i 表示金额为 i
for (int i = 1; i <= amount; i++) {
// coins[j] 表示最后一枚硬币的面额
for (int j = 0; j < coins.length; j++) {
// i >= coins[j] 能确保 i - coins[j] >= 0,数组在有效范围内
if (i >= coins[j]) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}

8、递归

将大问题转化为小问题,通过递归依次解决各个小问题。

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

两两交换链表中的节点

递归的终止条件是链表中没有节点,或者链表中只有一个节点,此时无法进行交换。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}

95. 不同的二叉搜索树 II

不同的二叉搜索树 II

给定一个整数 n,生成所有由 1 … n 为节点所组成的二叉搜索树。

利用二叉搜索树的性质,如果当前二叉搜索树的根节点是 i,那么左子树是 [1, i - 1],右子树是 [i + 1, n]。

利用递归解决问题,将大问题分解成为小问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new LinkedList<TreeNode>();
}
return generateTrees(1, n);
}

public List<TreeNode> generateTrees(int start, int end) {
List<TreeNode> allTrees = new LinkedList<TreeNode>();
if (start > end) {
allTrees.add(null);
return allTrees;
}

// 枚举可行根节点
for (int i = start; i <= end; i++) {
// 获得所有可行的左子树集合
List<TreeNode> leftTrees = generateTrees(start, i - 1);

// 获得所有可行的右子树集合
List<TreeNode> rightTrees = generateTrees(i + 1, end);

// 从左子树集合中选出一棵左子树,从右子树集合中选出一棵右子树,拼接到根节点上
for (TreeNode left : leftTrees) {
for (TreeNode right : rightTrees) {
TreeNode currTree = new TreeNode(i);
currTree.left = left;
currTree.right = right;
allTrees.add(currTree);
}
}
}
return allTrees;
}
}

509. 斐波那契数

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
}

9、滑动窗口

滑动窗口模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public void slidingWindow(String s1, String s2) {
int[] needs = new int[128];
int[] window = new int[128];

for (int i = 0; i < s1.length(); i++) {
needs[s1.charAt(i)]++;
}

int l = 0, r = 0;
int count = 0;
while (r < s2.length()) {
// ch 是将移入窗口的字符
char ch = s2.charAt(r);
// 窗口内数据更新操作
...
// 判断左侧窗口是否需要收缩
while (window needs shrink) {
// ch 是将移出窗口的字符
ch = s2.charAt(l);
// 窗口内数据更新操作
...
// 右移窗口
l++;
}
// 右移窗口
r++;
}
}

需要变化的地方

  1. 右指针右移之后窗口数据更新
  2. 判断窗口是否要收缩
  3. 左指针右移之后窗口数据更新
  4. 根据题意计算结果

76. 最小覆盖子串

最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public String minWindow(String s, String t) {
// 发现字符串的题 很多情况都是找子串问题
// 问题:如何从字符串中找到目标子串
// 滑动窗口
// 方法:整型数组存放 Char, Char 的 int 值范围为 0 ~ 127
// 利用数组 window 存放窗口中字符个数
// 利用数组 needs 存放匹配子串中需要的字符个数
int[] needs = new int[128];
int[] window = new int[128];

for (int i = 0; i < t.length(); i++) {
needs[t.charAt(i)]++;
}

int count = 0, l = 0, r = 0;
int minLength = s.length() + 1;
String res = "";

while (r < s.length()) {
char ch = s.charAt(r);
window[ch]++;
// 如果字符串 t 中有字符 ch,且当前窗口中的字符 ch 数量还不够
// 加等号是因为我们先做的 window[ch]++ 处理
if (needs[ch] > 0 && window[ch] <= needs[ch]) {
count++;
}
// 当前窗口包含了字符串 t
// 左移 l 直到不满足当前窗口包含字符串 t
while (count == t.length()) {
ch = s.charAt(l);
// 当需要删除的字符,是必须留在窗口内的
if (needs[ch] > 0 && needs[ch] == window[ch]) {
count--;
}
if ((r - l + 1) < minLength) {
minLength = r - l + 1;
res = s.substring(l, r + 1);
}
l++;
window[ch]--;
}
r++;
}
return res;
}
}

567. 字符串的排列

字符串的排列

给定两个字符串 s1s2,写一个函数来判断 s2 是否包含 s1 的排列。

滑动窗口,根据其模板修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] needs = new int[128];
int[] window = new int[128];

for (int i = 0; i < s1.length(); i++) {
needs[s1.charAt(i)]++;
}

int l = 0, r = 0;
int count = 0;
while (r < s2.length()) {
char ch = s2.charAt(r);
window[ch]++;
if (needs[ch] > 0 && window[ch] <= needs[ch]) {
count++;
}
while (count == s1.length()) {
ch = s2.charAt(l);
if (needs[ch] > 0 && needs[ch] == window[ch]) {
count--;
}
// 当符合条件的最小窗口长度等于 s1 的长度
if ((r - l + 1) == s1.length()) {
return true;
}
l++;
window[ch]--;
}
r++;
}
return false;
}
}

483. 找到字符串中所有字母异位词

找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int[] needs = new int[128];
int[] window = new int[128];

// 初始化
for (int i = 0; i < p.length(); i++) {
needs[p.charAt(i)]++;
}

int l = 0, r = 0, count = 0;
List<Integer> res = new ArrayList<Integer>();

while (r < s.length()) {
// ch 是将移入窗口的字符
char ch = s.charAt(r);

// 窗口内数据更新操作
window[ch]++;
if (needs[ch] > 0 && needs[ch] >= window[ch]) {
count++;
}

// 判断左侧窗口是否需要收缩
while (count == p.length()) {
// ch 是将移入出窗口的字符
ch = s.charAt(l);

// 窗口内数据更新操作
if (needs[ch] > 0 && needs[ch] == window[ch]) {
count--;
}
if (r - l + 1 == p.length()) {
res.add(l);
}
window[ch]--;

// 右移窗口
l++;
}

// 右移窗口
r++;
}
return res;
}
}

3、无重复字符的最长子串

无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

利用 滑动窗口 来解决这个问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] window = new int[128];

int l = 0, r = 0, count = 0;
int maxWindow = 0;

while (r < s.length()) {
// ch 是将移入窗口的字符
char ch = s.charAt(r);

// 窗口内数据更新操作
// 这里采取先 count++ 是因为,如果先 window[ch]++ 后
// 当出现重复情况时,count 少加一次
// 导致在收缩窗口的时候 count 多减了一次
if (window[ch] <= 1) {
count++;
}
window[ch]++;

// 判断左侧窗口是否需要收缩
while (window[ch] > 1) {
// ch2 是将移出窗口的字符
char ch2 = s.charAt(l);
// 窗口内数据更新操作
window[ch2]--;
count--;
// 右移窗口
l++;
}
if (count > maxWindow) {
maxWindow = count;
}
// 右移窗口
r++;
}
return maxWindow;
}
}

利用HashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合,记录每个字符是否出现过
Set<Character> set = new HashSet<Character>();
int n = s.length();
// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
int right = 0, ans = 0;
for (int left = 0; left < n; left++) {
if (left != 0) {
// 左指针向右移动一格,移除一个字符
set.remove(s.charAt(left - 1));
}
while (right < n && !set.contains(s.charAt(right))) {
// 不断地移动右指针
set.add(s.charAt(right));
right++;
}
// 第 k 到 j 个字符是一个极长的无重复字符子串
ans = Math.max(ans, set.size());
}
return ans;
}
}

10、回溯法

回溯法(backtrack)常用于遍历列表所有子集,是 DFS 深度搜索一种,一般用于全排列,穷尽所有可能,遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 $O(N!)$,它不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高。

回溯就是类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

回溯法模板

1
2
3
4
5
6
7
8
9
10
result = []
void backtrack(选择列表,路径):
if (满足结束条件):
result.add(路径);
return;
for 选择 in 选择列表:
做选择;
backtrack(选择列表,路径);
撤销选择;
backtrack(选择列表,路径);

做选择的时候,找子集从 i 开始 for 循环,找排列组合从 0 开始 for 循环。

总结:回溯类题一定要考虑的几个方面

  • 有效结果:当长度为输入长度的时候停止,并保存当前结果
  • 回溯条件:每一层都是全部元素遍历
  • 剪枝条件:要用check数组来保存用过的元素,用过的不能再用了,这是回溯里面的一个重要考虑因素

78. 子集

子集

给你一个整数数组 nums ,返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。

方法一: 逐个枚举,空集的幂集只有空集,每增加一个元素,让之前幂集中的每个集合,追加这个元素,就是新增的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<List<Integer>> enumerate(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
res.add(new ArrayList<Integer>());
for (Integer n : nums) {
int size = res.size();
for (int i = 0; i < size; i++) {
List<Integer> newSub = new ArrayList<Integer>(res.get(i));
newSub.add(n);
res.add(newSub);
}
}
return res;
}

方法二: 二进制位标记选取子集,枚举 $mask ∈ [0, 2^{n}-1]$ ,标记不同的位组成不同的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
for (int mask = 0; mask < (1 << nums.length); mask++) {
List newSub = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
// 比较当前位置是否要取
if ((mask & (1 << i)) != 0) {
newSub.add(nums[i]);
}
}
res.add(newSub);
}
return res;
}
}

方法三: 回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, new ArrayList<Integer>(), 0);
return res;
}

public void backtrack(int[] nums, List<Integer> list, int i) {
res.add(new ArrayList<Integer>(list));
for (int j = i; j < nums.length; j++) {
list.add(nums[j]);
backtrack(nums, list, j + 1);
list.remove(list.size() - 1);
}
}
}

90. 子集 II

子集 II

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

**说明:**解集不能包含重复的子集。

排序后,关键点在于画出递归树(排列树),然后观察如何去重:我们要去重的是同一树层上的“使用过”,同一树枝上的都是一个组合里的元素,不用去重

42618258fec183614b260c226836310c4cbd86787e143ce27285464d501ec46e-QQE688AAE59BBE20200608123027.png如果 nums[j] 是在同层的在for循环里重复出现的,那么 j 肯定大于 i,否则比较的两个元素就处于不同层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> tempList = new ArrayList<Integer>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtrack(nums, 0);
return res;
}
public void backtrack(int[] nums, int i) {
res.add(new ArrayList<Integer>(tempList));
for (int j = i; j < nums.length; j++) {
if (j > i && nums[j] == nums[j - 1]) continue;
tempList.add(nums[j]);
backtrack(nums, j + 1);
tempList.remove(tempList.size() - 1);
}
}
}

46. 全排列

全排列

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

套用回溯法模板的同时,画出递归树来完善代码逻辑,判断是否解决问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> tempList = new ArrayList<Integer>();

public List<List<Integer>> permute(int[] nums) {
backtrack(nums, 0, new boolean[nums.length]);
return res;
}

public void backtrack(int[] nums, int i, boolean[] visited) {
if (i == nums.length) {
res.add(new ArrayList<Integer>(tempList));
return;
}
for (int j = 0; j < nums.length; j++) {
if (visited[j] == true) {
continue;
}
visited[j] = true;
tempList.add(nums[j]);
backtrack(nums, i + 1, visited);
visited[j] = false;
tempList.remove(tempList.size() - 1);
}
}
}

47. 全排列 II

全排列 II

给定一个可包含重复数字的序列 nums按任意顺序 返回所有不重复的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> tempList = new ArrayList<Integer>();
public List<List<Integer>> permuteUnique(int[] nums) {
backtrack(nums, 0, new boolean[nums.length]);
return res;
}

public void backtrack(int[] nums, int i, boolean[] visited) {
if (i == nums.length) {
res.add(new ArrayList<Integer>(tempList));
return;
}
// start[] 数组用于去重
boolean[] start = new boolean[22];
for (int j = 0; j < nums.length; j++) {
if (visited[j] == true || start[nums[j] + 10] == true) {
continue;
}
visited[j] = true;
start[nums[j] + 10] = true;
tempList.add(nums[j]);
backtrack(nums, i + 1, visited);
visited[j] = false;
tempList.remove(tempList.size() - 1);
}
}
}

39. 组合总数

组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

如何限制不产生重复组合?

只要限制下一次选择的起点,是基于本次的选择,这样下一次就不会选到本次选择的同层左边的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> tempList = new ArrayList<Integer>();

public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtrack(candidates, 0, 0, target);
return res;
}

public void backtrack(int[] candidates, int start, int sum, int target) {
if (sum == target) {
res.add(new ArrayList<Integer>(tempList));
return;
}
for (int i = start; i < candidates.length; i++) {
if (sum + candidates[i] > target) {
continue;
}
tempList.add(candidates[i]);
// i 从 start 开始是因为元素可以重复选择
// 且能够限制下一层递归是从当前元素开始,不会出现重复选择之前的元素,造成解集重复
backtrack(candidates, i, sum + candidates[i], target);
tempList.remove(tempList.size() - 1);
}
}
}

17. 电话号码的字母组合

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

回溯法穷举所有可能的组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
char[][] dict = {
{'a', 'b', 'c'},
{'d', 'e', 'f'},
{'g', 'h', 'i'},
{'j', 'k', 'l'},
{'m', 'n', 'o'},
{'p', 'q', 'r', 's'},
{'t', 'u', 'v'},
{'w', 'x', 'y', 'z'}
};
List<String> res = new ArrayList<String>();
StringBuffer tempString = new StringBuffer();
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return res;
}
backtrack(digits, 0);
return res;
}
void backtrack(String digits, int i) {
if (i == digits.length()) {
res.add(tempString.toString());
return;
}
// 当前数字对应对应字典的下标
int index = digits.charAt(i) - '2';
for (int j = 0; j < dict[index].length; j++) {
tempString.append(dict[index][j]);
backtrack(digits, i + 1);
tempString.deleteCharAt(i);
}
}
}

131. 分割回文串

分割回文串

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

切割问题,类似组合问题。例如对于字符串 abcdef

  • 组合问题:选取一个 a 之后,在 bcdef 中再去选取第二个,选取 b之后在 cdef 中在选组第三个…
  • 切割问题:切割一个 a 之后,在 bcdef 中再去切割第二段,切割 b 之后在 cdef 中在切割第三段…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
List<List<String>> res = new ArrayList<List<String>>();
List<String> tempList = new ArrayList<String>();
public List<List<String>> partition(String s) {
backtrack(s, 0);
return res;
}
public void backtrack(String s, int i) {
if (i == s.length()) {
res.add(new ArrayList<String>(tempList));
return;
}
// 回溯所有分割方案
// 只有当前 s[i] 到 s[j] 能够被分割成回文串才能算作一次有效分割
// 那么在此基础上,继续往后寻找可能的分割方案
for (int j = i; j < s.length(); j++) {
if (check(s.substring(i, j + 1))) {
tempList.add(s.substring(i, j + 1));
backtrack(s, j + 1);
tempList.remove(tempList.size() - 1);
}
}
}

public boolean check(String s) {
int n = s.length();
for (int i = 0; i < n / 2; i++) {
if (s.charAt(i) != s.charAt(n - 1 - i)) {
return false;
}
}
return true;
}
}

93. 复原IP地址

复原IP地址

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

同样的自己画个树形图分析问题,可以利用 IP 地址的规则来剪枝:

  • 字符串长度在 4 到 12 之间;
  • IP 地址的一个段只可能是 3 位,最大为 255;
  • 每个段只有 3 种截取方法:截 1 位、截 2 位、截 3 位;
  • 由于 IP 地址 4 个段,所以这颗树最多 4 层。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
List<String> res = new ArrayList<String>();
List<String> tempStr = new ArrayList<String>();
public List<String> restoreIpAddresses(String s) {
backtrack(s, 0, 0);
return res;
}

// index 标记现在分割到了第几段
// i 表示字符串被分割到了第几位
public void backtrack(String s, int i, int index) {
if (index > 4) {
return;
}
if (index == 4 && i == s.length()) {
StringBuffer sb = new StringBuffer();
sb.append(tempStr.get(0));
for (int k = 1; k < tempStr.size(); k++) {
sb.append("." + tempStr.get(k));
}
res.add(sb.toString());
}
// j - i <= 3 表示 IP 地址的一个整数最多是三位
for (int j = i; j - i <= 3 && j < s.length(); j++) {
if (!check(s.substring(i, j + 1))) {
continue;
}

tempStr.add(s.substring(i, j + 1));
backtrack(s, j + 1, index + 1);
tempStr.remove(tempStr.size() - 1);
}
}


public boolean check(String s) {
int n = s.length();
// 去除 0 开头的情况
if (n > 1 && s.charAt(0) == '0') {
return false;
}
int num = Integer.valueOf(s);
if (num <= 255) {
return true;
}
return false;
}
}

11、初级算法

1、数组

26. 删除排序数组中的重复项

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

使用双指针

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int removeDuplicates(int[] nums) {
int k = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[k]) {
k++;
nums[k] = nums[i];
}
}
return k + 1;
}
}

122. 买卖股票的最佳时机 II

买卖股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

贪心,观察买卖股票收益即卖出价格减去买入价格,那么每次股票收益为正时都算到收益当中,加起来就是最大收益。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length, res = 0;
int[] priceDifference = new int[n - 1];
// 每天的股价差值
for (int i = 0; i < n - 1; i++) {
priceDifference[i] = prices[i + 1] - prices[i];
}
// 把所有正的股价差相加
for (int i = 0; i < n - 1; i++) {
if (priceDifference[i] > 0) {
res += priceDifference[i];
}
}
return res;
}
}

189. 旋转数组

旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

当我们将数组的元素向右移动 k 次后,尾部 k mod n 个元素会移动至数组头部,其余元素向后移动 k mod n 个位置。

数组的翻转:我们可以先将所有元素翻转,这样尾部的 k mod n 个元素就被移至数组头部,然后我们再翻转 [0, k mod n-1] 区间的元素和 [k mod n, n-1] 区间的元素即能得到最后的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}

public void reverse(int[] nums, int l, int r) {
int temp = 0;
while (l < r) {
temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;
r--;
}
}
}

217. 存在重复元素

存在重复元素

给定一个整数数组,判断是否存在重复元素。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<Integer>(nums.length);
for (int num : nums) {
if (!set.add(num)) {
return true;
}
}
return false;
}
}

350. 两个数组的交集 II

两个数组的交集 II

给定两个数组,编写一个函数来计算它们的交集。

由于同一个数字在两个数组中都可能出现多次,因此需要用哈希表存储每个数字出现的次数。对于一个数字,其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。

为了降低空间复杂度,首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数,然后遍历较长的数组得到交集。(这里我的代码并没有去实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] res = new int[Math.max(nums1.length, nums2.length)];
int p = 0;
for (int num : nums1) {
map.put(num, map.getOrDefault(num, 0) + 1);
}

for (int num : nums2) {
Integer temp = map.get(num);
if (temp != null && temp > 0) {
res[p++] = num;
map.put(num, --temp);
}
}
return Arrays.copyOf(res, p);
}
}

283. 移动零

移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

非 0 往前挪,剩下的补 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public void moveZeroes(int[] nums) {
int k = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
k++;
} else {
nums[i - k] = nums[i];
}
}
for (int i = 1; i <= k; i++) {
nums[nums.length - i] = 0;
}
}
}

双指针

使用双指针,左指针指向当前已经处理好的序列的尾部,右指针指向待处理序列的头部。

右指针不断向右移动,每次右指针指向非零数,则将左右指针对应的数交换,同时左指针右移。

注意到以下性质:

  • 左指针左边均为非零数;
  • 右指针左边直到左指针处均为零。

因此每次交换,都是将左指针的零与右指针的非零数交换,且非零数的相对顺序并未改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
right++;
}
}

public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}

1. 两数之和

两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。

使用哈希表,可以将寻找 target - x 的时间复杂度降低到从 O*(*N) 降低到 O(1)。

这样我们创建一个哈希表,对于每一个 x,我们首先查询哈希表中是否存在 target - x,然后将 x 插入到哈希表中,即可保证不会让 x 和自己匹配。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (hashtable.containsKey(target - nums[i])) {
return new int[] {hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}

36. 有效的数独

有效的数独

判断一个 9x9 的数独是否有效。

行和列都可以一次迭代完成,如何确保能一次迭代完成枚举子数独呢?

可以使用 box = (row / 3) * 3 + col / 3,这样将 9 个子数独从左到右从上到下划分为 0 ~ 8 共 9 个子数独。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public boolean isValidSudoku(char[][] board) {
Map<Integer, Integer>[] rowMap = new HashMap[9];
Map<Integer, Integer>[] colMap = new HashMap[9];
Map<Integer, Integer>[] boxMap = new HashMap[9];
for (int i = 0; i < 9; i++) {
rowMap[i] = new HashMap<Integer, Integer>(9);
colMap[i] = new HashMap<Integer, Integer>(9);
boxMap[i] = new HashMap<Integer, Integer>(9);
}

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
continue;
}
int num = (int) board[i][j];
int box = (i / 3) * 3 + j / 3;
// 更新 map
rowMap[i].put(num, rowMap[i].getOrDefault(num, 0) + 1);
colMap[j].put(num, colMap[j].getOrDefault(num, 0) + 1);
boxMap[box].put(num, boxMap[box].getOrDefault(num, 0) + 1);
// 检查是否满足条件
if (rowMap[i].get(num) > 1 || colMap[j].get(num) > 1 || boxMap[box].get(num) > 1) {
return false;
}
}
}
return true;
}
}

48. 旋转图像

旋转图像

给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。

先以对角线(左上<—>右下)为轴进行翻转,再对每行左右翻转即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public void rotate(int[][] matrix) {
// 先以对角线(左上<—>右下)为轴进行翻转,再对每行左右翻转即可。
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = temp;
}
}
}
}

2、字符串

387.字符串中的第一个唯一字符

字符串中的第一个唯一字符

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
if (map.containsValue(1)) {
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (map.get(ch) == 1) {
return i;
}
}
}
return -1;
}
}

另解: 维护一个队列,队头一定是只出现一次的字符

242. 有效的字母异位词

有效的字母异位词

给定两个字符串 st ,编写一个函数来判断 t 是否是 s 的字母异位词。

哈希映射,更新字符出现的次数,最后遍历整个哈希表判断是否都为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public boolean isAnagram(String s, String t) {
int n = s.length(), m = t.length();
if (n != m) {
return false;
}
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < m; i++) {
char ch = t.charAt(i);
int freq = map.getOrDefault(ch, 0);
if (freq == 0) {
return false;
}
map.put(ch, freq - 1);
}
for (int freq : map.values()) {
if (freq > 0) {
return false;
}
}
return true;
}
}

125. 验证回文串

验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public boolean isPalindrome(String s) {
int n = s.length();
int l = 0, r = n - 1;
while (l < r) {
while (l < r && !Character.isLetterOrDigit(s.charAt(l))) {
l++;
}
while (l < r && !Character.isLetterOrDigit(s.charAt(r))) {
r--;
}
if (l < r) {
if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
return false;
}
l++;
r--;
}
}
return true;
}
}

38. 外观数列

外观数列

给定一个正整数 n ,输出外观数列的第 n 项。「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。

普通解法

模拟该行为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public String countAndSay(int n) {
if (n == 1) {
return "1";
}
String sub = countAndSay(n - 1);
StringBuffer sb = new StringBuffer();
char ch = sub.charAt(0);
int times = 1;
for (int i = 1; i < sub.length(); i++) {
if (sub.charAt(i) != ch) {
sb.append(times);
sb.append(ch);
ch = sub.charAt(i);
times = 1;
} else {
times++;
}
}
// 解决末尾的阶段
sb.append(times);
sb.append(ch);
return sb.toString();
}
}

优化,添加哨兵 哨兵可以使我们不用在循环外处理边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public String countAndSay(int n) {
if (n == 1) {
return "1";
}
String sub = countAndSay(n - 1);
// 添加哨兵
sub = sub + "a";
StringBuffer sb = new StringBuffer();
char ch = sub.charAt(0);
int times = 1;
for (int i = 1; i < sub.length(); i++) {
if (sub.charAt(i) != ch) {
sb.append(times);
sb.append(ch);
ch = sub.charAt(i);
times = 1;
} else {
times++;
}
}
return sb.toString();
}
}

3、链表

237. 删除链表中的节点

删除链表中的节点

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点

1
2
3
4
5
6
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}

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

删除链表的倒数第 N 个结点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 小技巧,pre的下一个指针指向head,这样遍历到需要的位置时,pre就是需要的节点的前节点
ListNode preNode = new ListNode(0, head);
ListNode curNode = preNode, tempNode = preNode;
for (int i = 0; i < n ; i++) {
curNode = curNode.next;
}
while (curNode.next != null) {
curNode = curNode.next;
tempNode = tempNode.next;
}
tempNode.next = tempNode.next.next;
// 不返回head,是因为head有可能是被删掉的节点
return preNode.next;
}
}

234. 回文链表

回文链表

请判断一个链表是否为回文链表。

用到了反转链表和快慢指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}

// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);

// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}

// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}

private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}

private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}

无序刷题

3、无重复字符的最长子串

无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

利用 滑动窗口 来解决这个问题:

  • 用两个指针left,right来分别指向滑动窗口的左端和右端,即某个字串的开始位置和结束位置;
  • 每步操作都将左指针往右挪一位,表示枚举下一个字符为起始位置,然后不断地右移右指针,但需要确保滑动窗口中没有重复字符。移动结束后,记录该窗口的长度即不含有重复字符的子串的长度;
  • 枚举结束后,找到最长的子串的长度即为答案。

判断重复字符

使用哈希集合(Java中的HashSet)来帮助我们判断是否有重复的字符。左指针右移时,从哈希集合中移除一个字符,右指针右移时,向哈希集合中添加一个字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合,记录每个字符是否出现过
Set<Character> set = new HashSet<Character>();
int n = s.length();
// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
int right = 0, ans = 0;
for (int left = 0; left < n; left++) {
if (left != 0) {
// 左指针向右移动一格,移除一个字符
set.remove(s.charAt(left - 1));
}
while (right < n && !set.contains(s.charAt(right))) {
// 不断地移动右指针
set.add(s.charAt(right));
right++;
}
// 第 k 到 j 个字符是一个极长的无重复字符子串
ans = Math.max(ans, set.size());
}
return ans;
}
}

4、寻找两个正序数组的中位数

寻找两个正序数组的中位数

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1nums2

请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

暴力解法 只需要每次取 nums1nums2 中较小的那个数,一直取到中文数的位置再进行计算即可,时间复杂度是 O(m+n),达不到题目要求。

二分查找 将问题中的求中位数,转换成为 求第k小数 的特殊情况。假设我们要找第 k 小的数,每次循环排除掉 k/2 个数。看下面的例子,比如要找第 7 小的数字。

  • $k=7,k/2=3$
  • 数组A:(1,3,4),9
  • 数组B:(1,2,3),4,5,6,7,8,9,10

比较两个数组的第 k/2 个数字(向下取整),也就是比较第 3 个数字,数组A中的 4 和数组B中的 3 ,因为 34 小,所以可以表明数组 B 的前 k/2 个数字都不是第 k 个数字。也就是说 1,2,3 这三个数字不可能是第 7 小的数字,我们可以将它们给排除掉。然后将数组 A 和排除掉前 k/2 个数字的数组 B 重新比较,直到找第 1 小的数字,只需要判断两个数组中第一个数字哪个小就可以了。

总结

  • (n+m) 为两个数组合起来的长度,那么不论奇数还是偶数,我们 求第k小的数字 都可以通过计算第$(n+m+1)/2$和$(n+m+2)/2$个数字来解决。
    • (n+m) 是偶数时,两数相加除以2即可得到中位数;
    • (n+m) 是奇数时,计算了两次中位数,也应该是两数相加除以2。
  • nums1[k/2] 小于 nums2[k/2] 时,丢掉 nums1[] 的前 k/2 个数字;
  • nums1[k/2] 大于等于 nums2[k/2] 时,丢掉 nums2[] 的前 k/2个数字;
  • 当其中一个数组的长度为 0 时,只需要求另一个数组的第 k 小的数字;
  • 当k = 1时,求两个数组第一个数字中较小的那个;
  • k/2 超过数组长度时,取数组最后一个数字即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
// 当n+m为偶数时,应该计算 (left+right)/2
// 当n+m为奇数时,计算了两次中位数,也应该是 (left+right)/2
// 于是不论是奇数还是偶数,都可以用一套代码解决
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) / 2.0;
}

public static int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;

// 确保 nums1[] 一定比 nums2[] 短
// 当有空的数组出现时,一定是 nums1[]
if(len1 > len2) {
return getKth(nums2, start2, end2, nums1, start1, end1, k);
}
if(len1 == 0) {
return nums2[start2 + k - 1];
}

if (k == 1) return Math.min(nums1[start1], nums2[start2]);

int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;

if(nums1[i] < nums2[j]) {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
} else {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
}
}

7、 整数反转

整数反转

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。比如输入 123 输出 321 ,输入 120 输出 21 ,输入 -123输 出 -321

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为$ [−2^{31}, 2^{31} − 1]$。请根据这个假设,如果反转后整数溢出那么就返回 0。

主要是注意溢出问题。重复取出 x 的最后一位数字,并将它放到 res 的后面。最后 res 将与 x 相反。

这种方法在 temp = res * 10 + pop 时会有溢出风险。我们假设 res 是一个正数。

  • 如果 temp = res * 10 + pop 导致溢出,那么一定有res >= INTMAX/10​
  • 如果res > INTMAX / 10​,那么 temp = res * 10 + pop 一定会溢出
  • 如果res == INTMAX / 10,那么只要 pop 大于 INTMAX % 10​, temp = res * 10 + pop 就会溢出

res 为负时可以应用同样的逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int reverse(int x) {
int res = 0;
int mag = 10;
while (x != 0) {
if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && x % 10 > Integer.MAX_VALUE % 10)) {
return 0;
}
if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && x % 10 < Integer.MIN_VALUE % 10)) {
return 0;
}
res = res * mag + x % 10;
x = x / 10;
}
return res;
}
}

10. 正则表达式匹配

正则表达式匹配

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.''*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。

说明:

s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 .*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public boolean isMatch(String text, String pattern) {
// 如果都为空则匹配成功,text不空pattern空匹配失败
if (pattern.isEmpty()) {
return text.isEmpty();
}
// 第一个是否匹配上
boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

// 只有长度大于2的时候才考虑'*''
if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
// 看有没有可能,剩下的pattern匹配上全部的text
// 看有没有可能,剩下的text匹配整个pattern
// isMatch(text, pattern.substring(2)) 指当p第二个为*时,前面的字符不影响匹配所以可以忽略,所以将*以及*之前的一个字符删除后匹配之后的字符,这就是为什么用pattern.substring(2)
// pattern 直接跳过两个字符,表示 * 前边的字符出现0次
//如果第一个已经匹配成功,并且第二个字符为*时,这是我们就要判断之后的需要匹配的字符串是否是多个前面的元素(*的功能),这就是first_match && isMatch(text.substring(1), pattern))的意义
// pattern 不变,例如 text = aa,pattern = a*,第一个 a 匹配,然后 text 的第二个 a 接着和 pattern 的第一个 a 进行匹配。表示 * 用前一个字符替代
return (isMatch(text, pattern.substring(2)) || (first_match && isMatch(text.substring(1), pattern)));
} else {
// 没有星星的情况:第一个字符相等,而且剩下的text,匹配上剩下的pattern,没有星星且第一个匹配成功,那么s和p同时向右移动一位看是否仍然能匹配成功
return first_match && isMatch(text.substring(1), pattern.substring(1));
}
}
}

13. 罗马数字转整数

罗马数字转整数

罗马数字转整数,例如 "III" 转为 3"IV" 转为 4"VI" 转为 6,可以观察到如果前面的小于后面的是减法 "IV" = V - I ,前面大于后面是加法 "VI" = V + I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int romanToInt(String s) {
int sum = 0;
int preNum = getValue(s.charAt(0));
for(int i = 1;i < s.length(); i ++) {
int num = getValue(s.charAt(i));
if(preNum < num) {
sum -= preNum;
} else {
sum += preNum;
}
preNum = num;
}
sum += preNum;
return sum;
}

private int getValue(char ch) {
switch(ch) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
}

14. 最长公共前缀

最长公共前缀

纵向挨个比较

从第一个字符开始比较,遇到不相同或者某个字符串到末尾了结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) {
return "";
}
int point = 0;
while (point < strs[0].length()) {
for (int i = 1; i < strs.length; i++) {
if (point >= strs[i].length()) {
// 超出某个字符串的长度,那么以当前长度为最长公共前缀
return strs[0].substring(0, point);
}
if (strs[0].charAt(point) != strs[i].charAt(point)) {
// 如果当前位置的字符不相同,那么前面的是最长公共前缀
return strs[0].substring(0, point);
}
}
point++;
}
// 比较完了整个strs[0],它就是最长公共前缀
return strs[0];
}
}

二分查找

每次取查找范围的中间值 mid,判断每个字符串的长度为 mid 的前缀是否相同,如果相同则最长公共前缀的长度一定大于或等于 mid,如果不相同则最长公共前缀的长度一定小于 mid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
int minLength = Integer.MAX_VALUE;
for (String str : strs) {
minLength = Math.min(minLength, str.length());
}
int left = 0, right = minLength;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (isCommonPre(strs, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return strs[0].substring(0, left);
}

public static boolean isCommonPre(String[] strs, int mid) {
String commonPre = strs[0].substring(0, mid);
for (int i = 1; i < strs.length; i++) {
for (int j = 0; j < mid; j++) {
if (commonPre.charAt(j) != strs[i].charAt(j)) {
return false;
}
}
}
return true;
}
}

66. 加一

加一

给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

加一只可能出现两种情况:

  • 该位数字为 0~8,加一即可;
  • 该位数字为 9,进位并将该位置为 0

于是我们可以从数组的末尾即个位开始判断,如果不需要进位,则直接个位加 1 返回整个数组;如果需要进位则将该位置 0,接着去处理更高位,直到处理完最高位。

特殊情况如 99,处理完最高位后还需要进位,那么需要手动的进行扩充数组进位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10;
if (digits[i] != 0) {
return digits;
}
}
if (digits[0] == 0) {
digits = new int[digits.length + 1];
digits[0] = 1;
}
return digits;
}
}

334. 反转字符串

反转字符串

1
2
3
4
5
6
7
8
9
10
class Solution {
public void reverseString(char[] s) {
int n = s.length;
for (int i = 0; i < n / 2; i++) {
char temp = s[i];
s[i] = s[n - 1 - i];
s[n - 1 - i] = temp;
}
}
}

213. 打家劫舍II

打家劫舍 II

一个数组,相邻的不能同时选择,头和尾不能同时选择,求最大和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public int rob(int[] nums) {
// 总共n间房,从0开始计数,第一间和最后一间不能同时偷,转换为两个case
// 1) 不偷第一间,那么就是在 [1,n-1] 之间的最大值
// 2) 不偷最后一件,那么就是在 [0,n-2] 之间的最大值
// 状态转移方程: dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]),含义是投最后一间和不偷最后一间

if (nums.length == 1) {
return nums[0];
}
if (nums.length == 2) {
return Math.max(nums[0], nums[1]);
}
// 优化,因为整个过程中只需要用到 dp[i-1] 和 dp[i-2] 即可,因此可以优化为两个变量去记录
int n = nums.length;
// [0,n-2]
int rangeA = 0;
int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i <= n - 2; i++) {
int temp = Math.max(first + nums[i], second);
first = second;
second = temp;
}
rangeA = second;
// [1,n-1]
int rangeB = 0;
first = nums[1];
second = Math.max(nums[1], nums[2]);
for (int i = 3; i <= n - 1; i++) {
int temp = Math.max(first + nums[i], second);
first = second;
second = temp;
}
rangeB = second;
return Math.max(rangeA, rangeB);
}
}

87. 扰乱字符串

扰乱字符串

利用递归模拟这个过程,用 for 来模拟所有随机的可能。

超时代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public boolean isScramble(String s1, String s2) {
// 相等直接返回true
if (s1.equals(s2)) {
return true;
}
// 比较词频,词频不同一定不同
if (!check(s1, s2)) {
return false;
}
int length = s1.length();
for (int i = 1; i < length; i++) {
// s1 = s1[0,i) + s1[i,length)
// s2 = s2[0,i) + s2[i,length)
// 1) 保持顺序不变,那么比较 s1[0,i) && s1[i,length) 和 s2[0,i) && s2[i,length)
// 2) 交换子字符串,那么比较 s1[0,i) && s1[i,length) 和 s2[length-i,length) && s2[0,length - i)
if ((isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i, length), s2.substring(i, length)))
|| (isScramble(s1.substring(0, i), s2.substring(length - i, length)) && isScramble(s1.substring(i, length), s2.substring(0, length - i)))) {
return true;
}
}
return false;
}
public boolean check(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
Set<Character> set = new HashSet<>();
int length = s1.length();
for (int i = 0; i < length; i++) {
char a = s1.charAt(i);
char b = s2.charAt(i);
if (set.contains(a)) {
set.remove(a);
} else {
set.add(a);
}
if (set.contains(b)) {
set.remove(b);
} else {
set.add(b);
}
}
return set.isEmpty();
}
}

记忆化搜索:开辟一块内存来存储搜索结果,下次遇到直接返回结果,节约时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
// 记忆化搜索,保存每次 s1 和 s2 的比较结果
Map<String, Map<String, Boolean>> map = new HashMap<>();
public boolean isScramble(String s1, String s2) {
// 相等直接返回true
if (s1.equals(s2)) {
return true;
}
// 比较词频,词频不同一定不同
if (!check(s1, s2)) {
return false;
}
if (map.containsKey(s1) && map.get(s1).containsKey(s2)) {
return map.get(s1).get(s2);
}
int length = s1.length();
for (int i = 1; i < length; i++) {
// s1 = s1[0,i) + s1[i,length)
// s2 = s2[0,i) + s2[i,length)
// 1) 保持顺序不变,那么比较 s1[0,i) && s1[i,length) 和 s2[0,i) && s2[i,length)
// 2) 交换子字符串,那么比较 s1[0,i) && s1[i,length) 和 s2[length-i,length) && s2[0,length - i)
if ((isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i, length), s2.substring(i, length)))
|| (isScramble(s1.substring(0, i), s2.substring(length - i, length)) && isScramble(s1.substring(i, length), s2.substring(0, length - i)))) {
map.computeIfAbsent(s1, V -> new HashMap<>()).put(s2, true);
return true;
}
}
map.computeIfAbsent(s1, V -> new HashMap<>()).put(s2, false);
return false;
}
public boolean check(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
Set<Character> set = new HashSet<>();
int length = s1.length();
for (int i = 0; i < length; i++) {
char a = s1.charAt(i);
char b = s2.charAt(i);
if (set.contains(a)) {
set.remove(a);
} else {
set.add(a);
}
if (set.contains(b)) {
set.remove(b);
} else {
set.add(b);
}
}
return set.isEmpty();
}
}

220. 存在重复元素III

存在重复元素 III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 。

测试用例数字很大,所以应该考虑用 Long 来避免溢出问题。

方法1:滑动窗口 + TreeSet

滑动窗口来维护区间 [i-t, i+t]

TreeSet 支持添加和删除指定元素的操作,且内部元素有序,支持条件查找:

  • E ceiling(E e):查找是否有大于等于 e 的元素
  • E floor(E e):查找是否有小于等于 e 的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
// 集合中是否有元素的值在 [nums[i] - t, nums[i] + t] 之间
// 集合中是否有满足下界的元素
Long ceiling = set.ceiling((long)nums[i] - (long)t);
// 上界
if (ceiling != null && ceiling <= (long)nums[i] + (long)t) {
return true;
}
set.add((long)nums[i]);
// 维护滑动窗口
if (i >= k) {
set.remove((long)nums[i - k]);
}
}
return false;
}
}

方法2:桶排序

大概意思是对于数 x 来讲,满足 [x-t, x+t] 的数 y 一定有:(x+1)/(x+1)-1=(y+1)/(y+1)-1。然后分为 t+1 个桶,维护这个桶的数量,每次判断当前的数字落在哪一个桶中。一个桶中有两个数字则直接返回 true,相邻的桶也有可能存在满足的情况。

多线程编程

1114. 按序打印

题目大意:

请设计修改程序,以确保 second() 方法在 first() 方法之后被执行,third() 方法在 second() 方法之后被执行。

思路:

用信号量来实现,Semaphore 的 release 方法会增加计数,acquire 会减少计数并且如果计数为 0 的话 acquire 会阻塞等待。所以我们让 second 方法去获取 firstSemaphore 信号量,只有 first 方法执行完后才会释放信号量,同时 third 方法去获取 secondSemaphore 信号量,只有 second 方法执行完后才会释放该信号量。创建信号量的时候让计数值为 0。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Foo {
Semaphore firstSemaphore = new Semaphore(0);
Semaphore secondSemaphore = new Semaphore(0);
public Foo() {

}

public void first(Runnable printFirst) throws InterruptedException {
// printFirst.run() outputs "first". Do not change or remove this line.
printFirst.run();
firstSemaphore.release();
}

public void second(Runnable printSecond) throws InterruptedException {
firstSemaphore.acquire();
// printSecond.run() outputs "second". Do not change or remove this line.
printSecond.run();
secondSemaphore.release();
}

public void third(Runnable printThird) throws InterruptedException {
secondSemaphore.acquire();
// printThird.run() outputs "third". Do not change or remove this line.
printThird.run();
}
}

▲【必会题】必会题1115. 交替打印FooBar

题目大意:

两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用 foo() 方法,另一个线程将会调用 bar() 方法。

请设计修改程序,以确保 “foobar” 被输出 n 次。

思路:

思路一,信号量去控制顺序。

思路二,synchronized + 标志位 + 唤醒。

思路三,可重入锁 + Condition。

思路四,自旋 + 让出CPU。

思路五,CyclicBarrier 控制先后。

思路六,BLOCKING Queue。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
// 思路一:信号量控制顺序
class FooBar2 {
private int n;
private Semaphore foo = new Semaphore(1);
private Semaphore bar = new Semaphore(0);
public FooBar2(int n) {
this.n = n;
}

public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
foo.acquire();
printFoo.run();
bar.release();
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
bar.acquire();
printBar.run();
foo.release();
}
}
}
// 思路二:synchronized + 标志位 + 唤醒
class FooBar {
private int n;
private Object lock = new Object();
private volatile boolean flag = false;
public FooBar(int n) {
this.n = n;
}

public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized(lock) {
while (flag == true) {
lock.wait();
}
printFoo.run();
flag = true;
lock.notifyAll();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized(lock) {
while (flag == false) {
lock.wait();
}
printBar.run();
flag = false;
lock.notifyAll();
}
}
}
}
// 思路三:可重入锁 + Condition
class FooBar {
private int n;
private ReentrantLock lock = new ReentrantLock();
private Condition condition = lock.newCondition();
private boolean flag = true;
public FooBar(int n) {
this.n = n;
}

public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
lock.lock();
try {
while (flag == false) {
condition.await();
}
printFoo.run();
flag = false;
condition.signalAll();
} finally {
lock.unlock();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
lock.lock();
try {
while (flag == true) {
condition.await();
}
printBar.run();
flag = true;
condition.signalAll();
} finally {
lock.unlock();
}
}
}
}
// 思路四:自旋 + 让出CPU
class FooBar {
private int n;
private volatile boolean flag = true;
public FooBar(int n) {
this.n = n;
}

public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; ) {
if (flag == true) {
printFoo.run();
flag = false;
i++;
} else {
Thread.yield();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; ) {
if (flag == false) {
printBar.run();
flag = true;
i++;
} else {
Thread.yield();
}
}
}
}
// 思路五:CyclicBarrier 控制先后
class FooBar {
private int n;
private CyclicBarrier lock = new CyclicBarrier(2);
private boolean flag = true;
public FooBar(int n) {
this.n = n;
}

public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
while (flag == false);
flag = false;
printFoo.run();
try {
lock.await();
} catch (Exception e) {}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
try {
lock.await();
} catch (Exception e) {}
printBar.run();
flag = true;
}
}
}
// 思路六:BLOCKING Queue
class FooBar {
private int n;
private BlockingQueue<Integer> foo = new LinkedBlockingQueue<>(1);
private BlockingQueue<Integer> bar = new LinkedBlockingQueue<>(1);
public FooBar(int n) {
this.n = n;
}

public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
foo.put(i);
printFoo.run();
bar.put(i);
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
bar.take();
printBar.run();
foo.take();
}
}
}

热题100

31.下一个排列

下一个排列

实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

必须 原地 修改,只允许使用额外常数空间。

我们需要将一个左边的「较小数」与一个右边的「较大数」交换,以能够让当前排列变大,从而得到下一个排列。

同时我们要让这个「较小数」尽量靠右,而「较大数」尽可能小。当交换完成后,「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下,使变大的幅度尽可能小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 1.找到第一个较小数,满足 nums[i] < nums[i+1]
while (i >= 0 && !(nums[i] < nums[i + 1])) {
i--;
}
if (i >= 0) {
// 2.找到靠右的较大数,并交换
int j = nums.length - 1;
while (j > i && !(nums[j] > nums[i])) {
j--;
}
swap(nums, i, j);
}
// 此时可以保证区间 [i + 1, nums.length] 一定是降序
// 3.翻转区间[i, nums.length-1]
// a.如果 1. 中没找到合适的较小数,说明已经是最大数(整个数组是降序的),此时直接翻转就是最小数
// b.如果 1. 中找到了合适的较小数,为了保证变大的幅度尽可能的小,翻转区间[i+1 , nums.length-1]让它按照升序排列
reverse(nums, i + 1);
}
public void reverse(int[] nums, int k) {
int l = k, r = nums.length - 1;
while (l < r) {
swap(nums, l++, r--);
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

32. 最长有效括号

最长有效括号

题目大意:给你一个只包含 '('')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

思路:通过栈,在遍历给定字符串的过程中去判断到目前为止扫描的子串的有效性,同时计算得到最长有效括号的长度。

核心要点是,保持栈底元素为当前已经遍历过的元素中,【最后一个没有被匹配的右括号的下标】。

  • 初始在栈底放入 -1,表示【最后一个没有被匹配的右括号的下标】
  • 当遇到每个’(’,将它的下标存入栈中
  • 当遇到每个’)’,先弹出栈顶元素表示匹配了当前右括号:
    • 如果栈为空,说明当前的右括号为没有被匹配的右括号,我们将其下标放入栈中来更新【最后一个没有被匹配的右括号的下标】
    • 如果栈不为空,当前右括号的下标减去栈顶元素的下标即【以该右括号为结尾的最长有效括号的长度】

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
int maxLength = 0;
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ')') {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
maxLength = Math.max(maxLength, i - stack.peek());
}
} else {
stack.push(i);
}
}
return maxLength;
}
}