Weekly Contest 314

Problem A

The Employee That Worked on the Longest Task

思路

按照题目要求遍历一下就行

代码

class Solution:
    def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
        L = logs[0][1]
        ans = logs[0][0]
        for i in range(1,len(logs)):
            d = logs[i][1]-logs[i-1][1]
            # print(d)
            temp = logs[i][0]
            # print(d,temp,L)
            if d>L or (d==L and temp<ans):
                ans = temp
                L = d
        return ans

Problem B

Find The Original Array of Prefix Xor

思路

数学小规律 A^B = c A^C =B。按位推算可验证(1^0 = 1 1^1 = 0 0^0 =0)

代码

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

Problem C

Using a Robot to Print the Lexicographically Smallest String

思路

待补

代码

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]

Problem D

Paths in Matrix Whose Sum Is Divisible by K

思路

待补

代码

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

总结

出了两题，后面不太想做了，有空补补思路。