byu_rself

LC.P131[分割回文串] 方法一：回溯1234567891011121314151617181920212223242526272829303132class Solution { List<List<String>> ans = new ArrayList<>(); List<String> path = new ArrayList<>(); String s; public List<List<String>> partition(String s) { this.s = s; dfs(0); return ans; } private void dfs(int i) { if (i == s.length()) { ans.add(new ArrayList<>(path)); return; ...

LC.P1334[阈值距离内邻居最少的城市] 方法一：Dijkstra12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class Solution { private static final int INF = 0x3f3f3f3f; int[][] g; int n; int[] dist; boolean[] visited; int distanceThreshold; public int findTheCity(int n, int[][] edges, int distanceThreshold) { g = new int[n][n]; this.n = n; dist = new int[n]; visited = new boolean[n]; this.distanceThresho ...

LC.P40[组合总和II] 方法一：回溯+剪枝1234567891011121314151617181920212223242526272829class Solution { List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); int[] candidates; public List<List<Integer>> combinationSum2(int[] candidates, int target) { this.candidates = candidates; Arrays.sort(candidates); dfs(0, target); return ans; } private void dfs(int start, int target)  ...

LC.P39[组合总和] 方法一：朴素回溯123456789101112131415161718192021222324252627class Solution { List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); int[] candidates; public List<List<Integer>> combinationSum(int[] candidates, int target) { this.candidates = candidates; dfs(0, target); return ans; } private void dfs(int i, int target) { if (i == candidates.length) return ...

LC.P2300[咒语和药水的成功对数] 方法一：排序+二分1234567891011121314151617class Solution { public int[] successfulPairs(int[] spells, int[] potions, long success) { int n = spells.length, m = potions.length; Arrays.sort(potions); int[] ans = new int[n]; for (int i = 0; i < n; ++i) { int left = 0, right = m - 1; while (left < right) { int mid = left + right >> 1; if ((long) spells[i] * potions[mid] > ...

LC.P2258[逃离火灾] 方法一：二分+BFS12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576class Solution { static int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int m, n; boolean flag; int[][] grid, fire, people; public int maximumMinutes(int[][] grid) { this.grid = grid; m = grid.length; n = grid[0].length; ...

LC.P768[最多能完成排序的块II] 方法一：栈+贪心123456789101112131415class Solution { public int maxChunksToSorted(int[] arr) { Deque<Integer> stack = new ArrayDeque<>(); for (int x : arr) { if (!stack.isEmpty() && x < stack.peek()) { int max = stack.poll(); while (!stack.isEmpty() && x < stack.peek()) stack.poll(); stack.push(max); } else { stack.push(x ...

LC.P2609[最长平衡子字符串] 方法一：枚举12345678910111213141516171819class Solution { public int findTheLongestBalancedSubstring(String s) { int ans = 0, n = s.length(), k = 0; for (int i = 0; i < n; ) { int cnt0 = 0, cnt1 = 0; while (k < n && s.charAt(k) == '0') { ++k; ++cnt0; } while (k < n && s.charAt(k) == '1') { ++k; ...

LC.P517[超级洗衣机] 方法一：贪心12345678910111213141516class Solution { public int findMinMoves(int[] machines) { int sum = 0, n = machines.length; for (int x : machines) { sum += x; } if (sum % n != 0) return -1; int ans = 0, cnt = 0, avg = sum / n; for (int x : machines) { x -= avg; cnt += x; ans = Math.max(ans, Math.max(x, Math.abs(cnt))); } return ans; }} 时 ...

LC.P2586[统计范围内的元音字符串数] 方法一：遍历123456789101112131415class Solution { private static final Set<Character> set = new HashSet<>(Set.of('a', 'e', 'i', 'o', 'u')); public int vowelStrings(String[] words, int left, int right) { int ans = 0; for (int i = left; i <= right; ++i) { String s = words[i]; if (set.contains(s.charAt(0)) && set.contains(s.charAt(s.length() - 1))) { ...