byu_rself

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

常见问题[git push报错] unable to access ‘https://github.com/xxx.git/‘: Failed to connect to 127.0.0.1 port443原因分析 1.本机系统代理端口和git端口不一致 2.代理服务器未打开 3.加速器VPN未打开 三者有一种情况都会导致失败，侧重点放在原因1端口不一致，端口设置一致之后，若还出错，依次检查后面的原因2、3。 解决方法 1.查看到本机系统默认的代理端口号为:7890 2.设置git的代理端口号为7890 12git config --global http.proxy http://127.0.0.1:7890 git config --global https.proxy http://127.0.0.1:7890 3.重新push即可 常用命令 命令 描述 git init 初始化一个新的 Git 仓库 git add [file-name] 将指定的文件添加到暂存区 git commit -m “commit message” 将暂存区的文件提交到本 ...

邻接矩阵使用于边数较多的稠密图 1234567// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边int[][] w = new int[N][N];// 加边操作void add(int a, int b, int c) { w[a][b] = c;} 邻接表与数组存储单链表的实现一致（头插法），又称链式前向星存图，适用于边数较少的稀疏图 1234567891011121314int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];int idx;// 初始化Arrays.fill(he, -1);// 建图void add(int a, int b, int c) { e[idx] = b; ne[idx] = he[a]; he[a] = idx; w[idx] = c; idx++;} 其中，N为节点个数，M为边的个数 he数组：存储是某个节点所对应的边的集合（链表）的头结点； e数 ...