前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode笔记:Biweekly Contest 49 比赛记录

LeetCode笔记:Biweekly Contest 49 比赛记录

作者头像
codename_cys
发布2021-04-12 17:16:16
2990
发布2021-04-12 17:16:16
举报
文章被收录于专栏:我的充电站
  • LeetCode笔记:Biweekly Contest 49
    • 0. 赛后总结
    • 1. 题目一
      • 1. 解题思路
      • 2. 代码实现
    • 2. 题目二
      • 1. 解题思路
      • 2. 代码实现
    • 3. 题目三
      • 1. 解题思路
      • 2. 代码实现
    • 4. 题目四
      • 1. 解题思路
      • 2. 代码实现
      • 3. 算法优化

0. 赛后总结

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

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

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

1. 题目一

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

1. 解题思路

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

2. 代码实现

给出python代码实现如下:

代码语言:javascript
复制
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代码实现如下:

代码语言:javascript
复制
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)的时间复杂度内完成统计。

2. 代码实现

给出python代码实现如下:

代码语言:javascript
复制
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代码实现如下:

代码语言:javascript
复制
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的部分可以直接去掉,这部分我们也做了,此外,他们还考察了余数互补的部分,即直接将 n−k进行了配对消耗,从而大幅缩减了整体需要考察的余量的比例。

给出其代码实现如下:

代码语言:javascript
复制
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,但是基本处于同一个量级了。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/04/08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 0. 赛后总结
  • 1. 题目一
    • 1. 解题思路
      • 2. 代码实现
      • 2. 题目二
        • 1. 解题思路
          • 2. 代码实现
          • 3. 题目三
            • 1. 解题思路
              • 2. 代码实现
              • 4. 题目四
                • 1. 解题思路
                  • 2. 代码实现
                    • 3. 算法优化
                    领券
                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档