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;
    }
};