[LeetCode周赛复盘] 第 305 场周赛20220807

一、本周周赛总结

• T3写dfs一百多行做大牢，最后十分钟改dp过的。
• 看来我分数稳定了，掉大分。
  

二、 [Easy] 6136. 算术三元组的数目

链接: 6136. 算术三元组的数目

1. 题目描述

2. 思路分析

定级Easy。
由于数字不重复（严格递增），因此可以利用哈希表达到线性复杂度。

• 先把数字映射到下标。
• 然后枚举每个数字作为i，计算j、k，检查jk是否在数组里且满足下表大小。

3. 代码实现

class Solution:
    def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
        n = len(nums)
        t = {v:i for i,v in enumerate(nums)}
            
        ans = 0
        for i,v in enumerate(nums):
            a,b = v +diff,v+2*diff
            if a in t and b in t and i<t[a]<t[b]:
                ans += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11

三、[Medium] 6139. 受限条件下可到达节点的数目

链接: 6139. 受限条件下可到达节点的数目

1. 题目描述

2. 思路分析

定级Medium。
比较裸，建图的时候去掉受限节点，然后从0开始，floodfill。
最后返回搜索到的节点个数。

3. 代码实现

class Solution:
    def reachableNodes(self, n: int, es: List[List[int]], restricted: List[int]) -> int:
        r = set(restricted)
        g = defaultdict(list)
        for u,v in es:
            if u not in r and v not in r:
                g[u].append(v)
                g[v].append(u)
        
        vis = set()
        
        def dfs(u):
            vis.add(u)
            for v in g[u]:
                if v not in vis:
                    dfs(v)
        
        dfs(0)
        return len(vis)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

四、[Medium] 6137. 检查数组是否存在有效划分

链接: 6137. 检查数组是否存在有效划分

1. 题目描述

2. 思路分析

定级Medium。
很难，一开始写栈+回溯坐大牢。

• 实际用dp好做一些。
• 令dp[i]为以i为结尾的前缀串是否合法。
• 那么只有当最后2个或三个字符合法，且前边串合法的情况下，dp[i]==True。
• 仔细判断即可。

3. 代码实现

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        st = []
        n = len(nums)
        dp = [False] * n
        if nums[0] == nums[1]:
            dp[1] = True
        for i in range(2,n):
            v = nums[i]
            if v == nums[i-1] and dp[i-2]:
                dp[i] = True
                continue
            if v == nums[i-1] == nums[i-2] and (i-2==0 or dp[i-3] ):
                dp[i] = True
                continue
            # print(i,nums[i-1]+1 , nums[i-2]+2 ,i-2,dp[i-3])
            if v == nums[i-1]+1 == nums[i-2]+2 and(i-2==0 or dp[i-3]):
                dp[i] = True
                continue
            # print(dp)
        return dp[n-1]                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

五、[Hard] 6138. 最长理想子序列

链接: 6138. 最长理想子序列

1. 题目描述

2. 思路分析

定级Hard。
想了半天LIS其实不对，这题可以直接DP。开一个长度26的dp数组。

• dp[i]代表字符以i为结尾的前缀合法串长度。
• 从前向后枚举s，如果当前字符是v，那么它可以从前边[v-k,v+k]转移而来，即：
• dp[v] = max{dp[j]+1|j∈[v-k,v+k]},注意边界[0,25]。
• 实现时，可以先把s转换成数字方便处理。

3. 代码实现

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        s = [ord(c)-ord('a') for c in s]
        dp = [0] *26
        for i,v in enumerate(s):            
            dp[v] = max(dp[j]+1 for j in range(max(0,v-k),min(25,v+k)+1))
                
        return max(dp)
1
2
3
4
5
6
7
8