LeetCode笔记：Weekly Contest 314

codename_cys

发布于 2022-10-25 18:26:16

2540

发布于 2022-10-25 18:26:16

文章被收录于专栏：我的充电站我的充电站

1. 题目一

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

2432. The Employee That Worked on the Longest Task

1. 解题思路

这一题就是首先计算出来每个任务的耗时，然后取出最大值即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
        t = [0 for _ in range(n)]
        st = 0
        for idx, ed in logs:
            t[idx] = max(t[idx], ed - st)
            st = ed
        
        _max = 0
        res = 0
        for i in range(n):
            if t[i] > _max:
                res = i
                _max = t[i]
        return res

提交代码评测得到：耗时744ms，占用内存14MB。

2. 题目二

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

2433. Find The Original Array of Prefix Xor

1. 解题思路

这一题其实就是利用性质：a xor a xor b = b，因此，我们对整个数组进行逆推即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        n = len(pref)
        for i in range(n-1):
            pref[n-1-i] = pref[n-1-i] ^ pref[n-2-i]
        return pref

提交代码评测得到：耗时1692ms，占用内存29.8MB。

3. 题目三

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

2434. Using a Robot to Print the Lexicographically Smallest String

1. 解题思路

这一题我的思路还是比较暴力的，显然，我们要让输出结果字典序最小，那么就得优先打印最小的字符，而没打印一个字符，其前序的所有字符的顺序就已经基本固定了。

因此，我们只需要遍历字母表，从小到大依次顺序打印出当前最后一个位置之后包含的字符即可。

唯一特殊一些的是，有一个特殊情况，即如果一个字符被打印之后到下一个字符被打印之前，如果刚好前序存在还未打印的小字符，那么需要优先打印那些。

综上，我们就可以最终获得我们的结果。

2. 代码实现

给出python代码实现如下：

class Solution:
    def robotWithString(self, s: str) -> str:
        n = len(s)
        used = [0 for _ in s]
        last = 0
        res = ""
        for ch in string.ascii_lowercase:
            while last-1 >= 0 and s[last-1] <= ch:
                if used[last-1] == 0:
                    res += s[last-1]
                    used[last-1] = 1
                last -= 1
            for i, c in enumerate(s):
                if i >= last and c == ch and used[i] == 0:
                    res += ch
                    last = i
                    used[i] = 1
        s = "".join([ch for i, ch in enumerate(s) if used[i] == 0])
        return res + s[::-1]

提交代码评测得到：耗时3017ms，占用内存16.9MB。

4. 题目四

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

2435. Paths in Matrix Whose Sum Is Divisible by K

1. 解题思路

这一题有点坑爹，思路上我看了一下别人的解法，基本其实大家都一样，就是一个简单的动态规划，不过我一开始用的是cache，然后居然超时了，然后换成了数组，就能够通过，至于吗这……

2. 代码实现

给出python代码实现如下：

class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        MOD = 10**9 + 7
        
        n, m = len(grid), len(grid[0])
        dp = [[[0 for _ in range(k)] for _ in range(m)] for _ in range(n)]
        dp[0][0][grid[0][0] % k] = 1
        for i in range(n):
            for j in range(m):
                for mod in range(k):
                    if i-1 >= 0:
                        dp[i][j][mod] = (dp[i][j][mod] + dp[i-1][j][(mod-grid[i][j]) % k]) % MOD
                    if j-1 >= 0:
                        dp[i][j][mod] = (dp[i][j][mod] + dp[i][j-1][(mod-grid[i][j]) % k]) % MOD
        return dp[n-1][m-1][0]

提交代码评测得到：耗时8647ms，占用内存94MB。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除

python