• LeetCode笔记：Weekly Contest 292
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

• 比赛链接：https://leetcode.com/contest/weekly-contest-292

1. 题目一

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

• 2264. Largest 3-Same-Digit Number in String

1. 解题思路

这一题思路上倒是没啥，直接比较一下连续三个数就行了，不是很高效的解法，因为有大量的重复比较，不过对于easy级别的题目也够了。

2. 代码实现

给出python代码实现如下：

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        res = ""
        n = len(num)
        for i in range(n-2):
            if num[i] == num[i+1] == num[i+2]:
                if res == "" or int(res) < int(num[i:i+3]):
                    res = num[i:i+3]
        return res

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

2. 题目二

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

• 2265. Count Nodes Equal to Average of Subtree

1. 解题思路

这一题同样的本质上就是一个二叉树的后序遍历，不过遍历的时候需要返回一下子树中节点的总数和value之和就是了。

2. 代码实现

给出python代码实现如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
        res = 0
        
        def dfs(root):
            nonlocal res
            
            if root is None:
                return 0, 0
            lsum, lcnt = dfs(root.left)
            rsum, rcnt = dfs(root.right)
            s = lsum + rsum + root.val
            cnt = lcnt + rcnt + 1
            if s // cnt == root.val:
                res += 1
            return s, cnt
        
        dfs(root)
        return res

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

3. 题目三

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

• 2266. Count Number of Texts

1. 解题思路

这一题同样就是一个动态规划的问题。

不过在此基础上我们可以进一步地进行优化，只需要将连续数字分别进行考察，然后结果相乘就是最终的答案。

而对于连续数字，我们可以进一步抽象到对应的字符数目和长度，然后就是一个比较标准的动态规划的题目了。

2. 代码实现

给出python代码实现如下：

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        MOD = 10**9 + 7
        modes = [3, 3, 3, 3, 3, 4, 3, 4]
        
        @lru_cache(None)
        def dp(mode, cnt):
            if cnt == 0:
                return 1
            return sum(dp(mode, cnt-i) for i in range(1, min(mode, cnt)+1)) % MOD
        
        res = 1
        cnt = 0
        pre = ""
        for ch in pressedKeys:
            if ch == pre:
                cnt += 1
            else:
                if pre != "":
                    res = (res * dp(modes[ord(pre) - ord("2")], cnt)) % MOD
                pre = ch
                cnt = 1
        
        res = (res * dp(modes[ord(pre) - ord("2")], cnt)) % MOD
        return res

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

4. 题目四

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

• 2267. Check if There Is a Valid Parentheses String Path

1. 解题思路

这一题也差不多就是一个动态规划的题目，我们只需要依次将所有可行的路线找出来，然后用一个堆排优先找寻最为平衡的到达终点的路线即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        n, m = len(grid), len(grid[0])
        if grid[0][0] == ")" or grid[-1][-1] == "(":
            return False
        
        seen = {(1, 0, 0)}
        q = [(1, 0, 0)]
        while q:
            cnt, i, j = heapq.heappop(q)
            if i == n-1 and j == m-1:
                return cnt == 0
            if i+1 < n:
                if grid[i+1][j] == "(":
                    if (cnt+1, i+1, j) in seen:
                        continue
                    heapq.heappush(q, (cnt+1, i+1, j))
                    seen.add((cnt+1, i+1, j))
                else:
                    if cnt > 0:
                        if (cnt+1, i+1, j) in seen:
                            continue
                        heapq.heappush(q, (cnt-1, i+1, j))
                        seen.add((cnt-1, i+1, j))
            if j+1 < m:
                if grid[i][j+1] == "(":
                    if (cnt+1, i, j+1) in seen:
                        continue
                    heapq.heappush(q, (cnt+1, i, j+1))
                    seen.add((cnt+1, i, j+1))
                else:
                    if cnt > 0:
                        if (cnt-1, i, j+1) in seen:
                            continue
                        heapq.heappush(q, (cnt-1, i, j+1))
                        seen.add((cnt-1, i, j+1))
        return False

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