LeetCode刷题记录第五周

3904. 最小稳定下标 II

给你一个长度为 n 的整数数组 nums 和一个整数 k。

对于每个下标 i,定义它的 不稳定值 为 max(nums[0..i]) - min(nums[i..n - 1])。

换句话说:

  • max(nums[0..i]) 表示从下标 0 到下标 i 的元素中的 最大值 。
  • min(nums[i..n - 1]) 表示从下标 i 到下标 n - 1 的元素中的 最小值 。

如果某个下标 i 的不稳定值 小于等于 k,则称该下标为 稳定下标 。

返回 最小 的稳定下标。如果不存在这样的下标,则返回 -1。

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)
        nmax = [0] * n
        nmin = [0] * n
        for i in range(n):
            if i == 0:
                nmax[0] = nums[0]
                nmin[n-1] = nums[n-1]
                continue
            nmax[i] = max(nmax[i-1], nums[i])
            nmin[n-1-i] = min(nmin[n-i], nums[n-i-1])
        for i in range(n):
            if nmax[i] - nmin[i] <= k:
                return i
        return -1

这和3903的区别只在数据范围,不能接受O(n2)O(n^2)的解法,两题的O(n)O(n)解是一样的

1927. 求和游戏

Alice 和 Bob 玩一个游戏,两人轮流行动,Alice 先手 。

给你一个 偶数长度 的字符串 num ,每一个字符为数字字符或者 '?' 。每一次操作中,如果 num 中至少有一个 '?' ,那么玩家可以执行以下操作:

  1. 选择一个下标 i 满足 num[i] == '?' 。
  2. 将 num[i] 用 '0' 到 '9' 之间的一个数字字符替代。

当 num 中没有 '?' 时,游戏结束。

Bob 获胜的条件是 num 中前一半数字的和 等于 后一半数字的和。Alice 获胜的条件是前一半的和与后一半的和 不相等 。

  • 比方说,游戏结束时 num = "243801" ,那么 Bob 获胜,因为 2+4+3 = 8+0+1 。如果游戏结束时 num = "243803" ,那么 Alice 获胜,因为 2+4+3 != 8+0+3 。

在 Alice 和 Bob 都采取 最优 策略的前提下,如果 Alice 获胜,请返回 true ,如果 Bob 获胜,请返回 false 。

class Solution:
    def sumGame(self, num: str) -> bool:
        n = len(num)
        As = Aq = Bs = Bq = 0
        for i, c in enumerate(num):
            if i < n // 2:
                if c == '?': Aq += 1
                else: As += ord(c) - ord('0')
            else:
                if c == '?': Bq += 1
                else: Bs += ord(c) - ord('0')
        return (Aq + Bq) % 2 == 1 or 2 * (As - Bs) != 9 * (Bq - Aq)

可以理解为前一半数字的和减另一半数字的和的结果在一个数轴上面移动,只有最终停留在原点时Bob才能获胜。

如果有奇数个可填位置则Alice收尾,Alice必胜。

当左右两侧都有问号的时候,Alice总能将结果向绝对值最大的方向推动9,而Bob拉回来。

当左右两侧其中一侧的问号消灭干净,假设最后一轮Alice给出x,则数轴移动的范围为[x,x+9],只有9是一定可以实现的移动,也就是bob必须给出9-x并且本来也处在那个唯一的位置才行。往前以此类推,因此对bob的条件及其苛刻,只有满足2 * (As - Bs) != 9 * (Bq - Aq) 的时候才可能获胜。

从另一个角度看,Bob总可以通过给出9-x来使得Alice的操作无效化,仅有此时Bob可以在最终的结果中消灭Alice的自由度。但这种理解相对难以被证明。

115. 不同的子序列

给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

from functools import lru_cache
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        ns = len(s)
        nt = len(t)
        # self.DP = [([0] * (ns + 1)) for _ in range(nt+1)]
        @lru_cache(maxsize=None)
        def f(i, j): 
            if j == 0:
                return 1
            if i == 0:
                return 0
            return f(i-1,j-1)*(s[i-1] == t[j-1])+f(i-1,j) 
        return f(ns,nt)

f(i,j)代表当用到了s的前i个字符来实现t的前j个字符的方案数量

当s[i-1] != t[j-1]的时候说明s[i-1] 没有被使用,此时只能依赖f(i-1,j)来填充

当s[i-1] == t[j-1]的时候说明s[i-1] 可以被使用,此时追加f(i-1,j-1)作为补充

第一次超时是因为又忘了写(maxsize=None)了

这种情况的复杂度和DP表的大小一致,为O(mn)O(mn)

一开始想用BFS类似的思路,然后发现这个思路的复杂度是O(m2n)O(m^2n)

加入去重机制后队列中会出现的元素数量其实为O(mn)O(mn),但是判断数量为O(m2n)O(m^2n)

940. 不同的子序列 II

给定一个字符串 s,计算 s 的 不同非空子序列 的个数。因为结果可能很大,所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些(也可能不删除)字符但不改变剩余字符相对位置的一个新字符串。

  • 例如,"ace" 是 "abcde" 的一个子序列,但 "aec" 不是。
class Solution:
    def distinctSubseqII(self, s: str) -> int:
        MOD = 10**9 + 7
        end = [0] * 26
        T = 1                      # 含空串
        for ch in s:
            x = ord(ch) - 97
            old = end[x]
            end[x] = T
            T = (2 * T - old) % MOD
        return (T - 1) % MOD

难绷还是不会做。

首先这个题的难点在于去重,但是绝不能使用哈希表,因为组合种类太庞大了。

然后是DP要存什么内容,如果存长度为i的子序列为DP[i],那就还是要存储之前的子序列。

正确答案是存前i个字符中以字符c结尾的子序列数量,但其实也非常反直觉。

对于不同的子字符串,无论追加什么样的后缀都是新的不同的字符串,因此

old = end[x]  #保留之前的以x结尾的串数量
end[x] = T    #之前的每一个串都可以被延长,共有T+end[x]个,但有end[x]个重复
#重复的原理是之前的x结尾的子串有n个的话,就有n个不同的前缀存在在T中,因此延长操作是重复的
T = (2 * T - old) % MOD
#总数量是之前的子串 + 之前的子串+x - n个重复的操作

2265. 统计值等于子树平均值的节点数

给你一棵二叉树的根节点 root ,找出并返回满足要求的节点数,要求节点的值等于其 子树 中值的 平均值 。

注意:

  • n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ,并 向下舍入 到最近的整数。
  • root 的 子树 由 root 和它的所有后代组成。
# 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: TreeNode) -> int:
        cnt = 0
        def dfs(node: TreeNode):
            nonlocal cnt
            if not node: return (0, 0)
            left_sum , left_cnt = dfs(node.left)
            right_sum , right_cnt = dfs(node.right)
            if (left_sum + right_sum + node.val)// (1 + left_cnt + right_cnt) == node.val:
                cnt += 1
            return (left_sum + right_sum + node.val, left_cnt + right_cnt + 1) 
        dfs(root)
        return cnt

DFS问题看到的第一反应就是用栈,但是写栈的时候是从上往下搜索的,但题中问题需要从叶子节点倒推,因此递归是最优雅的写法。

这里用到了一个nonlocal语法,声明要直接修改外部的变量

如果一定要用栈,我们需要向下搜索的时候压一次栈,回代的时候再压一次栈

def averageOfSubtree(self, root: TreeNode) -> int:
    ans = 0
    memo = {}                    # node -> (sum, cnt),孩子算完的结果存这里
    stack = [(root, False)]      # (node, 是否已看过孩子)
    while stack:
        node, done = stack.pop()
        if not node:
            continue
        if not done:
            # 去程:先把自己"标记回程"压回去,再把两个孩子压上去(后进先出→左先处理)
            stack.append((node, True))
            stack.append((node.left, False))
            stack.append((node.right, False))
        else:
            # 回程:此刻两个孩子必然已结算完,结果躺在 memo 里
            ls, lc = memo.get(node.left, (0, 0))
            rs, rc = memo.get(node.right, (0, 0))
            s, c = node.val + ls + rs, 1 + lc + rc
            if s // c == node.val:
                ans += 1
            memo[node] = (s, c)  # 把自己的结果交给父节点用
    return ans

3483. 不同三位偶数的数目

给你一个数字数组 digits,你需要从中选择三个数字组成一个三位偶数,你的任务是求出 不同 三位偶数的数量。

注意:每个数字在三位偶数中都只能使用 一次 ,并且 不能 有前导零。

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        def count(x):
            m = sum(x[c] > 0 for c in range(10))
            n = sum(x[c] > 1 for c in range(10))
            return n + 2 * comb(m, 2)
        cnt = {}
        for n in range(10):
            cnt[n] = 0
        for n in digits:
            cnt[n] += 1
        n = len(digits)
        even = cnt[0] + cnt[2] + cnt[4] + cnt[6] + cnt[8]
        if even == 0:
            return 0
        ans = 0
        for i in range(5):
            if cnt[2*i] == 0:
                continue
            cnt[2*i] -= 1
            ans += count(cnt)
            if cnt[0] > 0:
                cnt[0] -= 1
                ans -= sum(cnt[c] > 0 for c in range(10))
                cnt[0] += 1
            cnt[2*i] += 1
        return ans

路边一条。

Related Posts