byu_rself

LC.P2656[K个元素的最大和] 方法一：贪心+数学123456789class Solution { public int maximizeSum(int[] nums, int k) { int x = -1; for (int num : nums) { x = Math.max(x, num); } return k * x + (k - 1) * k / 2; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P93[复原IP地址] 方法一：回溯123456789101112131415161718192021222324252627282930313233343536class Solution { List<String> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); char[] cs; int n; public List<String> restoreIpAddresses(String s) { cs = s.toCharArray(); n = cs.length; dfs(0); return ans; } private void dfs(int idx) { if (path.size() > 4) return; if (idx == n) { ...

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; ...