For example, each pair is labeled as** [l1, r1]**. Because the pairs sequence is ordered by **r**. So, we can just iterate it. For current pair, if the **l** is overlapped with previous pair, then don’t consider it. This is a greedy strategy.

# Monthly Archives: August 2020

## lc1563

dp[i][j] is the resultÂ between stone i, and stone j.

If left is greater, then

dp[from][from+delta] = sum(i, from+delta) + dp[i][from+delta]

Else

right part

If both left and right are same, then choose the one which dp has larger value

## lc1558

There are actually 2 types of OPs. One is to make all digit multiplying by 2, this can be shared by all numbers together. Another is **adding one**. This can’t be shared. So result would be count how many one digit, plus the highest bit count.

## lc1553

Solution 1, just like frog jump.

public static int minDays(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 0; i <= n; i++) { if (i * 2 <= n) { dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1); } if (i * 3 <= n) { dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1); } if (i + 1 <= n) { dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1); } } return dp[n]; }

Solution 2, don’t consider 1 step away. Only consider n%2, and n%3. Greedy.

public static int minDays(int n) { Map<Integer, Integer> dp = new HashMap(); return helper(n, dp); } private static int helper(int n, Map<Integer, Integer> dp) { if (n <= 2) { return n; } if (dp.containsKey(n)) { return dp.get(n); } int ans = 1 + Math.min(n % 2 + helper(n / 2, dp), n % 3 + helper(n / 3, dp)); dp.put(n, ans); return ans; }

## GoReplay traffic pattern change

After testing with GoReplay, it shows that GoReplay will change the traffic pattern. When setting a fix RPS rate traffic, GoReplay will just replay the traffic with fix RPS. For some caching use case, this may fail. Let’s say request 1, 2, 3, 4 are all same. We want to cache for request 1, then cache for 2, 3, 4 will hit. This cache hit will work on the replayed traffic, but not real traffic.