算法题记录 8

2080.区间内查询数字的频率（1702）

请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。

子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。

请你实现 RangeFreqQuery 类：

RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
int query(int left, int right, int value) 返回子数组 arr[left…right] 中 value 的 频率 。
一个 子数组 指的是数组中一段连续的元素。arr[left…right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。

涉及知识点

二分

解决思路

秒答题，很容易想到将各个value的位置记录下来。再在保存位置的数组中进行二分查找满足（left,right）即可。

class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        pos=defaultdict(list)
        for i,x in enumerate(arr):
            pos[x].append(i)
        self.pos=pos

    def query(self, left: int, right: int, value: int) -> int:
        a=self.pos[value]
        return bisect_right(a,right)-bisect_left(a,left)

3200.三角形的最大高度（1451）

给你两个整数 red 和 blue，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。

每一行的球必须是 相同 颜色，且相邻行的颜色必须 不同。

返回可以实现的三角形的 最大 高度。

涉及知识点

数学

解决思路

秒答题，可以直接模拟，也可以用等差数列推导出公式进行判断。

class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        def f(n: int, m: int) -> int:
            odd = isqrt(n)
            even = (isqrt(m * 4 + 1) - 1) // 2
            return even * 2 + 1 if odd > even else odd * 2
        return max(f(red, blue), f(blue, red))

3171.找到按位或最接近K的子数组（2163）

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个
子数组
，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] … OR nums[r])| 最小。

请你返回 最小 的绝对差值。

子数组 是数组中连续的 非空 元素序列。

涉及知识点

位操作

解决思路

位操作
i=1 时，把 nums[0] 到 nums[1] 的 OR 记录在 nums[0] 中。
i=2 时，把 nums[1] 到 nums[2] 的 OR 记录在 nums[1] 中，nums[0] 到 nums[2] 的 OR 记录在 nums[0] 中。
i=3 时，把 nums[2] 到 nums[3] 的 OR 记录在 nums[2] 中；nums[1] 到 nums[3] 的 OR 记录在 nums[1] 中；nums[0] 到 nums[3] 的 OR 记录在 nums[0] 中。

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        ans = inf
        for i, x in enumerate(nums):
            ans = min(ans, abs(x - k))
            j = i - 1
            # 如果 x 是 nums[j] 的子集，就退出循环
            while j >= 0 and nums[j] | x != nums[j]:
                nums[j] |= x
                ans = min(ans, abs(nums[j] - k))
                j -= 1
        return ans

3216.交换后字典序最小的字符串（1243）

给你一个仅由数字组成的字符串 s，在最多交换一次 相邻 且具有相同 奇偶性 的数字后，返回可以得到的
字典序最小的字符串
。

如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。

涉及知识点

贪心

解决思路

秒答题，从左往右贪心即可。

class Solution:
    def getSmallestString(self, s: str) -> str:
        t = list(s)
        for i in range(1, len(t)):
            x, y = t[i - 1], t[i]
            if x > y and ord(x) % 2 == ord(y) % 2:
                t[i - 1], t[i] = y, x
                break
        return ''.join(t)

3222.求出硬币游戏的赢家（1270）

给你两个 正 整数 x 和 y ，分别表示价值为 75 和 10 的硬币的数目。

Alice 和 Bob 正在玩一个游戏。每一轮中，Alice 先进行操作，Bob 后操作。每次操作中，玩家需要拿走价值 总和 为 115 的硬币。如果一名玩家无法执行此操作，那么这名玩家 输掉 游戏。

两名玩家都采取 最优 策略，请你返回游戏的赢家。

涉及知识点

数学

解决思路

秒答题，其实就一个解：拿1个75，4个10。奇偶判断下就行。

class Solution:
    def winningPlayer(self, x: int, y: int) -> str:
        return "Alice" if min(x, y // 4) % 2 else "Bob"

1547.切棍子的最小成本（2116）

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本 。

涉及知识点

动态规划

解决思路

动态规划的经典题型，转移方程为（在k处切一刀）：dfs(i,k)+dfs(k,j)+cuts[j]−cuts[i]。

动态规划

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts.sort()
        cuts = [0] + cuts + [n]

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int) -> int:
            if i + 1 == j:  # 无需切割
                return 0
            # 枚举切割位置 cuts[k]
            return min(dfs(i, k) + dfs(k, j) for k in range(i + 1, j)) + cuts[j] - cuts[i]

        return dfs(0, len(cuts) - 1)

递推

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts.sort()
        cuts = [0] + cuts + [n]

        m = len(cuts)
        f = [[0] * m for _ in range(m)]
        for i in range(m - 3, -1, -1):
            for j in range(i + 2, m):
                f[i][j] = min(f[i][k] + f[k][j] for k in range(i + 1, j)) + cuts[j] - cuts[i]
        return f[0][-1]

声明

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