Author Archives: lipeng

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, 4] connects to 2 virus node, so they won’t be counted.

 

img3

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. In another way, write it like dp[2][CB*]

dp[3][C*A] = min{
dp[3][**A] + cost[3][C],  // make a new connection in same row
dp[3][C**] + cost[3][A],
dp[2][**A] + cost[3][C],     // no C in row 2, C is new in row 3. build connection 3->C
dp[2][C**] + cost[3][A],
dp[2][C*A] + cost[3][C],    // CA is already included in row2, reuse C in row 3.
dp[2][C*A] + cost[3][A]
}

1595

Code:

public static int connectTwoGroups(List<List<Integer>> cost) {
    int col = cost.get(0).size();
    int[][] memo = new int[cost.size()][1 << col];
    for (int[] m : memo) {
        Arrays.fill(m, Integer.MAX_VALUE);
    }
    dfs(cost.size() - 1, (1 << col) - 1, memo, cost);
    return dfs(cost.size() - 1, (1 << col) - 1, memo, cost);
}

private static int dfs(int row, int b, int[][] memo, List<List<Integer>> cost) {
    if (memo[row][b] != Integer.MAX_VALUE) {
        return memo[row][b];
    }
    if ((b - (b & (-b))) == 0) {    // b only has 1 one in binary
        int col = 0;
        while ((b & (1 << col)) == 0) {
            col++;
        }
        memo[row][b] = 0;
        for (int i = 0; i <= row; i++) {
            memo[row][b] += cost.get(i).get(col);
        }
        return memo[row][b];
    }
    if (row == 0) {
        memo[row][b] = 0;
        for (int i = 0; i < cost.get(0).size(); i++) {
            if ((b & (1 << i)) > 0) {
                memo[row][b] += cost.get(0).get(i);
            }
        }
        return memo[row][b];
    }
    for (int col = 0; col < cost.get(0).size(); col++) {
        if ((b & (1 << col)) > 0) {
            memo[row][b] = Math.min(memo[row][b], dfs(row, b - (1 << col), memo, cost) + cost.get(row).get(col));
            memo[row][b] = Math.min(memo[row][b], dfs(row - 1, b - (1 << col), memo, cost) + cost.get(row).get(col));
            memo[row][b] = Math.min(memo[row][b], dfs(row - 1, b, memo, cost) + cost.get(row).get(col));
        }
    }
    return memo[row][b];
}

lc1622 Fancy Sequence

fancy1

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

 

fancy2

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 back by removing the operations before. Let it start from very beginning without any operation. Then in the end after all operations,  when getIndex, calculate forwardly with current mult, add

(a / b) % mod = (a * x) % mod

Here, x is inverse modular of b. In Java,

x = BigInteger.valueOf(a).modInverse(BigInteger.valueOf(mod)).longValue();

https://www.bilibili.com/video/av970029359/

Dockerfile CMD requires foreground command

Start a docker container with below Dockerfile. Since it has CMD [“nginx”]. The docker container exists after nginx command is finished. It couldn’t be connected even with –detach mode.

In order to keep the docker container running, needs the CMD run in foreground. Let it keep running. So it needs a “daemon off” in nginx.conf file.

FROM ubuntu:14.04

RUN apt-get update
RUN apt-get install -y nginx


#RUN echo "\ndaemon off;" >> /etc/nginx/nginx.conf

CMD ["nginx"]

EXPOSE 80
EXPOSE 443

 

 

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]

1639_3

2. In words array, for j column, when there is x number of letters which equals to target[i]. It is ‘a’ for this case. Then needs to add dp[i-1][j-1] * x. For dp[2][3], this part is result of [“acc”, “bbb”, “cac”], “ab”, multiplying number of ‘a’ in column 3, which is 2.

1639_2

For each column of the words, create a count[column][26] to mark the number of letters in that column.

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  <– e1
6 6 6
5 5 5  <– e2

Orders is 8. All the numbers can be used to add into answer.

For one column, it is  5+6+7. The formula is (e2 – e1 + 1) * (e1 + e2) / 2 = 18

So answer = answer + 18 * 3

After that, tree map becomes to (4, 3), (4, 5). Merging them, it becomes (4, 8). Orders -= 9

 

Consider case 7774, orders = 8. (7, 3), (4, 1)

1648

Only numbers in red will be added to answer.

In this case, availRow = 8 % 3 = 2. mod = 8 / 3 = 2

One part, (e1 – e2 + 1) * (e1 + e2) / 2 * 3. 3 is the number of column.

Another part, (secondElement.key + 1)*mod = (4 + 1) * mod = 5 * 2 = 10

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 a, a can be added in any elements.

When adding ee can be added in front of elements starting with e, i, o, u.

When adding ii can be added in front of elements starting with iou.

When adding oo can be added in front of elements starting with ou.

When adding uu can be added in front of elements starting with u.

lc1641

The elements are lexical order. This is an important criteria.

link

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.

transform

 

gray code

This is the gray code. The changing rule can be:

  1. update the rightmost big
  2. for xxx100…00, it can change the digit x which is next to 100..00

See lc1611

The property of gray code, is that each two adjacent number only have 1 bit difference.

For example, in decimal, if we want to update from 011 to 100, the electronic element may change like 100->101->111->100. There is potential ephemeral number 101, 111. In gray code, this won’t happen. Because each two adjacent number only has 1 bit difference.

Decimal Binary Gray
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000

 

Transformation from decimal to gray code. See here.

  1. keep the leftmost bit same.
  2. For each following bit, xor the 2 adjacent decimal bits

(10011001)gc -> (11010101)d

Transformation from gray code to decimal. See here

  1. keep the leftmost bit same.
  2. For each following bit, xor current gray code bit and decimal bit

(11010101)d -> (10011001)gc

 

Design Pattern summary by tech lead.

link

1. @3:00 Break programs into logically independent components, allowing component dependencies where necessary.

2. @3:10 Inspect your data objects and graph their interactions/where they flow. Keep classes simple. Keep one-way dataflow/interactions simple. @3:29 Simplicity — keep a small number of class types (controller, views, data objects) avoid creating classes that aliases those classes (managers, coordinators, helpers, handlers, providers, executor). @4:02 — Keep dataflow simple (e.g., don’t let Views have business logic; views shouldn’t need to communicate any data upstream).

3. @4:33 Keep data model objects pruned of logic, except if the logic is part of the objects’ states. Single Responsibility Principle. If you can’t describe a class’s responsibility straightforwardly, it’s too complex.

4. @5:25 Inspect class composition (“follow ownership graph”). Follow the life of a child (composed) object to make sure that accessibility to and operations done on that object is managed.

5. @5:55 Singletons (“basically globals floating in a system”). Use dependency injection (?) to ‘scope singletons’ and make them testable (?). Singletons often represent independent (uncoupled) objects which is good for representing independent execution flow. Too many inter-communicating singletons in a system make it difficult to trace data flow and understand the overall transformation of the data through the system.

6. @6:50 Singleton communication patterns. Singletons expose Publisher/Subscriber interface (one publisher object, many subscriber objects listening to events).

7. @7:41 Delegate communication pattern. (?)

8.@8:02 Chain of Responsibility Pattern. Hierarchical data flow — unhandled events bubble upwards to parent objects who should handle them. Conflicts with (2) by allowing upstream dataflow. Use with discretion.

9. @8:53 OOP’s Inheritance can create tightly coupled hierarchical objects that are hard to refactor (object dependencies). Use composition pattern to allow flexibility in what the container object can do.

10. @9:58 Lazy initialization. Startup performance boost.

11. @10:06 Adapter Pattern.

12. @10:26 Factory builder classes.