运动网站模板,佛山三水区有没有网站建设公司,从零开始学Wordpress建站,做做网站下载免费算法刷题笔记 3.25-3.29 1. 相同的树2. 二叉树的最近公共祖先3. 二叉搜索树中第K小的元素通过双端队列duque 中序遍历 4. 二叉树的锯齿形层序遍历new LinkedListInteger(levelList)双端队列复制 数组需要左右顺序#xff0c;考虑双端队列 5. 岛屿数量6. 字典序排数Integer(levelList)双端队列复制 数组需要左右顺序考虑双端队列 5. 岛屿数量6. 字典序排数有难度循环n次一次只入一个数 7. 克隆图如果该节点已经被访问过了则直接从哈希表中取出对应的克隆节点返回 8. 省份数量并查集 9. 课程表10. 所有可能的路径11. 判断二分图12. 字符串解码两个栈一个存数字一个存字母res一直更新 13. 快速排序14. 利用快速排序找到第k个数15. 归并排序16. 逆序对的数量 三、二分17. 在排序数组中查找元素的第一个和最后一个位置18. 数的三次方根 四、高精度19. 字符串相加20. 高精度减法21. 高精度乘法22. 高精度除法 五、前缀和S与差分a23. 区域和检索 - 数组不可变24. 子矩阵的和25. 差分26. 差分矩阵 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) {DequeTreeNode stack new ArrayDequeTreeNode();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 ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger ans new LinkedListListInteger();if (root null) {return ans;}QueueTreeNode nodeQueue new ArrayDequeTreeNode();nodeQueue.offer(root);boolean isOrderLeft true;while (!nodeQueue.isEmpty()) {DequeInteger levelList new LinkedListInteger();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 LinkedListInteger(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 ListInteger lexicalOrder(int n) {ListInteger ret new ArrayListInteger();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]);}QueueInteger 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 {ListListInteger ans new ArrayListListInteger();DequeInteger stack new ArrayDequeInteger();public ListListInteger 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 ArrayListInteger(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;LinkedListInteger stack_multi new LinkedList();LinkedListString 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 r1;int x nums[ij1];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,j1,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 r1;int x nums[ij1];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 (j1nums.length-k) {return quickSortFindKthLargest(nums,k,j1,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 lr1;mergeSort(nums,l,mid);mergeSort(nums,mid1,r);int i l,j mid1;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 (lr)1;int i l,j mid1;numberOfReverseOrderPairs(l,mid,nums);numberOfReverseOrderPairs(mid1,r,nums);int[] temp new int[r-l1];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 lr1;if (nums[mid] target) {l mid 1;} else {r mid;}}int ans1 r;l 0; r nums.length-1;while (l r) {int mid lr11;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();ListInteger A new ArrayList();ListInteger 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(-);}ListInteger C sub(A,B);for(int i C.size() - 1;i 0; i --){System.out.print(C.get(i));}}public static ListInteger sub(ListInteger A,ListInteger B){if(!cmp(A,B)){return sub(B,A);}ListInteger 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(ListInteger A,ListInteger 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. 高精度乘法
二刷
在草稿纸上演算一遍 运算过程便知道 代码逻辑
力扣链接 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 algorithmusing namespace std;vectorint div(vectorint A, int b, int r)
{vectorint 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;vectorint 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[n2][m2];int[][] sum new int[n2][m2];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][y21] - c;splits[x21][y1] - c;splits[x21][y21] 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();}}
}
