算法刷题笔记（3.25-3.29）

1. 相同的树

原题链接

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if ((p != null && q == null) || (p == null && q != null)) {return false;}if (p.val != q.val) {return false;}return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}

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

原题链接

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode ans;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {ans = null;dfs(root,p,q);return ans;}public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return false;}boolean l = dfs(root.left,p,q);boolean r = dfs(root.right,p,q);if (l == true && r == true && ans == null) {ans = root;return true;}if ((l == true || r == true) && (root == p || root == q) && ans == null) {ans = root;return true;}if (root == p || root == q) {return true;}return l || r;}}

3. 二叉搜索树中第K小的元素

通过双端队列duque 中序遍历

二叉搜索树中第K小的元素

class Solution {public int kthSmallest(TreeNode root, int k) {Deque<TreeNode> stack = new ArrayDeque<TreeNode>();while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();--k;if (k == 0) {break;}root = root.right;}return root.val;}
}

4. 二叉树的锯齿形层序遍历

原题链接

new LinkedList(levelList)双端队列复制 数组

需要左右顺序，考虑双端队列

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new LinkedList<List<Integer>>();if (root == null) {return ans;}Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();nodeQueue.offer(root);boolean isOrderLeft = true;while (!nodeQueue.isEmpty()) {Deque<Integer> levelList = new LinkedList<Integer>();int size = nodeQueue.size();for (int i = 0; i < size; ++i) {TreeNode curNode = nodeQueue.poll();if (isOrderLeft) {levelList.offerLast(curNode.val);} else {levelList.offerFirst(curNode.val);}if (curNode.left != null) {nodeQueue.offer(curNode.left);}if (curNode.right != null) {nodeQueue.offer(curNode.right);}}ans.add(new LinkedList<Integer>(levelList));isOrderLeft = !isOrderLeft;}return ans;}
}

5. 岛屿数量

class Solution {public int[][] posztion = {{0,-1},{0,1},{1,0},{-1,0}};public boolean[][] isUsed = new boolean[301][301];public int numIslands(char[][] grid) {int ans = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (isUsed[i][j] == false && grid[i][j] == '1') {bfs(grid,i,j,ans);ans++;}}}return ans;}public void bfs(char[][] grid,int x,int y, int ans) {for (int i = 0; i < 4; i++) {int a = x + posztion[i][0];int b = y + posztion[i][1];if (a >= 0 && a < grid.length && b >= 0 && b < grid[0].length&& isUsed[a][b] == false && grid[a][b] == '1') {isUsed[a][b] = true;bfs(grid,a,b,ans);}}}}

6. 字典序排数（有难度）

原题链接

循环n次，一次只入一个数

class Solution {public List<Integer> lexicalOrder(int n) {List<Integer> ret = new ArrayList<Integer>();int number = 1;for (int i = 0; i < n; i++) {ret.add(number);if (number * 10 <= n) {number *= 10;} else {while (number % 10 == 9 || number + 1 > n) {number /= 10;}number++;}}return ret;}
}

7. 克隆图

如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回

原题链接

class Solution {private HashMap <Node, Node> visited = new HashMap <> ();public Node cloneGraph(Node node) {if (node == null) {return node;}// 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回if (visited.containsKey(node)) {return visited.get(node);}// 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表Node cloneNode = new Node(node.val, new ArrayList());// 哈希表存储visited.put(node, cloneNode);// 遍历该节点的邻居并更新克隆节点的邻居列表for (Node neighbor: node.neighbors) {cloneNode.neighbors.add(cloneGraph(neighbor));}return cloneNode;}
}

8. 省份数量

原题链接

并查集

class Solution {public int findCircleNum(int[][] isConnected) {int cities = isConnected.length;int[] parent = new int[cities];for (int i = 0; i < cities; i++) {parent[i] = i;}for (int i = 0; i < cities; i++) {for (int j = i + 1; j < cities; j++) {if (isConnected[i][j] == 1) {union(parent, i, j);}}}int provinces = 0;for (int i = 0; i < cities; i++) {if (parent[i] == i) {provinces++;}}return provinces;}public void union(int[] parent, int index1, int index2) {parent[find(parent, index1)] = find(parent, index2);}public int find(int[] parent, int index) {if (parent[index] != index) {parent[index] = find(parent, parent[index]);}return parent[index];}
}

9. 课程表

原题链接

class Solution {private static final int N = 5001;private static int[] e;private static int[] ne;private static int[] h;private static int[] cnt;private static int idx;private static void add(int a,int b) {e[idx] = b;ne[idx] = h[a];cnt[b]++;h[a] = idx++;}public boolean canFinish(int numCourses, int[][] prerequisites) {e = new int[N];ne = new int[N];h = new int[N];cnt = new int[N];idx = 0;Arrays.fill(h,-1);for (int[] temp : prerequisites) {add(temp[1],temp[0]);}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (cnt[i] == 0) {queue.add(i);}}int sum = 0;while (!queue.isEmpty()) {int r = queue.remove();sum++;for (int i = h[r]; i != -1; i = ne[i]) {int j = e[i];cnt[j]--;if (cnt[j] == 0) {queue.add(j);}}}if (sum == numCourses) {return true;} else {return false;}}
}

10. 所有可能的路径

原题链接

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();Deque<Integer> stack = new ArrayDeque<Integer>();public List<List<Integer>> allPathsSourceTarget(int[][] graph) {stack.offerLast(0);dfs(graph, 0, graph.length - 1);return ans;}public void dfs(int[][] graph, int x, int n) {if (x == n) {ans.add(new ArrayList<Integer>(stack));return;}for (int y : graph[x]) {stack.offerLast(y);dfs(graph, y, n);stack.pollLast();}}
}

11. 判断二分图

原题链接

class Solution {private static final int UNCOLORED = 0;private static final int RED = 1;private static final int GREEN = 2;private int[] color;private boolean valid;public boolean isBipartite(int[][] graph) {int n = graph.length;valid = true;color = new int[n];Arrays.fill(color, UNCOLORED);for (int i = 0; i < n && valid; ++i) {if (color[i] == UNCOLORED) {dfs(i, RED, graph);}}return valid;}public void dfs(int node, int c, int[][] graph) {color[node] = c;int cNei = c == RED ? GREEN : RED;for (int neighbor : graph[node]) {if (color[neighbor] == UNCOLORED) {dfs(neighbor, cNei, graph);if (!valid) {return;}} else if (color[neighbor] != cNei) {valid = false;return;}}}
}

12. 字符串解码

两个栈，一个存数字，一个存字母

res一直更新

class Solution {public String decodeString(String s) {StringBuilder res = new StringBuilder();int multi = 0;LinkedList<Integer> stack_multi = new LinkedList<>();LinkedList<String> stack_res = new LinkedList<>();for(Character c : s.toCharArray()) {if(c == '[') {stack_multi.addLast(multi);stack_res.addLast(res.toString());multi = 0;res = new StringBuilder();}else if(c == ']') {StringBuilder tmp = new StringBuilder();int cur_multi = stack_multi.removeLast();for(int i = 0; i < cur_multi; i++) tmp.append(res);res = new StringBuilder(stack_res.removeLast() + tmp);}else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");else res.append(c);}return res.toString();}
}

13. 快速排序

原题链接

class Solution {public int[] sortArray(int[] nums) {int n = nums.length;quickSort(nums,0,n-1);return nums;}public void quickSort(int[] nums, int l, int r) {if (l >= r) {return;}int i = l-1, j = r+1;int x = nums[i+j>>1];while (i < j) {do i++; while(nums[i] < x);do j--; while(nums[j] > x);if (i < j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}quickSort(nums,l,j);quickSort(nums,j+1,r);}}

14. 利用快速排序找到第k个数

原题链接

class Solution {public int findKthLargest(int[] nums, int k) {return quickSortFindKthLargest(nums,k,0,nums.length-1);}public int quickSortFindKthLargest(int[] nums, int k, int l,int r) {if (l >= r) {return nums[l];}int i = l-1, j = r+1;int x = nums[i+j>>1];while (i < j) {do i++; while(nums[i] < x);do j--; while(nums[j] > x);if (i < j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}if (j+1<=nums.length-k) {return quickSortFindKthLargest(nums,k,j+1,r);} else {return quickSortFindKthLargest(nums,k,l,j);}}}

15. 归并排序

原题链接

class Solution {int[] tempNums;public int[] sortArray(int[] nums) {tempNums = new int[nums.length];int n = nums.length;mergeSort(nums,0,n-1);return nums;}public void mergeSort(int[] nums, int l, int r) {if (l >= r) {return;}int mid = l+r>>1;mergeSort(nums,l,mid);mergeSort(nums,mid+1,r);int i = l,j = mid+1;int idx = 0;while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {tempNums[idx++] = nums[i++];} else {tempNums[idx++] = nums[j++];}}while (i <= mid) {tempNums[idx++] = nums[i++];}while (j <= r) {tempNums[idx++] = nums[j++];}for (int q = l,k = 0; q <= r; q++) {nums[q] = tempNums[k++];}}}

16. 逆序对的数量

原题链接

class Solution {public static int ans;public int reversePairs(int[] record) {ans = 0;int n = record.length;numberOfReverseOrderPairs(0,n-1,record);return ans;}public static void numberOfReverseOrderPairs(int l,int r,int[] nums){if (l >= r) {return;}int mid = (l+r)>>1;int i = l,j = mid+1;numberOfReverseOrderPairs(l,mid,nums);numberOfReverseOrderPairs(mid+1,r,nums);int[] temp = new int[r-l+1];int k = 0;while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {temp[k++] = nums[i++];} else {temp[k++] = nums[j++];ans += mid - i + 1;}}while (i <= mid) {temp[k++] = nums[i++];}while (j <= r) {temp[k++] = nums[j++];}for (int q = l,p = 0; q <= r; q++) {nums[q] = temp[p++];}}}

三、二分

17. 在排序数组中查找元素的第一个和最后一个位置

力扣链接
acwing链接

class Solution {public int[] searchRange(int[] nums, int target) {if (nums == null || nums.length == 0) {return new int[]{-1,-1};}int l = 0, r = nums.length-1;while (l < r) {int mid = l+r>>1;if (nums[mid] < target) {l = mid + 1;} else {r = mid;}}int ans1 = r;l = 0; r = nums.length-1;while (l < r) {int mid = l+r+1>>1;if (nums[mid] <= target) {l = mid;} else {r = mid-1;}}int ans2 = r;if (nums[ans1] == target && nums[ans2] == target) {return new int[]{ans1,ans2};} else {return new int[]{-1,-1};}}
}

18. 数的三次方根

力扣连接
acwing链接

class Solution {public int mySqrt(int x) {int l = 0, r = x, ans = -1;while (l <= r) {int mid = l + (r - l) / 2;if ((long) mid * mid <= x) {ans = mid;l = mid + 1;} else {r = mid - 1;}}return ans;}
}

四、高精度

19. 字符串相加

力扣链接
acwing链接

class Solution {public String addStrings(String num1, String num2) {int i = num1.length() - 1, j = num2.length() - 1, add = 0;StringBuffer ans = new StringBuffer();while (i >= 0 || j >= 0 || add != 0) {int x = i >= 0 ? num1.charAt(i) - '0' : 0;int y = j >= 0 ? num2.charAt(j) - '0' : 0;int result = x + y + add;ans.append(result % 10);add = result / 10;i--;j--;}// 计算完以后的答案需要翻转过来ans.reverse();return ans.toString();}
}

20. 高精度减法

原题链接

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;public class Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);String s1 = scanner.next();String s2 = scanner.next();List<Integer> A = new ArrayList<>();List<Integer> B = new ArrayList<>();for(int i = s1.length() - 1;i >= 0;i --) A.add(s1.charAt(i) - '0');for(int i = s2.length() - 1;i  >= 0; i --) B.add(s2.charAt(i) - '0');if(!cmp(A,B)){System.out.print("-");}List<Integer> C = sub(A,B);for(int i = C.size() - 1;i >= 0; i --){System.out.print(C.get(i));}}public static List<Integer> sub(List<Integer> A,List<Integer> B){if(!cmp(A,B)){return sub(B,A);}List<Integer> C = new ArrayList<>();int t = 0;for(int i = 0;i < A.size();i ++){//这里应该是A.get(i) - B.get(i) - t ，因为可能B为零，所以需要判断一下是不是存在t = A.get(i) - t;if(i < B.size()) t -= B.get(i);C.add((t + 10) % 10);if(t < 0) t = 1;else t = 0;}//删除指定下标下面的值while(C.size() > 1 && C.get(C.size() - 1) == 0)  C.remove(C.size() - 1);return C;}public static boolean cmp(List<Integer> A,List<Integer> B){if(A.size() != B.size()) return A.size() > B.size();/* if(A.size() >= B.size()){return true;}else{return false;}*/for(int i = A.size() - 1;i >= 0;i --){if(A.get(i) != B.get(i)) {return A.get(i) > B.get(i);}}return true;}
}

21. 高精度乘法

二刷：

1. 在草稿纸上演算一遍 运算过程，便知道 代码逻辑

力扣链接
acwing链接

class Solution {public String multiply(String num1, String num2) {if (num1.equals("0") || num2.equals("0")) {return "0";}String ans = "0";int m = num1.length(), n = num2.length();for (int i = n - 1; i >= 0; i--) {StringBuffer curr = new StringBuffer();int add = 0;for (int j = n - 1; j > i; j--) {curr.append(0);}int y = num2.charAt(i) - '0';for (int j = m - 1; j >= 0; j--) {int x = num1.charAt(j) - '0';int product = x * y + add;curr.append(product % 10);add = product / 10;}if (add != 0) {curr.append(add % 10);}ans = addStrings(ans, curr.reverse().toString());}return ans;}public String addStrings(String num1, String num2) {int i = num1.length() - 1, j = num2.length() - 1, add = 0;StringBuffer ans = new StringBuffer();while (i >= 0 || j >= 0 || add != 0) {int x = i >= 0 ? num1.charAt(i) - '0' : 0;int y = j >= 0 ? num2.charAt(j) - '0' : 0;int result = x + y + add;ans.append(result % 10);add = result / 10;i--;j--;}ans.reverse();return ans.toString();}
}

22. 高精度除法

原题链接

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<int> div(vector<int> &A, int b, int &r)
{vector<int> C;r = 0;for (int i = A.size() - 1; i >= 0; i -- ){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(), C.end());while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a;vector<int> A;int B;cin >> a >> B;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');int r;auto C = div(A, B, r);for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];cout << endl << r << endl;return 0;
}

五、前缀和S与差分a

23. 区域和检索 - 数组不可变

力扣链接
acwing链接

class NumArray {int[] sums;public NumArray(int[] nums) {int n = nums.length;sums = new int[n + 1];for (int i = 0; i < n; i++) {sums[i + 1] = sums[i] + nums[i];}}public int sumRange(int i, int j) {return sums[j + 1] - sums[i];}
}

24. 子矩阵的和

acwing链接
力扣链接

class NumMatrix {int[][] sums;public NumMatrix(int[][] matrix) {int m = matrix.length;if (m > 0) {int n = matrix[0].length;sums = new int[m + 1][n + 1];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];}}}}public int sumRegion(int row1, int col1, int row2, int col2) {return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];}
}

25. 差分

力扣链接
acwing链接

class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] nums = new int[n];for (int[] booking : bookings) {nums[booking[0] - 1] += booking[2];if (booking[1] < n) {nums[booking[1]] -= booking[2];}}for (int i = 1; i < n; i++) {nums[i] += nums[i - 1];}return nums;}
}

26. 差分矩阵

原题链接

import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int q = scanner.nextInt();int[][] splits = new int[n+2][m+2];int[][] sum = new int[n+2][m+2];for (int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {sum[i][j] = scanner.nextInt();splits[i][j] = sum[i][j] - sum[i-1][j] - sum[i][j-1] + sum[i-1][j-1];}}for (int i = 0; i < q; i++) {int x1 = scanner.nextInt();int y1 = scanner.nextInt();int x2 = scanner.nextInt();int y2 = scanner.nextInt();int c = scanner.nextInt();splits[x1][y1] += c;splits[x1][y2+1] -= c;splits[x2+1][y1] -= c;splits[x2+1][y2+1] += c;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {sum[i][j] = splits[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];System.out.print(sum[i][j] + " ");}System.out.println();}}
}