LeetCode刷题总结
栈和队列
-
最小栈：请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(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
34public class MyStack {
private Stack<Integer> stackData; // 栈数据
private Stack<Integer> stackMin; // 栈的最小值
public MyStack1() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
public int pop() {
if (this.stackData.isEmpty()) throw new RuntimeException();
int val = this.stackData.pop();
if (val == this.getMin()) {
this.stackMin.pop();
}
return val;
}
public void push(int x) {
this.stackData.push(x);
if (!this.stackMin.isEmpty()) {
if (this.stackMin.peek() >= x) {
this.stackMin.push(x);
}
} else {
this.stackMin.push(x);
}
}
public int getMin() {
if (this.stackMin.isEmpty()) throw new RuntimeException();
return this.stackMin.peek();
}
} -
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
35public class MyQueue {
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
MyQueue1() {
this.stackPush = new Stack<>();
this.stackPop = new Stack<>();
}
public void add(int x) {
this.stackPush.push(x);
if (this.stackPop.isEmpty()) {
pushToPop();
}
}
// push栈元素压到pop栈，pop栈顶永远是优先级最高的
public void pushToPop() {
if (this.stackPop.isEmpty()) {
while (!this.stackPush.isEmpty()) {
this.stackPop.push(this.stackPush.pop());
}
}
}
public int poll() {
if (this.stackPush.isEmpty() && this.stackPop.isEmpty()) return -1;
pushToPop();
return this.stackPop.pop();
}
public int peek() {
return this.stackPop.peek();
}
} -
汉诺塔问题：求有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
39
40
41
42
43
44
45// 1. 小压大原则
// 2. 不可逆原则：若要求最小步数，则相邻操作之间不可逆
// 如果上一步是 L->M，则下一步绝对不是 M->L
public class HanoiProblem {
public enum State {
No, LToM, MToR, RToM, MToL
}
public static int minStep(int n) {
Stack<Integer> left = new Stack<>();
Stack<Integer> mid = new Stack<>();
Stack<Integer> right = new Stack<>();
left.push(Integer.MAX_VALUE);
mid.push(Integer.MAX_VALUE);
right.push(Integer.MAX_VALUE);
for (int i = n; i > 0; i--) {
left.push(i);
}
State[] record = {State.No};
int step = 0;
while (right.size() != n + 1) {
step += process(record, State.MToL, State.LToM, left, mid, "left", "mid");
step += process(record, State.RToM, State.MToR, mid, right, "mid", "right");
step += process(record, State.MToR, State.RToM, right, mid, "right", "mid");
step += process(record, State.LToM, State.MToL, mid, left, "mid", "left");
}
return step;
}
public static int process(State[] record, State preNoAct, State nowAct, Stack<Integer> s1, Stack<Integer> s2, String from, String to) {
if (record[0] != preNoAct && s1.peek() < s2.peek()) {
int val = s1.pop();
s2.push(val);
System.out.println("move " + val + " from " + from + " to " + to);
record[0] = nowAct;
return 1;
}
return 0;
}
public static void main(String[] args) {
System.out.println(minStep(2));
}
} -
用一个栈实现另一个栈的排序：将一个整数类型的栈从顶到底按从大到小的顺序排序，只能申请一个栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public class SortStack {
public static void sort(Stack<Integer> stack) {
Stack<Integer> help = new Stack<>(); // 辅助栈
while (!stack.isEmpty()) {
int cur = stack.pop();
while (!help.isEmpty() && help.peek() < cur) {
stack.push(help.pop());
}
help.push(cur);
}
while (!help.isEmpty()) {
stack.push(help.pop());
}
}
} -
示例：
1
2
3
4
5
6
7
8
9
10
11
12输入: arr = [1,3,-1,-3,5,3,6,7], 和 w = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 71
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
46public class MaxWindow {
// 方法一，暴力枚举，但是会超时
// O(N x w)
public static int[] getMaxWindow1(int[] arr, int w) {
int n = arr.length;
int[] res = new int[n - w + 1];
int left = 0;
int right = w;
while (right < n + 1) {
int maxVal = Integer.MIN_VALUE;
for (int i = left; i < right; i++) {
maxVal = Math.max(maxVal, arr[i]);
}
res[left] = maxVal;
left++;
right++;
}
return res;
}
// 方法二：双端队列实现，复杂度O(N)
public static int[] getMaxWindow2(int[] arr, int w) {
int n = arr.length;
int[] res = new int[n - w + 1];
Deque<Integer> dq = new LinkedList<>(); // 双端队列
int index = 0;
for (int i = 0; i < arr.length; i++) {
while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i]) {
dq.pollLast();
}
dq.addLast(i);
// 队头下标已过期
if (dq.peekFirst() == i - w) {
dq.pollFirst();
}
if (i >= w - 1) {
res[index++] = arr[dq.peekFirst()];
}
}
return res;
}
}
链表
重要技巧：
（1）特殊数据结构，如数组，哈希表等；
（2）快慢指针；
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14public class ReverseNode {
public Node reverseNode(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.next; // 记录后继节点
head.next = pre; // 当前节点指向前继节点
pre = head; // 更新前继节点
head = next; // 更新当前节点为后继节点
}
return pre;
}
} -
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// 快慢指针实现
public class RemoveLastNode {
public static Node removeNode(Node head, int k) {
if (head == null || k < 1) return null;
Node slow = head;
Node fast = head;
while (k != 0) {
fast = fast.next;
k--;
}
// 删除头节点
if (fast == null) {
head = head.next;
return head;
}
fast = fast.next;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
} -
环路检测：给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回
null。思路：
（1）设置快慢指针
slow和fast进行遍历，若fast遇到终点（null）则链表无环；（2）若链表有环，则快慢指针一定在某个环内位置相遇，此时
fast指针回到head的位置，每次走一步，slow指针不变，继续遍历，则两指针一定在环的入口相遇；1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public class DetectCycle {
public Node detectCycle(Node head) {
if (head == null || head.next == null) {
return null;
}
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// 快慢指针相遇
if (fast == slow) {
fast = head;
while (fast != slow) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
} -
判断两个链表是否相交：给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。1
2
3
4
5
6
7
8
9
10
11
12
13
14public class IntersectionNode {
public Node getIntersectionNode(Node headA, Node headB) {
Node n1 = headA;
Node n2 = headB;
while (n1 != n2) {
if (n1 == null) n1 = headA;
else n1 = n1.next;
if (n2 == null) n2 = headB;
else n2 = n2.next;
}
return n1;
}
}
字符串
-
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
} -
反转字符串 II：给定一个字符串
s和一个整数k，从字符串开头算起，每计数至2k个字符，就反转这2k字符中的前k个字符。- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于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
29class Solution {
public String reverseStr(String s, int k) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i += 2 * k) {
// 剩余字符小于 2k 但大于或等于 k 个，反转前 k 个字符
if (str.length >= i + k) {
reverse(str, i, i + k - 1);
continue;
}
// 剩余字符少于 k 个，将剩余字符全部反转
reverse(str, i, str.length - 1);
}
return String.copyValueOf(str);
}
public void reverse(char[] s, int left, int right) {
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
} - 如果剩余字符少于
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public String replaceSpace(String s) {
if(s==null){
return null;
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<s.length();i++){
if(s.charAt(i)==' '){
sb.append("%20");
}else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public class ReverseWords {
public static String reverseWords(String s) {
String[] strs = s
.trim() // 去除头尾空白符
.split(" "); // 以空格来分隔字符串
StringBuilder reverseString = new StringBuilder();
for (int i = strs.length - 1; i >= 0; i--) {
if (strs[i] == "") continue;
reverseString.append(strs[i]);
if (i != 0) {
reverseString.append(" ");
}
}
return reverseString.toString();
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public class ReverseLeftWords {
// 1.反转区间为前n的子串
// 2.反转区间为n到末尾的子串
// 3.反转整个字符串
public String reverseLeftWords(String s, int n) {
char[] str = s.toCharArray();
reverse(str, 0, n - 1);
reverse(str, n, s.length() - 1);
reverse(str, 0, s.length() - 1);
return String.copyValueOf(str);
}
// 反转字符串
public void reverse(char[] str, int start, int end) {
while (start < end) {
char tmp = str[start];
str[start] = str[end];
str[end] = tmp;
start++;
end--;
}
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public class StrStr {
public static int strStr(String haystack, String needle) {
int i = 0, j = 0;
int temp = 0;
while (i < haystack.length() && j < needle.length()) {
temp = i;
// 逐个匹配
while (i < haystack.length() && j < needle.length()
&& haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
// 匹配成功
if (j == needle.length()) {
return i - needle.length();
}
// 从下个位置继续匹配
i = temp + 1;
j = 0;
}
return -1;
}
} -
判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。
1
2
3
4
5
6
7
8
9
10
11public class RepeatedSubstringPattern {
public static boolean repeatedSubstringPattern(String s) {
String ss = s + s;
String substring = ss.substring(1, ss.length() - 1);
return substring.contains(s);
}
public static void main(String[] args) {
System.out.println(repeatedSubstringPattern("abaaba"));
}
}
二叉树
-
二叉树前序遍历
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
28public class PreOrderTraverse {
// 递归遍历
public static void preOrderRecur(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preOrderRecur(root.left);
preOrderRecur(root.right);
}
// 非递归遍历
public static void preOrderUnRecur(TreeNode root) {
if (root == null) return;
Stack<TreeNode> s = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
TreeNode cur = s.pop();
System.out.print(cur.val + " ");
if (cur.right != null) {
s.push(cur.right);
}
if (cur.left != null) {
s.push(cur.left);
}
}
}
} -
二叉树中序遍历
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
27public class InOrderTraverse {
// 递归遍历
public static void inOrderRecur(TreeNode root) {
if (root == null) return;
inOrderRecur(root.left);
System.out.print(root.val + " ");
inOrderRecur(root.right);
}
// 非递归遍历
public static void inOrderUnRecur(TreeNode root) {
if (root == null) return;
Stack<TreeNode> s = new Stack<>();
TreeNode cur = root;
while (!s.isEmpty() || cur != null) {
// 先依次将左边界入栈
if (cur != null) {
s.push(cur);
cur = cur.left;
} else {
cur = s.pop();
System.out.print(cur.val + " ");
cur = cur.right;
}
}
}
} -
二叉树后序遍历
后续遍历关键在于，当节点的 右子树存在且被访问后 或者是 右子树为空 才能访问自身。
在遍历过程中，先将节点从的左孩子到最左节点压栈， 设置标志变量 flag 来判断是否访问过左孩子， pre指针来指向先前访问过的节点。所有左孩子压栈后， 最后一个节点的左孩子为空（已被访问） ， 令flag=1；
当左孩子被访问时，进入循环，取栈顶节点：
-
当栈顶节点的右孩子 等于 空 或 前一个被访问的节点 时， 访问该节点， 令pre 等于当前节点， 当前节点出栈。
-
当栈顶节点的右孩子**不为空 **时， 继续遍历以右孩子为根节点的右子树。
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
40public class PostOrderTraverse {
// 递归遍历
public static void postOrderRecur(TreeNode root) {
if (root == null) return;
postOrderRecur(root.left);
postOrderRecur(root.right);
System.out.print(root.val + " ");
}
// 非递归遍历
public static void postOrderUnRecur(TreeNode root) {
if (root == null) return;
Stack<TreeNode> s = new Stack<>();
TreeNode cur = root;
int flag = 0;
TreeNode pre = null; // 前一个被访问的节点
do {
// 所有左节点入栈
while (cur != null) {
s.push(cur);
cur = cur.left;
}
flag = 1;
while (!s.isEmpty() && flag == 1) {
cur = s.peek();
// 若当前节点的右节点是【上一个被访问的节点】 或为【空】，则访问该节点
if (cur.right == null || cur.right == pre) {
s.pop();
System.out.print(cur.val + " ");
pre = cur;
} else {
//继续遍历右子树
cur = cur.right;
flag = 0;
}
}
} while (!s.isEmpty());
}
}另一种思路：由于前序遍历的顺序是 ”中左右“，后序遍历的顺序是”左右中“，因此更改前序遍历中的入栈顺序，然后将遍历结果反转，便能得到后序遍历的结果。
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 List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
} -
-
1
2
3
4
5
6
7class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
}
} -
二叉树的最小深度：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
1
2
3
4
5
6
7
8
9
10
11
12
13// 如果左子树为空，右子树不为空，最小深度是 1 + 右子树的最小深度。
// 反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的最小深度。
// 如果左右子树都不为空，返回 1 + 左右子树深度最小值。
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
if (root.left != null && root.right == null) return minDepth(root.left) + 1;
if (root.left == null && root.right != null) return minDepth(root.right) + 1;
return Math.min(minDepth(root.left) + 1, minDepth(root.right) + 1);
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
// 交换左右子树
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
} -
对称二叉树：判断二叉树是否为轴对称
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
return isSame(root.left,root.right);
}
public boolean isSame(TreeNode t1,TreeNode t2){
if(t1==null && t2==null) return true;
if(t1==null || t2==null) return false;
if(t1.val != t2.val) return false;
return isSame(t1.left,t2.right) && isSame(t1.right,t2.left);
}
} -
平衡二叉树：平衡二叉树的每个节点 的左右两个子树的高度差的绝对值不超过 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class BalanceTree {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
int h1 = getHeight(root.left);
int h2 = getHeight(root.right);
if (Math.abs(h1 - h2) > 1) return false;
else return isBalanced(root.left) && isBalanced(root.right);
}
// 求某个节点的最大高度
public int getHeight(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
else return Math.max(getHeight(root.left) + 1, getHeight(root.right) + 1);
}
} -
二叉树的所有路径：给你一个二叉树的根节点
root，按 任意顺序 ，返回所有从根节点到叶子节点的路径。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public class BinaryTreePaths {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new LinkedList<>();
dfs(root, paths, "");
return paths;
}
public void dfs(TreeNode root, List<String> paths, String path) {
if (root == null) return;
path += root.val;
if (root.left == null && root.right == null) {
paths.add(path);
return;
}
dfs(root.left, paths, path + "->");
dfs(root.right, paths, path + "->");
}
} -
左叶子之和：给定二叉树的根节点
root，返回所有左叶子之和。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
30public class LeftLeaves {
// 递归法
public int sumOfLeftLeaves1(TreeNode root) {
int res = 0;
if (root == null) return 0;
if (root.left == null && root.right == null) return 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
res += root.left.val;
}
return res + sumOfLeftLeaves1(root.left) + sumOfLeftLeaves1(root.right);
}
// 迭代法
public int sumOfLeftLeaves2(TreeNode root) {
if (root == null) return 0;
int res = 0;
Stack<TreeNode> s = new Stack<>();
s.push(root);
while (!s.isEmpty()) {
TreeNode node = s.pop();
if (node.left != null && node.left.left == null && node.left.right == null) {
res += node.left.val;
}
if (node.left != null) s.push(node.left);
if (node.right != null) s.push(node.right);
}
return res;
}
} -
找树左下角的值：给定一个二叉树的 根节点
root，请找出该二叉树的 最底层最左边 节点的值。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19// 利用层序遍历，最后一层的第一个值即为左下角的值
class Solution {
public int findBottomLeftValue(TreeNode root) {
if (root == null) return -1;
Queue<TreeNode> q = new LinkedList<>();
int res = 0;
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (i == 0) res = node.val; // 记录最后一层第一个值
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
}
return res;
}
} -
路径总和：给你二叉树的根节点
root和一个表示目标和的整数targetSum。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public class PathSum {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
targetSum -= root.val;
// 找到一条路径
if (root.left == null && root.right == null) {
return targetSum == 0;
}
if (root.left != null) {
boolean left = hasPathSum(root.left, targetSum);
if (left) return true;
}
if (root.right != null) {
boolean right = hasPathSum(root.right, targetSum);
if (right) return true;
}
return false;
}
} -
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
33public class BuildTree1 {
HashMap<Integer, Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
int n = inorder.length;
if (n == 0) return null;
map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(inorder[i], i); // 保存中序序列值得对应位置，方便查询
}
return helper(inorder, 0, n, postorder, 0, n); // 左闭右开
}
public TreeNode helper(int[] inorder, int inBegin, int inEnd,
int[] postorder, int postBegin, int postEnd) {
// 不满足左闭右开，说明没有元素，返回空树
if (inBegin >= inEnd || postBegin >= postEnd) return null;
// 找到后序遍历的最后一个元素在中序遍历中的位置
// 构造根节点
int rootIndex = map.get(postorder[postEnd - 1]);
TreeNode root = new TreeNode(inorder[rootIndex]);
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数
root.left = helper(inorder, inBegin, rootIndex,
postorder, postBegin, postBegin + lenOfLeft);
root.right = helper(inorder, rootIndex + 1, inEnd,
postorder, postBegin + lenOfLeft, postEnd - 1);
return root;
}
} -
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
33public class BuildTree2 {
HashMap<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = inorder.length;
if (n == 0) return null;
map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(inorder[i], i); // 保存中序序列值得对应位置，方便查询
}
return helper(preorder, 0, n, inorder, 0, n); // 左闭右开
}
public TreeNode helper(int[] preorder, int preBegin, int preEnd,
int[] inorder, int inBegin, int inEnd) {
// 不满足左闭右开，说明没有元素，返回空树
if (inBegin >= inEnd || preBegin >= preEnd) return null;
// 找到前序遍历的第一个元素在中序遍历中的位置
// 构造根节点
int rootIndex = map.get(preorder[preBegin]);
TreeNode root = new TreeNode(inorder[rootIndex]);
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数
root.left = helper(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
inorder, inBegin, rootIndex);
root.right = helper(preorder, preBegin + lenOfLeft + 1, preEnd,
inorder, rootIndex + 1, inEnd);
return root;
}
} -
验证二叉搜索树：给你一个二叉树的根节点
root，判断其是否是一个有效的二叉搜索树。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21/**
* 对于一个合法的二叉搜索树，节点的左子树只包含 小于 当前节点的数，节点的右子树只包含 大于 当前节点的数。
* 因此，它的中序遍历是升序的
*/
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
// 访问左子树
if (!isValidBST(root.left)) {
return 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
16class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
// 后序遍历,自底向上
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right == null) return null; // 未找到节点
if (left == null) return right; // 目标节点在右边找到
if (right == null) return left; // 目标节点在左边找到
// 如果left和right都不为空，则最近公共祖先就是root
return root;
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
/**
* 利用二叉搜索树的性质：
* 1. 若p和q节点的值都比当前节点的值小，则目标节点在左子树
* 2. 若p和q节点的值都比当前节点的值大，则目标节点在右子树
* 3. 若p和q节点的值在当前节点值得两边，则目标节点为当前节点
*/
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
return root;
}
}
}
回溯
-
回溯算法模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
/**
* -->循环体，树的宽度-->
*/
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归，树的深度
回溯，撤销处理结果
}
} -
组合：给定两个整数
n和k，返回范围[1, n]中所有可能的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
26class Combine {
List<List<Integer>> res;
LinkedList<Integer> path;
public List<List<Integer>> combine(int n, int k) {
res = new LinkedList<>();
path = new LinkedList<>();
process(n, k, 1);
return res;
}
public void process(int n, int k, int index) {
// 终止条件
if (path.size() == k) {
res.add(new LinkedList<>(path)); // 存放结果
return;
}
for (int i = index; i <= n-(k-path.size())+1; i++) { // jian'zhi
// 处理节点
path.add(i);
process(n, k, i + 1); // 递归
path.removeLast(); // 回溯，撤销处理结果
}
}
} -
组合总和 III：找出所有相加之和为
n的k个数的组合，且满足下列条件：- 只使用数字1到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
35public class CombinationSum3 {
List<List<Integer>> res;
LinkedList<Integer> path;
public List<List<Integer>> combinationSum3(int k, int n) {
res = new LinkedList<>();
path = new LinkedList<>();
process(n, k, 1);
return res;
}
public void process(int target, int k, int index) {
// 剪枝
if (target < 0) {
return;
}
// 终止条件
if (path.size() == k && target == 0) {
res.add(new LinkedList<>(path));
return;
}
for (int i = index; i <= 9; i++) {
// 处理节点
path.add(i);
target -= i;
// 递归
process(target, k, i + 1);
// 回溯
path.removeLast();
target += i;
}
}
} -
组合总和：给你一个 无重复元素 的整数数组
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
27
28
29
30
31
32
33
34
35public class CombinationSum {
List<List<Integer>> res;
LinkedList<Integer> path;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
res = new LinkedList<>();
path = new LinkedList<>();
process(candidates, target, 0);
return res;
}
public void process(int[] candidates, int target, int index) {
// 剪枝
if (target < 0) {
return;
}
if (target == 0) {
res.add(new LinkedList<>(path));
return;
}
for (int i = index; i < candidates.length; i++) {
// 处理节点
path.add(candidates[i]);
target -= candidates[i];
// 递归
process(candidates, target, i); // 关键：不用递归 i+1, 表示元素可以被重复取到
// 回溯
path.removeLast();
target += candidates[i];
}
}
} -
电话号码的字母组合：给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 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
34public class LetterCombinations {
char[][] map = {{}, {}, {'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;
StringBuilder sb = new StringBuilder();
public List<String> letterCombinations(String digits) {
res = new LinkedList<>();
if (digits.length() == 0) {
return res;
}
process(digits, 0);
return res;
}
public void process(String digits, int index) {
// 终止条件
if (index == digits.length()) {
res.add(sb.toString());
return;
}
int digit = digits.charAt(index) - '0';
char[] str = map[digit];
for (int i = 0; i < str.length; i++) {
sb.append(str[i]);
process(digits, index + 1); // 由于是不同数字之间组合，所以是 index与 index+1 ...之间组合
sb.deleteCharAt(sb.length() - 1); // 回溯，重新尝试
}
}
} -
组合总和 II：给定一个候选人编号的集合
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用 一次 。注意：**解集不能包含重复的组合。 **由于
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45class Solution {
List<List<Integer>> res;
LinkedList<Integer> path;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
res = new LinkedList<>();
path = new LinkedList<>();
Arrays.sort(candidates); // 排序，使相同元素在一起
process(candidates, target, 0);
return res;
}
public void process(int[] candidates, int target, int index) {
// 剪枝
if (target < 0) {
return;
}
if (target == 0) {
LinkedList<Integer> tmp = new LinkedList<>(path);
// // 简单判断去重，但是会超时
// if (!res.contains(tmp)) {
// res.add(tmp);
// }
res.add(tmp);
return;
}
for (int i = index; i < candidates.length; i++) {
// 去重
if (i > index && candidates[i] == candidates[i - 1]) {
continue;
}
// 处理节点
path.add(candidates[i]);
target -= candidates[i];
// 递归
process(candidates, target, i + 1);
// 回溯
path.removeLast();
target += candidates[i];
}
}
} -
分割回文串：给你一个字符串
s，请你将s分割成一些子串，使每个子串都是 回文串 。返回s所有可能的分割方案。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
41public class PalindromePartition {
List<List<String>> res = new LinkedList<>();
List<String> path = new LinkedList<>();
public List<List<String>> partition(String s) {
if (s.length() == 0) {
return null;
}
process(s, 0);
return res;
}
public void process(String s, int index) {
if (index >= s.length()) {
res.add(new LinkedList<>(path));
return;
}
for (int i = index; i < s.length(); i++) {
if (isPalindrome(s, index, i)) {
String tmp = s.substring(index, i + 1);
path.add(tmp);
} else {
continue;
}
process(s, i + 1); // 递归
path.remove(path.size() - 1); //回溯
}
}
// 判断回文
public boolean isPalindrome(String s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
} -
子集：给你一个整数数组
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
26class Subsets {
List<List<Integer>> res;
List<Integer> path;
public List<List<Integer>> subsets(int[] nums) {
res = new LinkedList<>();
path = new LinkedList<>();
res.add(new LinkedList<>()); // 空集
process(nums, 0);
return res;
}
public void process(int[] nums, int index) {
if (!res.contains(path)) {
res.add(new LinkedList<>(path));
}
if (path.size() == nums.length) return; // 说明找完了
for (int i = index; i < nums.length; i++) {
path.add(nums[i]);
process(nums, i + 1);
path.remove(path.size() - 1);
}
}
} -
子集 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
29public class Subsets2 {
List<List<Integer>> res;
List<Integer> path;
public List<List<Integer>> subsetsWithDup(int[] nums) {
res = new LinkedList<>();
path = new LinkedList<>();
Arrays.sort(nums); // 排序
res.add(new LinkedList<>()); // 空集
process(nums, 0);
return res;
}
public void process(int[] nums, int index) {
if (!res.contains(path)) {
res.add(new LinkedList<>(path));
}
if (path.size() == nums.length) return; // 说明找完了
for (int i = index; i < nums.length; i++) {
if (i > index && nums[i] == nums[i - 1]) { // 去重
continue;
}
path.add(nums[i]);
process(nums, i + 1);
path.remove(path.size() - 1);
}
}
} -
递增子序列：给你一个整数数组
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
27class Solution {
List<List<Integer>> res = new LinkedList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
process(nums, 0);
return res;
}
public void process(int[] nums, int index) {
if (path.size() > 1) {
res.add(new LinkedList<>(path));
}
// HashSet 去重
HashSet<Integer> hs = new HashSet<>();
for (int i = index; i < nums.length; i++) {
if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || hs.contains(nums[i])) {
continue;
}
path.add(nums[i]);
hs.add(nums[i]);
process(nums, i + 1);
path.remove(path.size() - 1);
}
}
} -
全排列：给定一个不含重复数字的数组
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
29
30
31
32
33public class Permute {
List<List<Integer>> res = new LinkedList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[nums.length];
process(nums, used);
return res;
}
/**
* 全排列问题，每次都需要从头开始搜索,因此不用参数index
* used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
*/
public void process(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
res.add(new LinkedList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
path.add(nums[i]);
used[i] = true;
process(nums, used);
// 回溯
used[i] = false;
path.remove(path.size() - 1);
}
}
} -
全排列 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
29
30
31
32public class PermuteUnique {
List<List<Integer>> res = new LinkedList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
process(nums, used);
return res;
}
public void process(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
res.add(new LinkedList<>(path));
return;
}
// HashSet 去重
HashSet<Integer> hs = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (used[i] || hs.contains(nums[i])) {
continue;
}
path.add(nums[i]);
hs.add(nums[i]);
used[i] = true;
process(nums, used);
// 回溯
used[i] = false;
path.remove(path.size() - 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60class Solution {
List<List<String>> res = new LinkedList<>();
public List<List<String>> solveNQueens(int n) {
char[][] matrix = new char[n][n];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[i][j] = '.';
}
}
process(matrix,n,0);
return res;
}
public void process(char[][] matrix, int n, int row) {
if (row == n) {
List<String> list = new LinkedList<>();
for (int i = 0; i < n; i++) {
StringBuilder sb = new StringBuilder();
int k = 0;
while (k < n) {
sb.append(matrix[i][k++]);
}
list.add(sb.toString());
}
res.add(list);
return;
}
for (int col = 0; col < n; col++) {
if (isValid(matrix, row, col, n)) {
matrix[row][col] = 'Q'; // 放置皇后
process(matrix, n, row + 1);
matrix[row][col] = '.'; // 回溯，撤销
}
}
}
// 检查是否合法
public static boolean isValid(char[][] matrix, int row, int col, int n) {
// 检查列
for (int i = 0; i < row; i++) {
if (matrix[i][col] == 'Q') {
return false;
}
}
// 检查左上
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (matrix[i][j] == 'Q') {
return false;
}
}
// 检查右上
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (matrix[i][j] == 'Q') {
return false;
}
}
return true;
}
}
贪心算法
-
分发饼干：对每个孩子
i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j，都有一个尺寸s[j]。如果s[j] >= g[i]，我们可以将这个饼干j分配给孩子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
25class BiscuitDistribution {
public int findContentChildren(int[] g, int[] s) {
// 排序
Arrays.sort(g);
Arrays.sort(s);
int res = 0;
int child = g.length - 1;
for (int i = s.length - 1; i >= 0; i--) {
if (child < 0) break;
// 不能分配
while (child > 0 && s[i] < g[child]) {
child--;
}
// 可以分配
if (s[i] >= g[child]) {
res++;
child--;
}
}
return res;
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public class WiggleSubsequence {
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int ans = 1;
int pre = 0;
int cur = 0;
for (int i = 1; i < nums.length; i++) {
cur = nums[i] - nums[i - 1];
if ((cur > 0 && pre <= 0) || (cur < 0 && pre >= 0)) {
ans++;
pre = cur;
}
}
return ans;
}
} -
最大子数组和：给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public class MaxSubArray {
public int maxSubArray(int[] nums) {
if (nums.length <= 1) {
return nums[0];
}
int res = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++) {
count += nums[i];
res = Math.max(res, count);
// 重置，因为遇到负数一定会使res减小
if (count < 0) {
count = 0;
}
}
return res;
}
} -
买卖股票的最佳时机 II：给你一个整数数组
prices，其中prices[i]表示某支股票第i天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回 你能获得的 最大 利润 。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/**
* 假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
* 相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
* 就是把利润分解为每天为单位的维度
*/
public class MaxProfit {
public int maxProfit(int[] prices) {
if (prices.length <= 1) {
return 0;
}
int ans = 0;
for (int i = 1; i < prices.length; i++) {
ans += Math.max(0, prices[i] - prices[i - 1]);
}
return ans;
}
} -
买卖股票的最佳时机：给定一个数组
prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。1
2
3
4
5
6
7
8
9
10class MaxProfit {
public int maxProfit(int[] prices) {
int ans = 0;
for (int i = 1; i < prices.length; i++) {
ans = Math.max(prices[i] - prices[i - 1], ans);
prices[i] = Math.min(prices[i], prices[i - 1]);
}
return ans;
}
} -
跳跃游戏：给你一个非负整数数组
nums，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17/**
* 每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
* 贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
*/
class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 1) return true;
int coverRange = 0;
for (int i = 0; i <= coverRange; i++) {
coverRange = Math.max(coverRange, i + nums[i]);
if (coverRange >= nums.length - 1) {
return true;
}
}
return false;
}
} -
跳跃游戏 II：给定一个长度为
n的 0 索引整数数组nums。初始位置为nums[0]。每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意nums[i + j]处:0 <= j <= nums[i]i + j < n
返回到达
nums[n - 1]的最小跳跃次数。生成的测试用例可以到达nums[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
24class Solution {
public int jump(int[] nums) {
if (nums.length <= 1) {
return 0;
}
int next = 0;
int step = 0;
int cur = 0;
for (int i = 0; i < nums.length; i++) {
next = Math.max(next, i + nums[i]);
if (next >= nums.length - 1) {
step++;
break;
}
if (i == cur) {
cur = next;
step++;
}
}
return step;
}
} -
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
37class Solution {
// 暴力模拟 O(n^2)
public int canCompleteCircuit(int[] gas, int[] cost) {
for(int i=0;i<gas.length;i++){
int rest = gas[i] - cost[i]; // 剩余油量
int pos = (i+1) % gas.length; // 模拟出发的位置
while(rest>0 && pos!=i){
rest += gas[pos] - cost[pos];
pos = (pos + 1) % gas.length;
}
if(rest>=0 && pos==i){
return i;
}
}
return -1;
}
// 贪心 O(N)
public int canCompleteCircuit(int[] gas, int[] cost) {
int rest = 0;
int total = 0;
int pos = 0;
for(int i=0;i<gas.length;i++){
rest += gas[i] - cost[i];
total += gas[i] - cost[i];
// 如果之前累加剩余油量为负值，则肯定无法从i之前的位置到达
if(rest<0){
pos = i + 1;
rest = 0;
}
}
if(total<0) return -1;
return pos;
}
} -
分发糖果：
n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：- 每个孩子至少分配到
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/**
* 本题采用了两次贪心的策略。
* 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
* 一次是从右到左遍历，只比较左边孩子评分比右边大的情况
*/
class Candy {
public static int candy(int[] ratings) {
int[] candys = new int[ratings.length];
candys[0] = 1;
// 从前往后，右边比左边大的情况
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candys[i] = candys[i - 1] + 1;
} else {
candys[i] = 1;
}
}
// 从前往后，左边比右边大的情况
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candys[i] = Math.max(candys[i + 1] + 1, candys[i]);
}
}
int res = 0;
for (int candy : candys) {
res += candy;
}
return res;
}
} - 每个孩子至少分配到
动态规划
-
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public int fib(int n) {
if (n == 0 || n == 1) return n;
int a = 0;
int b = 1;
for (int i = 2; i <= n; i++) {
int sum = a + b;
a = b;
b = sum;
}
return b;
}
} -
使用最小花费爬楼梯：给你一个整数数组
cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1]; // dp[i]表示爬前i个楼梯所需的最小花费
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
int p1 = dp[i - 1] + cost[i - 1];
int p2 = dp[i - 2] + cost[i - 2];
dp[i] = Math.min(p1, p2);
}
return dp[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// 暴力递归
class Solution {
public int rob(int[] nums) {
return helper(nums, 0);
}
public int helper(int[] nums, int index) {
if (index < 0 || index > nums.length - 1) {
return 0;
}
return Math.max(nums[index] + helper(nums, index + 2), helper(nums, index + 1));
}
}
// 动态规划
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
int[] money = new int[n]; // 偷盗前i个房屋，能获得的最大价值
money[0] = nums[0];
money[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
money[i] = Math.max(nums[i] + money[i - 2], money[i - 1]);
}
return money[n - 1];
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
// 两种情况：取首或取尾
return Math.max(helper(nums, 0, n - 2), helper(nums, 1, n - 1));
}
public int helper(int[] nums, int start, int end) {
if (start == end) {
return nums[start];
}
int[] money = new int[nums.length]; // 偷盗前i个房屋，能获得的最大价值
money[start] = nums[start];
money[start + 1] = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
money[i] = Math.max(nums[i] + money[i - 2], money[i - 1]);
}
return money[end];
}
} -
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
49class Solution {
// 暴力递归
public int rob(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) {
return root.val;
}
int val1 = root.val;
// 偷父节点
if (root.left != null) {
val1 += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val1 += rob(root.right.left) + rob(root.right.right);
}
// 不偷父节点
int val2 = rob(root.left) + rob(root.right);
return Math.max(val1, val2);
}
// 优化
// 通过map记录计算过的节点，降低时间复杂度
public int rob(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) {
return root.val;
}
// 如果已经计算过，则直接返回结果
if (map.containsKey(root)) {
return map.get(root);
}
int val1 = root.val;
// 偷父节点
if (root.left != null) {
val1 += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val1 += rob(root.right.left) + rob(root.right.right);
}
// 不偷父节点
int val2 = rob(root.left) + rob(root.right);
map.put(root, Math.max(val1, val2)); // 记录中间结果
return Math.max(val1, val2);
}
} -
不同路径：一个机器人位于一个
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
41public class RobotPath {
static int ans = 0;
// 暴力递归
public static int uniquePaths1(int m, int n) {
int[][] matrix = new int[m][n];
dfs(matrix, 0, 0);
return ans;
}
public static void dfs(int[][] matrix, int x, int y) {
if (x < 0 || y < 0 || x > matrix.length - 1 ||
y > matrix[0].length - 1 || matrix[x][y] != 0) {
return;
}
// 找到一条路径
if (x == matrix.length - 1 && y == matrix[0].length - 1) {
ans++;
}
matrix[x][y] = 1; // 标记，已经过的位置
dfs(matrix, x + 1, y);
dfs(matrix, x, y + 1);
matrix[x][y] = 0; // 回溯，撤回结果
}
// 动态规划
public static int uniquePaths2(int m, int n) {
int[][] dp = new int[m][n]; // dp[i][j]表示到达(i,j)的路径数
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
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
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
50public class RobotPathII {
static int ans = 0;
// 暴力递归
public static int uniquePathsWithObstacles1(int[][] obstacleGrid) {
dfs(obstacleGrid, 0, 0);
return ans;
}
public static void dfs(int[][] ob, int x, int y) {
if (x < 0 || y < 0 || x > ob.length - 1 || y > ob[0].length - 1 || ob[x][y] != 0) {
return;
}
if (x == ob.length - 1 && y == ob[0].length - 1) {
ans++;
}
ob[x][y] = 2;
dfs(ob, x + 1, y);
dfs(ob, x, y + 1);
ob[x][y] = 0;
}
// 动态规划
public static int uniquePathsWithObstacles2(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n]; // dp[i][j]:到达(i,j)的路径数
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] != 1) {
dp[i][0] = 1;
}
}
for (int j = 0; j < n; j++) {
if (obstacleGrid[0][j] != 1) {
dp[0][j] = 1;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 0) {
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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44public class RobotPathIII {
public static int uniquePathsIII(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int rest = 1; // 起点到终点需要一步（无障碍）
int[] start = new int[2];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
start[0] = i;
start[1] = j;
}
if (grid[i][j] == 0) {
rest++;
}
}
}
return dfs(grid, start[0], start[1], rest);
}
// 暴力递归
public static int dfs(int[][] grid, int x, int y, int rest) {
if (x < 0 || y < 0 || x > grid.length - 1 || y > grid[0].length - 1 || grid[x][y] == -1) {
return 0;
}
if (grid[x][y] == 2) {
return rest == 0 ? 1 : 0;
}
grid[x][y] = -1;
int sum = 0;
sum += dfs(grid, x + 1, y, rest - 1);
sum += dfs(grid, x, y + 1, rest - 1);
sum += dfs(grid, x - 1, y, rest - 1);
sum += dfs(grid, x, y - 1, rest - 1);
grid[x][y] = 0;
return sum;
}
}
评论
