LeetCode笔记:Biweekly Contest 49 比赛记录

0. 赛后总结

表示人果然来是老了,中午和同学聚餐,跑去吃日料自助,兴致所至畅饮3大杯梅酒,然后直接就给跪了,当时没啥反应,吃完回来之后发现头晕脑涨,一觉睡到晚上快8点,回去之后还是晕乎乎的,饭都不怎么吃得下,硬塞了一碗泡面之后躺在床上瞬间就觉得天旋地转,最终还是放弃了做比赛,估计周日的比赛也是呵呵了……

得亏是清明假期的第一天,要是第二天或者第三天搞这么一出我估计上班就挂了……

老年人了,还是得好好养生啊!

1. 题目一

给出题目一的试题链接如下:

1. 解题思路

这一题没啥好说的,就是根据行列关系给出格点是否为白色格点的判断即可。

2. 代码实现

给出python代码实现如下:

class Solution:
    def squareIsWhite(self, coordinates: str) -> bool:
        col, row = coordinates[0], coordinates[1]
        return (row in "1357" and col in "bdfh") or (row in "2468" and col in "aceg")

提交代码评测得到:耗时28ms,占用内存14.2MB。

2. 题目二

给出题目二的试题链接如下:

1. 解题思路

这一题思路其实也挺直接的,不妨设句子A长于句子B,则两者相似的充要条件为B可以通过插入一个小句来构成A。

换言之,只要不断删除头尾部分AB两个句子完全相同的部分,就可以将B完全删除。

2. 代码实现

给出python代码实现如下:

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        s1 = sentence1.strip().split()
        s2 = sentence2.strip().split()
        
        while s1 != [] and s2 != [] and s1[0] == s2[0]:
            s1.pop(0)
            s2.pop(0)
            
        while s1 != [] and s2 != [] and s1[-1] == s2[-1]:
            s1.pop()
            s2.pop()
        
        return s1 == [] or s2 == []

提交代码评测得到:耗时28ms,占用内存14.4MB。

当前最优的代码实现耗时24ms,其算法思路与我们是相似的,就不过多展开了。

3. 题目三

给出题目三的试题链接如下:

1. 解题思路

nice pair的定义为:

  • nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

变换公式可以得到:

  • nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])

因此,我们只需要记录下nums[i] - rev(nums[i])的值,即可在 O ( N ) O(N) O(N)的时间复杂度内完成统计。

2. 代码实现

给出python代码实现如下:

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        
        def rev(n):
            res = 0
            while n != 0:
                res = res * 10 + n % 10
                n = n // 10
            return res
        
        counter = defaultdict(int)
        for n in nums:
            counter[n - rev(n)] += 1
            
        res = 0
        for n in counter.values():
            res += n*(n-1)//2
        return res % MOD

提交代码评测得到:耗时680ms,占用内存24.6MB。

4. 题目四

给出题目四的试题链接如下:

1. 解题思路

这一题最后还是采用暴力的方式解决的。

就是考察所有的取用情况,然后将最优解进行输出,我们采用cache进行状态记录之后,整体的解法还是比较直接的。

2. 代码实现

直接给出python代码实现如下:

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        cnt = [0 for _ in range(batchSize)]
        for g in groups:
            cnt[g % batchSize] += 1
            
        @lru_cache(None)
        def dp(status, remain):
            if all(x == 0 for x in status[1:]):
                return 0
            nxt = list(status)
            res = 0
            for i in range(1, batchSize):
                if status[i] == 0:
                    continue
                nxt[i] -= 1
                res = max(res, dp(tuple(nxt), (remain+i)%batchSize))
                nxt[i] += 1
            return res if remain != 0 else res + 1
        
        return cnt[0] + dp(tuple(cnt), 0)

提交代码评测得到:耗时1200ms,占用内存48.4MB。

但是当前最优的算法耗时仅24ms,是我们效率的50倍,这就很悲伤了……

3. 算法优化

细看了一下他的代码,发现他们的核心思路和我们是一样的,不过他们在我们的代码基础上做了剪枝,首先,当然余数为0的部分可以直接去掉,这部分我们也做了,此外,他们还考察了余数互补的部分,即直接将 k k k与 n − k n-k n−k进行了配对消耗,从而大幅缩减了整体需要考察的余量的比例。

给出其代码实现如下:

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        cnt = [0 for _ in range(batchSize)]
        for g in groups:
            cnt[g % batchSize] += 1
            
        ans = cnt[0]
        cnt[0] = 0
        for i in range(1, batchSize // 2):
            pair = min(cnt[i], cnt[batchSize-i])
            ans += pair
            cnt[i] -= pair
            cnt[batchSize-i] -= pair
        if batchSize % 2 == 0:
            pair = cnt[batchSize//2] // 2
            ans += pair
            cnt[batchSize//2] -= 2*pair
            
        @lru_cache(None)
        def dp(status, remain):
            if all(x == 0 for x in status):
                return 0
            nxt = list(status)
            res = 0
            for i in range(1, batchSize):
                if status[i] == 0:
                    continue
                nxt[i] -= 1
                res = max(res, dp(tuple(nxt), (remain+i)%batchSize))
                nxt[i] += 1
            return res if remain != 0 else res + 1
        
        return ans + dp(tuple(cnt), 0)

提交代码评测得到:耗时64ms,占用内存15.3MB。

虽然没有达到最优的24ms,但是基本处于同一个量级了。

上一篇:LeetCode笔记:Biweekly Contest 55(补发)


下一篇:线性表(1)——栈的初步认识