九章 HIgh Frequency

九章 HIgh Frequency

1. Single Number I, II, III -> given an array of integers, every element appears twice except for two. find the two signles
2. Majority Number I, II, III
3. Best time to buy and sale stock I, II, III
4. Subarray I, II, III, IV
5. 2-Sum, 3-Sum, 4-Sum, k-Sum, 3-Sum Closest
6. Quick Questions

异或 xor
-不进位加法
-相同为0，不同为1

a^b=c
=> a^c = b
=> b ^ c = b

a^0 = a
a^a=0//抵消
a^(b^c) = (a^b)^c
c - c & (c-1) -> the low bit of c

Majority Number II
反例：1 0 3 10 4 1 1 2 2 2

Majority Number III
1. 保存k-1个数
2. O(1) 查询是否在这个集合中
3. O(1) count++
4. O(1) 插入
5. 对集合的所有数 count--

时间复杂度：看每个元素的操作次数-》每个元素进出数据结构几次

抵消的思路来实现O(1)的空间复杂度

Best Time to Buy and Sell Stock

九章 Data Structure

九章 Data  Structure

Linear Data Structure
1. Queue
2. Stack
3. Hash
Tree Data Structure
1. Heap
2. *Interval Tree

Min-Stack
Implement a stack, enable O(1) push, pop, top, min. Where Min() will return the value of minimum number in the stack

Implement a queue by two stacks
Q.push(x);
 S1-Push(x)
Q.pop():
  if S2.empty -> S1->S2
  S2.pop()
Q.top()
  Similar with Q.pop()

Largest rectangle in histogram

Construct MaxTree
find the first left and right bigger number of an element, and the smaller one of those two will be the parent of this element

Hash
Operations
  Insert - O(1)
  Delete - O(1)
  Find - O(1)
Hash Function
Collision
  Open Hashing (LinkedList)
  Closed Hashing (Array)
Hash Function
Typical: From String to int

int hashfunc(String key) {
  //do something to key
  //return a deterministic integer number
  return md5(key) % hash_table_size;
}

APR hashfunc - Magic Number 33
int hashfunc(String key) {
  int sum = 0;
  for (int i = 0; i < key.length(); i++) {
    sum = sum * 33 + (int)(key.charAt(i));
    sum = sum % HASH_TABLE_SIZE;
  }
  return sum;
}

Rehashing

Jave
What's differences of
HashTable-> thread safe
HashSet
HashMap
Which one is thread safe?

C++里面set是用红黑树实现的

LRU
Queue -> doesn't work
 1. Lookup
 2. delete
 3. insert
DoubleLinkedList + HashMap

Jave
LinkedHashMap = DoublyLinkedList + HashMap

Longest Consecutive Sequence

Heap
Operations
  Add O(log N)
  Remove O(logN)
  Min/Max O(1)
Heap - Implementation
Low Level data structure: Dynamic Array
  Heap {
    elems[], size;
 }
 elems[1] - root, also the minimum ele in elems
 i's left child: i * 2, right child: i * 2 + 1
Internal Method: siftup, siftdown
Add:
  push back to elems: size++; siftup
Remove:
 Replace the elem to be removed with the last elem; size --; sift up and sift down

Get median number

Building Outline -> scab line + heap to get max height

Trie -》 做stream of data的时候比较有用

九章 Dynamic Programming

九章 Dynamic Programming



// 从x，y出发，往下走的所有路径中，最小路径的权重之和是多少
int dfs(int x, int y) {
  if (x == n) {
    return 0;
  }
  if (hash[x][y] != -1) {
    return hash[x][y];
  }

  hash[x][y] = min(dfs(x+1, y), dfs(x+1, y+1)) + a[x][y];
  return hash[x][y];
}

dfs(0,0);
O(2^n)

(1, 0) -> (2,0), *(2,1)
(1,1) -> *(2, 1), (2,2)
O(n^2)
//记忆化搜索 Memorize Search

DP -> 记忆化搜索

//for
state: f[x][y] 表示从0,0出发， 到达x，y这个点的最短路径长度
function: f[x][y] = min(f[x-1][y], f[x-1][y-1]) + a[x][y];


动态规划的4点要素
1.状态State（灵感，创造力，存储小规模问题的结果）
2. 方程Function （状态之间的联系，怎么通过小的状态，来算大的状态）
3. 初始化 Initialization （最极限的小状态是什么，起点）
4. 答案 Answer （最大的那个状态是什么，终点）

Recursive VS DP
递归是一种程序的实现，方式是函数的自我调用
Function(x) {
  ...
  Function(x-1)
  ...
}
动态规划是一种解决问题的思想：大规模问题的结果，是由小规模问题的结果运算得到。动态规划可以用递归来实现(Memorization Search)

面试最常见的四种类型
1. Matrix DP（10%）
2. Sequence (40%)
3. Two Sequences DP (40%)
4. Backpack (10%)

如何想到使用DP
1. One of the following three:
a) Find a maximum/minimum result
b) yes/no
c) count all possible solutions
2. Can not sort (Can not swap)
   longest consecutive sequence

1. Matrix DP （triangle， unique path， Minimum Path Sum，...）
state: f[x][y] 表示从起点走到坐标x，y。。。。。。
function：研究最后一步怎么走
initialize：起点f[0][0] // f[0][i] f[i][0]
answer: 终点

2. Sequence DP （climbing stairs, jump game，Palindrome Partition II， word break，longest increasing subsequence）
state：f[i]表示“前i”个位置，数字，字母(以第i个为）。。。
function：f[i] = f[j]... j是i之前的一个位置
initialize: f[0]..
answer: f[n-1]..

3. Two sequence DP （longest common subsequence， longest common substring， edit distance, distince subsequence, interleaving string)
state：f[i][j]代表了第一个sequence的前i个数字，字符配上第二个sequence的前jge
function：f[i][j]=研究第i个和第j个的匹配关系
initilize：f[i][0]和f[0][i]
answer：f[s1.length()][s2.length()]

4. Backpack
题目：给n个正整数，一个数target，问能否从n个数中却出若干个数，他们的和为target
state：f[i][s]前i个数字，取出一些能否组成和为s
function：f[i][s]=f[i-1][S-a[i]] or f[i-1][s]
initialize:f[0][0]=true;f[0][1...SUM]=false
answer:f[n][target]

K Sum
n个数，取k个数，组成和为target
state：f[i][j][t]前i个数取j个数出来能否和为t
function:f[i][j][t] = f[i-1][j-1][t-a[i]] or f[i-1[j][t]
1.问是否可行（DP）
2.问方案总数 （DP）
3. 问所有方案（递归、搜索）

最小调整代价
n个数，可以对每个数字进行调整，使得相邻两个数的差都是小于target，调整的费用为
sigma（A[i]-B[i])
A[i]
A[i] < 200, target < 200
让代价最小
O（n*200*target）
state：f[i][v]前i个数，第i个数调整为v，满足相邻两个数小于等于target，所需要的最小代价
function：f[i][v] = min(f[i-1][v'] + |A[i] - v|, |v-v"|< target)

九章 Linked List

九章 Linked List

1. dummy nodes
  remove duplicates from sorted list
  remove duplicates from sorted list II

scenario: when the head is not determinated
    1. remove duplicates from sorted list I, II
    2. Merge Two sorted Lists
    3. Partition List
    4. Reverse Linked List I, II
    ....

Basic skills
1. insert a node
2. delete a node : a trick ->     a -> b -> c -> d
                               if you already loop at c, you cannot go back
                               you can copy d's value to c, then delete d, 偷梁换柱
3. reverse linked list:  a -> b -> c -> null
                                always keep updating three nodes: prev, cur, next
4. merge two linked list /  merge k sorted list
5. find middle of linked list
(c -> pass by value or pass by reference)
sum(int a)
sum(int* a)
sum(int& a)
sum(const int& a)
6. sort list nlog(n)
 6.1 find mid
  6.2 right = sortlist(mid.next)
   6.3 mid.next = null
   6.4 left = sortlist(head)
    merge(left, right)
7. reorder list
8. linked list circle

9. copy a linked list with next and arbit pointer

10. add two large numbers represented by linked list

11. convert sorted linked list to balance tree

九章 Binary Search

九章 Binary Search

1. find the first target
2. find the last target
3. find the range of a target [leetcode]
4. find the insert position of a target [leetcode]
5. find in rotated sorted array [leetcode]
6. find in rotated sorted array (with duplication in the array) [leetcode]
7. search a 2D Matrix
8. search a 2D matrix (not extremely bigger in each row)      
9. find the first bad version
10. find a peak


Sorted array  
1. remove duplicate from array  
2. merge sorted array
3. Median of two sorted array
4. find kth of two sorted array
5. recover rotated sorted array  -> offset
6. rotated string
7. reverse word lists