算法题记录 25

2269.找到一个数字的K美丽值（1724）

一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：

子字符串长度为 k 。
子字符串能整除 num 。
给你整数 num 和 k ，请你返回 num 的 k 美丽值。

注意：

允许有 前缀 0 。
0 不能整除任何值。
一个 子字符串 是一个字符串里的连续一段字符序列。

涉及知识点

字符串

解决思路

秒答题

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        s = str(num)
        ans = 0
        for i in range(k, len(s) + 1):
            x = int(s[i - k: i])  # 长为 k 的子串
            if x > 0 and num % x == 0:  # 子串能整除 num 
                ans += 1
        return ans

684.冗余连接（中等）

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

涉及知识点

并查集

解决思路

很标准的并查集题目，涉及查询连通分量、添加连通分量，因为a、b有边相连，如果a、b查询后的结果指向同一个节点x，证明还有其它路径相连，此时的边是冗余的。

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        s = str(num)
        ans = 0
        for i in range(k, len(s) + 1):
            x = int(s[i - k: i])  # 长为 k 的子串
            if x > 0 and num % x == 0:  # 子串能整除 num 
                ans += 1
        return ans

3194.最小元素和最大元素的最小平均值（1195）

你有一个初始为空的浮点数数组 averages。另给你一个包含 n 个整数的数组 nums，其中 n 为偶数。

你需要重复以下步骤 n / 2 次：

从 nums 中移除 最小 的元素 minElement 和 最大 的元素 maxElement。
将 (minElement + maxElement) / 2 加入到 averages 中。
返回 averages 中的 最小 元素。

涉及知识点

数组

解决思路

秒答题

class Solution:
    def minimumAverage(self, nums: List[int]) -> float:
        m=inf
        nums.sort()
        for i in range(len(nums)//2):
            m=min(m,(nums[0]+nums[-1])/2)
            nums=nums[1:-1]
        return m

688.骑士在棋盘上的概率（中等）

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。

象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

涉及知识点

表格、DFS

解决思路

结合之前做过的很多棋盘题、DFS题，该题的解题思路很容易想到，但是，如果我们用一个result去累加dfs的每个分支的最终概率，最终返回result，这样会导致内存爆掉。我们必须对dfs过程进行尽可能的简化，简化后的代码如下。

MOVE = (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)


class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        @cache
        def dfs(n: int, k: int, row: int, column: int) -> float:
            if not(0 <= row < n and 0 <= column < n):
                return 0
            if k == 0:
                return 1
            return sum(dfs(n, k - 1, row + dx, column + dy )for dx, dy in MOVE)/8

        if k == 0:
            return 1
        result=dfs(n, k, row, column)
        return result

3258.统计满足K约束的子字符串数量1（1258）

给你一个 二进制 字符串 s 和一个整数 k。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

字符串中 0 的数量最多为 k。
字符串中 1 的数量最多为 k。
返回一个整数，表示 s 的所有满足 k 约束 的子字符串的数量。

涉及知识点

滑动窗口

解决思路

以右端点为参考点，如果左边端点最远为i，那么i到右端点的字符串都能满足题意。如果发现右端点右移后不满足题意了，将左端点计数删除并右移一位。

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        ans = left = 0
        cnt = [0, 0]
        for i, c in enumerate(s):
            cnt[ord(c) & 1] += 1
            while cnt[0] > k and cnt[1] > k:
                cnt[ord(s[left]) & 1] -= 1
                left += 1
            ans += i - left + 1
        return ans

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。