LeetCode Contest #54

697. Degree of an Array

题目： 给定一个数组，定义这个数组的degree是数组中某一个数字出现次数的最大值。

degree of arr := max_i arr.count(arr[i])

求最短的一个continuous subarray，使得这个subarray的degree跟原数组相同。返回这个subarray的长度。

题解： 思路很简单，先把出现次数最多的数挑出来，然后看这些数在原数组中的“跨度”。

class Solution {
    map<int, int> cnt, left, right;
    /* left, right is used to record the*/
    /* left most position and right most position*/
    /* of a particular element.*/
public:
    int findShortestSubArray(vector<int>& nums) {
        for(int i=0;i<nums.size();++i){
            cnt[nums[i]]++;
            right[nums[i]] = i;
            if(!left.count(nums[i])) left[nums[i]] = i;
        }
        int ans = nums.size(), max_cnt = 0;
        for(auto p:cnt){
            if(p.second == max_cnt)
                ans = min(ans, right[p.first] - left[p.first] + 1);
            else if(p.second > max_cnt){
                max_cnt = p.second;
                ans = right[p.first] - left[p.first] + 1;
            }
        }
        return ans;
    }
};

696. Count Binary Substrings

题目： 给定一个指包括0和1的string，让你从中挑出满足以下条件的substring：

0跟1的个数相同
0都group together，1也都group together

也就是这种形式的substring：11…100…0或00…011…1，且其中1，0个数相等。

求这种substring的总数。

题解： 思路很简单，先把groups of continuous 1和0全提出来，然后这样的substring肯定出现在相邻的groups里面，个数就是min(#group1, #group0)。比如111跟0000相临，那满足条件的substring只可能是10, 1100, 111000，它们的个数就是1的个数，因为1比0少。

class Solution {
    inline char flip(char c){return c=='1'? '0':'1';}
    /* input '1' return '0', input '0' return '1';*/
public:
    int countBinarySubstrings(string s) {
        int ans = 0;
        for(auto i=s.find(s[0]); i<s.size() && i!=string::npos ;){
            auto j = s.find(flip(s[i]),i);
            if(j == string::npos) return ans;
            auto k = s.find(s[i], j);
            if(k == string::npos) k = s.size();
            ans += min(int(j-i), int(k-j));
            i = j;
        }
        return ans;
    }
};

698. Partition to K Equal Sum Subsets

题目： 给定一个数组，数组长度不超过16（也就是说规模很小），然后让你判断是否可以把这个数组分成k个groups，使得每个group的和相等。

题解： 其实是暴力，（反正我是这么做的，如果有人有更好的方法，非常欢迎提出来。）因为规模不大。

首先如果这个数组的sum不能被k整除，就不用考虑了。
如果可以整除，我的做法是分两步：
- 先求所有的group使得每个group的和是sum／k，用dfs
- 每一个group用一个二进制数表示，这样后面的操作容易些。
- 看这些groups能不能挑出k两个不相交的，还是用dfs
两个dfs都没超时，也是挺不容易的。
上面做法，有个地方要注意一下：判断两个group是否相交的时候，如果用(group1 & group2) == 0括号不能省啊。开始就是由于这个原因，我debug的时候半天不知道错在哪儿，后来索性改成!(group1 & group2)。

class Solution {
    vector<int> A, G;
    void dfs1(int cur, int i, int target){
        if(target == 0){
            G.push_back(cur);
            return;
        }
        for(int j=i;j<A.size();++j) if(target>=A[j]){
            dfs1(cur|(1<<j), j+1, target-A[j]);
        }
    }
    bool dfs2(int cur, int rest){
        if(!rest) return true;
        for(auto s:G) if(!(s&cur) && dfs2(cur|s, rest-1)) return true;
        return false;
    }
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        A.assign(nums.begin(),nums.end());
        int sum = 0;
        for(auto n:nums) sum+=n;
        if(!sum || k<=1) return true;
        if( sum%k ) return false;
        dfs1(0, 0, sum/k);
        return dfs2(0, k-1);
    }
};

699. Falling Squares

题目： 其实就是模拟俄罗斯方块，而且每个方块都是正方形。一系列方块由一个pair的数组给出，且对于每一个pair，第一个元素是正方形left edge的位置，第二个元素是边长。方块依次落下，要求输出一个数组，每个元素对应每一个方块落下之后的最大高度。

题解： 用一个map(sorted)来标记现有每个线段的高度：map<int, int> H，这样H[pos]表示pos右边的高度。知道碰到下一个比pos大，而且也在H中的元素，也就是高度改变的点。初始的时候令H[0] = H[2E8] = 0，其实是方便以后操作；然后每次加入一个方块后，更新这个H即可，不难写：

class Solution {
    map<int, int> H;
    int upd(const pair<int, int> &S){
        /*return the final height of the current falling square*/
        int l = S.first, h = S.second, r = S.first + S.second;
        auto it1 = --H.upper_bound(l), it2 = --H.upper_bound(r);
        int max_H = h + it1->second, tail_H = it2->second;
        ++it1;
        while(it1!=H.end() && it1->first < r){
            max_H = max(max_H, h + it1->second);
            it1 = H.erase(it1);
        }
        H[r] = tail_H;
        return H[l] = max_H;
    }
public:
    vector<int> fallingSquares(vector<pair<int, int>>& positions) {
        vector<int> ans;
        H[0] = H[2E8] = 0;
        int cur = 0;
        for(auto S:positions) ans.push_back(cur = max(cur, upd(S)));
        return ans;
    }
};