Category Archives: algorithm

UML Arrows

Aggregation Books is a part of Library. Dismiss of Library, it won’t lead dismiss of books.   class Library {     Book book; } Composition Library has books. Dismiss of Library, then books will be dismissed as well. class Library {     Book book; } Generalization/Extends BankAccount implements Fixed Account class BankAccount extends… Read More »

lc 600. Non-negative Integers without Consecutive Ones

100100001000 One[i]:  1XXXXXXXXXXXXX Zero[i]: 1XXXXXXXXXXXXX Zero[i] = zero[i + 1] + one[i + 1]; One[i] = zero[i] One[i] is the number of combination without continuous 11, with MSB 1 Zero[i] is the number of combination without continuous 11, with MSB 0 Then go over from MSB to LSB. If at any position, it has XX00YY,… Read More »

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… Read More »

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)… Read More »

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;… Read More »

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 =… Read More »

@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… Read More »

lc 654 Maximum Binary Tree

We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree. Just as in the previous problem, the given tree was constructed from an list A (root = Construct(A)) recursively with the following Construct(A) routine: If A is empty, return null. Otherwise, let A[i] be the largest element of A.  Create a root node with value A[i]. The left… Read More »

Local/Instance/Class variable

Local variable, variable defined inside method, constructor or block. Instance variable, a variable inside class. It can be instantiated. Class variable, inside class, but outside method. Must be static. Only one copy per class. public class MyTest { static String str = “abcd”; // classs variable, only one copy private String a = “123”; //… Read More »