LeetCode第109场周赛题解

933. 最近的请求次数

题目难度Easy

写一个 RecentCounter 类来计算最近的请求。

它只有一个方法：ping(int t)，其中 t 代表以毫秒为单位的某个时间。

返回从 3000 毫秒前到现在的 ping 数。

任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内，包括当前（指 t 时刻）的 ping。

保证每次对 ping 的调用都使用比之前更大的 t 值。

示例：

输入：inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
输出：[null,1,2,3,3]

提示：

每个测试用例最多调用 10000 次 ping。
每个测试用例会使用严格递增的 t 值来调用 ping。
每次调用 ping 都有 1 <= t <= 10^9。

思路：

用一个变量self.length记录满足条件的ping数，用一个列表（队列）self.pings记录符合条件的ping，每次调用ping函数，把不符合条件的ping记录从左侧出队。

时间复杂度 $O(N)$

空间复杂度 $O(N)$

代码：

class RecentCounter:

    def __init__(self):
        self.length = 0
        self.pings = []

    def ping(self, t: int) -> int:
        self.pings.append(t)
        self.length += 1
        while self.pings[0] < t - 3000:
            self.pings.pop(0)
            self.length -= 1
        return self.length
        
        
# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)

935. 骑士拨号器

题目难度Medium

国际象棋中的骑士可以按下图所示进行移动：

骑士的移动规则

电话拨号盘

这一次，我们将 “骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳 N-1 步。每一步必须是从一个数字键跳到另一个数字键。

每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下 N 位数字。

你能用这种方式拨出多少个不同的号码？

因为答案可能很大，所以输出答案模 10^9 + 7。

示例 1：

输入：1
输出：10

示例 2：

输入：2
输出：20

示例 3：

输入：3
输出：46

提示：

1 <= N <= 5000

思路：

递推算法，用dp[i][j]表示i-1位以j为结尾的电话号有多少种，初始值dp[0][j]均为1，那么根据棋盘上骑士的跳跃规则，可以得出每个号码的递推规则，具体见代码。

时间复杂度 $O(N)$

空间复杂度 $O(N)$ 由于当前状态只与上一个状态有关，所以也有 $O(1)$ 的实现方法

代码：

class Solution:
    def knightDialer(self, N: int) -> int:
        dp = [[1 for _ in range(10)] for _ in range(N)]
        for i in range(1, N):
            dp[i][0] = dp[i - 1][4] + dp[i - 1][6]
            dp[i][1] = dp[i - 1][6] + dp[i - 1][8]
            dp[i][2] = dp[i - 1][7] + dp[i - 1][9]
            dp[i][3] = dp[i - 1][4] + dp[i - 1][8]
            dp[i][4] = dp[i - 1][0] + dp[i - 1][3] + dp[i - 1][9]
            dp[i][5] = 0
            dp[i][6] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][7]
            dp[i][7] = dp[i - 1][2] + dp[i - 1][6]
            dp[i][8] = dp[i - 1][1] + dp[i - 1][3]
            dp[i][9] = dp[i - 1][2] + dp[i - 1][4]
            for j in range(10):
                dp[i][j] %= 1000000007
        return sum(dp[N - 1]) % 1000000007

934. 最短的桥

题目难度Medium

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）

示例 1：

输入：[[0,1],[1,0]]
输出：1

示例 2：

输入：[[0,1,0],[0,0,0],[0,0,1]]
输出：2

示例 3：

输入：[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1

提示：

1 <= A.length = A[0].length <= 100
A[i][j] == 0 或 A[i][j] == 1

思路：

先遍历找到第一个岛屿的一个点，然后用DFS把所有属于第一个岛屿的点入队，然后对队列里的所有点一起进行BFS，最先到达第二个岛屿的搜索层数就是答案。

时间复杂度 $O(N^2)$

空间复杂度 $O(N^2)$

代码：

解法1

class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:
        self.length = len(A)
        self.directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        self.island1 = []
        self.visited = [[False for _ in range(self.length)] for _ in range(self.length)]
        
        def dfs(i, j):
            A[i][j] = 0
            self.visited[i][j] = True
            self.island1.append((i, j))
            for d in range(4):
                y = i + self.directions[d][0]
                x = j + self.directions[d][1]
                if 0 <= x < self.length and 0 <= y < self.length and A[y][x] == 1:
                    dfs(y, x)
                    
        for i in range(self.length * self.length):
            x = i % self.length
            y = i // self.length
            if A[y][x] == 1:
                dfs(y, x)
                break
        
        ans = 0
        
        q = self.island1
        while q:
            ans += 1
            t = []
            while q:
                i, j = q.pop(0)
                for d in range(4):
                    y = i + self.directions[d][0]
                    x = j + self.directions[d][1]
                    if 0 <= x < self.length and 0 <= y < self.length and not self.visited[y][x]:
                        if A[y][x] == 1:
                            return ans - 1
                        t.append((y, x))
                        self.visited[y][x] = True
            q = t

        return ans - 1

解法2

import collections


class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:

        m = len(A)
        visit = set()
        queue = collections.deque()
        newq = collections.deque()

        for k in range(m * m):
            i, j = k // m, k % m
            if A[i][j] == 1:
                visit.add((i, j))
                queue.append((i, j))
                break

        while queue:
            i, j = queue.popleft()
            for x, y in [(i, j + 1), (1 + i, j), (i - 1, j), (i, j - 1)]:
                if 0 <= x < m and 0 <= y < m and (x, y) not in visit:
                    if A[x][y] == 1:
                        visit.add((x, y))
                        queue.append((x, y))
                    elif A[x][y] == 0:
                        newq.append((x, y, 1))

        while newq:
            i, j, step = newq.popleft()
            for x, y in [(i, j + 1), (1 + i, j), (i - 1, j), (i, j - 1)]:
                if 0 <= x < m and 0 <= y < m and (x, y) not in visit:
                    if A[x][y] == 0:
                        visit.add((x, y))
                        newq.append((x, y, step + 1))
                    elif A[x][y] == 1:
                        return step

936. 戳印序列

题目难度Hard

你想要用小写字母组成一个目标字符串 target。

开始的时候，序列由 target.length 个 '?' 记号组成。而你有一个小写字母印章 stamp。

在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行 10 * target.length 个回合。

举个例子，如果初始序列为 "?????"，而你的印章 stamp 是 "abc"，那么在第一回合，你可以得到 "abc??"、"?abc?"、"??abc"。（请注意，印章必须完全包含在序列的边界内才能盖下去。）

如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。

例如，如果序列是 "ababc"，印章是 "abc"，那么我们就可以返回与操作 "?????" -> "abc??" -> "ababc" 相对应的答案 [0, 2]；

另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成。任何超过此数字的答案将不被接受。

示例 1：

输入：stamp = "abc", target = "ababc"
输出：[0,2]
（[1,0,2] 以及其他一些可能的结果也将作为答案被接受）

示例 2：

输入：stamp = "abca", target = "aabcaca"
输出：[3,0,1]

提示：

1 <= stamp.length <= target.length <= 1000
stamp 和 target 只包含小写字母。

思路：

贪心法：逆向思维，我们可以求把target变成???……??的过程，再把这个过程反过来即可得到答案。从大到小枚举stamp的子串，并将子串左右部分用?补全。把所有子串按顺序存储在一个列表里，每次检测target里面是否含有这些子串，如果有，就将这些子串的位置都替换为?，如此往复，如果最终能够将target都变为?，那么说明有解，并把变换的步骤反过来输出。

时间复杂度 $O(N^2)$

空间复杂度 $O(N^2)$

代码：

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        sub_stamp = [stamp]
        l = len(stamp)
        for i in range(l - 1, 0, -1):
            for j in range(l - i + 1):
                s = '?' * j + stamp[j:j + i] + '?' * (l - j - i)
                sub_stamp.append(s)
        # print(sub_stamp)
        
        ans = []
        
        while True:
            index = -1
            for s in sub_stamp:
                index = target.find(s)
                if index != -1:
                    target = target[:index] + '?' * l + target[index + l:]
                    ans.append(index)
                    # print(ans, target)
                    break
            if index == -1:
                break
        
        return ans[::-1] if all(i == '?' for i in target) else []