Progress: 2018

• 5/1 Go over basic data structure in Java
• 7/18 LC 60
• 7/30 LC 100
• 8/5 LC 117
• 8/9 LC 130
• 8/14 LC 147
• 9/9 LC 176

2019

• 5/29 LC 209

• Tutorial link
• Pracetice Question Leetcode 307

7/31/18

• Need more understanding
• Question LC397
• LC 401

Integer.countBits(h * 64 + m) == num // count 1 bits in the integer

• Do some more reading (TO DO)
  • detail explaination of bit manupulation 8/2
  • Java Bit Operator 8/2
  • Binary Arithmetic
• LC 389 and LC 138 Find single number
  • if one element only shown at once but others show twice
  • we should use XOR to deal with this problem

• Data Structure, Implementation
• Understand Java Comparator
• Question LC 451 and LC 347

8/18

• LC 70

• LC 64
• LC 95/96 Not sure about the answer
• Reading tutorial This Link
• Coin change problem Coin Change I and II.
• LC 1029. Assign people to different cities (A and B). dp[i][j] is the minimum cost after you assigning i + j people. The index can be treated i person to A, j persons to B. You can either assign people to A or B, then the dynamic programming equation is:dp[i][j] = Math.min(costs[i + j -1][0] + dp[i-1][j],costs[i + j - 1][1] + dp[i][j-1]). It means "the cost of sending this person to city A/B + best in last step".
• LC 1027; Arithemic sequence.

dp[diff][index] // diff: difference bewtween two number i and j. index: the index of number j
Map<Integer,Integer> m = dp.computeIfAbsent(computation, func()); // a userful map method in java.

• LC 179
• Learn to use Java Comparator Class

Comparator<String> comp = new Comparator<String>(){
  @Override
  public int compare(String s1,String s2){
    return (s2 + s1).compare(s1 + s2);
  }
};

Arrays.sort(arr,comp);

• In the version of java 8 and after, we have a better way for the pointer. From LC 658 Binary Tree Search

 Collections.sort(arr, (a,b) -> a == b ? a - b : Math.abs(a-x) - Math.abs(b-x));

• String builder is faster and robust

• LC 207
• Kahn's Algorithm

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

• DFS (In practice, DFS is shown slower than BFS)

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
    
function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop   (not a DAG)
    mark n temporarily
    for each node m with an edge from n to m do
        visit(m)
    mark n permanently
    add n to head of L

• Tutorial
• Implement Trie Tree in this Repo
• Various applications

• LC 386
• Definition

• LC 415 Add String
  • Compute number from String
  • StringBuilder.reverse()

int x = num1.charAt(i) - '0';

• LC 453 Minimum Moves to equal array elements (n - 1 increments == 1 decrements)
• LC 456 Minimum Movies to equal array elements (1 increments or decrements). Best solution is moving all elements to the median
  • Use quick select to find the median in O(n). worst case running time is O(n^2)
  • quickSelect: 1) Use partition idea in quick sort to find the pivot. 2) check if pivot is the median or k-th largest element. 3) if not, only need to check larger part or smaller part based on what you are looking for.

// from wikipedia
function partition(list, left, right, pivotIndex)
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  // Move pivot to end
     storeIndex := left
     for i from left to right-1
         if list[i] < pivotValue
             swap list[storeIndex] and list[i]
             increment storeIndex
     swap list[right] and list[storeIndex]  // Move pivot to its final place
     return storeIndex

• LC 382 Count sample size within constructor is much faster than reservoir sampling. But reservoir sampling does not require the size of the sample
• Blog Reading
• LC 398 Pick up an index.

// how the possibility works
Random rand = new Random();
if( rand.nextInt(countOfItem) == 0 ) // pick this one;

• LC 284
• Make use of Java iterator

• LC 567
• Create sliding window substring to identify permutation

int[] map = new int[26];
        
for(int i = 0 ; i < s1.length(); i ++){
    map[s1.charAt(i) - 'a'] ++;    
    map[s2.charAt(i) - 'a'] --;
}
if(allZeroes(map)) return true;
for(int i = 0; i < s2.length() - windowSize; i ++){
    map[s2.charAt(i + windowSize) - 'a'] --;
    map[s2.charAt(i) - 'a'] ++;
    if(allZeroes(map)) return true;
}

• LC 452
• LC 948: Bag of token
  • Use smallest token to obtains points; Use point to exchange highest token -> Greedy Options.

• Insertion sort O(n) -> O(n^2)
• Selection sort O(n^2)
• Merge sort divide and conqueor Implemented
• Quick sort, randomized algorithm, applied expectation and random variable to solve the running time.
• Heap sort Implemented
• Stability of a sorting algorithm read this post
• Linear time sort O(n)
  • Counting sort - required previous knowledge the range of array
  • Bucket sort - Review for the random variable. Assume the uniform distribution. Proof by Linearity of Expectation
• Patience sort - find minimum number of ascending subsequence from an array. Implement by the priority queue.
• LC 791; Bucket sort for string - 1) create a bucket with 26 characters counts; 2) add char that are in bucket and original string, and clear that slot to 0; 3) Add characters in original string but not in sorted pattern into string; 4) Return the string.

• LC 560 Store the cumulative sum and number of appearance

• LC 241 Different Ways to Add Parentheses. Find all combination of computation from a given string.

• LC 721 merge acount
• For union find, the key idea is find a representative for each element. Then, group all items into a set with same representive/parent.

• Stack-like question is not necessarily using the data structure Stack. Try to abstract the stack idea by reversing whole problem.
• LC 880 Decode string
  • Count the letter + check if it is digit to find the longest string we need to check
  • Going backward from the end of this string
    • If start at a digit, going backward by divide the digit since it comes from multiplication.
    • If start at a char, then do increment and move backward
    • find the index of char and return it.

• LC 795
  • Idea: Each Iteration, we have three conditions.
    1. A[i] is in range, we increase result by i - j + 1, and remember how many we add to result.
    2. A[i] < L, the previous subarrays will still works, then we add what we remembered
    3. A[i] > R, the previous subarrays are not valid anymore, we reset count to 0, and change index j = i + 1.