BST Binary Search Tree Sep 20, 2017

Feature: In-order traverse --> sorted array

Tree Traverse Template:
• Pre-order: Operation, func(root.left), func(root.right)
• In-order: func(root.left), Operation,func(root.right)
• Post-order: func(root.left), func(root.right), Operation

Tree common template
• Stop condition:
  

  if(root == null) return;

• Traverse

XOR Sep 20, 2017

Feature: a ^ b ^ b = a

Usage:
• Swap 2 numbers without extra space.
• Odd, Even problem.
  Odd: get the number. Even: dissapear

Palindrome Sep 20, 2017

• Stack: Push and pop, the same
• One char as center, two pointers scan each side(Remember to seperate Odd and Even length)

String Operations Sep 20, 2017

Remember regex operation.

Delete Duplicates in one scan Sep 20, 2017

//Copy non-dup to the front of the arr
int len = 0;
for(int i=0 ; i < nums.length ; i++)
{
    if(val != nums[i])
    {
        nums[len] = nums[i];
        len++;
    }
}

Linked List-add node Sep 20, 2017

• Add orderly

//1, Create HeadNode
ListNode p = new ListNode(0);
ListNode head = p;
//2,Add
ListNode tempResult = new ListNode(0);
p.next = tempResult;
p = p.next;

• Add reversely

//1, Create HeadNode
ListNode newHead = new ListNode(-1);
while(head != null)
{
    ListNode temp = head.next;//tempNode
    head.next = newHead.next;
    newHead.next = head;
    head = temp;
}

Zigzag String Sep 20, 2017

// Simulate is fine.
    a   e
     b d f
      c   g

Int overflow Sep 20, 2017

• int cast to long then compare
• abs(INT_MIN) = abs(INT_MAX) +1

Continuously Get min/max Sep 20, 2017

• Priority Queue
• Sorted Array
• Heap

String to Int Sep 20, 2017

Calculate Sign, then pile them

//1,Sign
sign = 1 - 2 * (str[i++] == '-');
//2, Add(in and against the order)
base  = 10 * base + (str[i++] - '0');//in order
    //or
for(int i=str.length()-1 ; i>=0 ; i--)// against order
{
    result += (str.charAt(i)-'0') * Math.pow(10,p);
    p ++;
}

3 Sums Sep 20, 2017

• p pointer-> first num (outer loop)
• low pointer,high pointer -> scan the other part of arr, like binary search
• Compare scaned elements to avoid dupicates (low ?=low--, high?=high++)
• O(n^2)

Find n to the end Sep 20, 2017

• let pointer p walk n
• then q(from start) and p walk together
• when p reach the end, then q are now n from end
• Notice: when==-1, it must be headNode, return head

Blank Sep 20, 2017

• let pointer p walk n
• then q(from start) and p walk together
• when p reach the end, then q are now n from end
• Notice: when==-1, it must be headNode, return head

Two Binary Search(1) Sep 21, 2017

//1, Normal one
while(low<=high) // here "="
{
    mid = (low + high)/2;
    if(arr[mid] > x)
        high = mid - 1;
    else if(arr[mid] < x)
        low = mid + 1;
    else if(arr[mid] == x)
        return mid;
}
return -1;

Two Binary Search(2) Sep 21, 2017

//2, Insert elements or find the first target
while(low <= high)
{
    int mid = (low+high)/2;
    if(nums[mid]>=target)
        high = mid-1;
    else
        low = mid+1;
}
return low;
// eg: [1,2,2,2,3] target=2, result: 1 (leftest one found)
//     [1,3,3,3,4] target=2, result: 1 (insert index)

Recursive Problem Sep 23, 2017

• Give a simple example
• Solve the simple example step by step
• Give a bigger example
• Conclude the rule, find the duplicate steps and recursive.

Long Number Operation Sep 25, 2017

Backtracking Oct 6, 2017

• Write a Helper Function: take more papams
• Base case
• Choose
• Recursive: explore.
• Unchoose
• (Can use for loop)
• Question

Total Unique Paths -- DP Oct 14, 2017

• Recognize it is a DP problem.
• Find the equation from the edge.
• Init edge to 1
• map[i][j] = map[i-1][j]+map[i][j-1]
• return map[i-1][j-1]

Min Edit Distance -- DP Oct 18, 2017

• Recognize it is a DP problem.
• Define dp[][] meaning.
• Boundary
• General: Using matrix exaple or Suppose have previous stage data
• return
• Question
• Solution

Interleaving String -- DP Sep 17, 2017

• Try backtracking : TLE
• Reason: So many duplicate actions
• Use DP
• Question
• Solution

Construct Binary Tree from Preorder and Inorder Traversal Sep 17, 2017

• Preorder[0]: root
• Find index of preorder[0] in inorder
• Inorder[0-index]:left subtree
• Inorder[index-end]:right subtree
• Recurse
• Question

Path Sum II Sep 17, 2017

• When using recursion and want to take a Class Object as a parameter, pay attention to reference passing or value passing. If you want reference passing, create a copy of the previous object.
• In java: Basic types--Value passing; ClassObject--Reference passing
• Question

Tree Recursive Problems Sep 19, 2017

• Use a Simplest Tree as example.
• Summary the recursive prototype
• More Complicated example to find tricks

Consecutive Sequence Sep 19, 2017

• Require: O(n)
• If hashtable is Memory Exceeding Limit
• Use HashSet
• Ask, instead of find
• (Increase 1 at a time, and ask whether it is in the set)
• Question

HashMap put return value Sep 20, 2017

• HashMap put method returns :
• the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.
• So can use it to detect duplicate values
• Question

Iterate HashMap Sep 20, 2017

public static void printMap(Map mp) {
    Iterator it = mp.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry pair = (Map.Entry)it.next();
        System.out.println(pair.getKey() + " = " + pair.getValue());
        it.remove(); // avoids a ConcurrentModificationException
    }
}

Tree Leaves Jan 3, 2018

// if mentioned leaves, must be root.left == null && root.right == null
// plus    an operation on this node
if(root.left == null && root.right == null) { //leaf
    step = step + "->" +root.val;             //operation on this node
    result.add(step.substring(2, step.length()));
    return;
}

BST + Lowest Common Ancestor Jan 3, 2018

// 只要p和q在一个subtree里，就说明不是lowest，直到第一个让它们俩不在一个subtree的时候
// Attention: This is a Binary Search Tree

• Question

Tree Height Jan 8, 2018

// Base case return -1
int treeHeight(TreeNode root) {
    if(root == null)    return -1;
    return Math.max(treeHeight(root.left), treeHeight(root.right)) + 1;
}

Traverse Tree Iteratively Jan 9, 2018

• Using stack, to store the later used subtree
• Question

Count Set Bits of IntegerJan 18, 2018

• Brian Kernighan's Algorithm
• Question

 // O(log(n))
int count_set_bits(int n){
    int count = 0; // count accumulates the total bits set
    while(n != 0){
        n &= (n-1); // clear the least significant bit set
        count++;
    }
}

Topological Sort Jan 27, 2018

• Example problem: dependency problem
• Need to define a "Node" class
  • int bePointedCount
  • ArrayList(Node) children
  • boolean isDone = false
• Need a Set to remember remain nodes, if in a loop, remain.size() doesn't change, means there is loop
• Question

DFS Template Jan 31, 2018

 // DFS
boolean dfs(int[][] n, boolean[][] visited, int row, int col){
    if(...)
        return true;
    if(row < 0 || col < 0 || row >= board.length || col >= board[0].length || visited[row][col])
        return false;
    if(condition) {
        visited[row][col] = true; // make it visited
        boolean found = dfs(n, visited, row + 1, col);
        found |= dfs(n, visited, row - 1, col);
        found |= dfs(n, visited, row, col + 1);
        found |= dfs(n, visited, row, col - 1);
        if(!found)
            visited[row][col] = false; // if unsucessuful, turn visited back
    }
}

• Question

Majority Mar 10, 2018

• Boyer-Moore Majority Vote algorithm
• O(n) time + O(1) space
• Question

Check Parentheses August 7, 2018

// Count left ( then pair it with )
public boolean isValid(StringBuffer str) {
    int count = 0;
    for(int i = 0; i < str.length(); i++) {
        if(str.charAt(i) == '(')
            count ++;
        else if(str.charAt(i) == ')')
            count --;
        if(count < 0)
            return false;
    }
    return count == 0;
}