LeetCode笔记:Weekly Contest 229 比赛记录

时间:2021-2-27 作者:admin

0. 赛后总结

这周的比赛整体都给跪了,两场比赛都是不顺的要死,昨天的比赛还能归结到看错题目,这次的比赛就真的是没得洗了,第三题超时之后就没有更好的思路了,第四题压根没有一个可行的思路,想到的解法实现出来之后发现都有系统性的bug,简直了……

果然傲慢是原罪啊,明明自己还这么弱,还和人吹牛逼,flag一立,打脸立来,唉……

1. 题目一

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

1. 解题思路

这一题倒是没啥难度,直接按照题目意思交替组成新的字符串即可。

2. 代码实现

给出python代码实现如下:

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        n, m = len(word1), len(word2)
        i, j = 0, 0
        res = ""
        while i<n and j<m:
            res += word1[i] + word2[j]
            i += 1
            j += 1
        if i < n:
            res += word1[i:]
        if j < m:
            res += word2[j:]
        return res

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

当前最有代码实现耗时28ms,但是看了一下实现思路是完全相同的,就不过多展开了。

2. 题目二

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

1. 解题思路

这一题比赛的时候用暴力算法直接强行解掉了,不过代码实在是不够优雅,赛后重新看了一下,其实可以将算法复杂度退化至

O

(

N

)

O(N)

O(N)

首先,我们先算一下全部移动到第一个位置时的代价。

然后,我们假设已知全部移动到第

i

i

i个位置时的答案为

s

i

s_i

si,考察全部移动到第

i

+

1

i+1

i+1时的所需的代价数显然有:

s

i

+

1

=

s

i

+

c

i

(

t

o

t

c

i

)

s_{i+1} = s_{i} + c_{i} – (tot – c_{i})

si+1=si+ci(totci)

其中,

c

i

c_i

ci为到第

i

i

i个位置为止所包含的小球的数目,

t

o

t

tot

tot则是总的小球数目。

由此,通过数学归纳法的思路,我们就可以在

O

(

N

)

O(N)

O(N)的算法复杂度情况下获取所有位置上的解。

2. 代码实现

给出python代码实现如下:

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        boxes = [int(x) for x in boxes]
        n = len(boxes)
        cumsum = list(accumulate(boxes))
        res = [0 for _ in range(n)]
        s = 0
        for i in range(n):
            s += i*boxes[i]
        res[0] = s
        for i in range(1, n):
            s += cumsum[i-1] - (cumsum[-1] - cumsum[i-1])
            res[i] = s
        return res

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

为当前最优代码实现。

3. 题目三

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

1. 解题思路

这一题比赛的时候因为超时一直没能搞定,赛后看了一下别人的解法,然后就崩碎了我的三观,因为他的算法实现和我一模一样,就是比我多了一行代码,一行清理缓存的代码,然后就避免了超时的问题……

呵呵,这题真傻逼……

没啥复杂的,暴力求解的话就是动态规划,后面看看有没有什么更好的解题思路吧……

2. 代码实现

给出python代码实现如下:

class Solution:
    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        n, m = len(nums), len(multipliers)
        
        @lru_cache(None)
        def dp(i, j, k):
            if k == m:
                return 0
            return max(nums[i]*multipliers[k] + dp(i+1, j, k+1), nums[j]*multipliers[k] + dp(i, j-1, k+1))
        
        res = dp(0, n-1, 0)
        dp.cache_clear()
        return res

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

当前最优的代码实现耗时3336ms,并没有量级上的差异,但是有将近3倍的效率提升,因此,有兴趣的读者后续可以自行研究一下他们的思路。

4. 题目四

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

1. 解题思路

这一题在比赛的时候完全没有一个好的思路,直接的思路是先进行拼接之后对比正反两个字符串,考察公共子串相关的内容再进行考察,但是就是遇到了界限问题……

比赛结束之后失落了好久,然后今天看了一下答案之后发现就是一个动态规划问题而已,和上一题基本是异曲同工,只要用两个滑动指针分别从两侧向中心靠近即可。

2. 代码实现

给出python代码实现如下:

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        n, m = len(word1), len(word2)
        
        @lru_cache(None)
        def dp(i, j, s1, s2):
            if i >= n and not s1:
                return -10000
            if j < n and not s2:
                return -10000
            if i == j:
                return 1
            if i > j:
                return 0
            
            if s[i] == s[j]:
                return 2 + dp(i+1, j-1, True, True)
            else:
                return max(dp(i, j-1, s1, s2), dp(i+1, j, s1, s2))
            
        res = dp(0, n+m-1, False, False)
        dp.cache_clear()
        return max(res, 0)

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

当前最优的代码实现耗时2536ms,用兴趣的读者可以自行研读一下,这里暂时我就不多做展开了……

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。