[LeetCode]: 549. Binary Tree Longest Consecutive Sequence II

https://leetcode.com/contest/leetcode-weekly-contest-27/problems/binary-tree-longest-consecutive-sequence-ii/

Solution:
This is an interesting question. Similar to the one asking for the longest path for a binary tree, but this question add another constrain: the longest consecutive sequence. For each treenode, we need to check its left and right child. For the question asking for the longest path, we just need to return the larger one of longest paths from the left and right sub-trees, and the final result will be the maximum of (left + right + 1). But for this question, we need to return two values: one is the larger one of the two possible longest increasing paths from the left and right sub-trees, and the other is the larger one of the two possible longest decreasing paths from the left and right sub-trees. Since when move up to the next level (bottom-up direction), the longest consecutive sequence will be the maximum of (the larger one of the two possible longest increasing paths (could from the left sub-tree or the right sub-tree) + the larger one of the two possible longest decreasing paths (from the opposite side to the sub-tree in the first term)  + 1). See the code below:

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:
    int longestConsecutive(TreeNode* root) {
        int res = 0;
        find(root, res);
        return res;
    }
private:
    pair<int, int> find(TreeNode *r, int &res){
        if(!r) return make_pair(0, 0);
        pair<int, int> ra = find(r->left, res), rb = find(r->right, res);
        int a = 1, b = 1;
        if(r->left&&r->left->val+1==r->val) a = max(a, 1 + ra.first);
        if(r->right&&r->right->val+1==r->val) a = max(a, 1 + rb.first);
        if(r->left&&r->left->val-1==r->val) b = max(b, 1 + ra.second);
        if(r->right&&r->right->val-1==r->val) b = max(b, 1 + rb.second);
        res = max(res, a + b - 1);
        return make_pair(a, b);
    }
}; 

[LeetCode]: 327. Count of Range Sum

https://leetcode.com/problems/count-of-range-sum/#/description

Solution:
This is an interesting question. As stated in the introduction, the O(n2) method is not accepted. So we need to find a faster way. For this question, we are look for ranges that satisfy:
                          sum[i to j] = sum[0 to j] - sum[0 to i] >= lower; and
                          sum[i to j] = sum[0 to j] - sum[0 to i] <= upper
which can be further re-wrote as:
                         sum[0 to i] <= sum[0 to j] - lower; and
                         sum[0 to i] >= sum[0 to j] - upper.
Now it becomes clear that once we have sum[0 to i] where 0<=i<n (which can be obtained easily with O(n)), we can calculate the elements numbers by just looking the range of [sum[0 to j] - upper, sum[0 to j] - lower]. In order to avoid the re-counting, we can count the number of elements in the process of constructing the sorted array of sum[0 to i]. In this way, all the ranges found have at least one unique end. We also need to do the counting before inserting the element sum[0 to i] into the sorted array, to avoid the case that the sum[0 to i] locates just between [sum[0 to j] - upper, sum[0 to j] - lower]. (in this case, we will mistakenly count the elements by 1 more.)

Some details:
1):We also need to consider the sum[0 to i] itself, which can be elegantly solving by add a '0' element inside the sorted array in the beginning.
2): the long type can be used to avoid overflow problem.

The key point is by constructing a sorted array, the complexity can be reduced from O(n2) to O(nlnn). See code below:

Code:

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int res = 0;
        int n = nums.size();
        if(n==0) return res;
        vector<long> sums;
        sums.push_back(0);
        long sum = 0;
        for(int i=0; i<nums.size(); ++i){
            sum += nums[i];
            int left = findLeftPosition(sums, sum-upper);
            int right = findRightPosition(sums, sum-lower);
            res += right - left;
            int ind = findLeftPosition(sums, sum);
            sums.insert(sums.begin()+ind, sum);
        }
        return res;
    }
private:
    int findLeftPosition(vector<long> &s, long a){
        int left = 0, right = s.size();
        while(left < right){
            int m = left + (right - left)/2;
            if(s[m]<a) left = m+1;
            else right = m;
        }
        return left;
    }
    int findRightPosition(vector<long> &s, long a){
        int left = 0, right = s.size();
        while(left < right){
            int m = left + (right - left)/2;
            if(s[m]<=a) left = m + 1;
            else right = m;
        }
        return left;
    }
};

The code can be further simplified by using lower_bound() and upper_bound() functions. See below: Code:

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int res = 0, n = nums.size();
        vector<long> sums;
        sums.push_back(0);
        long sum = 0;
        for(int i=0; i<nums.size(); ++i){
            sum += nums[i];
            auto left = lower_bound(sums.begin(), sums.end(), sum-upper);
            auto right = upper_bound(sums.begin(), sums.end(), sum-lower);
            res += (int) (right - left);
            sums.insert(lower_bound(sums.begin(), sums.end(), sum), sum);
        }
        return res;
    }
}; 

[LeetCode]: 548. Split Array with Equal Sum

https://leetcode.com/contest/leetcode-weekly-contest-26/problems/split-array-with-equal-sum/

Solution:
This question is not very difficult, but the brute force loop cannot pass the OJ. So we need to find some way to use the intermediate information which means the one we have already calculated. Since we have already calculated it, there's no need to calculate it again. Instead, we can use the result from the previous calculation directly. That is exactly what is called memorization. DP is the one of the most common ways of memorization. The key point is: can the question be divided into sub-questions? If the answer is yes, then we can apply memorization.

For this question, for example, suppose we have already calculated that sum[i], meaning sum from 0 to i, is NOT the place where we can split the array with equal sum as required by the question, then in the latter processing, once we meet with the same value (sum[ii] == sum[i]), we can directly make a negative judge. (if sum[ii] == sum[i], which means the sum from i+1 to ii-1 is 0, so if the final result for sum[ii] is yes, then sum[i] should be yes too. But it is not, so sum[ii] must be no.) A hash map is enough to do memorization. See the code below:

Code:

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> sum;
        for(int i=0; i<n; ++i) i==0?sum.push_back(nums[i]):sum.push_back(nums[i] + sum[i-1]);
        unordered_map<int, bool> m;
        for(int i=0; i<n-1; ++i){
            if(m.find(sum[i]) == m.end()){
                for(int j=i+2; j<n-1; ++j){
                    if(sum[j]-sum[i+1]==sum[i]){
                        for(int k=j+2; k<n-2; ++k){
                            if(sum[k]-sum[j+1]==sum[i]&&sum[n-1]-sum[k+1]==sum[i]) return true;
                        }
                    }
                }
                m[sum[i]] = false;
            }
        }
        return false;
    }
};

[LeetCode]: 547. Friend Circles

https://leetcode.com/contest/leetcode-weekly-contest-26/problems/friend-circles/

Solution:
Will use bsf strategy: once find an element with value of 1, put it into a queue; then check all its "neighbors" that are friends with at least one of people in the "element" inside the queue. If the neighbor has a value of 1, indicating they are friends, put it into the queue. After checking all the neighbors, pop out the initial element. Then repeat the above process from the front of the queue until no element left. This is exactly why it is called "Breath Search First". Now we find one circle. We can move on to the rest un-visited elements in the matrix. A visiting matrix is used to label the visiting status of each elements, to make sure each element can only be visited once.

So, the routine procedure for bsf:
1: need a queue;
2: need a visiting matrix for labeling the visiting status.

For this question, we can use the symmetry of the matrix, to make the code a little bit simpler. See code below:

Code:

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int res = 0, n = M.size();
        vector<vector<bool>> v(n, vector<bool>(n, true));
        typedef pair<int, int> tp;
        queue<tp> q;
        for(int i=0; i<n; ++i){
            for(int j=i; j<n; ++j){
                if(M[i][j]==1&&v[i][j]){
                    q.push(tp(i, j));
                    v[i][j]=false;
                    while(q.size()){
                        tp t = q.front();
                        q.pop();
                        int x=t.first, y=t.second;
                        for(int k=0; k<n; ++k){
                            if(v[x][k]&&M[x][k]==1){
                                q.push(tp(x, k));
                                v[x][k]=false;
                            }
                            if(v[k][x]&&M[k][x]==1){
                                q.push(tp(k, x));
                                v[k][x]=false;
                            }
                            if(v[y][k]&&M[y][k]==1){
                                q.push(tp(y, k));
                                v[y][k]=false;
                            }
                            if(v[k][y]&&M[k][y]==1){
                                q.push(tp(k, y));
                                v[k][y]=false;
                            }
                        }
                    }
                    ++res;
                }
            }
        }
        return res;
    }
};  

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