byu_rself

LC.P847[访问所有节点的最短路径] 方法一：状态压缩+BFSclass Solution { private static final int INF = 0x3f3f3f3f; public int shortestPathLength(int[][] graph) { int n = graph.length; int mask = 1 << n; int[][] dist = new int[mask][n]; for (int i = 0; i < mask; ++i) Arrays.fill(dist[i], INF); Deque<int[]> queue = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { dist[1 << i][i] = 0; queue.offe ...

什么时候用状态压缩？需要标记当前点的访问状态，且题目的数据长度比较短（最好小于32位）。满足以上条件，那么就可以使用二进制表示长度为 32 的 int 来代指点是否被访问过。 示例$(000…0101)_2$ 代表编号为 0 和编号为 2 的节点已经被访问过，而编号为 11 的节点尚未被访问。 常用操作检查编号为$x$的点是否被访问过使用位运算 1a = (state >> x) & 1 来获取$state$中第 $x$ 位的二进制表示，如果 $a$ 为 $1$ 代表编号为$x$的节点已被访问，如果为$0$则未被访问。 标记编号为$x$的点已经被访问过使用位运算 1state | (1 << x)

LC.P2409[统计共同度过的日子数] 方法一：模拟将日期转化为天数进行模拟。 12345678910111213141516171819class Solution { static int[] months = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int[] sum = new int[13]; public int countDaysTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) { for (int i = 1; i <= 12; ++i) sum[i] = sum[i - 1] + months[i - 1]; int a1 = calculateDay(arriveAlice); int b1 = calculateDay(leaveAlice); int ...

视频学习链接：https://www.bilibili.com/video/BV1gf4y1r79E/?p=1&vd_source=21e06970a09504e227f7f3380f7cb09c Golang学习笔记Golang简介Golang的优势 123456789101112131415161718package main import ( "fmt" "time")func goFunc(i int) { fmt.Println("goroutine ", i, " ...")}func main() { for i := 0; i < 10000; i++ { go goFunc(i) //开启一个并发协程 } time.Sleep(time.Second)} Golang适合做什么(1)、云计算基础设施领域 代表项目：docker、kubernetes、e ...

LC.P1157[子数组中占绝大多数的元素] 方法一：随机化+二分查找12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758class MajorityChecker { static final int K = 20; int[] arr; Map<Integer, List<Integer>> loc; Random random; public MajorityChecker(int[] arr) { this.arr = arr; this.loc = new HashMap<>(); for (int i = 0; i < arr.length; ++i) { loc.putIfAbsent(arr[i], new ArrayList<>()) ...

LC.P2049[统计最高分的节点数目] 方法一：建图+DFS123456789101112131415161718192021222324252627282930313233343536373839class Solution { static int N = (int) 1e5 + 10, M = N * 2; static int[] he = new int[N], e = new int[M], ne = new int[M]; static int[] f = new int[N]; int idx; private void add(int a, int b) { e[idx] = b; ne[idx] = he[a]; he[a] = idx++; } public int countHighestScoreNodes(int[] parents) { Arrays.fill(he, -1); int n = paren ...

LC.P1042[不邻接植花] 方法一：建图+枚举1234567891011121314151617181920212223class Solution { public int[] gardenNoAdj(int n, int[][] paths) { List<Integer>[] g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int[] path : paths) { int x = path[0] - 1, y = path[1] - 1; g[x].add(y); g[y].add(x); } int[] ans = new int[n]; for (int x = 0; x < n; ++x) { boolean[] used = n ...

12345678910111213141516171819202122232425262728293031323334353637class UnionFind { private final int[] p; private final int[] size; public UnionFind(int n) { p = new int[n]; size = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; size[i] = 1; } } public int find(int x) { if (p[x] != x) p[x] = find(p[x]); // 路径压缩 return p[x]; } public boolean union(int a, int b) { ...

LC.P1697[检查边长度限制的路径是否存在] 方法一：离线查询+并查集离线查询：对于一道题目会给出若干询问，而这些询问是全部提前给出的，也就是说，不必按照询问的顺序依次对它们进行处理，而是可以按照某种顺序（例如全序、偏序（拓扑序）、树的 DFS 序等）或者把所有询问看成一个整体（例如整体二分、莫队算法等）进行处理。 与「离线」相对应的是「在线」思维，即所有的询问是依次给出的，在返回第 $k$ 个询问的答案之前，不会获得第$k+1$ 个询问。 12345678910111213141516171819202122232425262728293031323334class Solution { int[] p; private int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } private void union(int a, int b) { p[find(a)] = p[find(b)]; ...

LC.P1023[驼峰式匹配] 方法一：双指针123456789101112131415161718192021class Solution { public List<Boolean> camelMatch(String[] queries, String pattern) { List<Boolean> ans = new ArrayList<>(); int length = pattern.length(); for (String query : queries) { int n = query.length(), j = 0; boolean flag = true; for (int i = 0; i < n; ++i) { char c = query.charAt(i); if (j < length & ...