Day 71, ##, Single Number, Single Number II

Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
------------------------------------------------------------
XOR
we know A^A = 0 and A^A^B  == A^B^A == B;

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ret = 0;
        for (int i = 0; i < n; i++) {
            ret = ret ^ A[i];
        }
        return ret;
    }
};

Update on Dec-26-2014
other solutions:
#1 hashmap
#2 sort
Single Number II
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
-----------------------------------------------------------------
Solution #1
Consider all numbers in binary format. Using an array to contain the result of bits count mod by 3

class Solution {
public:
    int singleNumber(int A[], int n) {
        vector<int> v(32,0);
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < n; j++) {
                if ((A[j] >> i) & 1) {
                    v[i] = (v[i] + 1) % 3;
                }
            }
            ret |= (v[i] << i); 
        }
        return ret;
    }
};

Update on Dec-26-2014
vector can be replaced with a single variable
Solution #2
one contains bits that are shown once, two is for twice.
on

class Solution {
public:
    int singleNumber(int A[], int n) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < n; i++) {
            two = two | (one & A[i]); // plus bits shown in both one and A[i], now two may contain bits that show 3 times 
            one = one ^ A[i]; // discard bits that have been shown twice
            three = ~ (one & two); // find bits that are in both one and two, then invert them
            
            // discard bits that have been shown 3 times
            one = one & three; 
            two = two & three;
        }
        return one;
    }
};

COME_BACK
https://leetcode.com/discuss/6632/challenge-me-thx

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;
        for (int i = 0; i < nums.size(); i++) {
            one = ~two & (nums[i] ^ one);
            two = ~one & (nums[i] ^ two);
        }
        
        return one;
    }
};

Day 70, ##, Candy

Candy
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?
---------------------------------------------------------
Solution #1, O(n) space and complexity
scan ratings twice, from beginning to end then backwards

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        vector<int> candy(n,1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }
        
        int sum = candy[n - 1];
        for (int i = n -2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]) {
                candy[i] = candy[i + 1] + 1;
            }
            sum += candy[i];
        }
        return sum;
    }
};

Solution#2, O(1) space, but hard to get all corner cases right
Update on Dec-24-2014 
constant space

Constant space, O(n) complexity
#1 When index reaches 1 or 2, all candies at indexes before 1 or 2 can be finalized. So update totalCandy, clear curSum, reset current candy given at current index, top index and topCandy
#2 When ratings[i] < ratings[i - 1], increment all candies between current index and top(both should be exclusive) by one, and add 1 candy for current index. Then check if candies at [top], which is topCandy, is equal to i - top. if it is the case, increment topCandy and curSum.
for example, index_1 has 3 candies, index_3 has 3, index_4 has 2, we have to give one more candy to index_1

class Solution {
public:
    int candy(vector<int> &ratings) {
        int top = 0;
        int totalCandy = 0;
        int curSum = 1;
        int candy = 1;
        int topCandy = 1;
        
        for (int i= 1; i < ratings.size(); i++) {
            if (ratings[i] < ratings[i - 1]) {
                curSum += i - top - 1 + 1; // for clarity
                if (topCandy == i - top) {
                    curSum++;
                    topCandy++;
                }
                candy = 1;
            }else if (ratings[i] == ratings[i - 1]) {
                candy = 1;
                top = i;
                totalCandy += curSum;
                curSum = 1;
                topCandy = 1;
            }else {
                top = i;
                candy++;
                totalCandy += curSum;
                curSum = candy;
                topCandy = candy;
            }
        }
        
        return totalCandy + curSum;
    }
};

Day 69, #130, #132, ##, Surrounded Regions, Palindrome Partitioning II, Clone Graph

Surrounded Regions
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region .
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

------------------------------------------------------------------------------
Solution #1 dfs, cannot pass the latest test case, which has size of 200*200
Slot that is neither on the borders or has no path leading to the borders is to be turned.

class Solution {
public:
    void turn (int row, int col, vector<vector<char>> &board) {
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || board[row][col] != 'O' ) {
            return;
        }
        
        board[row][col] = 'T';
        turn(row + 1, col, board);
        turn(row - 1, col, board);
        turn(row, col + 1, board);
        turn(row, col - 1, board);
    }

    void solve(vector<vector<char>> &board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();
        
        for (int row = 0; row < m; row++) {
            turn(row,0,board); 
            turn(row,n - 1,board); 
        }
        
        for (int col = 0; col < n; col++) {
            turn(0,col,board); 
            turn(m - 1,col,board); 
        }
        
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (board[row][col] == 'O') {
                    board[row][col] = 'X';
                }else if (board[row][col] == 'T') {
                    board[row][col] = 'O';
                }  
            }
        }
        
    }
};

Update on Nov-25-2014
Solution #2 another dfs, cannot pass the latest test case, which is size of 200*200

class Solution {
public:
    bool turn(vector<vector<char> > &board, vector<vector<bool> > &visit, int row, int col) {
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) {
            return false;
        }

        if (board[row][col] == 'X' || !visit[row][col]) {
            return true;
        }
        
        visit[row][col] = false;
        if (turn(board,visit,row - 1,col) && turn(board,visit,row + 1,col) 
            && turn(board,visit,row,col - 1) && turn(board,visit,row,col + 1)) {
            board[row][col] = 'X';
        }
    }

    void solve(vector<vector<char>> &board) {
        int rows = board.size();
        if (rows == 0) return;
        int cols = board[0].size();
        vector<vector<bool> > visit(rows,vector<bool>(cols,true));
        
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                
                if (board[row][col] == 'O' && visit[row][col]) {
                    turn(board,visit,row,col);
             
                }
            }
        }
        
    }
};

Solution #3, bfs, similar approach as solution #1

class Solution {
public:
    void turn (vector<vector<char>> &board, int row, int col) {
        queue<pair<int,int>> que;
        que.push(make_pair(row,col));
        board[row][col] = 'T';
        
        while (!que.empty()) {
            row = que.front().first;
            col = que.front().second;
            que.pop();
            
            if (row > 0 && board[row - 1][col] == 'O') {
                que.push(make_pair(row - 1,col));
                board[row - 1][col] = 'T';
            }
            if (row < board.size() - 1 && board[row + 1][col] == 'O') {
                que.push(make_pair(row + 1,col));
                board[row + 1][col] = 'T';
            }
            if (col > 0 && board[row][col - 1] == 'O') {
                que.push(make_pair(row,col - 1));
                board[row][col - 1] = 'T';
            }
            if (col < board[0].size() - 1 && board[row][col + 1] == 'O') {
                que.push(make_pair(row,col + 1));
                board[row][col + 1] = 'T';
            }
        }
    }

    void solve(vector<vector<char>> &board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();
        
        for (int i = 0; i < m; i++) {
            if (board[i][n - 1] == 'O') {
                turn(board,i,n - 1);
            }
            if (board[i][0] == 'O') {
                turn(board,i,0);
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                turn(board,0,i);
            }
            if (board[m - 1][i] == 'O') {
                turn(board,m - 1,i);
            }
        }
        
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (board[row][col] == 'O') {
                    board[row][col] = 'X';
                }else if (board[row][col] == 'T') {
                    board[row][col] = 'O';
                } 
            }
        }
        
    }
};

Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
-------------------------------------------------------------------------
DP
dp[i] has the minimum cuts of string s[i : end]
if s[i : j], i <= j < n  forms a palindrome, dp[i] = min(dp[i], dp[j] + 1)
watch out for the special case: s[i : end] is a palindrome

using dp for palindrome verification as well

class Solution {
public:
    int minCut(string s) {
        int n = s.length();
        vector<int> dp(n + 1,0);
        vector<vector<bool> > pal(n,vector<bool>(n,false));
        
        // populate tables
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = n - 1 - i;
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1])) {
                    pal[i][j] = true;    
                }
            }
        }
        
        // dp
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (pal[i][j]) {
                    if (j == n-1) { 
                        // special case: s[i:e] is a palindrome
                        // hence no cut needed
                        dp[i] = 0;
                    }
                    else {
                        dp[i] = min(dp[i],dp[j + 1] + 1);
                    }
                }
            }
        }
        return dp[0];
    }
};

recursion with memoization

class Solution {
public:
    bool isPal(string s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s[i] != s[s.length() - 1 - i]) {
                return false;
            }
        }
    
        return true;
    }

    int cuts(string s, unordered_map<string,int> &dic) {
        int minC = INT_MAX;
        for (int i = 0; i < s.length() - 1; i++) {
         string s1 = s.substr(0,i + 1);
         string s2 = s.substr(i + 1);
         int temp1 = 0;
            int temp2 = 0;
            
            if (dic.find(s1) != dic.end()) {
                temp1 = dic[s1];
            }else {
                if (isPal(s1)) {
                    temp1 = 0;
                }else {
                    temp1 = cuts(s1,dic);
                }
          dic[s1] = temp1;
            }
            
            if (dic.find(s2) != dic.end()) {
                temp2 = dic[s2];
            }else {
                if (isPal(s2)) {
                    temp2 = 0;
                }else {
                    temp2 = cuts(s2,dic);
                }
             dic[s2] = temp2;
            }
            
            minC = min(minC, temp1 + temp2 + 1);
        }
        
        dic[s] = minC;
        return minC;
    }

    int minCut(string s) {
        if (isPal(s)) return 0;
        unordered_map<string,int> dic;
        return cuts(s,dic);
    }
};

Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
-----------------------------------------------------------
Typical BFS, can be solved iteratively by using a queue
Note: map new node to old node, updates have to be done with nodes stored in the map

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode* cpGraph (UndirectedGraphNode *node, unordered_map<UndirectedGraphNode*,UndirectedGraphNode*>& mapping) {
        if (mapping.find(node) != mapping.end()) {
            return mapping[node];
        }
        
        UndirectedGraphNode *cp = new UndirectedGraphNode(node->label);
        mapping[node] = cp;
        mapping[node]->neighbors = node->neighbors;
        for (int i = 0; i < node->neighbors.size(); i++) {
            mapping[node]->neighbors[i] = cpGraph(node->neighbors[i],mapping);     
        }
        
        return cp;
    }

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (node == NULL) return NULL;
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mapping;
        
        UndirectedGraphNode *cp = new UndirectedGraphNode(node->label);
        mapping[node] = cp;
        mapping[node]->neighbors = node->neighbors;
        for (int i = 0; i < node->neighbors.size(); i++) {
            mapping[node]->neighbors[i] = cpGraph(node->neighbors[i],mapping);     
        }
        return cp;
    }
};

Update on Dec-23-2014
refactoried

 
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *clone (UndirectedGraphNode *node,unordered_map<int,UndirectedGraphNode*> &dic) {
        if (dic.find(node->label) != dic.end()) {
            return dic[node->label];
        }
        
        UndirectedGraphNode *cp = new UndirectedGraphNode(node->label);
        dic[node->label] = cp;
        cp->neighbors = node->neighbors;
        for (int i = 0; i < node->neighbors.size(); i++) {
            cp->neighbors[i] = clone(node->neighbors[i],dic);
        }
        
        return cp;
    }

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL) return NULL;
        
        unordered_map<int,UndirectedGraphNode*> dic;
        return clone(node,dic);
    }
};

Update on Jun-23-2018
Java, bfs,
要记得存map！！！

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        
        Queue que = new LinkedList<>();
        Map map = new HashMap<>();
        
        que.add(node);
        map.put(node, new UndirectedGraphNode(node.label));
        
        while (!que.isEmpty()) {
            UndirectedGraphNode top = que.poll();
            UndirectedGraphNode clone = map.get(top);
                
            for (UndirectedGraphNode n : top.neighbors) {
                UndirectedGraphNode nClone;
                if (map.containsKey(n)) {
                    nClone = map.get(n);
                }else {
                    nClone = new UndirectedGraphNode(n.label);
                    que.add(n);
                    map.put(n, nClone);
                }
                
                clone.neighbors.add(nClone);
            }
        }
        
        return map.get(node);
    }
}

Day 68, #128, Longest Consecutive Sequence

Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
----------------------------------------------------------------------------
O(n),using a hash to map an integer and its number of consecutive integers found so far, initialized as 0
3 scenarios we have to tackle:
1) found connecting number on both left and right sides, attach 2 segments together
2) only the right
3) only the left

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int,int> mapping;
        int maxLen = 0;
        for (int i = 0; i < num.size(); i++) {
            int key = num[i]; 

            // skip duplicates
            if (mapping.find(key) == mapping.end()) {
                mapping[key] = 0;
            }else continue;
            
            if (mapping.find(key - 1) != mapping.end() && mapping.find(key + 1) != mapping.end() ) {
                int left = key - 1 - mapping[key - 1]; // find index of the left most number on current segment
                int right = key + 1 + mapping[key + 1]; // find index of the rightmost number on current segment
                mapping[left] += 2 + mapping[right]; // watch out for 2 
                mapping[right] = mapping[left];
                maxLen = max(mapping[left],maxLen);
            }else if (mapping.find(key - 1) != mapping.end()) {
                int left = key - 1 - mapping[key - 1];
                mapping[left]++;
                mapping[key] = mapping[left];
                maxLen = max(mapping[left],maxLen);
            }else if (mapping.find(key + 1) != mapping.end() ) {
                int right = key + 1 + mapping[key + 1];
                mapping[right]++;
                mapping[key] = mapping[right];
                maxLen = max(mapping[right],maxLen);
            }
        }
        return maxLen + 1;
    }
};

Update Nov-23-2014
Another approach

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int,bool> mapping;
        for (int i = 0; i < num.size(); i++) {
            mapping[num[i]] = true;
        }
        
        int longest = 0;
        for (int i = 0; i < num.size(); i++) {
            if (!mapping[num[i]]) continue;
            mapping[num[i]] = false;
            int left = num[i] - 1, right = num[i] + 1;
            int length = 1;
            
            while (mapping[left] || mapping[right]) {
                if (mapping[left]) {
                    mapping[left] = false;
                    length++;
                    left--;
                }
                if (mapping[right]) {
                    mapping[right] = false;
                    length++;
                    right++;
                }
            }
            
            longest = max(longest,length);
        }
        
        return longest;
    }
};

变种题：array可能变为tree，对于无重复的可以只记录范围，来节省空间

Day 67, #117, #123, #124, Populating Next Right Pointers in Each Node II, Best Time to Buy and Sell Stock III, Binary Tree Maximum Path Sum

Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

-----------------------------------------------------------------------
Same exact solution to #116 Populating Next Right Pointers in Each Nod

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void travese (TreeLinkNode* root, vector<TreeLinkNode*> &tails, int level) {
        if (root == NULL) {
            return;
        }
        if (tails.size() < level) {
            tails.push_back(root);
        }else {
            tails[level - 1]->next = root;
            tails[level - 1] = root;
        }
        travese(root->left,tails,level + 1);
        travese(root->right,tails,level + 1);
    }

    void connect(TreeLinkNode *root) {
        vector<TreeLinkNode*> tails;
        travese(root,tails,1);
    }
};

Update Feb-19-2015
constant space

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        while (root) {
            TreeLinkNode *cur = root, *pre = NULL, *nextLevel = NULL;
            
            while (cur) {
                if (cur->left != NULL) {
                    if (nextLevel == NULL) nextLevel = cur->left;
                    if (pre == NULL) pre = cur->left;
                    else {
                        pre->next = cur->left;
                        pre = cur->left;
                    }
                }
                
                if (cur->right != NULL) {
                    if (nextLevel == NULL) nextLevel = cur->right;
                    if (pre == NULL) pre = cur->right;
                    else {
                        pre->next = cur->right;
                        pre = cur->right;
                    }
                }
                
                cur = cur->next;
            }
            root = nextLevel;
        }
    }
};

Best Time to Buy and Sell Stock III
Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
------------------------------------------------------------------------------------------
DP
Divide prices[] in two parts, each which is solved as in #121 Best Time to Buy and Sell Stock
the max profit would be the largest value of  firstPart[i] + secondPart[i]

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.size() == 0) return 0;
        vector<int> dp1(prices.size(),0);
        vector<int> dp2 = dp1;
        
        int minimun = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp1[i] = max(dp1[i - 1], prices[i] - minimun);
            minimun = min(prices[i],minimun);
        }
        
        int maximum = prices.back();
        for (int i = prices.size() - 2; i >= 0; i--) {
            dp2[i] = max(dp2[i + 1], maximum - prices[i]);
            maximum = max(prices[i],maximum);
        }
        
        int maxProfit = 0;
        for (int i = 0; i < prices.size(); i++) {
            maxProfit = max(dp1[i] + dp2[i],maxProfit);
        }
        return maxProfit;
    }
};

Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.
--------------------------------------------------------------------------
Two scenarios:
1) Current node is the root(top) node of the path
2) Current node is in either left or right sub-tree of the path
Hence, according to the 1st, we have to include the sum of both left and right sub-trees when we calculate maximum. In another word, we produce its maximum value for each node in binary tree. But according to the 2nd, return back to upper level in recursive stack with only one or non of sub-trees.  

/**
 * 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 pathSum(TreeNode *root,int &maximumPath) {
        if (root == NULL) {
            return INT_MIN;
        }
        
        int leftSum = max(0,pathSum(root->left,maximumPath));
        int rightSum = max(pathSum(root->right,maximumPath),0);
        
        maximumPath = max(maximumPath,leftSum + rightSum + root->val);
        return max(leftSum,rightSum) + root->val;
    }

    int maxPathSum(TreeNode* root) {
        int m = INT_MIN;
        pathSum(root,m);
        return m;
    }
};

另一种写法

/**
 * 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 helper(TreeNode *root,int *sum) {
        if  (root == NULL) {
            *sum = 0;
            return INT_MIN;
        }
        
        int ls = 0, rs = 0;
        int leftM = helper(root->left,&ls);
        int rightM = helper(root->right,&rs);
        
        ls = max(ls,0);
        rs = max(rs,0);
        *sum = max(ls,rs) + root->val;
        
        return max(ls + rs + root->val, max(leftM,rightM));
    }


    int maxPathSum(TreeNode* root) {
        int sum = 0;
        return helper(root,&sum);
    }
};

Day 66, #103, #115, Binary Tree Zigzag Level Order Traversal, Distinct Subsequences

Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

----------------------------------------------------------------------
Similar to #102 Binary Tree Level Order Traversal

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > ret;
    
    void stackOrder2 (vector<int>& level, stack<TreeNode*>& cur, stack<TreeNode*>& next) {
        while (!cur.empty()) {
            TreeNode* node = cur.top();
            cur.pop();
            level.push_back(node->val);
            if (node->right != NULL) {
                next.push(node->right);
            }
            if (node->left != NULL) {
                next.push(node->left);
            }
        }
    }

    void stackOrder1 (vector<int>& level, stack<TreeNode*>& cur, stack<TreeNode*>& next) {
        while (!cur.empty()) {
            TreeNode* node = cur.top();
            cur.pop();
            level.push_back(node->val);
            if (node->left != NULL) {
                next.push(node->left);
            }
            if (node->right != NULL) {
                next.push(node->right);
            }
        }
    }

    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        stack<TreeNode*> st1, st2;
        if (root == NULL) return ret;
        int levelCount = 0;
        st1.push(root);
        while (!st1.empty() || !st2.empty()) {
            vector<int> level;
            if (levelCount % 2 == 0) {
                stackOrder1(level,st1,st2);
            }else {
                stackOrder2(level,st2,st1);
            }
            ret.push_back(level);
            levelCount++;
        }
        return ret;
    }
};

更新，Sep-10-2015

/**
 * 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:
    vector<int> zig(vector<vector<int>> &rt,queue<TreeNode*> &que) {
        int size = que.size();
        vector<int> cur;
        
        while (size > 0) {
            TreeNode *t = que.front();
            que.pop();
            cur.push_back(t->val);
            if (t->left != NULL) que.push(t->left);
            if (t->right != NULL) que.push(t->right);
            size--;
        }
        
        return cur;
    }


    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> rt;
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int level = 0;
        
        while (!que.empty()) {
            vector<int> cur = zig(rt,que);
            if (level % 2 == 1) {
                reverse(cur.begin(),cur.end());
            }
            rt.push_back(cur);
            level++;
        }
        
        return rt;
    }
};

Distinct Subsequences
--------------------------------------------------------------
Classic DP
Further reading:
http://stackoverflow.com/questions/20459262/distinct-subsequences-dp-explanation

class Solution {
public:
    int numDistinct(string S, string T) {
        int m = S.length();
        int n = T.length();
        vector<vector<int> > dp(m+1,vector<int>(n+1,0));
        
        for (int i = 0; i < m + 1; i++) {
            dp[i][n] = 1;
        }
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (S[i] == T[j]) {
                    dp[i][j] = dp[i+1][j] + dp[i+1][j+1];
                }else {
                    dp[i][j] = dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }
};

Update Nov-21-2014
If S[i] != T[j], we know that N[i][j] = N[i+1][j]
If S[i] = T[j], we have a choice. We can either 'match' these characters and go on with the next characters of both S and T, or we can ignore the match (as in the case that S[i] != T[j]).

递归：
COME_BACK
遇到这种题时，找小的test case，为了发现规律：如(ab, b)

int distinct(string s,string t) {
    if (t.length() == 0) return 1;
    if (s.length() == 0) return 0; 
    
    if (s[0] == t[0]) {
        return foo(s.substr(1),t.substr(1)) + foo(s.substr(1),t);
    }
    return foo(s.substr(1),t);
}

Day 65 - 2, #95, #99, Unique Binary Search Trees II, Recover Binary Search Tree

Unique Binary Search Trees II
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

-----------------------------------------------------------------------------------------
COME_BACK, Catalan number
Similar to #96 Unique Binary Search Trees
resource: http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf
there is space for optimization

/**
 * 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:
    vector<TreeNode *> helper(int start, int end) {
        vector<TreeNode*> rt;
        for (int i = start; i <= end; i++) {
            vector<TreeNode*> left = helper(start,i - 1);
            vector<TreeNode *> right = helper(i + 1, end);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode *root = new TreeNode(i + 1);
                    root->left = left[j];
                    root->right = right[k];
                    rt.push_back(root);
                }
            }
        }
        if (rt.size() == 0) rt.push_back(NULL);
        return rt;
    }

    vector<TreeNode*> generateTrees(int n) {
        return helper(0,n - 1);
    }
};

iterative,
OJ的要求的root左边的value一定比它小，右边一定被它大，因为是BST

/**
 * 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 *deepCopy(TreeNode *root,int offset) {
        if (root == NULL) return NULL;
        TreeNode *newRoot = new TreeNode(root->val + offset);
        newRoot->left = deepCopy(root->left,offset);
        newRoot->right = deepCopy(root->right,offset);
        return newRoot;
    }

    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> rt;
        vector<vector<TreeNode *>> dp(n + 1,vector<TreeNode*>());
        dp[0].push_back(NULL);
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                for (int left = 0; left < dp[j].size(); left++) {
                    for (int right = 0; right < dp[i - j - 1].size(); right++) {
                        TreeNode *root = new TreeNode(j + 1);
                        root->left = deepCopy(dp[j][left],0);
                        //root->left = dp[j][left];
                        root->right = deepCopy(dp[i - j - 1][right],j + 1);
                        dp[i].push_back(root);
                    }
                }
            }
        }
        
        return dp[n];
    }
};

O(1)额外空间
https://leetcode.com/discuss/20399/share-a-c-dp-solution-with-o-1-space
Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
-------------------------------------------------------
Solution #1: O(n) space - construct an array of size n, populate it by traversing tree in in-order...

Solution #2: in-space and iterative. Morris traversal:
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ 

Solution #3: In-space - typical in-order traversal , reach to the left most node, then walk back to the right most.
pre points to the node right before the current node in serialized binary tree.
The following code implements #3.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *pre;
    TreeNode* first;
    TreeNode* second;

    void inorder (TreeNode *root) {
        if (root == NULL) {
            return;
        }
        
        inorder(root->left);
        if (pre == NULL) {
            pre = root;
        }
        
        // found it!
        if (pre->val > root->val) {
            if (first == NULL) {
                first = pre;
            }
            second = root;
        }
        
        pre = root;
        inorder(root->right);
    }

    void recoverTree(TreeNode *root) {
        pre = NULL;
        first = NULL;
        inorder(root);
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }
};

Update Nov-19-2014 
watch out for pointer passing  as argument in C++

Day 65 - 1, #89, #90, #94, Gray Code, Subsets II, Binary Tree Inorder Traversal

Gray Code
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
---------------------------------------------------------------------------------
Solution#1, see patterns below

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret;
        ret.push_back(0);
        for (int i = 0; i < n; i++) {
            int size = ret.size();
            int bit = 1 << i;
            for (int j = size - 1; j >= 0; j--) {
                ret.push_back(ret[j] + bit);
            }
        }
        return ret;
    }
};

Solution#2, from internet

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret;
        int count = 0x01 << n;
        for(int i = 0 ; i < count; ++i) {
            ret.push_back(i ^ (i>>1));
        }
        return ret;
    }
};

Subsets II
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

----------------------------------------------------------
Solution #1. Similar to #78 Subsets
Add a hashset to skip duplicates

class Solution {
public:
    void subsets(vector<int> S, vector<vector<int> > &ret, vector<int> cur) {
        int length = S.size();
        unordered_set<int> mapping;
        for (int i = 0; i < length; i++) {
            vector<int> temp = cur;
            int head = S[0];
            S.erase(S.begin());
            if (mapping.find(head) == mapping.end()) {
                mapping.insert(head);
                temp.push_back(head);
                ret.push_back(temp);
                subsets(S,ret,temp);
            }
        }
    }

    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        sort(S.begin(),S.end());
        vector<vector<int> > ret;
        vector<int> cur;
        ret.push_back(cur);
        subsets(S,ret,cur);
        return ret;
    }
};

Update Nov-19-2014
Solution#2 iterative
如果 不重复，从头插。
如果是重复数字，只需插入到前一次所插入的数列中

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<int> empty;
        vector<vector<int> > rt;
        rt.push_back(empty);
        sort(S.begin(),S.end());
        
        int size = 0;
        for (int i = 0; i < S.size(); i++) {
            int start = 0;
            if (i > 0 && S[i] == S[i - 1]) {
                start = size;
            }
            
            size = rt.size();
            for (; start < size; start++) {
                vector<int> temp = rt[start];
                temp.push_back(S[i]);
                rt.push_back(temp);
            }
        }
         
        return rt;
    }
};

Java, 递归，去重

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> rt = new ArrayList<>();
        dfs(rt, nums, 0, new ArrayList<>());
        
        return rt;
    }
    
    private void dfs(List<List<Integer>> rt, int[] nums, int index, List<Integer> sofar) {
        rt.add(sofar);
        
        for (int i = index; i < nums.length; i++) {
            if (i > index && nums[i] == nums[i - 1]) continue;
            List<Integer> tmp = new ArrayList<>(sofar);
            tmp.add(nums[i]);
            dfs(rt, nums, i + 1, tmp);
        }
    }
}

迭代

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> rt = new ArrayList<>();
        rt.add(new ArrayList<Integer>());
        Arrays.sort(nums);
        
        int lastSize = 0;
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> rt_tmp = new ArrayList<>();
            
            int size = rt.size();
            if (i > 0 && nums[i] == nums[i - 1]) {
                size = lastSize;
            }
                
            for (int j = size; j > 0; j--) {
                int index = rt.size() - j;
                List<Integer> inner = new ArrayList<>(rt.get(index));
                inner.add(nums[i]);
                rt_tmp.add(inner);
            }
            lastSize = rt_tmp.size();
            rt.addAll(rt_tmp);
        }
        
        return rt;
    }
}

Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
-----------------------------------------------
Iterative approach
Solution #1, add a boolean value to indicate visited status
Other solutions:   

http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> ret;
        stack<pair<TreeNode*,bool> > s;
        s.push(make_pair(root,false));
        
        while (!s.empty()) {
            pair<TreeNode*,bool> p = s.top();
            if (p.first != NULL) {
                if (p.second == false) {
                    s.top().second = true;
                    s.push(make_pair(p.first->left,false));
                }else {
                    ret.push_back(p.first->val);
                    s.pop();
                    s.push(make_pair(p.first->right,false));
                }
            }else {
                s.pop();
            }
        }
        return ret;
    }
};

Update Nov-19-2014
basic idea: when a node is traversed for the second time, its value will be printed
当每一个node的左节点为NULL时，则需要打印这个node

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        stack<TreeNode *> st;
        vector<int> rt;
        
        while (!st.empty() || root != NULL) {
            if (root) {
                st.push(root);
                root = root->left;
            }else {
                rt.push_back(st.top()->val);
                root = st.top()->right;
                st.pop();
            }
        }
        return rt;
    }
};

＊表示怀疑＊方法三，用2个stack，一个用来存第一次visit的node，一个是第二次visit的node

方法四，Threaded binary tree. O(n) time, O(1) space 每往左走一个node，把之前node贴在它左子树的最右下角, 这是根据inorder traversal的特性决定的。算法见leetcode

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List inorderTraversal(TreeNode root) {
        List rt = new ArrayList<>();
        TreeNode cur = root;
        
        while (cur != null) {
            if (cur.left != null) {
                root = cur;
                cur = cur.left;
                TreeNode rightMost = cur;
                
                while (rightMost.right != null) {
                    rightMost = rightMost.right;
                }
                
                rightMost.right = root;
                root.left = null;
                
            }else {
                rt.add(cur.val);
                cur = cur.right;
            }
        }
        
        return rt;
    }
}

Day 64, #76, Minimum Window Substring

Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
-----------------------------------------------------------------------------

## 注意第14行，当前char如果为不需要时，直接跳过。第22行类似。围绕着t里面的字符
## 当发现至少存在一个符合substring时，count一直保持为0

O(n)
------ Explanation here ---------

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> needed(256,0);
        vector<int> owned(256,0);
        for (int i = 0; i < t.length(); i++) {
            needed[t[i]]++; 
        }
        
        int count = t.length();
        int start = 0;
        string rt = "";
        for (int i = 0; i < s.length(); i++) {
            if (needed[s[i]] == 0) continue;
            owned[s[i]]++;
            if (owned[s[i]] <= needed[s[i]]) {
                if (count == t.length()) start = i;
                count--;
            }
            
            if (count == 0) {
                while (needed[s[start]] == 0 || owned[s[start]] > needed[s[start]]) {
                    if (owned[s[start]] > needed[s[start]]) {
                        owned[s[start]]--;
                    }
                    start++;
                }
                if (rt == "" || rt.length() > i - start + 1) {
                    rt = s.substr(start,i - start + 1);
                }
            }
        }
        
        return rt;
    }
};

Java版，总体思路一样，实现上有一点出入
ToDo 扩展阅读，解决所有substring的通用方法：https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

class Solution {
    public String minWindow(String s, String t) {
        int[] needed = getMap(t);
        int[] sofar = new int[256];
        int count = t.length();
        
        int start = -1;
        String rt = "";
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i);
            sofar[c]++;
            if (needed[c] > 0 && sofar[c] <= needed[c]) {
                count--;
                if (start == -1) start = i;
            }
            while (start != -1 && sofar[s.charAt(start)] > needed[s.charAt(start)]) {
                sofar[s.charAt(start)]--;
                start++;
            }
            if (count == 0 && (i - start + 1 < rt.length() || rt == "")) {
                rt = s.substring(start,i + 1);
            }
        }
            
        return rt;
    }
    
    private int[] getMap(String t) {
        int[] map = new int[256];
        for (int i = 0; i < t.length(); i++) {
            map[t.charAt(i)]++;
        }
        
        return map;
    }
}

Day 63, #72， #75, Edit Distance， Sort Colors

Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
------------------------------------------------------------------------------------
Further reading:
Wagner–Fischer algorithm
Edit distance
http://www.youtube.com/watch?v=ocZMDMZwhCY

class Solution {
public:
    int minDistance(string word1, string word2) {
       int m = word1.length();
       int n = word2.length();
       
       vector<vector<int> > dp(m + 1,vector<int>(n + 1,0));
       
       // the distance of any first string to an empty second string
       for (int i = 0; i < m + 1; i++) {
           dp[i][0] = i;
       }
       
       // the distance of any second string to an empty first string
       for (int i = 0; i < n + 1; i++) {
           dp[0][i] = i;
       }
       
       for (int i = 1; i < m + 1; i++) {
           for (int j = 1; j < n + 1; j++) {
               if (word1[i - 1] == word2[j - 1]) {
                   dp[i][j] = dp[i - 1][j - 1]; 
               }else {
                   int temp = min(dp[i][j - 1],dp[i - 1][j]);
                   dp[i][j] = min(temp,dp[i - 1][j - 1]) + 1;
                   
               }
           }
       }
       return dp[m][n];
    }
};

Update on Nov-16-2014
if word[i] !=  word2[j] the cost from [i:end] to [j:end] is the minimal among

1. cost of insert + [i:end] [j - 1:end]
2. cost of delete + [i - 1:end] [j:end]
3. cost of replace + [i:end] [j:end]

if word1[i] == word2[j], then the distance of [i:end] and [j:end] is [i-1:end] and [j-1:end]
Improvement on this algorithm - Wagner–Fischer algorithm

O(n) space

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(),n = word2.length();
        if (m == 0) return n;
        if (n == 0) return m;
        vector<int> dp(n + 1,0);
        vector<int> pre(n + 1,0);
        for (int i = 0; i <= n; i++) {
            pre[i] = i;
        }
        
        for (int i = 1; i <= m; i++) {
            dp[0] = i;
            
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[j] = pre[j - 1];
                }else {
                    dp[j] = 1 + min(pre[j],min(dp[j - 1],pre[j - 1]));
                }
            }
            pre = dp;
        }
        
        return dp[n];
    }
};

递归：有重复子问题，所以用DP

int minDistance(string s1,string s2,int i,int j) {
    if (i == s1.length() && j == s2.length()) return 0;
    if (i == s1.length()) return s2.length() - j + 1;
    if (j == s2.length()) return s1.length() - i + 1;
    
    if (s1[i] == s2[j]) return edit(s1,s2,i + 1,j + 1);
    return 1 + min(edit(s1,s2,i + 1, j + 1),min(edit(s1,s2,i + 1,j),edit(s1,s2,i,j + 1)));
}

Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?---------------------------------------------------------
One pass

class Solution {
public:
    void sortColors(int A[], int n) {
        int itr = 0;
        int ptrZero = 0;
        int ptrTwo = n - 1;
        while (itr <= ptrTwo) {
            if (A[itr] == 1) {
                itr++;
            }else if (A[itr] == 0) {
                swap(A[itr],A[ptrZero]);
                ptrZero++;
                if (ptrZero >= itr) {
                    itr++;
                }
            }else if (A[itr] == 2) {
                swap(A[itr],A[ptrTwo]);
                ptrTwo--;
            }
        }
    }
};

Update on Jan-26-2015
re-factoried

class Solution {
public:
    void swap(int A[], int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    void sortColors(int A[], int n) {
        int start = 0;
        int end = n - 1;
        int itr = 0;
        
        while (itr <= end) {
            if (A[itr] == 0) {
                swap(A,itr,start);
                start++;
                itr++;
            }else if (A[itr] == 2) {
                swap(A,itr,end);
                end--;
            }else {
                itr++;
            }
        }
    }
};

Day 62, #68, #69, Text Justification, Sqrt(x)

Text Justification
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.
Corner Cases:

• A line other than the last line might contain only one word. What should you do in this case?
  In this case, that line should be left-justified.

--------------------------------
This is one of the most muthaFking types of questions. It makes people suicidal until it  passes the OJ.

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        int used = 0;
        vector<string> ret;
        vector<string> temp;
        if (L == 0) {
            ret.push_back("");
            return ret;
        }
        
        bool flag =false;
        for (int i = 0; i < words.size(); i++) {
            // always have one element in the temp. ease the pain
            if (!flag) {
                temp.clear();
                used = 0;
                used = words[i].length();
                temp.push_back(words[i]);
                flag = true;
            }else {
                // keep feeding the temp
                if (words[i].length() + 1 + used <= L) {
                    temp.push_back(" " + words[i]);
                    used += 1 + words[i].length();
                }
                
                // if used + current word's length is larger than L
                // clear temp, form the line and push it to ret
                else {
                    i--; // back by one step
                    flag = false;
                    if (temp.size() == 1) {
                        string str = temp[0];
                        for (int j = 0; j < L - used; j++) {
                            str += " ";
                        }
                        ret.push_back(str);
                        continue;
                    }
                    
                    // calculate extra space between words 
                    int spaceCount = (L - used) / (temp.size() - 1);
                    int extraSpace = (L - used) % (temp.size() - 1);
                    string space = "";
                    for (int j = 0; j < spaceCount; j++) {
                        space += " ";
                    }
                    
                    string str = temp[0];
                    for (int j = 1; j < temp.size(); j++) {
                        if (extraSpace > 0) {
                            str += " ";
                            extraSpace--;
                        }
                        str += space + temp[j];
                    }
                    ret.push_back(str);
                }
            }
        }
        
        // dealing with the last line
        if (flag) {
            string str = temp[0];
            for (int i = 1; i < temp.size(); i++) {
                str += temp[i];
            }
            for (int i = used; i < L; i++) {
                str += " ";
            }
            ret.push_back(str);
        }
        
        return ret;
    }
};

Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
--------------------------------------------------
Solution#1, binary search
why always return right in the end??
A: Inorder to break out the loop, we either have sq == x or left > right, for this Sqrt(x) method, we need to return the lower bound(ex. input is 250, return 15, not 16)

class Solution {
public:
    int sqrt(int x) {
        long long left = 0;
        long long right = x /2 + 1;
        while (left <= right) {
            long long mid = (left + right) / 2;
            long long sq = mid * mid;
            if (sq == x) {
                return mid;
            }
            if (sq < x) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return right; // why always return right
    }
};

Solution#2
Newton's method
Update on Jan-23-2015 
could be if (fabs(i - j) < 0.000001) break;

class Solution {
public:
    int sqrt(int x) {
        if (x == 0) return 0;
        double i = 1.0;
        double j = 1;
        while (true) {
            j = (i + x / i) / 2.0;
            if (i == j) break;
            i = j;
        }
        
        return (int)j;
    }
};

Day 61, #56, #57, Merge Intervals, Insert Interval

Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
----------------------------------------------------------------

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    static bool comp (const Interval &i1, const Interval &i2) {
        return i1.start < i2.start;
    }

    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(),intervals.end(),comp);
        vector<Interval> ret;
        
        if (intervals.size() == 0) {
            return ret;
        }
        
        ret.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start <= ret.back().end) {
                if (intervals[i].end > ret.back().end) {
                    ret.back().end = intervals[i].end;
                }
            }else {
                ret.push_back(intervals[i]);
            }
        }
        return ret;
    }
};

Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
------------------------------------------------------------ 
Solution#1

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> ret;
        int index = 0;
        int size = intervals.size();
        
        while (index < size && newInterval.start > intervals[index].end) {
            ret.push_back(intervals[index]);
            index++;
        }
        
        // deal with overlapping
        while (index < size && newInterval.end >= intervals[index].start ) {
            newInterval.start = min(newInterval.start,intervals[index].start);
            newInterval.end = max(newInterval.end,intervals[index].end);
            index++;
        }
        
        ret.push_back(newInterval);
        // push in the rest
        while (index < size) {
            ret.push_back(intervals[index]);
            index++;
        }
        return ret;
    }
};

Solution#2 -- in place
do it later

Day 60, #51, #52, #54, N-Queens, N-Queens II, Spiral Matrix

N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

----------------------------------------------------------------------
Typical DFS. Set up 3 vector<bool>s to indicate conflict
Red is backslash
Blue is slash
Green is row

class Solution {
public:
    void queens(vector<vector<string> > &ret,vector<bool> &slash, vector<bool> &backslash, vector<bool> &usedRow, vector<string> cur, int col, int n) {
        if (col == n) {
            ret.push_back(cur);
            return;
        }

        for (int row = 0; row < n; row++) {

            // check conflicts in diagonals and same row
            if (slash[col + row] && backslash[row-col + n] && usedRow[row]) {
                cur[row][col] = 'Q';
                slash[col + row] = false;
                backslash[row-col + n] = false;
                usedRow[row] = false;
                queens(ret,slash,backslash,usedRow,cur,col+1,n);
                
                // backtrack
                cur[row][col] = '.';
                slash[col + row] = true;
                backslash[row-col + n] = true;
                usedRow[row] = true;
            }
        }
    }

    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string> > ret;
        vector<bool> slash(n*2,true);
        vector<bool> backslash(n*2,true);
        vector<bool> usedRow(n,true);
        
        // populate vectors
        string str = "";
        for (int i = 0; i < n; i++) {
            char c = '.';
            str += c;
        }
        vector<string> cur(n,str);
        
        queens(ret,slash,backslash,usedRow,cur,0,n);
        return ret;
    }
};

Update Feb-10-2015
Using bit operation

class Solution {
public:
    string getString(int n, int p) {
        string s(n,'.');
        s[p] = 'Q';
        return s;
    }

    void queens(vector<vector<string> > &rt, vector<string> cur,int slash, int backSlash, int row, int n) {
        int upperLimit = (1 << n) - 1;
        if (row == upperLimit) {
            rt.push_back(cur);
            return;
        }
        
        int possiblePositions = upperLimit & (~(slash | backSlash | row));
        int itr = possiblePositions;
        int p = n - 1;
        while (possiblePositions != 0) {
            int rightMost = possiblePositions & (-possiblePositions);
            if (itr & 1) {
                string s = getString(n,p);
                vector<string> temp = cur;
                temp.push_back(s);
                possiblePositions -= rightMost;
                
                queens(rt,temp,(slash + rightMost) << 1,(backSlash + rightMost) >> 1,row + rightMost,n);
            }
            p--;
            itr >>= 1;
        }
    }

    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string> > rt;
        vector<string> cur;
        queens(rt,cur,0,0,0,n);
        
        return rt;
    }
};

Java, updated on Sep-8th-2018
O(n!)
T(n) = n * T(n - 1)

class Solution {
    public List> solveNQueens(int n) {
        boolean[] cols = new boolean[n];
        boolean[] diag = new boolean[n * 2]; // row + col
        boolean[] antiDiag = new boolean[n * 2]; // row - col + n - 1
        
        List> rt = new ArrayList<>();
        dfs(0, n, new ArrayList(), rt, cols, diag, antiDiag);
        
        return rt;
    }
    
    private void dfs(int row, int n, List sofar, List> rt,
                    boolean[] cols, boolean[] diag, boolean[] antiDiag) {
        
        if (row >= n) {
            rt.add(sofar);
            return;
        }
                
        String cur = "";
        for (int i = 0; i < n; i++) {
            if (!cols[i] && !diag[row + i] && !antiDiag[row - i + n - 1]) {
                cols[i] = true;
                diag[row + i] = true;
                antiDiag[row - i + n - 1] = true;
            
                String tmp = cur + "Q";
                for (int j = i + 1; j < n; j++) tmp += "."; 
                List tmpSofar = new ArrayList<>(sofar);
                tmpSofar.add(tmp);
                
                dfs(row + 1, n, tmpSofar, rt, cols, diag, antiDiag);
                
                cols[i] = false;
                diag[row + i] = false;
                antiDiag[row - i + n - 1] = false;
            }
            
            cur += ".";
        }
    }
}

N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
---------------------------------------------------------------------
Solution #1 similar to previous problem
Note that usedRow[row] should be checked first otherwise it exceeds OJ's  time limit

class Solution {
public:
void queens(int &ret,vector<bool> &slash, vector<bool> &backslash, vector<bool> &usedRow, int col, int n) {
        if (col == n) {
            ret++;
            return;
        }

        for (int row = 0; row < n; row++) {
            if (usedRow[row] && slash[col + row] && backslash[row-col + n]) {
                slash[col + row] = false;
                backslash[row-col + n] = false;
                usedRow[row] = false;
                queens(ret,slash,backslash,usedRow,col+1,n);
                
                // backtrack
                slash[col + row] = true;
                backslash[row-col + n] = true;
                usedRow[row] = true;
            }
        }
    }

    int totalNQueens(int n) {
        vector<bool> slash(n*2,true);
        vector<bool> backslash(n*2,true);
        vector<bool> usedRow(n,true);
        
        int ret = 0;
        queens(ret,slash,backslash,usedRow,0,n);
        return ret;
    }
};

Solution #2
http://www.matrix67.com/blog/archives/266  

Update on Nov-13-2014 
基本思路为DFS
~(row | slash | backSlash) 代表每行上的可放位置，当切入到下一行时，slash跟backSlash分别需要位移一位
possiblePosition 代表当前行所有可放入棋子的位置
rightMostOne 代表当前放入棋子的位置
拿一个例子走一遍代码，立即能明白此算法

class Solution {
public:
    void bitOP(int &num, int row, int slash, int backSlash, int n) {
        int upperLimit = (1 << n) - 1; // upperLimit has n of '1'
        if (row == upperLimit) {
            num++;
            return;
        }
        
        int possiblePosition = upperLimit & (~(row | slash | backSlash)); // get posiible positions for queen in a row
        while (possiblePosition != 0) {
            int rightMostOne = possiblePosition & (-possiblePosition); // get the most right '1' as new queen's position
            possiblePosition -= rightMostOne;
            bitOP(num, row + rightMostOne, (slash + rightMostOne) << 1, (backSlash + rightMostOne) >> 1,n);
        }
        
    }

    int totalNQueens(int n) {
        int num = 0;
        bitOP(num,0,0,0,n);
        return num;
    }
};

Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].
-----------------------------------------------------------
Similar to #59, Spiral Matrix II
start at the outer most layer

class Solution {
public:
    void spiral (vector<vector<int> > &matrix, vector<int> &ret, int m, int n, int k) {
        if (m <= 0 || n <= 0) {
            return;
        }
        
        if (m == 1) {
            for (int i = 0; i < n; i++) {
                ret.push_back(matrix[k][k + i]);
            }
            return;
        }
        
        if (n == 1) {
            for (int i = 0; i < m; i++) {
                ret.push_back(matrix[k + i][k]);
            }
            return;
        }
        
        // going right
        for (int i = 0; i < n - 1; i++) {
            ret.push_back(matrix[k][i + k]);    
        }
        
        // going down
        for (int i = 0; i < m - 1; i++) {
            ret.push_back(matrix[k + i][n - 1 + k]);
        }
        
        // going left
        for (int i = 0; i < n - 1; i++ ) {
            ret.push_back(matrix[m - 1 + k][n - 1 + k - i]);
        }
        
        // going up
        for (int i = 0; i < m - 1; i++ ) {
            ret.push_back(matrix[k + m - 1 - i][k]);
        }
        
        spiral(matrix,ret,m-2,n-2,k+1);
    }

    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        int m = matrix.size();
        vector<int> ret;
        if (m == 0) return ret;
        int n = matrix[0].size();
        spiral(matrix,ret,m,n,0);
        return ret;
    }
};

Day 59, #47, #48, Permutations II, Rotate Image

Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
--------------------------------------------------------------------------------
Check duplicates in each for loop run

class Solution {
public:
    void per (vector<int> num,vector<int> cur,vector<vector<int> > &ret) {
        if (num.size() == 0) {
            ret.push_back(cur);
        }
        unordered_set<int> mapping;
        for (int i = 0; i < num.size(); i++) {
            if (mapping.find(num[i]) == mapping.end()) {
                mapping.insert(num[i]);
                vector<int> v = cur;
                vector<int> w = num;
                v.push_back(w[i]);
                w.erase(w.begin()+i);
                per(w,v,ret);
            }
        }
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > ret;
        vector<int> cur;
        per(num,cur,ret);
        return ret;
    }
};

Update on Nov-8th-2014
Solution#2, using sort

class Solution {
public:
    void permute(vector<vector<int> > &rt,vector<int> cur,vector<int> num) {
        if (0 == num.size()) {
            rt.push_back(cur);
        }
        
        for (int i = 0; i < num.size(); i++) {
            vector<int> cpCur = cur;
            vector<int> cpNum = num;
            cpCur.push_back(num[i]);
            cpNum.erase(cpNum.begin() + i);
            permute(rt,cpCur,cpNum);
            
            while (i + 1 < num.size() && num[i] == num[i + 1]) {
                i++;
            }
            
        }
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(),num.end());
        vector<vector<int> > rt;
        vector<int> cur;
        permute(rt,cur,num);
        
        return rt;
    }
};

类似Permutation 1，每次确定一个数，重复的跳过

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

    void per(vector<vector<int> > &rt, vector<int> nums, int index) {
        if (index == nums.size() - 1) {
            rt.push_back(nums);
            return;
        }
        
        for (int i = index; i < nums.size(); i++) {
            if (i != index && nums[i] == nums[index]) continue;
            swap(nums,i,index);
            per(rt,nums,index + 1);
        }
        
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> rt;
        per(rt,nums,0);
        
        return rt;
    }
};

Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
-------------------------------------------------------------
Solution #1, n*n space

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int n = matrix.size();
        vector<vector<int> > cp(n,vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cp[j][n-1-i] = matrix[i][j];
            }
        }
        matrix = cp;
    }
};

Solution #2, in space

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int n = matrix.size();
        for (int row = 0; row < n / 2 ; row++) {
            for (int col = row; col < n - 1 - row; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[n-1-col][row];
                matrix[n-1-col][row] = matrix[n-1-row][n-1-col];
                matrix[n-1-row][n-1-col] = matrix[col][n-1-row];
                matrix[col][n-1-row] = temp;
            }
        }
    }
};

Day 58, #42, #43, #55, Trapping Rain Water, Multiply Strings, Jump Game II

Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

-----------------------------------------------------------------------------------
O(n) solution. for each bar, find the max height bar on the left and right. then for this bar it can hold min(max_left, max_right) - height

class Solution {
public:
    int trap(int A[], int n) {
        vector<int> leftMax(n,0);
        vector<int> rightMax(n,0);
        
        // get left max for each element
        for (int i = 1; i < n; i++) {
            leftMax[i] = max(leftMax[i - 1],A[i - 1]);
        }
        
        // get right max for each element
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = max(rightMax[i + 1], A[i + 1]);
        }
        
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int water = min(leftMax[i],rightMax[i]) - A[i]; 
            if (water > 0) {
                sum += water; 
            }
        }
        return sum;
    }
};

Update on Nov-6th-2014
come back
Solution #2, if leftMax < rightMax, leftIndex can contain (leftMax - A[leftIndex]) water, regardless what it looks like between leftIndex and rightIndex

class Solution {
public:
    int trap(int A[], int n) {
        int sum = 0;
        int leftMax = 0, rightMax = 0;
        int leftIndex = 0, rightIndex = n - 1;
        
        while (leftIndex <= rightIndex) {
            leftMax = max(leftMax,A[leftIndex]);
            rightMax = max(rightMax,A[rightIndex]);
            if (leftMax < rightMax) {
                sum += leftMax - A[leftIndex];
                leftIndex++;
            }else {
                sum += rightMax - A[rightIndex];
                rightIndex--;
            }
        }
        
        return sum;
    }
};

Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
--------------------------------------
Multiply numbers using straightforward math

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.length(), len2 = num2.length();
        string sum(len1 + len2,'0');
      
        for (int i = len1 - 1; i >= 0; i--) {
            int carry = 0;
            for (int j = len2 - 1; j >= 0; j--) {
                int cur = (sum[i + j + 1] - '0') + carry + (num1[i] - '0') * (num2[j] - '0');
                sum[i + j + 1] = cur % 10 + '0';
                carry = cur / 10;
            }
            sum[i] += carry;   
        }
        
        int start = 0;
        while (sum[start] == '0') {
            start++;
        }
        if (start == sum.length()) return "0";
        return sum.substr(start);
    }
};

Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
---------------------------------------------------------------------------
Greedy, the point of this question is to find the largest distance with minimum steps
Every time 'i' passes curMax, increment step

class Solution {
public:
    int jump(int A[], int n) {
        int curMax = 0, newMax = 0;
        int step = 0;
        for (int i = 0; i < n; i++) {
            if (i > curMax) {
                // set up new max from old steps
                curMax = newMax;
                step++;
            }
            newMax = max(newMax,i + A[i]); // this line should be placed after if condition, 'cause new step has been made
        }
        return step;
    }
};

Update on Nov-7th-2014
a slightly different version, handles the case where the goal cannot be reached

class Solution {
public:
    int jump(int A[], int n) {
        if (n == 1) return 0;
        int step = 1;
        int currentReach = A[0];
        int maxCanReach = A[0];
        
        for (int i = 1; i < n; i++) {
            if (i > currentReach) {
                // to handle cases where the end cannot be reached
                if (currentReach == maxCanReach) {
                    return -1;
                }
                step++;
                currentReach = maxCanReach;
            }
            maxCanReach = max(maxCanReach,i + A[i]);
        }
        
        return step;
    }
};

Day 57 #37, #40, Sudoku Solver, Combination Sum II

Search in Rotated Sorted Array
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

------------------------------------------
set up three 2D arrays as caches to store used numbers in each row, column and sub-block

class Solution {
public:
    bool sudoku (vector<vector<char> > &board, vector<vector<bool> > &rows, 
            vector<vector<bool> > &cols, vector<vector<bool> > &subs, int index) {
        if (index == 81) {
            return true;
        }
        int rowIndex = index / 9;
        int colIndex = index % 9;
        
        if (board[rowIndex][colIndex] == '.') {
            for (int i = 0; i < 9; i++) {
                if (!(rows[rowIndex][i] || cols[colIndex][i] || subs[(rowIndex / 3) * 3 + colIndex / 3][i])) {
                    board[rowIndex][colIndex] = '1' + i;
                    rows[rowIndex][i] = true;
                    cols[colIndex][i] = true;
                    subs[rowIndex / 3 * 3 + colIndex / 3][i] = true;
                    
                    // if conditions is false, backtrack
                    if (!sudoku(board, rows, cols, subs,index + 1)) {
                        board[rowIndex][colIndex] = '.';
                        rows[rowIndex][i] = false;
                        cols[colIndex][i] = false;
                        subs[rowIndex / 3 * 3 + colIndex / 3][i] = false;
                    }else {
                        return true;
                    }
                }
            }
            return false;
        }else {
            // if slot is filled already
            return sudoku(board, rows, cols, subs,index + 1);
        }
    }

    void solveSudoku(vector<vector<char> > &board) {
        // declare and populate caches
        vector<vector<bool> > rows(9,vector<bool>(9,false));
        vector<vector<bool> > cols(9,vector<bool>(9,false));
        vector<vector<bool> > subs(9,vector<bool>(9,false));
        for (int rowIndex = 0; rowIndex < 9; rowIndex++) {
            for (int colIndex = 0; colIndex < 9; colIndex++) {
                if (board[rowIndex][colIndex] != '.') {
                    int val = board[rowIndex][colIndex] - '1';
                    rows[rowIndex][val] = true;
                    cols[colIndex][val] = true;
                    subs[(rowIndex / 3) * 3 + colIndex / 3][val] = true;
                }
            }
        }
        
        // recursive call starts here
        sudoku(board,rows,cols,subs,0);
    }
};

Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
------------------------------------------------------------
Similar to #39 Combination Sum

class Solution {
public:
    void comb (vector<int>& candidates, int target, vector<vector<int> > &ret, vector<int> cur,int start) {
        if (target == 0) {
            ret.push_back(cur);
        }else {
            for (int i = start; i < candidates.size(); i++) {
                if (target - candidates[i] >= 0) {
                    vector<int> v= cur;
                    v.push_back(candidates[i]);
                    comb(candidates,target-candidates[i],ret,v,i+1); // no element can be re-used, so i + 1
                }
                
                // skip duplicates 
                while (candidates.size() - 1 > i && candidates[i] == candidates[i + 1]) {
                    i++;
                }
            }
        }
    }

    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        vector<vector<int> > ret;
        vector<int> cur;
        comb(num,target,ret,cur,0);
        return ret;
    }
};

类似

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

        while (index + 1 < candidates.size() && candidates[index] == candidates[index + 1]) {
            index++;
        }
        helper(rt,candidates,cur,target,index + 1);
        
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vector<int>> rt;
        vector<int> cur;
        helper(rt,candidates,cur,target,0);
        
        return rt;
    }
};

Day 56 #33, #34, Search in Rotated Sorted Array, Search for a Range

Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
------------------------------------------------------------
reference with excellent explanation
array is half sorted and the half rotated. Always start with the sorted half then determine which half that our target resides in

class Solution {
public:
    int search(int A[], int n, int target) {
        int start = 0, end = n - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (A[mid] == target) {
                return mid;
            }
            // first half is sorted
            if (A[start] <= A[mid]) {
                if (A[start] <= target && target <= A[mid]) {
                    end = mid - 1;
                }else {
                    start = mid + 1;
                }
            }else { // second half is sorted
                if (A[mid] <= target && target <= A[end]) {
                    start = mid + 1;
                }else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
};

Update on Dec-15-2014
A[end] would never have a chance to be equal to A[mid]. However, A[start] would in the cases that only contain two elements
that's why A[start] <= A[mid]  

Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
-----------------------------------------------------------------
注意掌握以下第一种方法
binary search
if hit target, continue searching to expand the range

class Solution {
public:
    void bin (int A[], int start, int end, int target, vector<int> &ret) {
        if (start > end) return;
        int mid = start + (end - start) / 2;
        if (A[mid] == target) {
            if (mid < ret[0] || ret[0] == -1) {
                ret[0] = mid;
                bin(A,start,mid - 1, target, ret);
            }
            if (mid > ret[1]) {
                ret[1] = mid;
                bin(A,mid + 1,end, target, ret);
            }
        }else if (A[mid] < target) {
            bin(A,mid + 1,end, target, ret);
        }else {
            bin(A,start,mid - 1, target, ret);
        }
    }

    vector<int> searchRange(int A[], int n, int target) {
        vector<int> ret(2,-1);
        bin(A,0,n-1,target,ret);
        return ret;
    }
};

class Solution {
public:
    void leftSearch(int A[], int left, int right, int target, vector<int> &range) {
        if (left > right) {
            return;
        }
        
        int mid = left + (right - left) / 2;
        if (A[mid] == target) {
            range[0] = mid;
            leftSearch(A,left,mid - 1,target,range);
        }else if (A[mid] < target) {
            leftSearch(A,mid + 1,right,target,range);
        }
    }
    
    void rightSearch(int A[], int left, int right, int target, vector<int> &range) {
        if (left > right) {
            return;
        }
        
        int mid = left + (right - left) / 2;
        if (A[mid] == target) {
            range[1] = mid;
            rightSearch(A,mid + 1,right,target,range);
        }else if (A[mid] > target) {
            rightSearch(A,left,mid - 1,target,range);
        }
    }
    

    vector<int> searchRange(int A[], int n, int target) {
        int left = 0;
        int right = n - 1;
        vector<int> range(2,-1);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) {
                range[0] = mid;
                range[1] = mid;
                leftSearch(A,left,mid - 1,target,range);
                rightSearch(A,mid + 1,right,target,range);
                break;
            }else if (A[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        
        return range;
    }
};

iterative，用2个额外二分法函数，一个是找连续target的起始点，一个是找连续target的终止点
设置好循环的终止条件就行