算法题记录 5

3226.使两个整数相等的位更改次数（1247）

给你两个正整数 n 和 k。

你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。

涉及知识点

位操作

解决思路

秒答题，如果能够更改，n and k的结果应该等于k，否则没法转化。如果可以转化，我们取n^k，剩下的1的个数就是需要变更的次数，这里记住python有自带的函数bit_count()即可。

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        return -1 if n&k!=k else (n^k).bit_count()

3259.超级饮料的最大强化能量（1484）

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。

返回在接下来的 n 小时内你能获得的 最大 总强化能量。

注意 你可以选择从饮用任意一种能量饮料开始。

涉及知识点

动态规划

解决思路

秒答题，根据题意列出状态转移方程即可。注意python的@cache装饰器。也可改成for循环的递推形式。

DP

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        c=(energyDrinkA,energyDrinkB)
        @cache
        def dfs(i:int,j:int)->int:
            if i<0:
                return 0
            return max(dfs(i-1,j),dfs(i-2,j^1))+c[j][i]
        
        return max(dfs(len(energyDrinkA)-1,0),dfs(len(energyDrinkA)-1,1))

递推

class Solution:
    def maxEnergyBoost(self, a: List[int], b: List[int]) -> int:
        n = len(a)
        f = [[0, 0] for _ in range(n + 2)]
        for i, (x, y) in enumerate(zip(a, b)):
            f[i + 2][0] = max(f[i + 1][0], f[i][1]) + x
            f[i + 2][1] = max(f[i + 1][1], f[i][0]) + y
        return max(f[-1])

887.鸡蛋掉落（2377）

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

涉及知识点

动态规划

解决思路

有难度，需要反向思考，注意该题并不符合反复二分的直觉。假设我们知道要执行i次，现有j个鸡蛋，那么可以确定的最高楼层为dfs(i-1,j-1)+1+dfs(i-1,j),dfs(i-1,j-1)+1表示的是从该楼层扔下去，鸡蛋碎了。dfs(i-1,j)表示的是从dfs(i-1,j-1)+1楼层扔下去鸡蛋没碎，还可以确定的楼层。递归边界为i或j=0。从1遍历i，如果dfs(i,j)>=n了，那么此时的i就是解。当然也可以换成效率更高的递推做。

动态规划

class Solution:
    @cache
    def superEggDrop(self, k: int, n: int) -> int:
        def dfs(i:int,j:int)->int:
            if i==0 or j==0:
                return 0
            return dfs(i-1,j)+dfs(i-1,j-1)+1

        for i in count(1):
            if dfs(i,k)>=n:
                return i

递推

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        f = [[0] * (k + 1) for _ in range(n + 1)]
        for i in count(1):  # 从 1 开始枚举 i
            for j in range(1, k + 1):
                f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + 1
            if f[i][k] >= n:
                return i

2270.分割数组的方案数（1334）

给你一个下标从 0 开始长度为 n 的整数数组 nums 。
如果以下描述为真，那么 nums 在下标 i 处有一个 合法的分割 ：

前 i + 1 个元素的和 大于等于 剩下的 n - i - 1 个元素的和。
下标 i 的右边 至少有一个 元素，也就是说下标 i 满足 0 <= i < n - 1 。
请你返回 nums 中的 合法分割 方案数。

涉及知识点

数组操作

解决思路

秒答题，根据题意列出数学公式化简，遍历数组判断是否满足式子并计数即可。

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        t=(sum(nums)+1)//2
        return sum(s>=t for s in accumulate(nums[:-1]))

声明

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