vampire`blogs

leetcode-1423. 可获得的最大点数 使用滑动数组 12345678910111213141516171819202122232425262728293031323334353637383940414243444546class Solution { public int maxScore(int[] cardPoints, int k) { int n = cardPoints.length; int result = 0; if (k >= n) { //全拿 for (int i = 0; i < n; i++) { result += cardPoints[i]; } return result; } // 定义滑动数组 int l = 0; int r = n - k - ...

leetcode-743. 网络延迟时间 floyd算法求多源最短路 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647class Solution { int[][] dist; int inf = 1000000000; public int networkDelayTime(int[][] times, int N, int K) { dist = new int[N + 1][N + 1]; for (int i = 0; i < N + 1; i++) { for (int j = 0; j < N + 1; j++) { if (i == j) { // 自己到自己距离为0 dist[i][j] = 0; ...

leetcode-957. N 天后的牢房 原始思路 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253class Solution { int count = 0; Map<String, Integer> map = new HashMap<>(); public int[] prisonAfterNDays(int[] cells, int N) { int[] ans = new int[cells.length]; dfs(cells, N, ans); int k = N % map.size(); if (k == 0) { k = map.size(); } String[] spl = new String[cells.length]; ...

leetcode-890. 查找和替换模式 原始思路 1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { public List<String> findAndReplacePattern(String[] words, String pattern) { List<String> result = new ArrayList<>(); Map<Character, Character> map = new HashMap<>(); Map<Character, Character> rmap = new HashMap<>(); for (int i = 0; i < words.length; i++) { map.clear(); ...

leetcode-921. 使括号有效的最少添加 原始思路 1234567891011121314151617181920class Solution { public int minAddToMakeValid(String S) { char c1 = '('; char c2 = ')'; Stack<Character> stack = new Stack<>(); for (int i = 0; i < S.length(); i++) { char chr = S.charAt(i); if (stack.empty()) { stack.push(chr); }else { if (chr == c2 && stack.peek() == c ...

acwing- 858. Prim算法求最小生成树 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[][] g = new int[501][501]; int[] dist = new int[501]; boolean[] st = new boolean[501]; //初始化g for(int i = 1; i < g.length; i++){ Array ...

leetcode-701. 二叉搜索树中的插入操作 原始思路 1234567891011121314151617181920212223242526272829303132333435class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } dfs(root, val); return root; } public void dfs(TreeNode root, int val) { if (root == null) { return; } if (root.val > val){ if (root.left == null) & ...

leetcode-947. 移除最多的同行或同列石头 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960class Solution { public int removeStones(int[][] stones) { int N = stones.length; int[] parent = new int[N]; for (int i = 0; i < N; i++) { parent[i] = i; } // 数据读入 for (int i = 0; i < stones.length; i++) { int[] arr = stones[i]; int x = arr[0]; ...

leetcode-130. 被围绕的区域 原始思路：并查集 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172class Solution { public void solve(char[][] board) { int n1 = board.length; if (n1 == 0) { return; } int n2 = board[0].length; int[] parent = new int[n1 * n2]; // 初始化并查集 for (int i = 0; i < parent.length; i++) { parent[i] = i; ...

leetcode-684. 冗余连接 并查集解决图中只存在一个树的问题 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556class Solution { int[] parent; public int[] findRedundantConnection(int[][] edges) { int N = edges.length + 1; parent = new int[N]; int[] result = new int[]{}; //读入所有边去除删除的边 for (int i = 0; i < edges.length; i++) { // 初始化并查集 for (int j = 0; j < N; j++) { ...