自己建设网站在哪里建设,qq星是哪个公司的产品,免费做简单网站,公司网站建设建议LeetCode笔记#xff1a;Weekly Contest 357 1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 比赛链接#xff1a;https://leetcode.com/contest/weekly-contest-357
1. 题目一
给出题目一的试题链接如下…LeetCode笔记Weekly Contest 357 1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 比赛链接https://leetcode.com/contest/weekly-contest-357
1. 题目一
给出题目一的试题链接如下
2810. Faulty Keyboard
1. 解题思路
这一题就是按照题目给出的条件重新转义一下字符串即可倒是不用怎么多说。
2. 代码实现
给出python代码实现如下
class Solution:def finalString(self, s: str) - str:out for ch in s:if ch i:out out[::-1]else:out out chreturn out提交代码评测得到耗时50ms占用内存16.3MB。
2. 题目二
给出题目二的试题链接如下
2811. Check if it is Possible to Split Array
1. 解题思路
这一题其实就是个脑筋急转弯不难想到事实上只要存在两个相邻的数加和大于目标值然后总是存在一种切分方法对数组进行切分。
反之也不难思考如果所有相邻元素的加和均小于目标值那么一定无法将目标数组切分为单一元素的子序列只要考虑一下连续三个元素的切分即可。
因此答案事实上就变成一行代码的事了。
2. 代码实现
给出python代码实现如下
class Solution:def canSplitArray(self, nums: List[int], m: int) - bool:n len(nums)return n 2 or any(nums[i] nums[i1] m for i in range(n-1))提交代码评测得到耗时55ms占用内存16.2MB。
3. 题目三
给出题目三的试题链接如下
2812. Find the Safest Path in a Grid
1. 解题思路
这一题我的实现上多少有一些复杂不过思路上倒是非常清晰的就是分两步。
第一步求出每一个位置上的safeness factor这个用一个bfs即可完成。
第二步就是求一条连通路径使得从起点到终点的safeness factor最大。这个用一个dsu即可实现我们只需要按照safeness factor对所有的格子进行倒序排序然后不断地将其进行聚类直到起点和终点被连通为止此时的safeness factor就是可以获得的最大的safeness factor。
2. 代码实现
给出python代码实现如下
class DSU:def __init__(self, n):self.root {(i,j): (i,j) for i in range(n) for j in range(n)}def find(self, p):if self.root[p] ! p:self.root[p] self.find(self.root[p])return self.root[p]def union(self, a, b):x self.find(a)y self.find(b)self.root[y] xreturnclass Solution:def maximumSafenessFactor(self, grid: List[List[int]]) - int:n len(grid)factors [[0 for _ in range(n)] for _ in range(n)]q [[i, j, 0] for i in range(n) for j in range(n) if grid[i][j] 1]seen {(i, j) for i, j, _ in q}while q:i, j, d q.pop(0)if i-1 0 and (i-1, j) not in seen:factors[i-1][j] d1q.append((i-1, j, d1))seen.add((i-1, j))if i1 n and (i1, j) not in seen:factors[i1][j] d1q.append((i1, j, d1))seen.add((i1, j))if j-1 0 and (i, j-1) not in seen:factors[i][j-1] d1q.append((i, j-1, d1))seen.add((i, j-1))if j1 n and (i, j1) not in seen:factors[i][j1] d1q.append((i, j1, d1))seen.add((i, j1))dsu DSU(n)s sorted([(i, j) for i in range(n) for j in range(n)], keylambda x: factors[x[0]][x[1]], reverseTrue)for i, j in s:if i-1 0 and factors[i-1][j] factors[i][j]:dsu.union((i-1, j), (i, j))if i1 n and factors[i1][j] factors[i][j]:dsu.union((i1, j), (i, j))if j-1 0 and factors[i][j-1] factors[i][j]:dsu.union((i, j-1), (i, j))if j1 n and factors[i][j1] factors[i][j]:dsu.union((i, j1), (i, j))if dsu.find((0, 0)) dsu.find((n-1, n-1)):return factors[i][j]return 0提交代码评测得到耗时5276ms占用内存90.3MB。
4. 题目四
给出题目四的试题链接如下
2813. Maximum Elegance of a K-Length Subsequence
这一题说来惭愧实在是没啥思路看了其他大佬们的一些解答也没怎么看明白所以这里就不班门弄斧了后面有时间我再想想吧这里就先放弃了……
