# Monthly Archives: June 2019

## lc950 Reveal Cards In Increasing Order

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;
}```

## lc945. Minimum Increment to Make Array Unique

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.

## lc964. Least Operators to Express Number

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}

## lc960. Delete Columns to Make Sorted III

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;
}```

## HEAD detached

You may have below after git log:

```commit f6601f5ae74d5b61303b17f1edcb56a6755c18ea

Commit message

commit 1e98a15d9a182ba965955bc960fa394a3de5c36a

Commit message...```

git branch shows:

```8c85904323f8:AlexaMacawDeciderService lipl\$ git branch
* (HEAD detached from refs/heads/lipl-branch-name)
branch1
branch2
branch3
mainline```

Also it shows HEAD detached. It is good time to create a branch and specify most recent commit:

`git branch new-branch-name f6601f5ae74d5b61303b17f1edcb56a6755c18ea`

Thus, git branch shows that a new branch based on current commit was created:

```8c85904323f8:AlexaMacawDeciderService lipl\$ git branch
* new-branch-name
branch1
branch2
branch3
mainline```

## @JsonIgnoreProperties

@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;
}```

## wait(), notify(), notifyAll(), sleep()

wait(), notify().

obj.wait() will release the object’s lock, until some other thread calls obj.notify(). When calling obj.wait(), current thread should own obj. Normally, it is called like:

synchronized(obj) { // acquire obj
obj.wait();
}

IllegalMonitorStateException will be thrown if current thread doesn’t own obj.

obj.notify() wakes up single thread which waits for obj lock.
obj.notifyAll() wakes up all thread which wait for obj lock. But they will compete for the lock.

sleep() will still hold the lock.

https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#wait–

## Visitor pattern

1. ```1. Visitable
public interface Visitable {
int accept(Visitor visitor);
}

2. ConcreteVisitable
public class LiquorVisitable implements Visitable {
@Override
int accept(Visitor visitor) {
return visitor.visit(this);
}
}

public class FoodVisitable implements Visitable {
@Override
int accept(Visitor visitor) {
return visitor.visit(this);
}
}

2. Visitor
public interface Visitor {
int visit(LiquorVisitable liquorVisitable);
int visit(FoodVisitable foodVisitable);
}

public TaxVisitor implements Visitor {
@Override
int visit(LiquorVisitable liquorVisitable) {
// calculate liquor tax
return ...
}

@Override
int visit(FoodVisitable foodVisitable) {
// calculate food tax
return ...
}
}```

We have items: liquor, food. TaxVisitor is used to calculate all the tax on them. Considering holiday has different tax. We can create a HolidayTaxVisitor to calculate the tax on each item on holiday.

https://www.geeksforgeeks.org/visitor-design-pattern/