[LeetCode]: 545. Boundary of Binary Tree

https://leetcode.com/contest/leetcode-weekly-contest-25/problems/boundary-of-binary-tree/

Solution:
Need to get the left boundary, the right boundary, and the leaves. It is straightforward for the first two. For the last one, we need to the transverse of the tree. For simplicity, we can do it recursively. See code below:

/**
 * 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> boundaryOfBinaryTree(TreeNode* root) {
        vector<int> l, res, r;
        if(!root) return l;
        l.push_back(root->val);
        TreeNode* p = root->left, *p1 = root->right;
        if(!p && !p1) return l;
        while(p){
            if(p->left || p->right) l.push_back(p->val);
            if(p->left) p = p->left;
            else p = p->right;
        }
        while(p1){
            if(p1->left || p1->right) r.push_back(p1->val);
            if(p1->right) p1 = p1->right;
            else p1 = p1->left;
        }
        help(res, root);
        reverse(res.begin(), res.end());
        while(res.size()){
            l.push_back(res.back());
            res.pop_back();
        }
        while(r.size()){
            l.push_back(r.back());
            r.pop_back();
        }
        return l;
    }
private:
    void help(vector<int> &r, TreeNode* t){
        if(!t) return;
        help(r, t->left);
        if(!t->left && !t->right) {
            r.push_back(t->val);
        }
        help(r, t->right);
    }
};

[LeetCode]: 546. Remove Boxes

https://leetcode.com/contest/leetcode-weekly-contest-25/problems/remove-boxes/

Solution:
This question is not easy. May use the dsf strategy, but the brutal force one cannot pass the OJ. One way to optimize it is to use memorization of the intermediate states. The parameters for the states needs include the range, the number of repeated elements, and the earned points. The range needs two parameters: the left and right. So we need a three-dimensional array to represent the states, and the value of it will be earned points. Let us dp[l][r][ct] represent the highest points earned in the range of l to r, where l is the left boundary, r is the right boundary, and ct is the number of repeated elements. The we need to calculate dp[0][n-1][0].

We can first calculate the dp[l][r][ct] = dsf(l+1, r, 0) + (ct+1)*(ct+1), which is equivalent to separate the original array into the first element and the rest ones;
Then is the key part:  since we need to find the maximum, we need to loop the whole array, and when the same elements as the first element is found, the transition equation can be wrote:
                 dp[l][r][ct] = max(dp[l][r][ct], dsf(l+1, i-1, 0) + dsf(i, r, ct+1)),  when arr[l] == arr[i].
where i is between l+1 and r. The second term in the max() is to divide the array into two parts: the first one is from l+1 to i-1 with 0 repeated elements; the other is from i to r with ct+1 repeated elements so far (arr[l] == arr[i]). (or the l element is now adjacent with the ith element.)

In order to reduce the complexity of the dsf, we can assign some unique initial value to dp[l][r][ct], for example, a negative value. Then when the dp[l][r][ct] becomes positive, it means it has already been calculated. So we can just use the calculated results directly. This is exactly how memorization works. See code below for details:

Code:

const int N = 100;
int dp[N][N][N];

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        memset(dp, -1, sizeof(dp));
        return dsf(boxes, 0, n-1, 0);
    }

    int dsf(vector<int> &b, int l, int r, int ct){
        if(l>r) return 0;
        int t = dp[l][r][ct];
        if(t!=-1) return t;
        t = dsf(b, l+1, r, 0) + (ct+1)*(ct+1);
        for(int i=l+1; i<=r; ++i){
            if(b[i]==b[l]) t=max(t, dsf(b, l+1, i-1, 0) + dsf(b, i, r, ct+1));
        }
        return dp[l][r][ct]=t;
    }
};

[LeetCode]: 544. Output Contest Matches

https://leetcode.com/contest/leetcode-weekly-contest-24/problems/output-contest-matches/

Solution:
This question is pretty straightforward: will used string vector to store the initial array, then gradually combine them by adding the first one with the last one, ... until only one array left. See code below: 

Code:

class Solution {
public:
    string findContestMatch(int n) {
        if(n<2) return"";
        vector<string> res;
        for(int i=1; i<=n; ++i){
            res.push_back(to_string(i));
        }
        while(res.size()>1){
            int t = res.size();
            for(int i=0;i<t/2; ++i){
                res[i] = '(' + res[i] + ',' + res.back() + ')';
                res.pop_back();
            }
        }
        return res[0];
    }
}; 

[LeetCode] 542. 01 Matrix

https://leetcode.com/contest/leetcode-weekly-contest-24/problems/01-matrix/

Solution:
This question seems not hard, but it is not easy to pass the OJ. One way to do it is kind of brute force bfs: for each element, gradually expand the searching range step by step until find the 0 element. But it is not fast enough.

One way to improve it is to think it in an opposite way: starting from elements with 0 value. Then gradually expand it: the first layer of neighbors should be 1; then the next layer should be 2; ... It's kind of using memorization. See code below:

Code:

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        vector<vector<int>> res = matrix;
        if(!matrix.size() || !matrix.front().size()) return res;
        int m = matrix.size(), n = matrix.front().size();
        typedef pair<int, int> tp;
        queue<tp> q;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(matrix[i][j]==0) q.push(tp(i, j));
                else res[i][j] = -1;
            }
        }
        vector<tp> d={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while(q.size()){
            tp tt = q.front();
            int a = tt.first, b = tt.second;
            q.pop();
            for(auto t:d){
                int x = a + t.first, y = b + t.second;
                if(x>=0&&x<m&&y>=0&&y<n&&res[x][y]==-1){
                    res[x][y] = res[a][b] + 1;
                    q.push(tp(x,y));
                }
            }
        }
        return res;
    }
};

[LeetCode] 536. Construct Binary Tree from String

https://leetcode.com/contest/leetcode-weekly-contest-23/problems/construct-binary-tree-from-string/

Solution:
The basic idea is to form the root first; then form the left children; then the right one. So we will use recursion strategy. See code below:

Note: The description for this question is not very clear, for example: the meaning of the '-' (it means negative number actually), and also the number can be larger than 10...

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* str2tree(string s) {
        TreeNode* res;
        int n = s.size(), i = 0;
        if(n==0) return NULL;
        int flag = 1;
        if(s[i] == '-'){
            flag = -1;
            ++i;
        }
        if(i<n&&(s[i]-'0'>=0)&&(s[i]-'0'<=9)) {
            int t=0; 
            while(i<n&&(s[i]-'0'>=0)&&(s[i]-'0'<=9)) t = t*10 + (s[i++]-'0');
            res = new TreeNode(flag*t); 
        }
        if(i<n&&s[i]=='('){
            int t = 1, ct = i+1;
            while(t>0&&ct<n){
                if(s[ct]=='(') ++t;
                if(s[ct]==')') --t;
                ++ct;
            } 
            if(t==0)res->left = str2tree(s.substr(i+1, ct-i-1)); //left children;
            if(t==0&&ct<n&&s[ct]=='(')res->right = str2tree(s.substr(ct+1, n-ct-2));//right children;
        }
        return res;
    }
};

[LeetCode] 514. Freedom Trail

https://leetcode.com/contest/leetcode-weekly-contest-22/problems/freedom-trail/

Solution:
Basically, there are two ways to switch into the target position. One is to from left to right; the other is the opposite direction. And we need to pick up the shorter one to continue. The difficult part is that there are duplicates in both the ring and key, so we need to try each of them, so we can use brute force DSF and then return the one with the shortest length. To reduce the time complexity, a hash map can be used to built up the relationship between the char in the key and the corresponding positions in the ring. See code below, (even though it is still too slow to pass the OJ)

Code:

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int m=ring.size(), n=key.size();
        if(!m || !n) return 0;
        int res = m*n;
        unordered_map<int, vector<int>> map;
        for(auto a: key){
            if(map.find(a-'a') == map.end()){
                for(int i=0; i<m; ++i){
                    if(ring[i]==a) map[a-'a'].push_back(i);
                }
            }
        }
        findDSF(ring, 0, key, 0, 0, map, res);
        return res;
    }
private:
    void findDSF(string r, int i, string key, int j, int l, unordered_map<int, vector<int>> &m, int &res){
        if(l>=res) return;
        if(j==key.size()){res = l; return;}
        for(auto k:m[key[j]-'a']){
            int t1 = abs(k-i), t = r.size(), t2 = t - t1;
            findDSF(r, k, key, j+1, l+min(t1, t2)+1, m, res);
        }
    }
}; 

Since the above brute force DSF cannot pass the OJ, we need to think about something else that is faster. DP is one choice. Let's use dp[i][j] represent the shortest length to match key [0, to i] and ring[0-j]. When key[i] == ring[j], 
                             

dp[i][j] = min(dp[i-1][k] + min steps from k to j)  for  all k (0<= k < ring.size())

The min steps from k to j can be obtained by comparing the two way mentioned above: one is from left to right; the other is the opposite way. And we need to choose the shorter one.
Some details for initialization:
1): the maximum steps will be the length of ring times the length of the key; (why? because this is the worst case: for every char in the key, we need to search the whole ring);
2): We can initialize the dp[i][j] with the maximum steps, since we are looking for minimum;
3): dp[0][0] can be set as 0, which is legal for empty ring and empty key.

Code:

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int m=ring.size(), n=key.size();
        if(!m || !n) return 0;
        int res = m*n;
        vector<vector<int>> dp(n+1, vector<int>(m, res));
        dp[0][0] = 0;
        for(int i=1; i<=n; ++i){
            for(int j=0; j<m; ++j){
                if(ring[j]==key[i-1]){
                    for(int k=0; k<m; ++k){
                        int t1 = abs(k-j), t2 = m-t1;//two ways from k to j;
                        dp[i][j]=min(dp[i][j], dp[i-1][k] + min(t1, t2) + 1); //+1 for the "click" step;
                        if(i==n) res = min(res, dp[i][j]);
                    }
                }
            }
        }
        return res;
    }
};

[LeetCode] 533. Lonely Pixel II

https://leetcode.com/contest/leetcode-weekly-contest-22/problems/lonely-pixel-ii/

Solution:
First step need to scan the 2D matrix to figure out how many columns and rows having the N 'B'. And we can record the index into two vectors: one for the row collections; and the other for the column collection. Then for each column inside the column collection, we need to check the validity by going though the associated row to the 'B' element inside the column. If there's no same row existing in the previously row collection with N 'B', just go to the next column; if yes, we need to further check all the associated rows to the rest 'B' elements inside the same column. If all of them (associated rows) are the same, count +1; or, go to the next column. Finally, return count * N.

An alternative way is that when counting the columns, after knowing there's N 'B' elements, we can further make sure all the associated rows to the 'B' element inside the column are the same. If not, it is not necessary to keep it in the column collection. Then in the following step, we just need to make sure there's at least one row existing in the row collections matches the associated row to the 'B' element inside the column to be checked.

Code:

class Solution {
public:
    int findBlackPixel(vector<vector<char>>& picture, int N) {
        if(picture.empty() || picture.front().empty()) return 0;
        int res = 0;
        int m = picture.size(), n = picture.front().size();
        vector<int> v1, v2;
        for(int i=0; i<m; ++i){
            int t = 0;
            for(int j=0; j<n; ++j){
                if(picture[i][j] == 'B') ++t;
            }
            if(t==N) v1.push_back(i);
        }
        for(int j=0; j<n; ++j){
            int t = 0;
            for(int i=0; i<m; ++i){
                if(picture[i][j] == 'B') ++t;
            }
            if(t==N) v2.push_back(j);
        }
        for(int j=0; j<v2.size(); ++j){
            for(int i=0; i<m; ++i){
                if(picture[i][v2[j]] !='B') continue;
                if(picture[i][v2[j]]=='B'&&isV(picture, i, v1)){
                    vector<int> v3(1, i);
                    bool flag = true;
                    for(int k=0; k<m; ++k){
                        if(picture[k][v2[j]]=='B'&&!(isV(picture, k, v3))){
                            flag = false;
                            break;
                        }
                    }
                    if(flag) ++res;
                }
                break;
            }
        }
        return res*N;
    }
private:
bool isV(vector<vector<char>> &p, int x, vector<int> &v1){
        for(int i=0; i<v1.size(); ++i){
            bool flag = true;
            for(int j=0; j<p.front().size(); ++j){
                if(p[v1[i]][j] != p[x][j]){
                    flag = false;
                    break;
                }
            }
            if(flag) return true;
        }
        return false;
    }
};