# Category Archives: algorithm

## hungarian algorithm template

public int findMaxMatch(boolean[][] graph) { int match = 0; int[] match = new int[graph.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 »

## binary search template

https://youtu.be/JuDAqNyTG4g?t=802

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

## Find count of sum pairs in array, which the sum is greater than target.

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 »

## 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 = dp[(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 , mult=c add=((a+b)*c+d) From  to , adding change operation of +a, +b, *c, +d, it needs apply *mult + add   Reversely, from  to , to calculate back with +a, +b, *c, +d, it needs apply ( – add) / mult   In all, the calculation is like when appending each value, calculate… Read More »

## lc1639

Considering words = [“acca”,”bbbb”,”caca”], target = “aba” dp 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 = dp 2. In words array, for j column, when there is x… Read More »