[LeetCode] 499. The Maze II

https://leetcode.com/contest/leetcode-weekly-contest-17/problems/the-maze-ii/

Solution:
will use DSF strategy. Use a bool flag to represent the status of the ball, true for stop and false for moving. The reason for distinguishing these two is that once it stops, it can move all the directions (if OK); but once it moves, it can only goes one direction (recorded in the trace string) until hits on the wall. And once the ball hits on the wall, there will be a switch between stop and move. In order to avoid duplicates, a visit vector is used to trace the visiting status of the ball positions only when it stops. For the smallest path, we will trace the steps needed. Once find the steps needed are larger than the one that have already been found, the recursion can return since it is not necessary. 

Code:

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        vector<string> ss;
        string s;
        vector<vector<bool>> visit(maze.size(), vector<bool>(maze.front().size(), true));
//label only when stop;
        visit[ball[0]][ball[1]] = false;
        int step = 0, l = 0;
        bool flag = true;//stop;
        findDSF(maze, ball[0], ball[1], hole, visit, s, ss, step, l, flag);
        if(ss.empty()) return "impossible";
        sort(ss.begin(), ss.end());
        return ss[0];
    }
private:
    void findDSF(vector<vector<int>> &m, int x, int y, vector<int> &h, vector<vector<bool>> &v, 
string s, vector<string> &ss, int step, int &l, bool flag){
        if(ss.size()&&step>l) return;//if more step needed, can give up;
        if(x==h[0] && y==h[1]){
            if(ss.empty() || step == l){ ss.push_back(s); l = step;}
            else{
                if(step<l){ ss.clear(); ss.push_back(s); l = step;}
            }
            return;
        }
        if(flag){//ball stops now, and is going to move;
            if(x-1>=0&&!m[x-1][y]&&v[x-1][y]){
                flag = false;
                if(x-1==0||(x-1>0&&m[x-2][y])) {flag = true;v[x-1][y] = false;}
                findDSF(m, x-1, y, h, v, s+'u', ss, step+1, l, flag);
                v[x-1][y] = true;
                flag = true;
            }
            if(x+1<m.size()&&!m[x+1][y]&&v[x+1][y]){
                flag = false;
                if(x+1==m.size()-1||(x+1<m.size()-1&&m[x+2][y])) 
                    {flag = true;v[x+1][y] = false;}
                findDSF(m, x+1, y, h, v, s+'d', ss, step+1, l, flag);
                v[x+1][y] = true;
                flag = true;
            }
            if(y+1<m.front().size()&&!m[x][y+1]&&v[x][y+1]){
                flag = false;
                if((y+1==m.front().size()-1)||(y+1<m.front().size()-1&&m[x][y+2])) 
                    {flag=true;v[x][y+1]=false;}
                findDSF(m, x, y+1, h, v, s+'r', ss, step+1, l, flag);
                v[x][y+1] = true;
                flag = true;
            }
           if(y-1>=0&&!m[x][y-1]&&v[x][y-1]){
                flag = false;
                if((y-1==0)||(y-1>0&&m[x][y-2])) {flag = true;v[x][y-1] = false;}
                findDSF(m, x, y-1, h, v, s+'l', ss, step+1, l, flag);
                v[x][y-1] = true;
                flag = true;
            }
        }
        else{//ball is moving, and it may stop when hits on the wall;
            if(s.back()=='u'&&x-1>=0&&!m[x-1][y]&&v[x-1][y]){
                if(x-1==0||(x-1>0&&m[x-2][y])) {flag = true;v[x-1][y] = false;}
                findDSF(m, x-1, y, h, v, s, ss, step+1, l, flag);
                v[x-1][y] = true;
                flag = false;
            }
            else if(s.back()=='d'&&x+1<m.size()&&!m[x+1][y]&&v[x+1][y]){
                if(x+1==m.size()-1||(x+1<m.size()-1&&m[x+2][y])) 
                    {flag = true;v[x+1][y] = false;}
                findDSF(m, x+1, y, h, v, s, ss, step+1, l, flag);
                v[x+1][y] = true;
                flag = false;
            }
            else if(s.back()=='r'&&y+1<m.front().size()&&!m[x][y+1]&&v[x][y+1]){
                if(y+1==m.front().size()-1||(y+1<m.front().size()-1&&m[x][y+2])) 
                    {flag = true;v[x][y+1]=false;}
                findDSF(m, x, y+1, h, v, s, ss, step+1, l, flag);
                v[x][y+1] = true;
                flag = false;
            }
            else if(s.back() =='l'&&y-1>=0&&!m[x][y-1]&&v[x][y-1]){
                if(y-1==0||(y-1>0&&m[x][y-2])) {flag = true;v[x][y-1] = false;}
                findDSF(m, x, y-1, h, v, s, ss, step+1, l, flag);
                v[x][y-1] = true;
                flag = false;
            }
            else return;
        }
    }
};

The code length is too long for DSF, and it should be shorter if using BSF. But we need to trace the path and steps too. So we need some data structure to connect the positions with the steps and paths. Pair structure (pair<int, string> is chosen for step and path, and positions can be represented by a two dimensional array. So the data structure overall looks like this: vector<vector<pair<int, string>>>.  The code below is based on BSF strategy.

Code:

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        pair<int, string> dp[30][30];
        int n=maze.size(), m=maze[0].size();
        for(int i=0;i<n;i++)for(int j=0;j<m;j++) dp[i][j]=make_pair(10000000,"");
        vector<int> dx={1, 0, 0, -1};
        vector<int> dy={0, -1, 1, 0};
        string c="dlru"; 
        queue<pair<int,int>> q;
        q.push(make_pair(ball[0],ball[1]));
        dp[ball[0]][ball[1]]=make_pair(0,"");
        while(q.size()){
            pair<int, int> t=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                pair<int, int> now=t;
                int v=0;
                while(1){
                    if(now.first==hole[0]&&now.second==hole[1])break;
                    pair<int, int> next=make_pair(now.first+dx[i],now.second+dy[i]);
                    if(next.first<0||next.second<0||next.first>=n||next.second>=m)break;
                    if(maze[next.first][next.second]==1)break;
                    v++;
                    now=next;
                }
                pair<int, string>tt=make_pair(dp[t.first][t.second].first+v,dp[t.first][t.second].second+c[i]);
                if(v&&dp[now.first][now.second]>tt){
                    dp[now.first][now.second]=tt;
                    q.push(now);
                }
            }
        }
        if(dp[hole[0]][hole[1]].first==10000000)return "impossible";
        return dp[hole[0]][hole[1]].second;
    }
};

[LeetCode] 495. Teemo Attacking

https://leetcode.com/contest/leetcode-weekly-contest-17/problems/teemo-attacking/

Solution:
This question should be an easy level question. The only thing need to do is to compare the difference of the adjacent elements in the array with that of the duration time. If larger, then it will take duration time to recover; if smaller, it will take the difference.

Code:

class Solution {
public:
    int findPosisonedDuration(vector<int>& timeSeries, int duration) {
        int res = duration, l = timeSeries.size();
        if(l == 0) res = 0;
        for(int i=1; i<l; ++i){
            int t = timeSeries[i]-timeSeries[i-1];
            res += t>=duration?duration:t;
        }
        return res;
    }
};

[LeetCode] 501. Find Mode in Binary Tree

https://leetcode.com/contest/leetcode-weekly-contest-17/problems/find-mode-in-binary-tree/
Find all the elements that appears mostly.

Solution:
Use a hashmap to count the time of duplicates. Then save the elements with the highest appearing time into the output.

Code:

/**
 * 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> findMode(TreeNode* root) {
        vector<int> res;
        unordered_map<int, int> m;
        int ct = 0;
        findM(root, m, ct);
        for(auto a:m){
            if(a.second == ct) res.push_back(a.first);
        }
        return res;
    }
private:
    void findM(TreeNode* root, unordered_map<int, int> &m, int &c){
        if(!root) return;
        c = max(c, ++m[root->val]);
        findM(root->left, m, c);
        findM(root->right, m, c);
    }
};

[LeetCode] 316. Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/

Solution:
The hard part is the smallest in lexicographical order. So in addition to a hashmap, we also need an extra vector to label each elements for the status of visiting. First to count the appearance times for each letters in the input string. Then when scan the input string, for each new element, we need to compare it with the last letter in the output string. If the new element is smaller than the last letter in the string and also the counting for the last element is larger than 0 (which means there is still more than 0 elements in the rest part of the input string), we need to set the status of the last letter to be un-visited and remove it. Otherwise, we can add the new elements in the back of the output string and set the visiting status as true. See code below.

Code:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string res = "0";
        vector<int> m(26, 0), visit(26, 0);
        for(auto a:s) ++m[a-'a'];
        for(auto a:s){
            int t = a-'a';
            --m[t];
            if(visit[t]) continue;
            while(a<res.back() && m[res.back()-'a']){
                visit[res.back()-'a'] = 0;
                res.pop_back();
            }
            res.push_back(a);
            visit[t] = 1;
        }
        return res.substr(1);
    }
}; 

Further thinking:
How about the largest lexicographical order?
Ans: set the res to be "~" or some others that are larger than 'z'; and then change the "a<res.back()" inside the while condition into "a>res.back()". Done.

http://www.cnblogs.com/grandyang/p/5085379.html

[LeetCode] 312. Burst Balloons

https://leetcode.com/problems/burst-balloons/

Solution:
A very good question since that I have to change the way how I do analysis usually. Initially I started with to pick one element (k), then think about how to deal with the rest part. (I think this is may be the common way to think about this question, which will eventually lead to brute force DSF).

But if we change the way to think it a little bit, we will surprise ourselves (at least to me). Instead of picking up element k firstly, how about choose it at the end? Imagine we have elements array from i to j (we can put 1 at each end for boundary conditions). Let's use dp[i][j] represents the max we can get in this range, then dp[i][j] = max{dp[i][j], d[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]}, where i<= k <= j. The key point for understanding this is that we will pick element k as the end.  Amazing, isn't it?

Some details for implementation of dp:
From the transition equation, we can see that dp[i][j] will be calculated from dp[i][k-1] and dp[k+1][j], and k-1 < j and k+1 > i. This indicates that one possible way to do it is to start with larger i and smaller j.  And dp[1][n] is the final answer we need. (for i>j, dp[i][j] is apparently zero due to definition.)

Code:

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n+2, vector<int>(n+2,0));
        for(int i=n; i>=1; --i){
            for(int j=i; j<=n; ++j){
                for(int k=i; k<=j; ++k){
                    dp[i][j] = max(dp[i][j],  dp[i][k-1]+dp[k+1][j]+nums[i-1]*nums[k]*nums[j+1]);
                }
            }
        }
        return dp[1][n];
    }
}; 

[LeetCode] 464. Can I Win

https://leetcode.com/problems/can-i-win/


Solution:
One of the important constrains is that each element can only be used once. Therefore, if we use dp strategy, we have to take it into account since it will change the "status" of the sub-questions.

We can use binary representation for the status of the element usage. For each element, if it is not used yet, its status is 1; once used, become 0. So there will be 2^n status in total, where n is the total number of elements.

In order to increase efficiency, we need memorization of the results for the status visited previously, which is a very common trick to short the running time. Since we have already calculated it, there's no need for re-calculation. For this question, we will use a hashmap for implementation.

Another parameter for each sub-status is the target value, and it will also changes (becomes smaller) as some elements is chosen. So here we will use a vector<unordered_map<int, bool> > structure to store the status information, to memorize both the target value and status information. The index of the vector will be used for the target value.

The two players in this game will always play optimally, so once there is one way that the second player cannot win, the first will win. If for all the possible ways, the second player can always win, then the first player have to lose. At this point, we will use dsf strategy for searching.

Code:

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        int m = maxChoosableInteger, d = desiredTotal;
        if(m>=d) return true;
        if(m*(m+1)<d*2) return false;
        vector<unordered_map<int, bool>> dp(d);
        int t = (1<<m) - 1;
        return canWin(m, d, dp, t);
    }
private:
    bool canWin(int m, int d, vector<unordered_map<int, bool>> &dp, int sta){
        if(dp[d-1].count(sta)) return dp[d-1][sta];
        for(int i=0; i<m; ++i){
            if((1<<i)&sta){// i element is not used.
                if(i+1>=d || !canWin(m, d-i-1, dp, sta^(1<<i))){
                    dp[d-1][sta] = true;
                    return true;
                }
            }
        }
        dp[d-1][sta] = false;//the second player always win.
        return false;
    }
}; 

After finishing this, also noticed that there are some other way for implementation, and here is one example with discussion:

https://discuss.leetcode.com/topic/68896/java-solution-using-hashmap-with-detailed-explanation

"After solving several "Game Playing" questions in leetcode, I find them to be pretty similar. Most of them can be solved using the top-down DP approach, which "brute-forcely" simulates every possible state of the game.
The key part for the top-down dp strategy is that we need to avoid repeatedly solving sub-problems. Instead, we should use some strategy to "remember" the outcome of sub-problems."

"For this question, the key part is: what is the state of the game? Intuitively, to uniquely determine the result of any state, we need to know:

1. The unchosen numbers
2. The remaining desiredTotal to reach

A second thought reveals that 1) and 2) are actually related because we can always get the 2) by deducting the sum of chosen numbers from original desiredTotal.
Then the problem becomes how to describe the state using 1)."
(one of the equivalent ways to understand this is that if we know condition 1 (the unchosen numbers) only, then we can determine the state completely, since that every element can be only used once.)

So only one hashmap is enough to memorize the sub-status for choosing elements.

Code:

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        int m = maxChoosableInteger, d = desiredTotal;
        if(m>=d) return true;
        if(m*(m+1)<d*2) return false;
        unordered_map<int, bool> dp;
        return canWin(m, d, dp, 0);
    }
private:
    bool canWin(int m, int d, unordered_map<int, bool> &dp, int sta){
        if(dp.count(sta)) return dp[sta];
        for(int i=0; i<m; ++i){
            if(((1<<i)&sta)==0){
                if(i+1>=d || !canWin(m, d-i-1, dp, sta|(1<<i))){
                    dp[sta] = true;
                    return true;
                }
            }
        }
        dp[sta] = false;
        return false;
    }
};  

[quize] 1: Coin Game

Question:
There are two players, (you and your friend), and you are going to pick up coins alternatively from a bag of coins(total number is n). The rule is every time you or your friend can pick up 1 to 4 coins, and the winner will be the one who picks up the last coin. Then how can you know or what kind of strategy are you going to take to win? Suppose you will pick up first and your friend is as smart as you.

Solution:
Start from small samples:
if there is only 1 coin, you will win;
                        2                        win;
                        3                        win;
                       4                         win;
                       5 coins, you will lose no matter what you do...
                       6 , if you choose 1, then leave 5 coins to you friend to choose from, and you will will.
                       7,  you choose 2, and then win.
....

So if the total number of coins are n, then if n%(1+4) == 0, you will never win, otherwise you can win if you and your friend are clever enough.

Further thinkings:
1: how about that you (and your friend) can pick up up to 10 coins, instead of 4?
2: how about that each number can be only chosen once? see the following post:
http://startleetcode.blogspot.com/2017/01/464-can-i-win.html

[LeetCode] 486. Predict the Winner

https://leetcode.com/contest/leetcode-weekly-contest-16b/problems/predict-the-winner/

Solution:
Will use dp strategy.Define dp[l][r] as the max gain for one player comparing with his opponent in the range from l to r.

Code:

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int l=n-2; l>=0; --l){
            for(int r=l+1; r<n; ++r){
                dp[l][r] = max(nums[l]-dp[l+1][r], nums[r]-dp[l][r-1]);
            }
        }
        return dp[0][n-1]>=0;
    }
}; 

[LeetCode] 310. Minimum Height Trees

https://leetcode.com/problems/minimum-height-trees/

Solution:
Based on the properties of the undirected graph, there will most two MHTs. (For example, only two elements (should be two), or three elements (one or two), ... But the rigorous proving is not available now...)). 

First step to build a graph to connect all the nodes. Usually one two-dimensional vector is ok for building a graph, but for this question, we will visit (or delete) some elements, so it will be convenient using unordered_set instead of vector. After building the graph, we can start the search by putting vertices with outdegree of 1 into a queue. Then loop the queue, for each element, find all the elements connected. Then for all the connected elements, reduce their outdegrees (-1) by removing the element initially found in the queue.  If their outdegree becomes 1, put them into the queue. Continue this loop until the number of the total number of the elements is less than 3. It is like a "bottom up" fashion to find the top elements or "roots". 

Code:

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        if(n==1) return{0};
        vector<int> res;
        vector<unordered_set<int>> graph(n);
        queue<int> q;
        for(auto a:edges){
            graph[a.first].insert(a.second);
            graph[a.second].insert(a.first);
        }
        for(int i=0; i<n; ++i){
            if(graph[i].size() == 1) q.push(i); 
        }
        while(n>2){
            int l = q.size();
            n -= l;
            for(int i=0; i<l; ++i){
                int p = q.front();
                q.pop();
                for(auto a:graph[p]){
                    graph[a].erase(p);
                    if(graph[a].size() == 1) q.push(a);
                }
            }
        }
        while(q.size()){
            res.push_back(q.front());
            q.pop();
        }
        return res;
    }
}; 

http://www.cnblogs.com/grandyang/p/5000291.html

[LeetCode] 307. Range Sum Query - Mutable

https://leetcode.com/problems/range-sum-query-mutable/

Solution:
Will use dynamic programming strategy. Let dp(i) represent the sum of elements from 0 to i-1. Then the sum of elements from i to j inclusively can be expressed as (dp[j+1] - dp[i]). Once one element is changed, all the dp[i] after that elements need to be updated.

Code:

class NumArray {
public:
    NumArray(vector<int> &nums) {
        sum.push_back(0);
        for(auto a:nums) sum.push_back(sum.back() + a);
    }

    void update(int i, int val) {
        if(i<sum.size()-1){
            int t = val - (sum[i+1]-sum[i]);
            for(int j=i+1; j<sum.size(); ++j) sum[j] += t;  
        }
    }

    int sumRange(int i, int j) {
        if(j<sum.size()-1) return sum[j+1]-sum[i];
    }
private:
    vector<int> sum;
};

306. Additive Number

https://leetcode.com/problems/additive-number/

Solution:
use DSF strategy. It is kinds of brute force implementation. As long as one is found (or reaching to the end of the string in the DSF search), return true. After all tries, return false. For the overflow, can use string instead of integer for the adding. See code below.

Code:

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int l = num.size();
        if(l<3) return false;
        for(int i=1; i<l-1; ++i){
            for(int j=i+1; j<l; ++j){
                string s1 = num.substr(0, i);
                string s2 = num.substr(i, j-i);
                if(dsf(num, j, s2, add(s1, s2))) return true;
                if(num[i] == '0') break;
            }
            if(num[0] == '0') break;
        }
        return false;
    }
private:
    bool dsf(string num, int ind, string s1, string s2){
            if(num.size()-ind < s2.size()) return false;
            if(num.substr(ind) == s2) return true;
            for(int i=0; i<s2.size(); ++i){
                if(s2[i] != num[ind+i]) return false;
            }
            ind += s2.size();
            return dsf(num, ind, s2, add(s1, s2));
        }
    string add(string s1, string s2){
        if(s1.size()>s2.size()) return add(s2, s1);
        if(s1.empty()) return s2;
        string res;
        int carrier = 0;
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        for(int i=0; i<s1.size(); ++i){
            int t = carrier + (s1[i]-'0') + (s2[i] - '0');
            carrier = t/10;
            t %= 10;
            res.push_back(t+'0');
        }
        for(int i=s1.size(); i<s2.size(); ++i){
            int t = carrier + s2[i] - '0';
            carrier = t/10;
            t %= 10;
            res.push_back(t+'0');
        }
        if(carrier) res.push_back(carrier+'0');
        reverse(res.begin(), res.end());
        return res;
    }
};

301. Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/  b

Solution:
will use BSF strategy. It is like brute force BSF, but will use a hash map to reduce duplicates; and also, this question ask for the minimum change, so once find the valid one, we just need to save all the valid strings in the same "layer" of the BSF.

Code:

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        unordered_map<string, int> m;
        queue<string> q;
        q.push(s);
        ++m[s];
        bool found = false;//label for valid layer.
        while(q.size()){
            string t = q.front();
            q.pop();
            if(isValid(t)){
                res.push_back(t);
                found = true;
            }
            if(found) continue;
            for(int i=0; i<t.size(); ++i){
                if(t[i] != '(' && t[i] != ')') continue;
                string temp = t.substr(0, i) + t.substr(i+1);//brute force BSF
                if(m.find(temp) == m.end()){
                    q.push(temp);
                    ++m[temp];
                }
            }
        }
        return res;
    }
private:
    bool isValid(string str){
        int ct = 0;
        for(auto a:str){
            if(a == '(') ++ct;
            if(a == ')' && ct-- == 0) return false;
        }
        return ct == 0;
    }
};

http://www.cnblogs.com/grandyang/p/4944875.html

287. Find the Duplicate Number

https://leetcode.com/problems/find-the-duplicate-number/

Solution:
Use radix sort. (so it seems not a "hard" level question...)

Code:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int res = 0, l = nums.size();
        for(int i=0; i<l; ++i){
            while(i+1 != nums[i]){
                if(nums[i] == nums[nums[i]-1]){
                    res = nums[i];
                    break;
                }
                swap(nums[i], nums[nums[i]-1]);
            }
            if(res) break;
        }
        return res;
    }
};

290. Word Pattern

https://leetcode.com/problems/word-pattern/

Solution:
Use double hash maps to build up one-to-one relationship.

Code:

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector<string> v(26, "");
        unordered_map<string, char> m;
        int i = 0, j = 0, l1 = pattern.size(), l2 = str.size();
        for(; i<l1 && j<l2; ++i){
            while(j<l2 && str[j] == ' ') ++j;
            int t = j;
            while(t<l2&&str[t] != ' ') ++t;
            string s = str.substr(j, t-j);
            if(v[pattern[i]-'a'] == "" && m.find(s) == m.end()){ 
                v[pattern[i]-'a'] = s;
                m[s] = pattern[i];
            }
            else{ 
                if(v[pattern[i]-'a'] != s || m[s] != pattern[i]) return false;
            }
            j = t;
        }
        return i == l1 && j == l2;
    }
};

486. Max Consecutive Ones II

https://leetcode.com/problems/max-consecutive-ones ii/
This is the following question of 485. If for most one 0 can be flipped to 1, then what is the max consecutive 1s?

Solution:
Nee two variables. One for the previous length of 1s, which may be used when there is only one 0 existing between 1s. The other is the count of 1s after 0.

Code:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, l = nums.size(), c1 = 0, pre = 0;//c1 is the counting of 1s.
        for(int i=0; i<l; ++i){
            ++pre;// the counting for previous 1s.
            ++c1;
            if(nums[i] == 0){
                c1 = pre;
                pre = 0;
            } 
            res = max(res, c1);
        }
        return res;
    }
};

485. Max Consecutive Ones

https://leetcode.com/problems/max-consecutive-ones/

Solution:
It is an easy question. If element is 1, count+1; otherwise, count = 0. Update res for each loop.

Code:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, l = nums.size();
        for(int i=0; i<l; ++i){
            int t = i;
            while(t<l && nums[t] == 1) ++t;
            res = max(res, t-i);
            i = t;
        }
        return res;
    }
};

Another way to code:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, l = nums.size(), c1 = 0;//c1 is the counting of 1;
        for(int i=0; i<l; ++i){
            ++c1;
            if(nums[i] == 0) c1 = 0;
            res = max(res, c1);
        }
        return res;
    }
};

488. Zuma Game

https://leetcode.com/problems/zuma-game/

Solution:
will use dsf strategy to find the minimum steps for reaching the end(empty string). If find two same adjacent elements and also have more than one at hand, then match to cancel them; if can only find one element which is different from its left and right neighbors, and there are more than two that kind of elements at hand, then add two to match to cancel. After each canceling, need to consider possible sequential canceling. For example, GGRRGG. When the mid RR was cancelled, then the rest GGGG will cancel automatically.

Code:

class Solution {
public:
    int findMinStep(string board, string hand) {
        int res = INT_MAX;
        vector<int> v(26, 0);
        for(auto a:hand) ++v[a-'A'];
        dsf(board, hand.size(), v, 0, res);
        return res==INT_MAX?-1:res;
    }
private:
    void dsf(string b, int l, vector<int> &v, int count, int &r){
        if(b.size()>=3) b = helper(b);
        if(b.empty()) r = min(r, count);
        else if(l<=0) return;
        else{
            for(int i=0; i<b.size(); ++i){
                if(i<b.size()-1 && b[i]==b[i+1] && v[b[i]-'A']){
                    --v[b[i]-'A'];
                    b.insert(i+b.begin(), b[i]);
                    dsf(b, l-1, v, count+1, r);
                    b.erase(i+b.begin());
                    ++v[b[i]-'A'];
                }
                else{
                    if(v[b[i]-'A'] >= 2){
                        v[b[i]-'A'] -= 2;
                        char t = b[i];
                        b.erase(i+b.begin());//corner case: b may become empty now.
                        dsf(b, l-2, v, count+2, r);
                        b.insert(i+b.begin(), t);
                        v[b[i]-'A'] += 2;
                    }
                }
            }
        }
    }
    string helper(string s){
        bool flag = true;
        while(s.size()>=3 && flag){
            for(int i=0; i<s.size()-2; ++i){
                if(s[i]==s[i+1] && s[i] == s[i+2]){
                    int t = 3;
                    while(i+t<s.size() && s[i] == s[i+t]) ++t;//more than 3. 
                    s.erase(s.begin()+i, s.begin()+i+t);
                    flag = true;
                    break;
                }
                else flag = false;
            }
        }
        return s;
    }
};

260. Single Number III

https://leetcode.com/problems/single-number-iii/

Solution:
Do not have any clue for this question with time complexity of O(n) and space complexity of O(1). Thought about bitwise operation, but still cannot figure out how to distinguish two different numbers until searching online. The reference link is listed below.

First step is to obtain the xor of the two different nums, which is trivial; then is the key part: choose one non-zero bit of the xor result as an indicator to separate the initial nums into two groups. Each group should have one of two unique elements. Then it is trivial to find them.

Code:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2, 0);
        int t = 0; 
        for(auto a:nums) t ^= a;
        t &= -t; //the most-right non-zero bit;
        for(auto a: nums){
            if(t&a) res[0] ^=a;
            else res[1] ^=a;
        }
        return res;
    }
};

http://www.cnblogs.com/grandyang/p/4741122.html

240. Search a 2D Matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/

Solution:

An interesting question. Let look at element Matrix[x][y]. All the elements in the up-left region are smaller; and all the elements in the down-right region are larger. And the rest two parts (up-right and down-left) are unknown. However, if we start from the most down-left corner, or the most up-right corner, only one unknown region will left initially. Let's choose the most up-right corner as the starting point. If Matrix[x][y] is larger than target, --y; else if Maxtrix[x][y] is smaller than target, ++ x; else if Matrix[x][y] equals to target, return true. If no element can be found after scanning, return false.

Code:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix.front().empty()) return false;
        int m = matrix.size(), n = matrix.front().size(), x = 0, y = n-1;
        while(x<m && y>=0){
            if(matrix[x][y] == target) return true;
            else if(matrix[x][y] < target) ++x;
            else --y;
        }
        return false;
    }
};

482. License Key Formatting

https://leetcode.com/contest/leetcode-weekly-contest-14/problems/license-key-formatting/

Solution:
feel like it is not a "medium" level question, should be a "simple" one. Scan from the right to left, if it is '-', remove it; if it is char from 'a' to 'z', convert it to the corresponding uppercase, count + 1; otherwise, count + 1, continue.  If the total elements accumulate to K, add '-'; continue scanning until end.

Code:

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        int i = S.size()-1, t = 0;
        while(i>=0){
            if(S[i] == '-') S.erase(S.begin()+i);
            else{
                if(S[i] >= 'a' && S[i] <= 'z' ) S[i] = S[i] - 'a' + 'A';
                ++t;
                if(t == K){
                    S.insert(S.begin()+i, '-');
                    t = 0;
                }
            }
            --i;
        }
        if(S[0] == '-') S.erase(S.begin());
        return S;
    }
};

481. Magical String

https://leetcode.com/contest/leetcode-weekly-contest-14/problems/magical-string/

Solution:
Need to find some pattern for this question. After careful observation, it is found that:
1): the 1 and 2 groups appears alternatively;
2): the numbers of char inside each group are determined by the previous sequential char value in the same string (that's one of reasons why it is magical, as indicated);

Code:

public:
    int magicalString(int n) {
        if(n<1) return 0;
        if(n<4) return 1;
        int res = 1;
        string s = "122";
        for(int i=2, t=2; i<n; ++i){// t as the flag to be 1 or 2 for adding;
            if(s[i] == '1'){
                ++res;
                if(t == 1){
                    s += "2";
                    t = 2;
                }
                else{
                    s += "1";
                    t = 1;
                }
            }
            else{
                if(t == 1){
                    s += "22";
                    t = 2;
                }
                else{
                    s += "11";
                    t = 1;
                }
            }
        }
        return res;
    }
};

236. Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ 

Solution: 

One of the classical questions (The first time to see this question backs to my undergraduate...). The lowest common ancestor (LCA) should have the following features: 

1): the LCA itself is one of the two target nodes; 

2): if 1) is not the case, then the two target nodes should locate at different sides (left and right) of LCA; 

3): if we find two target nodes at the same side (left or right), then it is one of the ancestors, but not the LCA. So we need go to lower level for continuing search.

Code:

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q) return root;
        bool a = findN(root->left, p), b = findN(root->right, q);
        if(a&&b || (!a && !b)) return root;
        if(a&&!b) return lowestCommonAncestor(root->left, p, q);
        return lowestCommonAncestor(root->right, p, q);
    }
private:
    bool findN(TreeNode* r, TreeNode* t){
        if(!r) return false;
        if(r == t) return true;
        return findN(r->left, t) || findN(r->right, t);
    }
}; 

223. Rectangle Area

https://leetcode.com/problems/rectangle-area/

Solution:
An interesting question. Looks like very simple, but not easy to code initially. However, after careful thinking, it is quick straightforward. If the minimum of the two right edge smaller than the maximum of the two left edge, then there's no overlap; similar argument can also be applied on the y-axis.

Further thinking:
1): how about more than two rectangles? A simple solution is calculate the overlap of any pairs of rectangles with time complexity of O(n2). Is there a better one?
2): Similar to Skyline problem, how to solve the "rectangle-line problem"?

Code:

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int res = 0;
        res += (C-A)*(D-B) + (G-E)*(H-F);
        if(min(C, G)>max(A, E) && min(D, H)>max(B, F))//avoiding overflow problem. 
        res -= (min(C, G)-max(A, E))*(min(D, H)-max(B, F));
        return res;
    }
};