LeetCode Contest #54

2017-10-31 PKU GoodSpeed 北美加群小助手Jogchat 北美加群小助手Jogchat

本学渣今天起晚了,所以没有选择参加(因为会掉分,归根结底还是实力不够硬)。

题看了一遍,不是很难,第三题有点麻烦。

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个数相等

求这种 subtring 的总数。

题解:思路很简单,先把 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;

    }

};

最后推荐一个竞赛网站,http://atcoder.jp 日本的一个平台,每周六早晨都有比赛,大家有兴趣可以参加。题难度主要分 beginner, regular 跟 grand 三个级别(本学渣现在在 regular 级别被各种秒)。题质量很高,解题思路很新颖,而且算法之神 tourist也经常常参加。


长按扫码关注



阅读 5733

微信扫一扫
关注该公众号