Monthly Archives: June 2019

Count how many element it has. We don’t care about the number in array. We only care about the index. If there are 5 elements, we will need to a figure out the result for [0, 1, 2, 3, 4](which is actually [0, 4, 1, 3, 2]).

Then, we sort the input array, and reorder the deck[] according to index sequence.

Reverse process is like below:

public static int[] deckRevealedIncreasing(int[] deck) {
    int[] ans = new int[deck.length];
    Deque<Integer> deque = new LinkedList<>();
    deque.addLast(deck.length - 1);
    for (int i = deck.length - 2; i >= 0; i--) {
        deque.addFirst(deque.removeLast());
        deque.addFirst(i);
    }
    Arrays.sort(deck);
    for (int i = 0; i < ans.length; i++) {
        ans[i] = deck[deque.removeFirst()];
    }
    return ans;
}

Solution 1 takes O(N^2) time, O(1) space, it requires sort the array. Then iterate the element 1 by 1. The point is to memorize the previous element where it reaches. Then calculate for current is based on previous reach.

// reach is the height it should reach on each element
public static int minIncrementForUnique3(int[] A) {
    int ans = 0, reach = Integer.MIN_VALUE;
    Arrays.sort(A);
    for (int a : A) {
        reach = Math.max(a, reach + 1);
        ans += a >= reach ? 0 : reach - a;
    }
    return ans;
}

Second solution takes O(N + KlogK) time, where K is the number of different number in array. Use TreeMap to store the number for each element. Still remember previous element where it reaches.

Increment is the size for green part. Come up with a formula to calculate that part.

public static int minIncrementForUnique(int[] A) {
    TreeMap<Integer, Integer> tm = new TreeMap<>();
    for (int a : A) {
        tm.put(a, tm.getOrDefault(a, 0) + 1);
    }
    int reach = Integer.MIN_VALUE, ans = 0;
    for (Map.Entry<Integer, Integer> entry : tm.entrySet()) {
        int key = entry.getKey(), num = entry.getValue();
        reach = Math.max(reach + 1, key);
        ans += reach * num + num * (num - 1) - key * num;
        reach += num - 1;
    }
    return ans;
}

Solution 3 is similar to solution 1. Since the element in A[] won’t be greater than 4000. So create an array with length 4000. Do similar solution as solution 1.

leastOpsExpressTarget(int x, int target)

1. when x > target. min{2 * target – 1, (x – target) * 2}. For example, n = 5, target = 3. First option is 5/5+5/5+5/5. Second option is 5-5/5-5/5. So, formula is

2. needs to calculate the product=x*x*…*x to approach target.

int k = 1;
long product = x;
while (product < target) {
    product *= x;
    k++;
}

3. when product==target, answer is k – 1. For example, n=3, target=27. 3*3*3 has totally 2 operators.

4. when product > target, we need to check if product –  target > target. Because the next round, we should only step in smaller set. Or else there would be circle. For example:

in that case, when product > target and product – target > target, resultRight = leastOpsExpressTarget(x, product – target) + k

5. Calculate product / k case. resultLeft = leastOpsExpressTarget(x, product/x) + k – 1

6. result = min{left, right}

https://leetcode.com/problems/delete-columns-to-make-sorted-iii/

1. Naive way O(n^2) to calculate longest subsequence

dp[i] is the longest subsequence ending with i position.

if charAt(j) <= charAt(i), then dp[i] = max(dp[i], dp[j] + 1)

2. Only cares about column i, column j, where all chartAt(j) <= charAt(i), then we update dp[i]

public static int minDeletionSize(String[] A) {
    int[] dp = new int[A[0].length()];
    Arrays.fill(dp, 1);
    int res = A[0].length();
    for (int i = 0; i < A[0].length(); i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < A.length; k++) {
                if (A[k].charAt(j) > A[k].charAt(i)) {
                    break;
                }
                if (k == A.length - 1) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        res = Math.min(res, A[0].length() - dp[i]);
    }
    return res;
}

@JsonIgnoreProperties is used in jackson deserialization. When a json file is deserialized to a class, it is ok that field is missing. For example, we have class A:

@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
public class A {

    @JsonProperty
    int a;

    @JsonProperty
    int b;
}

It is ok to deserialize {“a”:1}, which misses field b.

But it is not ok to deserialize {“a”:1, “b”:2, “c”:3}

In order to be able to deserialize a stream with unknown field, we need to use @JsonIgnoreProperties annotation:

@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
@JsonIgnoreProperties(ignoreUnknown = true)
public class A {

    @JsonProperty
    int a;

    @JsonProperty
    int b;
}