public int findMaxMatch(boolean[][] graph) { int match = 0; int[] match = new int[graph[0].length]; for (int i = 0; i < graph.length; i++) { boolean[] visited = new int[graph.length]; if (find(i, graph, match, visited)) { match++; } } return match; } // match[j], for each record j in B set, it matches to a… Read More »
https://youtu.be/JuDAqNyTG4g?t=802
二分图 <==> 不存在寄数环 <==> 可以二色染色 practice lc785
HashMap targetSum currSum for (int n : nums) { 1. see if currSum satisfy 2. count number of targetSum 3. put currSum into map. } In this case, it can handle [0, 0, 0], targetSum = 0, which returns 5. practice https://leetcode.com/problems/path-sum-iii/
space complexity O(n), time complexity for both union and find , in practice is normally less than 5. So can be treated as O(1) constant time. https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86 空间复杂度[编辑] 容易看出，不交集森林的空间复杂度是{\displaystyle \mathrm {O} \left(n\right)}。 时间复杂度[编辑] 对于同时使用路径压缩和按秩合并优化的不交集森林，每个查询和合并操作的平均时间复杂度仅为{\displaystyle O(\alpha (n))}，{\displaystyle \alpha (n)}是反阿克曼函数。由于阿克曼函数{\displaystyle A}增加极度迅速，所以{\displaystyle \alpha (n)}增长极度缓慢，对于任何在实践中有意义的元素数目{\displaystyle n}，{\displaystyle \alpha (n)}均小于5，因此，也可以粗略地认为，并查集的操作有常数的时间复杂度。
Given an array [4 2 1 3 5], and a target. Return the number of pairs that the sum is greater than or equal to 5. Technique: 1. sort, 2. use two pointers. 1. Order is not fixed. [2, 3], [3, 2] are different. [3, 3] is ok. [1 2 3 4 5] [1, 4]… Read More »
For each virus node, count how many normal it connects. By doing dfs, if a normal connects to another virus node, then branch from this normal node won’t count. In below case, there are 2 virus node [0, 5]. node 1 can connect with [1, 2, 8, 9]. 5 can connect with [6, 7]. [3,… Read More »
Assume there are 4 points in first group, labeled with 0, 1, 2, 3. 3 points in second group, labeled with A, B, C. Define dp[i][j]. Use binary to symbolize j, for example dp[2][6] = dp[2][(110)]. This means minimum cost for first 3 (0, 1, 2) points in first group connecting with B, C points in second group.… Read More »
at [2], mult=c add=((a+b)*c+d) From [0] to [2], adding change operation of +a, +b, *c, +d, it needs apply [0]*mult + add Reversely, from [2] to [0], to calculate back with +a, +b, *c, +d, it needs apply ([2] – add) / mult In all, the calculation is like when appending each value, calculate… Read More »
Considering words = [“acca”,”bbbb”,”caca”], target = “aba” dp[1][2] means the result for target “ab” and words=[“acc”, “bbb”, “cac”] To calculate dp[i][j]: 1. dp[i][j] = dp[i][j – 1]. This means when words has is 1 letter small, the result to cover target[0,…,i]. In this case, dp[2][3] = dp[2][2] 2. In words array, for j column, when there is x… Read More »