LeetCode Contest 54 | 叶某人的碎碎念

这次比赛之后，下次再遇到O(n²)的题目，而且n < 1000的时候，一定要用C++！这是泪的教训啊😭

第一题Degree of an Array

给定一个非空包含非负整数的数组nums，它的degree定义为出现次数最多的数字的出现次数。找出一个最短的连续子数组，使得它的degree与nums的degree一样。返回子数组的长度。

在统计每个数字频率的同时，记录这个数字出现的最左和最右位置(l, r)。那么包含这个数字的最短数组的长度为r-l+1。

class Solution(object):
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt = {}
        f = 0
        for i, n in enumerate(nums):
            if n not in cnt:
                cnt[n] = [1, i, i]
            else:
                c, a, _ = cnt[n]
                cnt[n] = [c+1, a, i]
            f = max(f, cnt[n][0])
        return min(v[2]-v[1]+1 for v in cnt.values() if v[0]==f)

第二题Count Binary Substrings

给定只包含01的字符串，问形如0...01...1或者1...10...0且0和1个数一样的非空子字符串的个数。

将字符串按照0和1按组分块，比如"001110011"分成

"00", "111", "00", "11"
那么连续的两块能贡献出它们最小长度那么多了符合规定的字符串。比如"00", "111"贡献了两个
"01", "0011"

class Solution(object):
    def countBinarySubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        cnt = map(len, re.split('(0+)', s))
        return sum(min(a, b) for a, b in zip(cnt[:-1], cnt[1:]))

第三题Partition to K Equal Sum Subsets

给定一个数组nums和k，问是否可以将nums分成k个和相等的子集。

一个经典的DP问题：给定一个长度为m数组，在O(ms)的时间内判断改数组是否有个子集之和为s。我们可以用dp[i]表示是否有子集之和为i，为了找到这个子集，可以用x = dp[i]表示状态i由状态x加上i-x得到。DP之后，我们可以根据dp的值在O(m)的时间内找到一个和为s的子集。

对于这个问题，我们可以使用上述DP找出和为s的一个子集，去除这个子集中的元素之后得到一个变短的nums。重复上述步骤，如果nums最后能变成空集，则返回True，否则返回False。

注意：这是一个贪心＋DP的算法，为了保证算法的正确性，要对nums从大到小排序。

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        s = sum(nums)
        if s % k != 0:
            return False
        s /= k
        if max(nums) > s:
            return False
        nums.sort(key=lambda x: -x)

        while nums:
            dp = [-1] * (s+1)
            dp[0] = 0
            for n in nums:
                for i in xrange(s, -1, -1):
                    if i + n <= s and dp[i] != -1 and dp[i+n] == -1:
                        dp[i+n] = i
                if dp[s] != -1:
                    break
            if dp[s] == -1:
                return False
            a = s
            while a != 0:
                nums.remove(a-dp[a])
                a = dp[a]
        return True

第四题Falling Squares

在一个无限长的数轴上，一些正方形从足够高垂直掉落。每个正方形将会给定坐下角的横坐标x和长度l。现在有n个正方形依次掉落，并按俄罗斯方块的规则叠起来。现在要求在所有正方形都掉落之后返回一个数组，数组的第i个数为第i个正方形掉落后所得整个图形的最大高度。

第一个想法是线段树，写完之后妥妥的MLE，因为要维护一个长度为10⁸的线段。后来发现正方形的个数最多是1000，所以O(n²)的算法也是可以接受的。但是用Python写还是TLE了，赛后用C++无压力AC了。。。

想法的关键是这样的，对于第i个正方形，扫描之前掉落并与其有重叠部分的正方形高度，以找到第i个正方形最终的高度。

class Solution {
public:
    vector<int> fallingSquares(vector<pair<int, int>>& positions) {
        int n = positions.size();
        vector<int> h(n, 0);
        vector<int> ans(n, 0);
        int c = 0;
        for (int i = 0; i < n; i ++) {
            int t = 0;
            for (int j = 0; j < i; j ++)
                if (overlap(i, j, positions))
                    t = max(t, h[j]);
            t += positions[i].second;
            c = max(c, t);
            ans[i] = c;
            h[i] = t;
        }
        return ans;
    }
private:
    bool overlap(int i, int j, vector<pair<int, int>>& p) {
    int a = p[i].first;
    int b = a+p[i].second;
    int x = p[j].first;
    int y = x + p[j].second;
    return !(a >= y || x >= b);
    }
};

leetcode contest