byu_rself

LC.P773[滑动谜题] 方法一：BFS12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class Solution { int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}; public int slidingPuzzle(int[][] board) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < 2; ++i) { for (int j = 0; j < 3; ++j) { s ...

LC.P1239[串联字符串的最大长度] 方法一：剪枝DFS1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859class Solution { static Map<Integer, Integer> map = new HashMap<>(); int n; int ans = Integer.MIN_VALUE; int[] hash; private int get(int cur) { if (map.containsKey(cur)) return map.get(cur); int ans = 0; for (int i = cur; i > 0; i -= lowbit(i)) ans++; map.put(cur, ans); return ans; ...

LC.P1125[最小的必要团队] 方法一：状态压缩+记忆化搜索1234567891011121314151617181920212223242526272829303132333435363738class Solution { private long all; private int[] mask; private long[][] cache; public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) { int m = reqSkills.length; Map<String, Integer> map = new HashMap<>(); for (int i = 0; i < m; ++i) map.put(reqSkills[i], i); int n = people.size(); mask = ...

LC.P433[最小基因变化] 方法一：BFS(超时)12345678910111213141516171819202122232425262728293031class Solution { public int minMutation(String startGene, String endGene, String[] bank) { Set<String> set = new HashSet<>(List.of(bank)); if (!set.contains(endGene)) return -1; Deque<String> queue = new ArrayDeque<>(); char[] g = new char[]{'A', 'C', 'G', 'T'}; queue.offer(startGene); int ...

LC.P1040[移动石子直到连续 II] 方法一：滑动窗口123456789101112131415161718class Solution { public int[] numMovesStonesII(int[] stones) { int n = stones.length; Arrays.sort(stones); // 计算空位 int s1 = stones[n - 2] - stones[0] - n + 2; int s2 = stones[n - 1] - stones[1] - n + 2; int maxMove = Math.max(s1, s2); // 没有空位 if (s1 == 0 || s2 == 0) return new int[]{Math.min(2, maxMove), maxMove}; int maxCnt = 0; for (int left = 0, ...

LC.P2059[转化数字的最小运算数] 方法一：BFS1234567891011121314151617181920212223class Solution { public int minimumOperations(int[] nums, int start, int goal) { Deque<Integer> queue = new ArrayDeque<>(); Map<Integer, Integer> map = new HashMap<>(); queue.offer(start); map.put(start, 0); while (!queue.isEmpty()) { int cur = queue.poll(); int step = map.get(cur); for (int num : nums) { ...

LC.P1017[负二进制转换] 方法一：模拟12345678910111213141516class Solution { public String baseNeg2(int n) { if (n == 0) return "0"; StringBuilder builder = new StringBuilder(); while (n != 0) { int remainder = n % (-2); n /= -2; if (remainder < 0) { remainder += 2; ++n; } builder.append(remainder); } return builder.reverse().toString(); } ...

LC.P1765[地图中的最高点] 方法一：多源BFS12345678910111213141516171819202122232425262728class Solution { static int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public int[][] highestPeak(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] ans = new int[m][n]; Deque<int[]> queue = new ArrayDeque<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) ...

LC.P1162[地图分析] 方法一：BFS(超时)对每个海洋位置做一次 BFS：求得每个海洋的最近陆地距离，然后在所有的距离中取 $max$作为答案。 1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { int n; int[][] grid; int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public int maxDistance(int[][] grid) { this.grid = grid; n = grid.length; int ans = -1; for (int i = 0; i < n; ++i) { for (int j = ...

LC.P2427[公因子的数目] 方法一：枚举123456789class Solution { public int commonFactors(int a, int b) { int ans = 0; for (int i = 1; i <= Math.min(a, b); ++i) { if (a % i == 0 && b % i == 0) ++ans; } return ans; }} 时间复杂度：$O(min(a,b))$ 空间复杂度：$O(1)$ 方法二：枚举到最大公因数1234567891011121314class Solution { public int commonFactors(int a, int b) { int ans = 0; int g = gcd(a, b); for (int i = 1; i < ...