总结

general
遇到问题将算法模块化，可以假设一些方法已经给出或者之后再编写，可以加快找出主体思路的速度，减少浪费时间在细节上

*先想test case

-----------------------------------------------------------------------
tree

https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-binary-search-and-red-black-trees/



#遇到prefix，stream of strings等，上tries

#（写法）递归时，在返回所需要的极值，传入pointer同时计算partial的值（如height，path sum）
例子：
LC #124 Binary Tree Maximum Path Sum
GeeksforGeeks: Diameter of a Binary Tree
# 另一种写法，返回的是partial的值，参数中pass by reference一个极值

#(写法) bfs，用一个queue和size来区分每一层，例子：level order traversal等等 #1 bst
遇到bst题目先考class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0) return 0;
        int dp0 = costs[0][0];
        int dp1 = costs[0][1];
        int dp2 = costs[0][2];
        
        for (int i = 1; i < n; i++) {
            int t0 = dp0, t1 = dp1, t2 = dp2;
            dp0 = costs[i][0] + min(t1,t2);
            dp1 = costs[i][1] + min(t2,t0);
            dp2 = costs[i][2] + min(t1,t0);
        }

        return min(min(dp0,dp1),dp2);
    }
};虑in place遍历方法：pre - in - post（#94，#144，#145，#105，#106）
注：#94跟#173的单stack写法

dfs寻找路径，可以用一个大小为树的高度的vector跟int level表示当前高度

-----------------------------------------------------------------------
string
palindrome(LC: #5, #9, #125, #131, #132, #214), 可以预先用DP检测palindrome存值

-----------------------------------------------------------------------
dp
from Tara: 局部最优解关键词：最大，最小，至少，至多

从recursion引出dp

string类的，先从小的test case下手，如(ab,b) 
例题：LC #115,distinct subsequence

矩阵类（见矩阵词条）

多层dp，paint house

-----------------------------------------------------------------------
array
直接上：双指针和hashmap
-----------------------------------------------------------------------
subsets / combination
此类问题有2种解题思路（LC #90，#77，#39， #40）
假如有集合{1，2，3，4，5}
#1 传统combination
递归: 第一层递归，每次取{}空集合，各插入一元素。第二层递归，此时集合内含有一个元素，每次插入index大于它的元素
第一层{1},{2}, {3}, {4}, {5}
第二层{1, 2}, {1,3},{1,4}, {1,5},{2, 3}, {2,4},{2,5},{3,4}.....
第三层{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5}.....{2,3,4},{2,3,5}......
.....

遍历：看LC #90 Subsets代码

#2 类似bitmap
集合内的每个元素都有2种情况--被包括在集合或不被包括在集合
递归：见Google interview questions #2，第2题

遍历：
subsets的总个数为 2^原集合的大小，设一个loop大小为总个数，把每一个从0 到 总个数 - 1（看做二进制）的数作为bit mask，来跟原集合对应
看LC #90 Subsets代码
-----------------------------------------------------------------------
math
#1加减法, LC #2，#66，#67， 
#1 各种类型与integer的暂时互相转化
#2 carry可以用来当sum用
#3 loop的终止条件配合loop内的判断
#4 dummy node

--------------------------------------------------------------------
矩阵
矩阵路径：如果只能往下和往右走的话，用recursion或者dp (LC #130, #200)
如果增加其他方向，Dijkstra和普通的BFS都可以适用 (Google interview questions #3, 后几题) (Google interview questions #2, 第5题follow up)


矩阵中找最大的sub矩阵：
LC：#85 Maximal Rectangle, #221 Maximal Square, Google interview #6 倒数第2道，http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

------------------------------------------------------------------------
Linked List
快慢指针的使用：
如下循环结束后，slow将指向中点（奇数个）或指向后半部分的起点（偶数个）

ListNode *slow = head, *fast = head;
while (fast != NULL) {
    fast = fast->next;
    if (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
}

-------------------------------------------------------------------------
点跟线段，坐标
sort x或y
closest pair of points(code 见coursera 第一章)

找median
example: 见google interview #5 第1,2部分 的oil pipe，朋友矩阵

------------------------------------------------------------------
随机性的题（待写）
general，高中概率论：某个值最终被选中的概率 = 当前被选中的概率 * 之前没被选中的概率

扑克牌http://www.geeksforgeeks.org/shuffle-a-given-array/

用ran(5)生成ran(7): 二维数组
{[1,2,3,4,5],
  [6,7,1,2,3],
  [4,5,6,7,1],
  [2,3,4,5,6],
  [7,0,0,0,0]}

Reservoir sampling: Google interview questions #4 倒数第2题
https://en.wikipedia.org/wiki/Reservoir_sampling
http://www.geeksforgeeks.org/reservoir-sampling/

-------------------------------------------------------------
Sorting
Merge sort: count inversions, LC # 148，#88，#23，#21
radix sort/count sort/bucket sort: LC #164

------------------------------------------------------------------
游戏算法
https://www.topcoder.com/community/data-science/data-science-tutorials/%20algorithm-games/
定理：

• All terminal positions are losing.
• If a player is able to move to a losing position then he is in a winning position.
• If a player is able to move only to the winning positions then he is in a losing position.

第一个例子：The Game of Nim
当所有piles的size xor之后如果是0的话，当前为losing position，因为输的条件是0，从0开始第一步肯定会让xor的值变成非0。
如果当前xor为非0，则从最左侧的1的个数为奇开始，改变当前的pile，可使xor变成0

------------------------------------------------------------
Binary search
(写法)
while (left <= right) {
    ....
}
if target is not found, after the search, "left" is always the index where target should be inserted. and "right" equals to "left - 1"
LC #35, #74, #240

----------------------------------------
Divide and conquer
切两半，需要的值可能在任意一边，或者是横跨两边。
example：closest pair of points， lc #53 maximum subarray,

-------------------------------------------------------
Recursion
(写法)对于求各种集合的题（如permutation，combination，求所有path），sub-set可以用pass by reference来代替，减少递归时的空间，LC #113 Path Sum II

---------------------------------------------------
Graph
bfs： 例题：person找血缘关系，第2部分第8题

Union find: 代码，google interview #7 第一部分第1题
http://blog.csdn.net/dm_vincent/article/details/7655764
The input is a sequence of pairs of integers, where each integer represents an object of some type and we are to interpret the pair p q as meaning p is connected to q. We assume that "is connected to" is an equivalence relation:
case study:
http://algs4.cs.princeton.edu/15uf/

-----------------------------------
Interval的题
排序，merge或者split，见google#6，飞哥的题。LC的那几道

------------------------------------------
sliding window的题
当发现至少一个window符合要求时，以后的操作都要维护、保持这个window的合法性
例子： LC #3 Longest Substring Without Repeating Characters, #76 Minimum Window Substring 等等

--------------------------------------------------
Longest sub-string/sequence 类
考虑DP，lintcode上有一套

Google interview questions #1

找出二叉查找树中出现频率最高的元素。树中结点满足left->val <= root->val <= right->val。如果多个元素出现次数相等，返回最小的元素。 http://blog.csdn.net/luckyxiaoqiang/article/details/8934593

不用额外空间. in-order

struct TreeNode{
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int val) {
      this->val = val;
   }
};

void countNodesHelper(TreeNode *root, TreeNode *&pre, int &count, int &maxCount) {
 if (root == NULL) return;
 countNodesHelper(root->left,pre,count,maxCount);
 
 if (pre == NULL) {
    pre = root;
    count = 1;
  
 }else {
    if (pre->val == root->val) {
       count++;
       if (maxCount < count) {
          maxCount = count;
       }
    }else {
       count = 1;
    }
 }
   pre = root;
   countNodesHelper(root->right,pre,count,maxCount);
}

int countNodes(TreeNode *root) {
   int maxCount = 0,count = 0;
   TreeNode *pre = NULL;
   foo(root,pre,count,maxCount);
   return maxCount;
}

-----------------------------------------------
有一个函数
long compute(int i) {
return …;
}
返回值有可能出错概率是 p=1/10000。

还有一个函数
long total(int n) {
long s = 0;
for (int i =0; i < n; i++) {
   s += compute(i);
}
return s;
}
这样出错概率就是 np;

问： 如何改第二个函数，让他的出错概率小于p?

http://www.mitbbs.com/article_t/JobHunting/32996657.html
----------------------------------------------------------------------------------------------
REF http://www.mitbbs.com/article_t/JobHunting/32980969.html

1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
      （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
(string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
,b,b,b,a,c,bb, bbb, bb, abbba.

int countHelper(string &s, int left, int right) {
   int count = 0;
 
   while (left >= 0 && right < s.length()) {
      if (s[left] == s[right]) {
         count++;
         right++;
         left--;
      }else {
         break;
      }
   }
   
   return count;
}
 
int countPal(string s) {
   int count = 0;
  
   for (int i = 1; i < s.length(); i++) {
      count += countHelper(s,i - 1,i); // even
      count += countHelper(s,i,i); // odd
   }
  
   return count + 1;
}

2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长[连续]
路径。
例如（括号对应上面node）  [修改：还有条件是 连续]
   树：                     2
                 |            |            |                |
                5            7          3                 6
         （|       | ）（   | ）   （|）         （|       |）
            6       3         2          4             5       8
                                 |
                                  3

返回3因为 （2-3-4） 这条线。优化要求时间O(n)
DFS，tree寻找路径
increasing order

struct TreeNode {
    int val;
    vector children;
    TreeNode(int val) {
        this->val = val;
    }
};
 
int longestPathHelper(TreeNode *root, int &longest) {
  
    int cur = 1;
    for (int i = 0; i < root->children.size(); i++) {
        TreeNode *child = (root->children)[i];
        if (root->val == child->val - 1) {
            cur = max(cur,longestPathHelper(root->children[i],longest) + 1);
        }else {
            cur = longestPathHelper(child,longest);
        }
   
    }
    longest = max(cur,longest);
    return cur;
}
 
int longestIncreasingPath(TreeNode *root) {
    if (root == NULL) return 0;
    int longest = 0;
    longestPathHelper(root,longest);
    return longest;
}

返回路径

struct TreeNode {
    int val;
    vector<TreeNode *> children;
    TreeNode(int val) {
        this->val = val;
    }
};
 
void longestPathHelper(TreeNode *root,TreeNode *pre, vector<int> path, vector<int> &longestPath) {
    vector<int> curLongest;
    if (pre != NULL && root->val == pre->val + 1) {
        curLongest = path;    
    }
    curLongest.push_back(root->val);

    for (int i = 0; i < root->children.size(); i++) {
        longestPathHelper(root->children[i],root,curLongest,longestPath);
    }
    
    if (longestPath.size() < curLongest.size()) {
        longestPath = curLongest;    
    } 
}
 
void longestIncreasingPath(TreeNode *root) {
    vector<int> longestPath,path;
    if (root == NULL) return;
    
    longestPathHelper(root,NULL,path,longestPath);
    for (int i : longestPath) {
        cout << i << endl;
    }
}

3.时间区间合并问题，leetcode上有相似题，关键词interval

4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return 
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
（2）优化第一部分用O（log2(N)) 时间复杂度
如果存在超过 1/4 的数，则次数必定会覆盖length / 4, length / 2, length *（3 / 4）这3点中的至少一点，所以只要对这3点上的数做二分搜索，就能找到其长度，然后与 1 / 4的长度对比。复杂度为 O(lgN)

int findFirst(vector<int> &nums, int elem) {
  int left = 0, right = nums.size() - 1;
  
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == elem) {
      if (mid - 1 >= 0 && nums[mid - 1] != nums[mid]) {
         return mid;
      }
      right = mid - 1;
    }else if (nums[mid] > elem) {
      right = mid - 1;
    }else {
      left = mid + 1;
    }
  }
  
  return 0;
}

int findLast(vector<int> &nums, int elem) {
  int left = 0, right = nums.size() - 1;
  
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == elem) {
      if (mid + 1 < nums.size() && nums[mid + 1] != nums[mid]) {
       return mid;
      }
      left = mid + 1;
    }else if (nums[mid] > elem) {
      right = mid - 1;
    }else {
      left = mid + 1;
    }
  }
  
  return 0;
}

bool helper(vector<int> &nums, int index) {
  int last = findLast(nums,nums[index]);
  int first = findFirst(nums,nums[index]);
  
  if (last - first + 1 > nums.size() / 4) {
    return true;
  }
  
  return false;
}

bool longerThanAQuarter(vector<int> &nums) {
  int length = nums.size();
  return helper(nums,length / 4) || helper(nums,length / 2) || helper(nums,length - 1 -length / 4);
}

(3)完全平方解集，做一个：int minsol（int i）。
比如1=1^2 所以minsol(1)返回1,
2=1^2+1^2 返回2,
4=2^2或者4个1^2,1比4小， 返回1，
12=2^2+2^2+2^2或者3^2+3个1^2返回3.

DP

int shortest(int num) {
    int t = sqrt(num);
    if (t * t == num) return 1;
       
    vector<int> dp(num + 1,INT_MAX);
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= num; i++) {
    int sq = sqrt(i);
        if (sq * sq == i) {
            dp[i] = 1;
        }else {
            for (int j = 1; j < i / 2 + 1; j++) {
                dp[i] = min(dp[i],dp[j] + dp[i - j]);
            }
        }
    }
    
    return dp.back();
}

5.有一个游戏，他说是fishing game，给一个数组vector<int> Basket, 比如里面元素
是{2，3，5，1，3，4，7}
有A，B 2个player，规定只能从Basket2端选数字，意思就是A开始的话一开始A只能选2
或者7，然后B选，同样只能2端选。所以比如一开始A选了7，B只能从2和4中选。问给定
数组A能取的最大值。B的策略已知，是greedy，就是总会取最大的那个数。
写一个 int maxA（vector<int>& Basket）；
Lintcode, Coins in a Line III http://www.lintcode.com/en/problem/coins-in-a-line-iii/#
DP, Memoization. iteration待写

int helper(vector<int> &nums, int start, int end, vector<vector<int> > &dp) {
    if (start == end) return 0;
    if (start + 1 == end) {
        return min(nums[start],nums[end]);
    }
 
    if (dp[start][end] != 0) return dp[start][end];

    if (nums[start] < nums[end]) {
        end--;
    }else {
        start++;
    }
 
    int play_1 = helper(nums,start + 1,end,dp) + nums[start];
    int play_2 = helper(nums,start,end - 1,dp)  + nums[end];
 
    dp[start][end] = max(play_1,play_2);
    return max(play_1,play_2);
}

int play(vector<int> &nums) {
    vector<vector<int> > dp(nums.size(),vector<int>(nums.size(),0));

    return max(helper(nums,0,nums.size() - 2, dp) + nums[nums.size() - 1],helper(nums,0,nums.size() - 2, dp) + nums[nums.size() - 1]);
}

Day 113, ##, Basic Calculator II, Summary Ranges

Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

--------------------------------------------------
look ahead,COME_BACK, 如果加入括号呢？
注意对i的处理

class Solution {
public:
    long long lookAhead(string &s, int &i) {
        long long num = 0;
        while (i < s.length()) {
            if (s[i] == ' ') {
                i++;
            }else if (isdigit(s[i])) {
                num = 10 * num + s[i] - '0'; 
                i++;
            }else
                break;
        }
        
        i--;
        return num;
    }

    int calculate(string s) {
        long long num = 0, rt = 0;
        long long sign = 1;
        
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) {
                num = lookAhead(s,i);
            }else if (s[i] == '+') {
                rt += sign * num;
                sign = 1;
                num = 0;
            }else if (s[i] == '-') {
                rt += sign * num;
                sign = -1;
                num = 0;
            }else if (s[i] == '*') {
                i++;
                num *= lookAhead(s,i);
            }else if (s[i] == '/') {
                i++;
                num /= lookAhead(s,i);
            }
        }
        
        if (num > 0) return rt + sign * num;
        return rt;
    }
};

Summary Ranges 

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

----------------------------------------------------------
nums[i] == nums[i - 1] + 1 与 nums[i] - nums[i - 1] == 1 相比较，前者不会有溢出的问题
re-factory之后的代码

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int start = 0;
        vector<string> rt;
        if (nums.size() == 0) return rt;
        
        for (int i = 1; i <= nums.size(); i++) {
            if (i == nums.size() || nums[i] != nums[i - 1] + 1) {
                if (i - start == 1) {
                    rt.push_back(to_string(nums[start]));
                }else {
                    rt.push_back(to_string(nums[start]) + "->" + to_string(nums[i - 1]));
                }
                start = i;
            }
        }
        
        return rt;
    }
};

re-factory之前的代码

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int start = 0;
        vector<string> rt;
        if (nums.size() == 0) return rt;
        
        for (int i = 1; i < nums.size(); i++) {
            if ((long long)nums[i] - (long long)nums[i - 1] == 1) {
                continue;
            }
            if (i - start == 1) {
                string s = to_string(nums[start]);
                rt.push_back(s);
                start = i;
            }else {
                string s = to_string(nums[start]) + "->" + to_string(nums[i - 1]);
                rt.push_back(s);
                start = i;
            }
        }
        
        if (start == nums.size() - 1) {
            string s = to_string(nums[start]);
            rt.push_back(s);
        }else {
            string s = to_string(nums[start]) + "->" + to_string(nums.back());
            rt.push_back(s);
        }
        
        return rt;
    }
};

Day 112, ##, Count Complete Tree Nodes, Rectangle Area, Basic Calculator, Implement Stack using Queues, Invert Binary Tree

Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.

--------------------------------------------
O(logN * logN)，遇到perfect tree, 直接计算并返回，反之继续数儿子们
看了答案

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
       if (root == NULL) return 0;
       int left = 0, right = 0;
       TreeNode *leftItr = root, *rightItr = root;
       while (leftItr != NULL) {
           left++;
           leftItr = leftItr->left;
       }
       
       while (rightItr != NULL) {
           right++;
           rightItr = rightItr->right;
       }
       
       if (left == right) return pow(2,left) - 1;
       return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

iterative
检查右子树是不是perfect tree，如果是，则缺口在左子树，此时加上右边的个数。
如果不是，则缺口在右子树，此时加上左边的个数
此题关键在于对高度的判断，然后对树的分解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getHeight(TreeNode *root) {
        int height = 0;
        while (root != NULL) {
            height++;
            root = root->left;
        }
        
        return height;
    }

    int countNodes(TreeNode* root) {
        int height = getHeight(root);
        int count = 0;
        while (root != NULL) {
            if (getHeight(root->right) == height - 1) {
                count += 1 << height - 1;
                root = root->right;
            }else {
                count += 1 << height - 2;
                root = root->left;
            }
            
            height--;
        }
        
        return count;
    }
};

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

----------------------------------------------
看了答案

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        if (D < F || H < B || G < A || C < E) {
            return (H - F) * (G - E) + (C - A) * (D - B);
        }
        
        int right = min(D,H) - max(B,F);
        int top = min(C,G) - max(E,A);
        
        return (D - B) * (C - A) + (H - F) * (G - E) - right * top;
    }
};

Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

---------------------------------------------------------------------
看了答案，用初始化 sign = 1来处理符号，能解决特殊情况.
对()的处理

class Solution {
public:
    int calculate(string s) {
        stack<int> st;
        int sign = 1;
        int rt = 0;
        int num = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) {
                num = num * 10 + s[i] - '0';
            }else if (s[i] == '+') {
                rt += sign * num;
                sign = 1;
                num = 0;
            }else if (s[i] == '-') {
                rt += sign * num;
                sign = -1;
                num = 0;
            }else if (s[i] == '(') {
                st.push(rt);
                st.push(sign);
                sign = 1;
                rt = 0;
            }else if (s[i] == ')') {
                rt += num * sign;
                sign = st.top();
                st.pop();
                rt = sign * rt + st.top();
                st.pop();
                num = 0;
            }
        }
        
        if (num != 0) {
            return rt + sign * num;
        }
        
        return rt;
    }
};

Java, updated on Aug-16th-2018. 整体思路类似，只不过遇到数字做加减。上面c＋＋的算法是遇到符号做加减。

class Solution {
    public int calculate(String s) {
        Stack<Integer> st = new Stack<>();
        int i = 0;
        int eval = 0;
        int sign = 1;
        
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c == '(') {
                st.push(eval);
                st.push(sign);
                eval = 0;
                sign = 1;
            }else if (c == ')') {
                sign = st.pop();
                eval = st.pop() + eval * sign;
            }else if (Character.isDigit(c)) {
                String cur = "";
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    cur += s.charAt(i);
                    i++;
                }
                i--;
                eval += sign * Integer.parseInt(cur);
            }else if (c == '-') {
                sign = -1;
            }else if (c == '+') {
                sign = 1;
            }
            
            i++;
        }
        
        return eval;
    }
}

Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

----------------------------------------------------
用queue的大小来控制倒腾，只用一个queue，而不是两个

class Stack {
public:
    // Push element x onto stack.
    void push(int x) {
        topElem = x;
        q.push(x);
    }

    // Removes the element on top of the stack.
    void pop() {
        for (int i = 0; i < q.size() - 1; i++) {
            topElem = q.front();
            q.push(q.front());
            q.pop();
        }
        q.pop();
    }
    
    // Get the top element.
    int top() {
        return topElem;
    }

    // Return whether the stack is empty.
    bool empty() {
        return q.empty();
    }
private:
    queue<int> q;
    int topElem;
};

Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

---------------------------------------------------
recursive

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return NULL;
        TreeNode *temp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(temp);
        
        return root;
    }
};

iterative

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        queue<TreeNode *> que;
        que.push(root);
        
        while (!que.empty()) {
            TreeNode *node = que.front();
            que.pop();
            TreeNode *temp = node->left;
            node->left = node->right;
            node->right = temp;
            
            if (node->left != NULL) {
                que.push(node->left);
            }
            if (node->right != NULL) {
                que.push(node->right);
            }
        }
        
        return root;
    }
};

Day 111, ##, Contains Duplicate II, Contains Duplicate III, Maximal Square

Contains Duplicate II
Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between iand j is at most k. ------------------------------------------------
this is one of the onsite interview questiona at fb, and I failed

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> dic;
        for (int i = 0; i < nums.size(); i++) {
            if (dic.find(nums[i]) != dic.end()) {
                return true;
            }
            dic[nums[i]] = i;
            
            // save space
            if (i - k >= 0) {
                dic.erase(nums[i - k]);
            }
        }
        return false;
    }
};

Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
------------------------------------------------------------
方法1，bucket sort，O(n)，如果每个bucket里出现2个元素，则可直接返回true。所以确保了在程序运行过程中每个bucket只可能存在1个或者0个元素
casting的问题
k < 1 或 t < 0 直接返回false

(long long)t + 1, + 1是为了防止当t 为0

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (k <= 0 || t < 0) return false;
        unordered_map<long long,int> bucket;
        
        for (int i = 0; i < nums.size(); i++) {
            long long inter = nums[i] + 2147483648;
            long long curBucket = inter / ((long long)t + 1);
            if (bucket.find(curBucket) != bucket.end() 
                || (bucket.find(curBucket - 1) != bucket.end() && abs((long long)nums[i] - bucket[curBucket - 1]) <= t)
                || (bucket.find(curBucket + 1) != bucket.end() && abs((long long)nums[i] - bucket[curBucket + 1]) <= t)) {
                return true;
            }
            
            bucket[curBucket] = (long long)nums[i];
            if (i - k >= 0) {
                long long oldBucket = (nums[i - k] + 2147483648) / ((long long)t + 1);
                bucket.erase(oldBucket);
            }
        }
        
        return false;
    }
};

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.
-------------------------------------------------------------
看了提示tag
O(m * n) 空间, dp[i][j] 代表以i，j为右下角的正方形边长

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<vector<int> > dp(m,vector<int>(n,0));
        int maxSquare = 0;
        
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                maxSquare = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
                maxSquare = 1;
            }
        }
        
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = 1 + min(dp[i - 1][j - 1],min(dp[i - 1][j],dp[i][j - 1]));
                    maxSquare = max(maxSquare,dp[i][j]);
                }
            }
        }
        
        return maxSquare * maxSquare;
    }
};

O(n)空间优化，注意 else 语句将 dp[j] 清0

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<int> dp(n + 1, 0);
        int maxSquare = 0, pre = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n + 1; j++) {
                int temp = dp[j];
                if (matrix[i][j - 1] == '1') {
                    dp[j] = 1 + min(dp[j - 1],min(pre,dp[j]));
                    maxSquare = max(maxSquare,dp[j]);
                }else {
                    dp[j] = 0;
                }
                
                pre = temp;
            }
        }
        
        return maxSquare * maxSquare;
    }
};

Day 110, ##, The Skyline Problem

The Skyline Problem 

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

 

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

---------------------------------------------------
Runtime error, C++ vector<> has its maximum size.
Use a heightMap of size INT_MAX

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<int> heightMap(INT_MAX,0);
        for (int i = 0; i < buildings.size(); i++) {
            int left = buildings[i][0];
            int height = buildings[i][1];
            int right = buildings[i][2];
            
            for (int j = left; j < right; j++) {
                heightMap[j] = max(height,heightMap[j]);
            }
        }
        
        vector<pair<int,int> > rt; 
        int preHeight = 0;
        for (int i = 0; i <= INT_MAX; i++) {
            if (preHeight != heightMap[i]) {
                rt.push_back(make_pair(i,heightMap[i]));
            }
            
            preHeight = heightMap[i];
        }
        
        return rt;
    }
};

方法1：http://www.cnblogs.com/easonliu/p/4531020.html
一句话，找线段。将所有点按照x坐标排序，注意当点重复时，将线段左边点排在线段后边点之前。遍历所有点，遇到左点说明遭遇新线段，插入它的高度在heap。遇到右点说明线段终止，从heap删除该高度（线段）。对比当前跟之前的高度，就能确定线段分界点
因为只需要求的是building的轮廓，所以heap_top保留的是当前x坐标下最高的线段

以下为方法1
处理重复点
c++ 中operator方法的写法
priority_queue不提供中间删除操作
用map而不是set，防止当不同线段的头和尾重复时，确保删除正确

class Solution {
public:
    struct cmp {
        bool operator() (const pair<int, int>& p1, const pair<int, int>& p2) {
            if (p1.first == p2.first) {
                return p1.second < p2.second;
            }
            return p1.first < p2.first;
        }
    };

    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int,int> > points, rt;
        for (int i = 0; i < buildings.size(); i++) {
            points.push_back(make_pair(buildings[i][0],-buildings[i][2]));
            points.push_back(make_pair(buildings[i][1],buildings[i][2]));
        }
        sort(points.begin(),points.end(),cmp());
        
        priority_queue<int> heightMap;
        heightMap.push(0); // to handle end of a building
        unordered_map<int,int> deleted;
        int pre = 0;
        for (int i = 0; i < points.size(); i++) {
            // left point
            if (points[i].second < 0) {
                heightMap.push(-points[i].second);
            }else {
                // right point
                deleted[points[i].second]++;
                while (!heightMap.empty() && deleted[heightMap.top()] > 0) {
                    deleted[heightMap.top()]--;
                    heightMap.pop();
                }
            }
            
            int cur = heightMap.top();
            if (cur != pre) {
                rt.push_back(make_pair(points[i].first,cur));
                pre = cur;
            }
        }
        
        return rt;
    }
};

方法2：http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/
basic divide and conquer, 难度在于细节处理上。注意线段的结束点高度设为0

class Solution {
public:
    vector<pair<int,int>> merge(vector<pair<int,int>> left,vector<pair<int,int>> right) {
        vector<pair<int,int>> rt;
        int h1 = 0, h2 = 0;
        int i = 0, j = 0;
        while (i < left.size() && j < right.size()) {
            int x = 0, h = 0;
            if (left[i].first < right[j].first) {
                x = left[i].first;
                h1 = left[i].second;
                h = max(h1,h2);
                i++;
            }else if (left[i].first > right[j].first){
                x = right[j].first;
                h2 = right[j].second;
                h = max(h1,h2);
                j++;
            }else {
                x = left[i].first;
                h1 = left[i].second;
                h2 = right[j].second;
                h = max(h1,h2);
                i++;
                j++;
            }
            if (rt.size() == 0 || rt.back().second != h) {
                rt.push_back(make_pair(x,h));
            }
        }
        
        rt.insert(rt.end(),left.begin() + i,left.end());
        rt.insert(rt.end(),right.begin() + j,right.end());
        return rt;
    }

    vector<pair<int,int>> divide(vector<vector<int>>& buildings, int left,int right) {
        if (left == right) {
            vector<pair<int,int>> rt;
            rt.push_back(make_pair(buildings[left][0],buildings[left][2]));
            rt.push_back(make_pair(buildings[left][1],0));
            return rt;
        }
        int mid = (left + right) / 2;
        vector<pair<int,int>> leftPart = divide(buildings,left,mid);
        vector<pair<int,int>> rightPart = divide(buildings,mid + 1,right);
        return merge(leftPart,rightPart);
    }
    

    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> rt;
        if (buildings.size() == 0) return rt;
        return divide(buildings,0,buildings.size() - 1);
    }
};

阅读：https://briangordon.github.io/2014/08/the-skyline-problem.html
Java

class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        
        List<int[]> points = getSortedPoints(buildings);
        return getSkyline(points);        
    }
    
    private List<int[]> getSkyline(List<int[]> points) {
        PriorityQueue<Integer> que = new PriorityQueue<>((a, b) -> b - a);
        Map<Integer, Integer> map = new HashMap<>();
        List<int[]> rt = new ArrayList<>();
        que.add(0);
        map.put(0, 1);
        
        for (int[] point : points) {
            int x = point[0];
            int height = point[1];
            
            if (height > 0) {
                if (que.peek() < height) {
                    rt.add(new int[]{x, height});
                }
                
                que.add(height);
                map.put(height, map.getOrDefault(height, 0) + 1);
            }else {
                
                map.put(-height, map.get(-height) - 1);
                while (map.get(que.peek()) == 0)  {
                    que.poll();
                }
                
                if (-height > que.peek()) {
                    rt.add(new int[]{x, que.peek()});
                }
                
            }
        }
        
        return rt;
    }
    
    private List<int[]> getSortedPoints(int[][] buildings) {
        List<int[]> points = new ArrayList<>();
        
        for (int[] building : buildings) {
            points.add(new int[]{building[0], building[2]});
            points.add(new int[]{building[1], -building[2]});    
        }
        
        Collections.sort(points, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        
        return points;
    }
}

Day 109, 215, ##, Kth Largest Element in an Array, Combination Sum III, Contains Duplicate

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

----------------------------------------------
quick-select。因为是in-place，注意storedIndex的初始值为left

class Solution {
public:
    void swap(vector<int> &nums,int index_1, int index_2) {
        int temp = nums[index_1];
        nums[index_1] = nums[index_2];
        nums[index_2] = temp;
    }

    int partition(vector<int> &nums,int left, int right) {
        int mid = left + (right - left) / 2;
        swap(nums,mid,right);
        
        int storedIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] <= nums[right]) {
                swap(nums,i,storedIndex);
                storedIndex++;
            }    
        }
        swap(nums,storedIndex,right);
        
        return storedIndex;
    }

    int findKthLargest(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        
        while (left <= right) {
            int pivot = partition(nums,left,right);
            if (pivot == nums.size() - k) {
                return nums[pivot];
            }
            if (pivot < nums.size() - k) {
                left = pivot + 1;
            }else {
                right = pivot - 1;
            }
        }
        
        return -1;
    }
};

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

-------------------------------------------------

class Solution {
public:
    void dfs(vector<vector<int>> &rt, vector<int> cur, int startNum, int k, int sum) {
        if (k == 0 && sum == 0) {
            rt.push_back(cur);
            return;
        }
        
        if (k < 0 || sum < 0) return;
        
        for (int i = startNum; i < 10; i++) {
            vector<int> temp = cur;
            temp.push_back(i);
            dfs(rt,temp,i + 1,k - 1,sum - i);
        }
        
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> rt;
        vector<int> cur;
        dfs(rt,cur,1,k,n);
        
        return rt;
    }
};

类似

class Solution {
public:
    void helper(vector<vector<int> > &rt, vector<int> cur, int target,int k, int index) {
        if (k == 0 && target == 0) {
            rt.push_back(cur);
            return;
        }
        if (k < 0 || target < 0 || index > 9) return;
        
        helper(rt,cur,target,k,index + 1);
        cur.push_back(index);
        helper(rt,cur,target - index,k - 1, index + 1);
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> rt;
        vector<int> cur;
        helper(rt,cur,n,k,1);
        
        return rt;
    }
};

Contains Duplicate
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct. ------------------------------------------------
hash set

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> st;
        for (int i = 0; i < nums.size(); i++) {
            if (st.find(nums[i]) != st.end()) {
                return true;
            }
            st.insert(nums[i]);
        }
        
        return false;
    }
};

sort

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i - 1] == nums[i]) {
                return true;
            }
        }
        
        return false;
    }
};