Category Archives: algorithm

git merge, rebase, branch

Sometimes, when develop a feature branch, then, we merge back to master branch. This results a ring. This made the merge point has 2 parents. So tracing back the diff would be difficult. The scenario we allow the ring and merge point is that the feature branch is kinda big feature. In the branch, it… 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[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 »

lc1648

This problem needs to aggregate to (num, count) tree map. Always stick to top 2 elements. After processed first element, aggregate the count of first element to second element. For example, 77744444, orders = 10. For TreeMap, it has (7, 3), (4, 5) It can be added to answer by below numbers: 7 7 7 … Read More »

lc1641

Assume a, e, i, o, u variables mean the number of elements which starts with a, e, i, o, u. Take below as example, length is 5 now. There are a number of elements which starts with a, e number of elements which starts with e, etc. When extend the length to 6. When adding… Read More »

leetcode 1605

The point is to assign each rowSum value to each cell in each row, assign each colCum value to each cell in each row. For example, need to assign 6 to m[0][1], m[1][1], m[2][1]. Check this video for detail process.  

gray code

This is the gray code. The changing rule can be: rule1: update the rightmost bit rule2: for xxx100…00, it can change the digit x which is next to 100..00 See lc1611 For example, 1001000 has 2 ways of change: 1. rule1 -> 1001001 2. rule2 -> 1011000 Another example, 1111 has 2 ways of change: 1. rule1 ->… Read More »