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