文章目录
-
-
1. 二叉树的最近公共祖先
-
2. 斐波那契数列
-
3. 青蛙跳台阶问题
-
4. 合并两个排序的链表
-
5. 反转链表
-
6. 二叉树的镜像
-
7. 二叉树的深度
-
8. 顺时针打印矩阵
-
9. 二叉搜索树的最近公共祖先
-
10. 两个链表的第一个公共节点
-
11. 对称的二叉树
-
12. 最长不含重复字符的子字符串
-
13. 连续子数组的最大和(最大子数组和)
-
14. 从尾到头打印链表
-
15. 删除链表的节点
-
16. 用两个栈实现队列
-
17. 求1+2+…+n
-
18. 平衡二叉树
-
19. 替换空格
-
20. 二叉搜索树的第k大节点
-
21. 链表中倒数第k个节点
-
22. 数组中重复的数字
-
23. 二维数组中的查找
-
24. 前序和中序遍历->构建二叉树（重建二叉树）
-
25. 打印从1到最大的n位数
-
26. 二进制中1的个数
-
27. 机器人的运动范围
-
28. 树的子结构
-
29. 调整数组顺序使奇数位于偶数前面
-
30. 二叉树层序遍历
-
31. 和为s的两个数字
-
32. 数值的整数次方
-
33. 从上到下打印二叉树
-
34. 从上到下打印二叉树 III
-
35. 包含min函数的栈
-
36. 字符串的排列
-
37. 二叉搜索树与双向链表
-
38. 0～n-1中缺失的数字
-
39. 旋转数组的最小数字【高频】
-
40. 不用加减乘除做加法
-
41. 剪绳子
-
42. 剪绳子 II
-
43. 二叉搜索树的后序遍历序列
-
44. 第一个只出现一次的字符
-
45. 二叉树中和为某一值的路径
-
46. 在排序数组中查找数字 I
-
47. 最小的k个数
-
48. 数组中出现次数超过一半的数字
-
49. 矩阵中的路径
-
50. 正则表达式匹配
-
51. 左旋转字符串
-
52. 和为s的连续正数序列
-
53. 栈的压入、弹出序列
-
54.复杂链表的复制
-
55. 翻转单词顺序
-
56. 丑数
-
57. 构建乘积数组
-
58. 扑克牌中的顺子
-
59. 数组中的逆序对
-
60. 礼物的最大价值
-
61.把数组排成最小的数
-
62.序列化二叉树
-
-
HOT
-
排序
1. 二叉树的最近公共祖先
1.剑指 Offer 68 – II. 二叉树的最近公共祖先
2022.7.17
力扣算法 Java 刷题笔记【二叉树篇】hot100（十）GIT原理之最近公共祖先（二叉树的最近公共祖先）中等 1
五个变式
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (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 && right != null) {
return root;
}
return left == null ? right : left;
}
}
/*
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
return right;
}
if (right == null) {
return left;
}
return root;
}
}
*/
2. 斐波那契数列
剑指 Offer 10- I. 斐波那契数列
2022.7.17
力扣算法 Java 刷题笔记【动态规划篇 DP】hot100（一）动态规划解题核心框架 & 斐波那契数 & 零钱兑换 5
解法一：自顶向下（备忘录）–递归
class Solution {
// static final int MOD = 1000000007;
int[] memo = null;
public int fib(int n) {
if (n <= 1) {
return n;
}
if (memo == null) {
memo = new int[n + 1];
}
if (memo[n] != 0) {
return memo[n];
}
memo[n] = fib(n - 1) + fib(n - 2); // 取模 memo[n] = (fib(n - 1) + fib(n - 2)) % MOD;
return memo[n];
}
}
解法二：自底向上（dp）–迭代
class Solution {
public int fib(int n) {
if (n == 0) {
return 0;
}
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 取模 dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n];
}
}
3. 青蛙跳台阶问题
剑指 Offer 10- II. 青蛙跳台阶问题
2022.7.17
力扣算法 Java 刷题笔记【动态规划篇 DP】hot100（一）动态规划解题核心框架 & 斐波那契数 & 零钱兑换 5
class Solution {
static final int MOD = 1000000007;
public int numWays(int n) {
if (n <= 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
}
return dp[n];
}
}
4. 合并两个排序的链表
剑指 Offer 25. 合并两个排序的链表
2022.7.17
力扣算法 Java 刷题笔记【链表篇】hot100（一）合并 K 个升序链表（困难） 删除链表的倒数第 N 个结点（中等） 7
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1), p = dummy;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
p.next = l2;
l2 = l2.next;
} else {
p.next = l1;
l1 = l1.next;
}
p = p.next;
}
if (l1 == null) {
p.next = l2;
}
if (l2 == null) {
p.next = l1;
}
return dummy.next;
}
}
5. 反转链表
剑指 Offer 24. 反转链表
2022.7.17
解法一：递归
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}
}
解法二：迭代
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head, nxt = head;
while (cur != null) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
6. 二叉树的镜像
剑指 Offer 27. 二叉树的镜像
2022.7.18
力扣算法 Java 刷题笔记【二叉树篇】hot100（一）翻转二叉树 填充每个节点的下一个右侧节点指针（中等） 二叉树展开为链表（中等）3
// 后序遍历
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
TreeNode node = new TreeNode();
node = left;
root.left = right;
root.right = node;
return root;
}
}
/*
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode node = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(node);
return root;
}
}
*/
/* 前序遍历
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode node = root.left;
root.left = root.right;
root.right = node;
mirrorTree(root.left);
mirrorTree(root.right);
return root;
}
}
*/
7. 二叉树的深度
剑指 Offer 55 – I. 二叉树的深度
2022.7.18
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
return Math.max(leftMax, rightMax) + 1; // return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
}
8. 顺时针打印矩阵
剑指 Offer 29. 顺时针打印矩阵
2022.7.18
class Solution {
public int[] spiralOrder(int[][] matrix) {
int m = matrix.length;
if (m == 0) {
return new int[0];
}
int n = matrix[0].length;
int upper_bound = 0, lower_bound = m - 1;
int left_bound = 0, right_bound = n - 1;
int[] res = new int[m * n];
res[m * n - 1] = -1;
int id = 0;
while (res[m * n - 1] == -1) { // 注意循环条件-->此处仍有改进空间
if (upper_bound <= lower_bound) {
for (int i = left_bound; i <= right_bound; i++) {
res[id++] = matrix[upper_bound][i];
}
upper_bound++;
}
if (left_bound <= right_bound) {
for (int i = upper_bound; i <= lower_bound; i++) {
res[id++] = matrix[i][right_bound];
}
right_bound--;
}
if (upper_bound <= lower_bound) {
for (int i = right_bound; i >= left_bound; i--) {
res[id++] = matrix[lower_bound][i];
}
lower_bound--;
}
if (left_bound <= right_bound) {
for (int i = lower_bound; i >= upper_bound; i--) {
res[id++] = matrix[i][left_bound];
}
left_bound++;
}
}
return res;
}
}
9. 二叉搜索树的最近公共祖先
剑指 Offer 68 – I. 二叉搜索树的最近公共祖先
2022.7.18
方法一：同二叉树（题1）
方法二：利用二叉搜索树的性质
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int val1 = Math.min(p.val, q.val);
int val2 = Math.max(p.val, q.val);
return find(root, val1, val2);
}
public TreeNode find(TreeNode root, int val1, int val2) {
if (root == null) {
return null;
}
if (val1 > root.val) {
return find(root.right, val1, val2);
}
if (val2 < root.val) {
return find(root.left, val1, val2);
}
return root;
}
}
10. 两个链表的第一个公共节点
[剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/ 2022.7.19
力扣算法 Java 刷题笔记【链表篇】hot100（一）合并 K 个升序链表（困难） 删除链表的倒数第 N 个结点（中等） 7
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
if (p1 == null) {
p1 = headB;
} else {
p1 = p1.next;
}
if (p2 == null) {
p2 = headA;
} else {
p2 = p2.next;
}
}
return p1;
}
}
11. 对称的二叉树
剑指 Offer 28. 对称的二叉树
2022.7.19
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return check(root.left, root.right);
}
boolean check(TreeNode left, TreeNode right) {
if (left == null || right == null) {
return left == right;
}
if (left.val != right.val) {
return false;
}
return check(left.left, right.right) && check(left.right, right.left);
}
}
12. 最长不含重复字符的子字符串
剑指 Offer 48. 最长不含重复字符的子字符串
2022.7.19
力扣算法 Java 刷题笔记【数组篇 滑动窗口算法】hot100（四）最小覆盖子串、字符串的排列、异位词、 无重复字符的最长子串 4
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> window = new HashMap<>();
int l = 0, r = 0;
int res = 0;
while (r < s.length()) {
char c = s.charAt(r);
window.put (c, window.getOrDefault(c, 0) + 1);
r++;
while (window.get(c) > 1) {
window.put(s.charAt(l), window.get(s.charAt(l)) - 1);
l++;
}
res = Math.max(res, r - l);
}
return res;
}
}
13. 连续子数组的最大和(最大子数组和)
剑指 Offer 42. 连续子数组的最大和
2022.7.19
方法一：动态规划（不是最优解）
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
res = Math.max(dp[i], res);
}
return res;
}
}
最优解
class Solution {
public int maxSubArray(int[] nums) {
int dp = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
dp = Math.max(dp + nums[i], nums[i]);
max = Math.max(dp, max);
}
return max;
}
}
14. 从尾到头打印链表
剑指 Offer 06. 从尾到头打印链表
2022.7.20
最优解：时间 O(n) 空间 O(1)
从右边往左填充
public int[] reversePrint(ListNode head) {
if(head == null)
return new int[0];
// 统计链表节点个数，方便创建数组
int count = 0;
ListNode temp = head;
while(temp != null){
count++;
temp = temp.next;
}
int[] res = new int[count];
int k = count - 1;
// 从右往左填充数组
while(head != null){
res[k--] = head.val;
head = head.next;
}
return res;
}
方法一：反转后取值
class Solution {
int count = 0;
public int[] reversePrint(ListNode head) {
if (head == null) {
return new int[0];
}
ListNode last = reverseNode(head);
int[] res = new int[count];
for (int i = 0; last != null; i++) {
res[i] = last.val;
last = last.next;
}
return res;
}
ListNode reverseNode(ListNode head) {
count++;
if (head == null || head.next == null) {
return head;
}
ListNode last = reverseNode(head.next);
head.next.next = head;
head.next = null;
return last;
}
}
方法二：栈
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();
ListNode temp = head;
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
int size = stack.size();
int[] print = new int[size];
for (int i = 0; i < size; i++) {
print[i] = stack.pop().val;
}
return print;
}
}
15. 删除链表的节点
剑指 Offer 18. 删除链表的节点
2022.7.20
力扣算法 Java 刷题笔记【链表篇】hot100（一）合并 K 个升序链表（困难） 删除链表的倒数第 N 个结点（中等） 7
方法一：常规解法
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode res = head;
if (head.val == val) {
return head.next;
}
while (head != null) {
if (head.next == null) {
break;
}
if (head.next.val == val) {
head.next = head.next.next;
}
head = head.next;
}
return res;
}
}
方法二：递归
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) {
return null;
}
if (head.val == val) {
return head.next;
} else {
head.next = deleteNode(head.next, val);
}
return head;
}
}
方法三：双指针
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head.val == val) {
return head.next;
}
ListNode pre = head, cur = head.next;
while (cur != null && cur.val != val) {
pre = cur;
cur = cur.next;
}
if (cur != null) {
pre.next = cur.next;
}
return head;
}
}
16. 用两个栈实现队列
剑指 Offer 09. 用两个栈实现队列
2022.7.20
class CQueue {
private Stack<Integer> s1, s2;
public CQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void appendTail(int value) {
s1.push(value);
}
public int deleteHead() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
if (s2.size() == 0) {
return -1;
}
return s2.pop();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
17. 求1+2+…+n
剑指 Offer 64. 求1+2+…+n
2022.7.20
class Solution {
int res = 0;
public int sumNums(int n) {
if (n == 1) {
return 1;
}
res = n + sumNums(n - 1);
return res;
}
}
树->遍历框架
链表->双指针、虚拟头节点
注意边界
18. 平衡二叉树
剑指 Offer 55 – II. 平衡二叉树
2022.7.21
class Solution {
public boolean isBalanced(TreeNode root) {
maxDeepth(root);
return isBalancedTree;
}
boolean isBalancedTree = true;
int maxDeepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMaxDeepth = maxDeepth(root.left);
int rightMaxDeepth = maxDeepth(root.right);
if (Math.abs(leftMaxDeepth - rightMaxDeepth) > 1) {
isBalancedTree = false;
}
return 1 + Math.max(leftMaxDeepth, rightMaxDeepth);
}
}
19. 替换空格
剑指 Offer 05. 替换空格
2022.7.21
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') {
sb.append("%20");
}else {
sb.append(c);
}
}
return sb.toString();
}
}
20. 二叉搜索树的第k大节点
剑指 Offer 54. 二叉搜索树的第k大节点
2022.7.21
力扣算法 Java 刷题笔记【二叉搜索树 BST 篇】hot100（一）BST 中序遍历的应用: BST 第 K 小的元素（中等）二叉搜索树转化累加树（中等）3
class Solution {
public int kthLargest(TreeNode root, int k) {
traverse(root, k);
return res;
}
int i = 0, res = 0;
void traverse(TreeNode root, int k) {
if (root == null) {
return;
}
traverse(root.right, k);
i++;
if (i == k) {
res = root.val;
return;
}
traverse(root.left, k);
}
}
21. 链表中倒数第k个节点
剑指 Offer 22. 链表中倒数第k个节点
2022.7.21
力扣算法 Java 刷题笔记【链表篇】hot100（一）合并 K 个升序链表（困难） 删除链表的倒数第 N 个结点（中等） 7
方法一：栈
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
Stack<ListNode> sk = new Stack<>();
while (head != null) {
sk.push(head);
head = head.next;
}
for (int i = 1; i < k; i++) {
sk.pop();
}
return sk.pop();
}
}
方法二：双指针
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode slow = head, fast = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
22. 数组中重复的数字
剑指 Offer 03. 数组中重复的数字
2022.7.21
哈希表：时间 O(n) 空间 O(n) 我们更关注时间复杂度
class Solution {
public int findRepeatNumber(int[] nums) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int val = nums[i];
hashMap.put(val, hashMap.getOrDefault(val, 0) + 1);
if (hashMap.get(val) > 1) {
return val;
}
}
return -1;
}
}
最优解：
下标法
：时间 O(n) 空间 O(1) —> 看到 0~n-1 联想下标法
下标法：通过不停交换元素，使得元素和它所对应的下标相等： nums[i] = i
public int findRepeatNumber(int[] nums) {
// 遍历数组
for(int i = 0; i < nums.length; i++) {
// 之所以用while，是因为交换之后，改位置的元素任然没有在正确的位置
while(i != nums[i]){
if(nums[i] == nums[nums[i]]){
return nums[i];
}
// nums[i] 正确的位置在 nums[nums[i]]
int k = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = k;
}
}
return -1;
}
23. 二维数组中的查找
剑指 Offer 04. 二维数组中的查找
2022.7.21
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix.length == 0) { //matrix == null || matrix.length <= 0 || matrix[0].length <= 0
return false;
}
int n = matrix.length, m = matrix[0].length;
int row = 0, col = m - 1;
while (row < n && col >= 0) {
if (matrix[row][col] > target) {
col--;
} else if (matrix[row][col] < target) {
row++;
} else {
return true;
}
}
return false;
}
}
24. 前序和中序遍历->构建二叉树（重建二叉树）
剑指 Offer 07. 重建二叉树
2022.7.22
力扣算法 Java 刷题笔记【二叉树篇】hot100（二）最大二叉树（中等） 从前序与中序遍历序列构造二叉树（中等） 3
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int index = 0, rootVal = preorder[preStart];
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd,
inorder, index + 1, inEnd);
return root;
}
}
25. 打印从1到最大的n位数
剑指 Offer 17. 打印从1到最大的n位数
2022.7.22
class Solution {
public int[] printNumbers(int n) {
int max = (int)Math.pow(10, n);
int[] res = new int[max - 1];
for (int i = 0; i < max - 1; i++) {
res[i] = i + 1;
}
return res;
}
}
大数问题：
26. 二进制中1的个数
剑指 Offer 15. 二进制中1的个数
2022.7.24
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
}
27. 机器人的运动范围
剑指 Offer 13. 机器人的运动范围
2022.7.24
力扣算法 Java 刷题笔记【DFS篇】hot100（三）岛屿问题（一） 3
力扣算法 Java 刷题笔记【DFS篇】hot100（三）岛屿问题（二） 2|1
class Solution {
int res = 0;
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
dfs(m, n, 0, 0, k, visited);
return res;
}
void dfs(int m, int n, int i, int j, int k, boolean[][] visited) {
if (i < 0 || j < 0 || i > m - 1 || j > n - 1) {
return;
}
if (i / 10 + i % 10 + j / 10 + j % 10 > k) {
return;
}
if (visited[i][j] == true) {
return;
}
res++;
visited[i][j] = true;
dfs(m, n, i - 1, j, k, visited);
dfs(m, n, i + 1, j, k, visited);
dfs(m, n, i, j - 1, k, visited);
dfs(m, n, i, j + 1, k, visited);
}
}
28. 树的子结构
剑指 Offer 26. 树的子结构
2022.7.24
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) {
return A == B;
}
if (A.val == B.val && check(A, B)) {
return true;
}
return isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
boolean check(TreeNode A, TreeNode B) {
if (B == null) {
return true;
}
if (A == null && B != null) {
return false;
}
if (A.val != B.val) {
return false;
}
return check(A.left, B.left) && check(A.right, B.right);
}
}
29. 调整数组顺序使奇数位于偶数前面
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
2022.7.24
class Solution {
public int[] exchange(int[] nums) {
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] % 2 == 1) {
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
fast++;
}
return nums;
}
}
30. 二叉树层序遍历
剑指 Offer 32 – II. 从上到下打印二叉树 II
2022.7.25
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
List<Integer> temp = new LinkedList<>();
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
temp.add(cur.val);
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
res.add(temp);
}
return res;
}
}
31. 和为s的两个数字
剑指 Offer 57. 和为s的两个数字
2022.7.25
class Solution {
public int[] twoSum(int[] nums, int target) {
int slow = 0, fast = nums.length - 1;
while (slow < fast) {
int sum = nums[slow] + nums[fast];
if (sum < target) {
slow++;
}
if (sum > target) {
fast--;
}
if (sum == target) {
return new int[]{nums[slow], nums[fast]};
}
}
return null;
}
}
32. 数值的整数次方
剑指 Offer 16. 数值的整数次方
2022.7.25
class Solution {
public double myPow(double x, int n) {
if (n == 0) {
return 1;
}
if (n == Integer.MIN_VALUE) {
return myPow(1 / x, -(n + 1)) / x;
}
if (n < 0) {
return myPow(1 / x, -n);
}
if (n % 2 == 1) {
return myPow(x, n - 1) * x;
}
if (n % 2 == 0) {
double sub = myPow(x, n / 2);
return sub * sub;
}
return -1;
// if (n % 2 == 1) {
// return myPow(x, n - 1) * x;
// } else {
// double sub = myPow(x, n / 2);
// return sub * sub;
// }
}
}
33. 从上到下打印二叉树
剑指 Offer 32 – I. 从上到下打印二叉树
2022.7.25
class Solution {
public int[] levelOrder(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
if (root == null) {
return new int[0];
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
res.add(cur.val);
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}
// return res.stream().mapToInt(Integer::valueOf).toArray();
int[] ans = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
ans[i] = res.get(i);
}
return ans;
}
}
34. 从上到下打印二叉树 III
剑指 Offer 32 – III. 从上到下打印二叉树 III
2022.7.25
双端对列
复杂情况还是用笔画一画，更清晰->辅助分析
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
Deque<TreeNode> dq = new LinkedList<>();
dq.offer(root);
int count = 0;
while (!dq.isEmpty()) {
List<Integer> temp = new LinkedList<>();
int sz = dq.size();
if (count % 2 == 0) {
for (int i = 0; i < sz; i++) {
TreeNode cur = dq.pollFirst();
temp.add(cur.val);
if (cur.left != null) {
dq.offerLast(cur.left);
}
if (cur.right != null) {
dq.offerLast(cur.right);
}
}
}
if (count % 2 == 1) {
for (int i = 0; i < sz; i++) {
TreeNode curr = dq.pollLast();
temp.add(curr.val);
if (curr.right != null) {
dq.offerFirst(curr.right);
}
if (curr.left != null) {
dq.offerFirst(curr.left);
}
}
}
count++;
res.add(temp);
}
return res;
}
}
35. 包含min函数的栈
剑指 Offer 30. 包含min函数的栈
2022.7.26
class MinStack {
Stack<Integer> sk = new Stack<>();
Stack<Integer> minStack = new Stack<>();
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
sk.push(x);
}
public void pop() {
if (minStack.peek().equals(sk.peek())) {
minStack.pop();
}
sk.pop();
}
public int top() {
return sk.peek();
}
public int min() {
return minStack.peek();
}
}
36. 字符串的排列
剑指 Offer 38. 字符串的排列
2022.7.26
class Solution {
public String[] permutation(String s) {
permutaUnique(s.toCharArray());
String[] arr = new String[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
List<String> res = new LinkedList<>();
boolean[] used;
StringBuilder track = new StringBuilder();
public List<String> permutaUnique(char[] nums) {
Arrays.sort(nums);
used = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(char[] nums) {
if (track.length() == nums.length) {
res.add(track.toString());
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i] == true) {
continue;
}
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
track.append(nums[i]);
used[i] = true;
backtrack(nums);
track.deleteCharAt(track.length() - 1);
used[i] = false;
}
}
}
37. 二叉搜索树与双向链表
剑指 Offer 36. 二叉搜索树与双向链表
2022.7.26
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
traverse(root);
head.left = pre;
pre.right = head;
return head;
}
void traverse(Node root) {
if (root == null) {
return;
}
traverse(root.left);
if (pre == null) {
head = root;
} else {
pre.right = root;
root.left = pre;
}
pre = root;
traverse(root.right);
}
}
38. 0～n-1中缺失的数字
剑指 Offer 53 – II. 0～n-1中缺失的数字
2022.7.26
力扣算法 Java 刷题笔记【数组篇 二分搜索】hot100（一）二分查找、搜索插入位置、在排序数组中查找元素的第一个和最后一个位置 3
class Solution {
public int missingNumber(int[] nums) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > mid) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
39. 旋转数组的最小数字【高频】
剑指 Offer 11. 旋转数组的最小数字
2022.7.26
class Solution {
public int minArray(int[] numbers) {
int l = 0, r = numbers.length - 1;
while (l < r) {
if (numbers[l] < numbers[r]) {
return numbers[l];
}
int mid = l + (r - l) / 2;
if (numbers[mid] > numbers[l]) {
l = mid + 1;
} else if (numbers[mid] < numbers[l]) {
r = mid;
} else {
l++;
}
}
return numbers[l];
}
}
40. 不用加减乘除做加法
剑指 Offer 65. 不用加减乘除做加法
2022.7.27
class Solution {
public int add(int a, int b) {
if(a == 0 || b == 0) {
return a == 0 ? b : a;
}
// 设 a = 1001
// 设 b = 0101
// 求和 1100
int sum = a ^ b;
// 进位 0001 << 1 = 0010
int carry = (a & b) << 1;
// add(1100, 0010)
return add(sum, carry);
}
}
41. 剪绳子
剑指 Offer 14- I. 剪绳子
2022.7.28
class Solution {
public int cuttingRope(int n) {
if (n <= 2) {
return 1;
}
if (n == 3) {
return 2;
}
if (n == 4) {
return 4;
}
int res = n / 3;
int mod = n % 3;
if (n % 3 == 0) {
return (int)Math.pow(3, res);
} else if (n % 3 == 1) {
return (int)(Math.pow(3, res - 1) * 4);
} else {
return (int)(Math.pow(3, res) * 2);
}
}
}
42. 剪绳子 II
剑指 Offer 14- II. 剪绳子 II
2022.7.28
class Solution {
public int cuttingRope(int n) {
if (n < 4) {
return n - 1;
}
int res = n / 3;
int mod = n % 3;
int p = 1000000007;
if (mod == 0) {
return (int)(pow(3, res));
} else if (mod == 1) {
return (int)(pow(3, res - 1) * 4 % p);
} else {
return (int)(pow(3, res) * 2 % p);
}
}
long pow (int a, int n) {
long sum = 1;
int p = 1000000007;
for (int i = 0; i < n; i++) {
sum = sum * a % p;
}
return sum;
}
}
43. 二叉搜索树的后序遍历序列
剑指 Offer 33. 二叉搜索树的后序遍历序列
2022.7.28
class Solution {
public boolean verifyPostorder(int[] postorder) {
return verify(postorder, 0, postorder.length - 1);
}
boolean verify(int[] postorder, int start, int end) {
if (start >= end) {
return true;
}
int p = start;
while (postorder[p] < postorder[end]) {
p++;
}
int m = p;
while (postorder[m] > postorder[end]) {
m++;
}
return m == end && verify(postorder, start, p - 1) && verify(postorder, p, m - 1);
}
}
44. 第一个只出现一次的字符
剑指 Offer 50. 第一个只出现一次的字符
2022.7.28
class Solution {
public char firstUniqChar(String s) {
int[] nums = new int[26];
for (int i = 0; i < s.length(); i++) {
nums[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (nums[c - 'a'] == 1) {
return c;
}
}
return ' ';
}
}
45. 二叉树中和为某一值的路径
剑指 Offer 34. 二叉树中和为某一值的路径
2022.7.28
class Solution {
List<List<Integer>> res = new LinkedList<>();
// LinkedList<Integer> path = new LinkedList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
dfs(root, target);
return res;
}
void dfs(TreeNode root, int sum) {
if (root == null) {
return;
}
path.add(root.val);
sum = sum - root.val;
if (root.left == null && root.right == null && sum == 0) {
res.add(new LinkedList<>(path));
}
dfs(root.left, sum);
dfs(root.right, sum);
// path.removeLast();
path.remove(path.size() - 1);
}
}
46. 在排序数组中查找数字 I
剑指 Offer 53 – I. 在排序数组中查找数字 I
2022.7.29
力扣算法 Java 刷题笔记【数组篇 二分搜索】hot100（一）二分查找、搜索插入位置、在排序数组中查找元素的第一个和最后一个位置 3
class Solution {
public int search(int[] nums, int target) {
int left_index = left_bound(nums, target);
if (left_index == -1) {
return 0;
}
int right_index = right_bound(nums, target);
return right_index - left_index + 1;
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
right = mid - 1;
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
left = mid + 1;
}
}
if (right < 0 || nums[right] != target) {
return -1;
}
return right;
}
}
47. 最小的k个数
剑指 Offer 40. 最小的k个数
2022.7.29
方法一：优先队列
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
int[] res = new int[k];
int i = 0;
for (int a : arr) {
pq.offer(a);
if (pq.size() > arr.length - k) {
res[i] = pq.poll();
i++;
}
}
return res;
}
}
******** 另一种写法
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 默认是小根堆，实现大根堆需要重写一下比较器。
Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
for (int num: arr) {
if (pq.size() < k) {
pq.offer(num);
} else if (num < pq.peek()) {
pq.poll();
pq.offer(num);
}
}
int[] res = new int[pq.size()];
int idx = 0;
for(int num: pq) {
res[idx++] = num;
}
return res;
}
}
方法二：快排
48. 数组中出现次数超过一半的数字
剑指 Offer 39. 数组中出现次数超过一半的数字
2022.7.29
摩尔投票法（对拼消耗）
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int candicate = 0;
for (int num : nums) {
if (count == 0) {
candicate = num;
}
count += candicate == num ? 1 : -1;
}
return candicate;
}
}
49. 矩阵中的路径
剑指 Offer 12. 矩阵中的路径
2022.7.31
class Solution {
int m = 0, n = 0, len = 0;
public boolean exist(char[][] board, String word) {
m = board.length;
n = board[0].length;
len = word.length();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, i, j, word, 0)) {
return true;
}
}
}
return false;
}
boolean dfs(char[][] board, int i, int j, String word, int k) {
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(k)) {
return false;
}
if (k == len - 1) {
return true;
}
board[i][j] = '\n';
boolean res = dfs(board, i - 1, j, word, k + 1) ||
dfs(board, i + 1, j, word, k + 1) ||
dfs(board, i, j - 1, word, k + 1) ||
dfs(board, i, j + 1, word, k + 1);
board[i][j] = word.charAt(k);
return res;
}
}
50. 正则表达式匹配
剑指 Offer 19. 正则表达式匹配
2022.7.31
https://www.bilibili.com/video/BV1jd4y1U7kE/?spm_id_from=pageDriver&vd_source=28639105a09afd80125a0dc2b769abba
https://www.iamshuaidi.com/275.html
https://offer.iamshuaidi.com/84.html
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1]; // 默认是 false
dp[0][0] = true;
for (int j = 2; j <= m; j++) {
if (p.charAt(j - 1) == '*') { // * 可以等于 0
dp[0][j] = dp[0][j - 2];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (p.charAt(j - 1) != '*') {
if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = false;
}
} else { // 当 j = 1 时 由于第一位不可能为 '*' 故不会进入这个逻辑， j - 2 就不会越界
if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
dp[i][j] = dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 1] || dp[i - 1][j];
}
}
}
}
return dp[n][m];
}
}
51. 左旋转字符串
剑指 Offer 58 – II. 左旋转字符串
2022.7.31
最优解
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
int len = s.length();
for (int i = n; i < len + n; i++) {
sb.append(s.charAt(i % len));
}
return sb.toString();
}
}
方法一：
class Solution {
public String reverseLeftWords(String s, int n) {
int len = s.length();
StringBuilder sb = new StringBuilder(s);
reverseString(sb,0,n-1);
reverseString(sb,n,len-1);
return sb.reverse().toString();
}
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
}
方法二：
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n) + s.substring(0, n);
}
}
52. 和为s的连续正数序列
剑指 Offer 57 – II. 和为s的连续正数序列
2022.7.31
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> list = new LinkedList<>();
for (int l = 1, r = 1, sum = 0; r < target; r++) {
sum += r;
while (sum > target) {
sum -= l;
l++;
}
if (sum == target) {
int[] temp = new int[r - l + 1];
for (int i = 0; i < temp.length; i++) {
temp[i] = l + i;
}
list.add(temp);
}
}
return list.toArray(new int[list.size()][]); //初始化一个能存list.size()个一维数组的二维数组
/*
int[][] ans = new int[list.size()][];
for (int i = 0; i < list.size(); i++) {
ans[i] = list.get(i);
}
return ans;
*/
}
}
53. 栈的压入、弹出序列
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
if (pushed == null || pushed.length == 0) {
return true;
}
Stack<Integer> sk = new Stack();
int k = 0;
for (int i = 0; i < pushed.length; i++) {
sk.push(pushed[i]);
while (!sk.isEmpty() && sk.peek() == popped[k]) {
sk.pop();
k++;
}
}
return sk.isEmpty();
}
}
54.复杂链表的复制
剑指 Offer 35. 复杂链表的复制
2022.8.9
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node cur = head;
while (cur != null) {
Node newNode = cur.next;
cur.next = new Node(cur.val);
cur.next.next = newNode;
cur = newNode;
}
cur = head;
while (cur != null) {
cur.next.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
cur = head;
Node headNode = cur.next;
Node curNode = cur.next;
while (cur != null) {
cur.next = cur.next.next;
cur = cur.next;
curNode.next = cur == null ? null : cur.next;
curNode = curNode.next;
}
return headNode;
}
}
55. 翻转单词顺序
剑指 Offer 58 – I. 翻转单词顺序
2022.8.9
最优解
class Solution {
public String reverseWords(String s) {
if (s.length() == 0 || s == null) {
return s;
}
s = s.trim();
StringBuilder sb = new StringBuilder();
int i = s.length() - 1, j = i;
while (i >= 0) {
while (i >= 0 && s.charAt(i) != ' ') i--;
sb.append(s.substring(i + 1, j + 1) + " ");
while (i >= 0 && s.charAt(i) == ' ') i--;
j = i;
}
return sb.toString().trim();
}
}
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c != ' ') {
sb.append(c);
} else if (!sb.isEmpty() && sb.charAt(sb.length() - 1) != ' ') {
sb.append(' ');
}
}
if (sb.length() > 1 && sb.charAt(sb.length() - 1) == ' ') {
sb.deleteCharAt(sb.length() - 1);
}
reverse(sb, 0, sb.length() - 1);
for (int i = 0; i < sb.length(); ) {
for (int j = i; j < sb.length(); j++) {
if (j + 1 == sb.length() || sb.charAt(j + 1) == ' ') {
reverse(sb, i, j);
i = j + 2;
break;
}
}
}
return sb.toString();
}
void reverse(StringBuilder sb, int i, int j) {
while (i < j) {
char temp = sb.charAt(i);
sb.setCharAt(i, sb.charAt(j));
sb.setCharAt(j, temp);
i++;
j--;
}
}
}
56. 丑数
剑指 Offer 49. 丑数
2022.8.10
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
int a = 1, b = 1, c = 1;
for (int i = 2; i < n + 1; i++) {
dp[i] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
if (dp[a] * 2 == dp[i]) {
a++;
}
if (dp[b] * 3 == dp[i]) {
b++;
}
if (dp[c] * 5 == dp[i]) {
c++;
}
}
return dp[n];
}
}
57. 构建乘积数组
剑指 Offer 66. 构建乘积数组
2022.8.10
// 前缀积
class Solution {
public int[] constructArr(int[] a) {
if (a.length == 0) {
return new int[0];
}
int[] prefix = new int[a.length];
prefix[0] = a[0];
for (int i = 1; i < a.length; i++) {
prefix[i] = prefix[i - 1] * a[i];
}
int[] postfix = new int[a.length];
postfix[a.length - 1] = a[a.length - 1];
for (int j = a.length - 2; j >= 0; j--) {
postfix[j] = postfix[j + 1] * a[j];
}
int[] b = new int[a.length];
b[0] = postfix[1];
b[b.length - 1] = prefix[b.length - 2];
for (int k = 1; k < b.length - 1; k++) {
b[k] = prefix[k - 1] * postfix[k + 1];
}
return b;
}
}
58. 扑克牌中的顺子
剑指 Offer 61. 扑克牌中的顺子
2022.8.10
方法一
//集合 Set + 遍历
class Solution {
public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0, min = 14;
for(int num : nums) {
if(num == 0) continue; // 跳过大小王
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if(repeat.contains(num)) return false; // 若有重复，提前返回 false
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
方法二
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int joker = 0;
for (int i = 0; i < 4; i++) {
if (nums[i] == 0) {
joker++;
} else if ( nums[i] == nums[i + 1]) {
return false;
}
}
return nums[4] - nums[joker] < 5;
}
}
59. 数组中的逆序对
剑指 Offer 51. 数组中的逆序对
2022.8.22
// 归并排序（也可以用冒泡，但是冒泡时间复杂度太高）
class Solution {
public int reversePairs(int[] nums) {
int[] temp = new int[nums.length];
return mergeSort(nums, temp, 0, nums.length - 1);
}
int mergeSort(int[] nums, int[] temp, int lo, int hi) {
if (lo >= hi) {
return 0;
}
int middle = (hi - lo) / 2 + lo;
int x1 = mergeSort(nums, temp, lo, middle);
int x2 = mergeSort(nums, temp, middle + 1, hi);
int x3 = merge(nums, temp, middle, lo, hi);
return x1 + x2 + x3;
}
int merge(int[] nums, int[] temp, int middle, int lo, int hi) {
int count = 0;
int i = lo, j = middle + 1;
for (int k = lo; k <= hi; k++) {
if (i > middle) {
temp[k] = nums[j++];
} else if (j > hi) {
temp[k] = nums[i++];
} else if (nums[i] <= nums[j]) { // 边界条件
temp[k] = nums[i++];
} else {
count += middle + 1 - i;
temp[k] = nums[j++];
}
}
for (int p = lo; p <= hi; p++) {
nums[p] = temp[p];
}
return count;
}
}
60. 礼物的最大价值
剑指 Offer 47. 礼物的最大价值
2022.8.22
// 二维数组
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
优化
// 一维数组:因为只用到上一行
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] dp = new int[n];
dp[0] = grid[0][0];
for (int j = 1; j < n; j++) {
dp[j] = dp[j - 1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
dp[0] = dp[0] + grid[i][0];
for (int j = 1; j < n; j++) {
dp[j] = Math.max(dp[j - 1], dp[j]) + grid[i][j];
}
}
return dp[n - 1];
}
}
61.把数组排成最小的数
剑指 Offer 45. 把数组排成最小的数
2022.8.22
// 快排 + 字符->字典序
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
quickSort(strs, 0, nums.length - 1);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < strs.length; i++) {
sb.append(strs[i]);
}
return sb.toString();
}
void quickSort(String[] strs, int lo, int hi) {
if (lo >= hi) {
return;
}
int i = partition(strs, lo, hi);
quickSort(strs, lo, i - 1);
quickSort(strs, i + 1, hi);
}
int partition(String[] strs, int lo, int hi) {
String pivot = strs[lo];
int i = lo + 1, j = hi;
while (i <= j) {
while (j > lo && (strs[j] + pivot).compareTo(pivot + strs[j]) >= 0) {
j--;
}
while (i < hi && (strs[i] + pivot).compareTo(pivot + strs[i]) <= 0) {
i++;
}
if (i >= j) {
break;
}
swap(strs, i, j);
}
swap(strs, lo, j);
return j;
}
void swap(String[] strs, int i, int j) {
String temp = strs[i];
strs[i] = strs[j];
strs[j] = temp;
}
}
62.序列化二叉树
剑指 Offer 37. 序列化二叉树
2022.8.23
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode t = q.poll();
if (t != null) {
q.add(t.left);
q.add(t.right);
sb.append(t.val + ",");
} else {
sb.append("null,");
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() <= 0) {
return null;
}
String[] s = data.split(",");
Queue<TreeNode> q = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(s[0]));
q.offer(root);
int i = 1;
while (!q.isEmpty()) {
TreeNode t = q.poll();
// 构建左节点
if (!s[i].equals("null")) {
TreeNode left = new TreeNode(Integer.parseInt(s[i]));
t.left = left;
q.offer(left);
}
i++;
// 构建右节点
if (!s[i].equals("null")) {
TreeNode right = new TreeNode(Integer.parseInt(s[i]));
t.right = right;
q.offer(right);
}
i++;
}
return root;
}
}
HOT
1. 每日温度【高频】
739. 每日温度
2022.7.27
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Stack<Integer> sk = new Stack<>(); //单调栈
for (int i = temperatures.length - 1; i >= 0; i--) {
while (!sk.isEmpty() && temperatures[sk.peek()] <= temperatures[i]) {
sk.pop();
}
res[i] = sk.isEmpty() ? 0 : sk.peek() - i;
sk.push(i);
}
return res;
}
}
2. N数之和
15. 三数之和
2022.7.27
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
return nSum(nums, 3, 0, 0);
}
List<List<Integer>> nSum(int[] nums, int n, int start, int target) {
List<List<Integer>> res = new LinkedList<>();
if (n < 2 || nums.length < n) {
return res;
}
if (n == 2) {
int l = start, r = nums.length - 1;
while (l < r) {
int left = nums[l], right = nums[r];
int sum = left + right;
if (sum > target) {
r--;
}
if (sum < target) {
l++;
}
if (sum == target) {
res.add(Arrays.asList(left, right)); // Arrays.asList()
while (l < r && nums[l] == left) { // 剪枝
l++;
}
while (l < r && nums[r] == right) {
r--;
}
}
}
}
if (n > 2) {
for (int i = start; i < nums.length; i++) {
List<List<Integer>> tuples = nSum(nums, n - 1, i + 1, target - nums[i]);
for (List<Integer> tuple : tuples) {
List<Integer> t = new LinkedList<>(tuple); // 注意实例化
t.add(nums[i]);
res.add(t);
}
while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
i++;
}
}
}
return res;
}
}
3. 复原 IP 地址
93. 复原 IP 地址
2022.8.5
class Solution {
static final int SEG_COUNT = 4;
List<String> ans = new ArrayList<String>();
int[] segments = new int[SEG_COUNT];
public List<String> restoreIpAddresses(String s) {
dfs(s, 0, 0);
return ans;
}
public void dfs(String s, int segId, int segStart) {
// 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
if (segId == SEG_COUNT) {
if (segStart == s.length()) {
StringBuffer ipAddr = new StringBuffer();
for (int i = 0; i < SEG_COUNT; i++) {
ipAddr.append(segments[i]);
if (i != SEG_COUNT - 1) {
ipAddr.append('.');
}
}
ans.add(ipAddr.toString());
}
return;
}
// 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
if (segStart == s.length()) {
return;
}
// 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
if (s.charAt(segStart) == '0') {
segments[segId] = 0;
dfs(s, segId + 1, segStart + 1);
}
// 一般情况，枚举每一种可能性并递归
int addr = 0;
for (int segEnd = segStart; segEnd < s.length(); segEnd++) {
addr = addr * 10 + (s.charAt(segEnd) - '0');
if (addr > 0 && addr <= 0xFF) {
segments[segId] = addr;
dfs(s, segId + 1, segEnd + 1);
} else {
break;
}
}
}
}
4. 简化路径【华子】
71. 简化路径
2022.7.27
class Solution {
public String simplifyPath(String path) {
String[] parts = path.split("/");
Stack<String> stk = new Stack<>();
// 借助栈计算最终的文件夹路径
for (String part : parts) {
if (part.isEmpty() || part.equals(".")) {
continue;
}
if (part.equals("..")) {
if (!stk.isEmpty()) stk.pop();
continue;
}
stk.push(part);
}
// 栈中存储的文件夹组成路径
String res = "";
while (!stk.isEmpty()) {
res = "/" + stk.pop() + res;
}
return res.isEmpty() ? "/" : res;
}
}
5. 接雨水
42. 接雨水
2022.8.5
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int left_max = 0, right_max = 0;
int res = 0;
while (left < right) {
left_max = Math.max(left_max, height[left]);
right_max = Math.max(right_max, height[right]);
if (left_max < right_max) {
res += left_max - height[left];
left++;
} else {
res += right_max - height[right];
right--;
}
}
return res;
}
}
6. 轮转数组
189. 轮转数组
2022.8.5
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);
}
private void reverse(int[] nums, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
7. 重排链表
143. 重排链表
2022.8.6
class Solution {
public void reorderList(ListNode head) {
Deque<ListNode> dq = new LinkedList<>();
ListNode cur = head;
while (cur != null) {
dq.addLast(cur);
cur = cur.next;
}
while (!dq.isEmpty()) {
if (cur == null) {
cur = dq.pollFirst();
} else {
cur.next = dq.pollFirst();
cur = cur.next;
}
cur.next = dq.pollLast();
cur = cur.next;
}
if (cur != null) {
cur.next = null;
}
}
}
8. 只出现一次的数字
136. 只出现一次的数字
2022.8.6
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int n : nums) {
res ^= n;
}
return res;
}
}
9. 最长回文子串
5. 最长回文子串
2022.8.7
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
String String1 = palindrom(s, i, i + 1);
String String2 = palindrom(s, i, i);
res = res.length() > String1.length() ? res : String1;
res = res.length() >String2.length() ? res : String2;
}
return res;
}
String palindrom(String s, int start, int end) {
while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
start--;
end++;
}
return s.substring(start + 1, end);
}
}
10. 回文链表
234. 回文链表
2022.8.7
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) {
slow = slow.next;
}
ListNode newNode = reverse(slow);
while (newNode != null) {
if (newNode.val != head.val) {
return false;
}
newNode = newNode.next;
head = head.next;
}
return true;
}
ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
}
11. 相交链表
160. 相交链表
2022.8.7
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
if (a == null) {
a = headB;
} else {
a = a.next;
}
if (b == null) {
b = headA;
} else {
b = b.next;
}
}
return a;
}
}
12. 数组中的第 K 个最大元素（中等）
215. 数组中的第K个最大元素
2022.8.7
方法一：二叉堆（优先队列）【推荐】
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int e : nums) {
pq.offer(e);
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
}
方法二：快排
class Solution {
public int findKthLargest(int[] nums, int k) {
shuffle(nums);
int lo = 0, hi = nums.length - 1;
k = nums.length - k;
while (lo <= hi) {
int p = partition(nums, lo, hi);
if (p < k) {
lo = p + 1;
} else if (p > k) {
hi = p - 1;
} else {
return nums[p];
}
}
return -1;
}
// void sort(int[] nums, int lo, int hi) {
// if (lo >= hi) {
// return;
// }
// int p = partition(nums, lo, hi);
// sort(nums, lo, p - 1);
// sort(nums, p + 1, hi);
// }
int partition(int[] nums, int lo, int hi) {
int pivot = nums[lo];
int i = lo + 1, j = hi;
while (i <= j) {
while (j > lo && nums[j] > pivot) {
j--;
}
while (i < hi && nums[i] <= pivot) {
i++;
}
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, lo, j);
return j;
}
void shuffle(int[] nums) {
Random rand = new Random();
int n = nums.length;
for (int i = 0; i < n; i++) {
swap(nums, i, i + rand.nextInt(n - i));
}
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
13. K 个一组翻转链表
25. K 个一组翻转链表
2022.8.7
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 新建两个结点
ListNode a = head, b = head;
for (int i = 0; i < k; i++) {
if (b == null) {
return a;
}
b = b.next;
}
ListNode newNode = reverse(a, b);
a.next = reverseKGroup(b, k);
return newNode;
}
ListNode reverse(ListNode a, ListNode b) {
ListNode pre = null, cur = a, nxt = a;
// 循环条件记得改为 b
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
14. 不同路径
62. 不同路径
2022.8.8
class Solution {
int[][] memo = null;
public int uniquePaths(int m, int n) {
memo = new int[m][n];
return dp(m - 1, n - 1);
}
int dp(int i, int j) {
if (i == 0 || j == 0) {
return 1;
}
if (memo[i][j] != 0) {
return memo[i][j];
}
memo[i][j] = dp(i - 1, j) + dp(i, j - 1);
return memo[i][j];
}
}
15. 零钱兑换
322. 零钱兑换
2022.8.8
public class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 这里我们还得给dp[i]赋予一个尽量大的初始值
for(int i = 0; i <= amount; i++) {
dp[i] = amount + 1;
}
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
// 计算机 dp[i] 所需要的最少硬币数量
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
16. LRU 缓存
146. LRU 缓存
2022.8.8
class LRUCache {
int cap;
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
// 将 key 变为最近使用
makeRecently(key);
return cache.get(key);
}
public void put(int key, int val) {
if (cache.containsKey(key)) {
// 修改 key 的值
cache.put(key, val);
// 将 key 变为最近使用
makeRecently(key);
return;
}
if (cache.size() >= this.cap) {
// 链表头部就是最久未使用的 key
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
// 将新的 key 添加链表尾部
cache.put(key, val);
}
private void makeRecently(int key) {
int val = cache.get(key);
// 删除 key，重新插入到队尾
cache.remove(key);
cache.put(key, val);
}
}
// 详细解析参见：
// https://labuladong.github.io/article/?qno=146
17. 打家劫舍
class Solution {
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
int [] dp = new int[nums.length];
dp[0] = nums[0];
// 每次做数组判定时都需要做数组边界判定，防止越界
if(nums.length < 2)
return nums[0];
dp[1] = (nums[0]>nums[1]) ? nums[0] : nums[1];
for(int i = 2; i<nums.length; i++)
dp[i] = ((nums[i] + dp[i-2]) > dp[i-1]) ? (nums[i]+dp[i-2]) : dp[i-1];
return dp[nums.length-1];
}
}
18. 二叉树的右视图
class Solution {
List<Integer> res = new ArrayList<>();
// 记录递归的层数
int depth = 0;
public List<Integer> rightSideView(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历函数
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序遍历位置
depth++;
if (res.size() < depth) {
// 这一层还没有记录值
// 说明 root 就是右侧视图的第一个节点
res.add(root.val);
}
// 注意，这里反过来，先遍历右子树再遍历左子树
// 这样首先遍历的一定是右侧节点
traverse(root.right);
traverse(root.left);
// 后序遍历位置
depth--;
}
}
19. 二叉树的完全性检验
class Solution {
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// 遍历完所有非空节点时变成 true
boolean end = false;
// while 循环控制从上向下一层层遍历
while (!q.isEmpty()) {
int sz = q.size();
// for 循环控制每一层从左向右遍历
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
if (cur == null) {
// 第一次遇到 null 时 end 变成 true
// 如果之后的所有节点都是 null，则说明是完全二叉树
end = true;
} else {
if (end) {
// end 为 true 时遇到非空节点说明不是完全二叉树
return false;
}
// 将下一层节点放入队列，不用判断是否非空
q.offer(cur.left);
q.offer(cur.right);
}
}
}
return true;
}
}
20. 航班预订统计【华子】
1109. 航班预订统计
2022.8.10
写法一：
// 差分数组
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] res = new int[n];
Difference df = new Difference(res);
for (int[] booking : bookings) {
int i = booking[0] - 1;
int j = booking[1] - 1;
int val = booking[2];
df.increment(i, j, val);
}
return df.result();
}
class Difference {
private int[] diff;
public Difference(int[] nums) {
assert nums.length > 0;
diff = new int[nums.length];
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
public int[] result() {
int[] res = new int[diff.length];
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}
}
写法二：
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] res = new int[n];
int[] diff = new int[n];
for (int[] booking : bookings) {
int i = booking[0] - 1;
int j = booking[1] - 1;
int val = booking[2];
for (int k = i; k <= j; k++) {
diff[k] += val;
}
}
return diff;
}
写法三:
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] res = new int[n];
int[] diff = new int[n];
for (int[] booking : bookings) {
int i = booking[0] - 1;
int j = booking[1] - 1;
int val = booking[2];
diff[i] += val;
if (j + 1 < n) {
diff[j + 1] -= val;
}
}
res[0] = diff[0];
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
排序
1. 快速排序
2022/2 – 7/27
算法思想：以最左边的数字为基准数，两个哨兵分别位于数组的左右两端，右端的先出发，遇到比基准数小或相等的就停下，此时左边哨兵出发，遇到比基准数大的的就停下，然后交换两个数字的，重复这个过程，直到两个哨兵相遇，此时将相遇时的数字与基准数交换，这样基准数左边都是比基准数小或相等的，右边都是比基准数大的，分别在左右两部分做递归操作即可；
void sort(int[] nums, int lo, int hi) {
if (lo >= hi) {
return;
}
int p = partition(nums, lo, hi);
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
int partition(int[] nums, int lo, int hi) {
int pivot = nums[lo];
int i = lo + 1, j = hi;
while (i <= j) { // 注意边界
while (j > lo && nums[j] > pivot) {
j--;
}
while (i < hi && nums[i] <= pivot) {
i++;
}
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, lo, j);
return j;
}
void shuffle(int[] nums) {
Random rand = new Random();
int n = nums.length;
for (int i = 0; i < n; i++) {
swap(nums, i, i + rand.nextInt(n - i));
}
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
复杂度分析：
partition 执行的次数是二叉树节点的个数，每次执行的复杂度就是每个节点代表的子数组 nums[lo…hi] 的长度，所以总的时间复杂度就是整棵树中「数组元素」的个数。
假设数组元素个数为 N，那么二叉树每一层的元素个数之和就是 O(N)；分界点分布均匀的理想情况下，树的层数为 O(logN)，所以理想的总时间复杂度为 O(NlogN)。
空间复杂度: 递归堆栈的深度（树高） O(logN)
快速排序的效率存在一定随机性，如果每次 partition 切分的结果都极不均匀：
快速排序就退化成选择排序了，树高为 O(N)，每层节点的元素个数从 N 开始递减，总的时间复杂度为：
N + (N – 1) + (N – 2) + … + 1 = O(N^2)
快速排序理想情况的时间复杂度是 O(NlogN)，空间复杂度 O(logN)，极端情况下的最坏时间复杂度是 O(N^2)，空间复杂度是 O(N)
。
2. 归并排序
归并排序是建立在归并操作的一种高效的排序方法，该方法采用了分治的思想，比较适用于处理较大规模的数据，但比较耗内存
2022/2/22 – 8/5
class Solution {
public int[] sortArray(int[] nums) {
int[] temp = new int[nums.length];
mergeSort(nums, temp, 0, nums.length - 1);
return nums;
}
void mergeSort(int[] nums, int[] temp, int lo, int hi) {
if(lo == hi) {
return;
}
if (lo < hi) {
int middle = lo + (hi - lo) / 2;
mergeSort(nums, temp, lo, middle);
mergeSort(nums, temp, middle + 1, hi);
merge(nums, temp, middle, lo, hi);
}
}
void merge(int[] nums, int[] temp, int middle, int lo, int hi) {
int i = lo, j = middle + 1;
for (int k = lo; k <= hi; k++) {
if (i > middle) {
temp[k] = nums[j];
j++;
} else if (j > hi) {
temp[k] = nums[i];
i++;
} else if (nums[i] <= nums[j]) {
temp[k] = nums[i];
i++;
} else {
temp[k] = nums[j];
j++;
}
}
for (int p = lo; p <= hi; p++) {
nums[p] = temp[p];
}
}
}
3. 插入排序
适用处理数据量比较少或者部分有序的数据
- 用一个数组存储要排序的数据（无序）
- 用for循环从前到后遍历整个数组，将无序元素一个一个地插入到正确的位置（排好序的位置），第一个元素我认为它是排好序的，所以我从第二个元素开始遍历
- 用一个临时变量把待插元素（将要插入到有序集合的元素）存起来，然后逐个和有序集合里的元素比较，如果集合里的元素大于待插元素，就将它向后移动一个单元，这样当遇到有序集合中小于等于待插元素的元素时就有地方放待插元素了
2022/7 – 8/5
class Solution {
public int[] sortArray(int[] nums) {
for (int i = 1; i < nums.length; i++) {
insertSort(nums, i);
}
return nums;
}
void insertSort(int[] nums, int i) {
int temp = nums[i];
int j = i - 1;
for (; j >= 0 && nums[j] > temp; j--) {
nums[j + 1] = nums[j];
}
nums[j + 1] = temp;
}
}
4. 冒泡排序
从第一个石子开始，让它和右边相邻的石子进行比较，如果左边的石子大于右边的石子，那么就交换两个石子的位置，（也可以左小于右交换，这里采用大于交换），这样每比较一次，大的就跑到右边，直到跑到最右边
- 第一层循环是控制趟数
- 第二层就是控制你第 i+1趟（因为i从0开始）所比较的次数，第 i +1 趟比较了 N – 1 – i 次
2022/8/22
class Solution {
public int[] sortArray(int[] nums) {
bubbleSort(nums);
return nums;
}
void bubbleSort(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
int temp = 0;
for (int i = 0; i < nums.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < nums.length - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
}
}
版权声明：本文为weixin_46644403原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。