Category Archives: algorithm

hungarian algorithm template

  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 »

PreSum template

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/

Union Find complexity

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,因此,也可以粗略地认为,并查集的操作有常数的时间复杂度。

leetcode 928

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 »

lc1595

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 »

lc1622 Fancy Sequence

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 »

lc1639

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 »