LeetCode Contest 45 | 叶某人的碎碎念

这次比赛也是卡在第三题上！😂
机智小伙伴是用状态机做的，非常厉害。

第一题Judge Route Circle

给定一个只含R（右），L（左），U（上）和D（下）的字符串表示移动方向，问是否能回到出发点。

简单的统计。

class Solution(object):
    def judgeCircle(self, moves):
        """
        :type moves: str
        :rtype: bool
        """
        cnt = collections.Counter(moves)
        return cnt['L']==cnt['R'] and cnt['D']==cnt['U']

第二题Find K Closest Elements

给定k和x，在数组中找出跟x距离最短的k个数。

对数组按第一关键字距离，第二关键字本身来排序。排序后的前k个数就是我们想要的了。

class Solution(object):
    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """
        arr.sort(key=lambda n: (abs(n-x), n))
        return sorted(arr[:k])

第三题Split Array into Consecutive Subsequences

给定一个已经排好序的数组（可能包含重复数字），问是否能将数组分成若干份，使得每份都是长度不小于3的连续数字。

我自己的算法比赛的时候没有写出来，因为在写递归程序的时候没有设置边界条件，所以出现了递归层数太多的错误。下面的算法来自于机智的小伙伴。

假设nums的数字都是连续的，令uni为nums不重复出现数字的数组，cnt是相对应的每个数字在nums出现的次数。那么对于每个数字n，我们维护状态

need[0], need[1], need[2]
其中need[0]表示以n结尾长度不小于3的连续数组个数，need[1]表示放了n之后还需要1个数才能构成长度为3的连续数组的个数。类似的，need[2]表示放了n之后还需要2个数才能构成长度为3的连续数组的个数。

对于每个新的n，我们必须首先保证可以need[1]和need[2]的数组得到延续，否则返回False。也就是说cnt[n]必须不小于need[1]+need[2]。如果满足此条件，那么我们将cnt[n]的值减少need[1]+need[2]。

接下来，need[0]至少要更新为need[1]。考虑到经过上一步之后cnt[n]的值可能非零，那么以前以n－1结束的数组也可以相应延长到以n结束。所以

need[0] = min(need[0], cnt[n])+need[1]

need[1]只能来自于need[2]，所以need[1] = need[2]。

对于need[2]，似乎要更新为0，但是可能出现的情况是cnt[n]的数目大于原来need[0]的数目，所以延长了以前的数组之后可能还有剩下的n，所以我们可能要以n开始寻找下两个数。因此，

need[2] = max(0, cnt[n]-need[0])

当所有数遍历之后，need[1]+need[2]需要为0我们才能分解这个数组。

我程序的cnt跟上述的cnt稍微有点差别。第一部分是统计uni和cnt。第二部分找出uni中所有连续的块并放在stack中。第三部分是对每个连续块进行处理。

class Solution(object):
    def isPossible(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        uni = []
        cnt = []
        for n in nums:
            if len(uni) > 0 and uni[-1]==n:
                cnt[-1] += 1
            else:
                uni.append(n)
                cnt.append(1)

        stack = []
        i = 0
        while i < len(uni):
            j = i+1
            while j < len(uni) and uni[j]-1==uni[j-1]:
                j += 1
            if j-i<3:
                return False
            stack.append((i, j))
            i = j

        for i, j in stack:
            need = [0] * 3
            for k in range(i, j):
                if cnt[k] < need[1]+need[2]:
                    return False
                cnt[k] -= (need[1]+need[2])
                need = min(cnt[k], need[0])+need[1], need[2], max(0, cnt[k]-need[0])
            if need[1]+need[2]>0:
                return False
        return True

第四题Remove 9

将从1开始的所有整数中含9的整数全部去掉后的第n个数是什么？

如果将9都去掉了，剩下的数字是有0，1，...，8组成的。所以剩下的数可以看作9进制的数。现在给定n，我们只要找出9进制中第n个数是什么就行。也就是将输入的n转成9进制输出就行。

class Solution(object):
    def newInteger(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans, p = 0, 1
        while n > 0:
            ans += (n % 9) * p
            n /= 9
            p *= 10
        return ans

leetcode contest