算法题记录 23

2234.花园的最大总美丽值（2562）

Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。

给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花 不能 移走。同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。

如果一个花园有 至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之 和 ：

完善 花园数目乘以 full.
剩余 不完善 花园里，花的 最少数目 乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。
请你返回 Alice 种最多 newFlowers 朵花以后，能得到的 最大 总美丽值。

涉及知识点

贪心、双指针

解决思路

思路很清晰，我们希望有最多花的几个花园尽量去满足target，剩下的花园的花的最小值尽可能大。所以我们可以把原数组排序，前缀为需要被平均抬高的未种满花园，后缀为被种满的花园，这样最终结果等于avg_pre*partial+后缀个数*full。

class Solution:
    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:
        n = len(flowers)
        for i in range(n):
            flowers[i] = min(flowers[i], target)

        # 如果全部种满，还剩下多少朵花？
        left_flowers = newFlowers - (target * n - sum(flowers))

        # 没有种花，所有花园都已种满
        if left_flowers == newFlowers:
            return n * full  # 答案只能是 n*full（注意不能减少花的数量）

        # 可以全部种满
        if left_flowers >= 0:
            # 两种策略取最大值：留一个花园种 target-1 朵花，其余种满；或者，全部种满
            return max((target - 1) * partial + (n - 1) * full, n * full)

        flowers.sort()  # 时间复杂度的瓶颈在这，尽量写在后面

        ans = pre_sum = j = 0
        # 枚举 i，表示后缀 [i, n-1] 种满（i=0 的情况上面已讨论）
        for i in range(1, n + 1):
            # 撤销，flowers[i-1] 不变成 target
            left_flowers += target - flowers[i - 1]
            if left_flowers < 0:  # 花不能为负数，需要继续撤销
                continue

            # 满足以下条件说明 [0, j] 都可以种 flowers[j] 朵花
            while j < i and flowers[j] * j <= pre_sum + left_flowers:
                pre_sum += flowers[j]
                j += 1

            # 计算总美丽值
            # 在前缀 [0, j-1] 中均匀种花，这样最小值最大
            avg = (left_flowers + pre_sum) // j  # 由于上面特判了，这里 avg 一定小于 target
            total_beauty = avg * partial + (n - i) * full
            ans = max(ans, total_beauty)

        return ans

3232.判断是否可以赢得数字游戏（1163）

给你一个 正整数 数组 nums。

Alice 和 Bob 正在玩游戏。在游戏中，Alice 可以从 nums 中选择所有个位数 或 所有两位数，剩余的数字归 Bob 所有。如果 Alice 所选数字之和 严格大于 Bob 的数字之和，则 Alice 获胜。

如果 Alice 能赢得这场游戏，返回 true；否则，返回 false。

涉及知识点

数组

解决思路

秒答题

class Solution:
    def canAliceWin(self, nums: List[int]) -> bool:
        count1,count2,count3=0,0,0
        for i in range(len(nums)):
            if 0<nums[i]<10:
                count1+=nums[i]
            if 9<nums[i]<100:
                count2+=nums[i]
            count3+=nums[i]
        if count3-2*max(count1,count2)<0:
            return True
        else:
            return False

2717.半有序排列（1296）

给你一个下标从 0 开始、长度为 n 的整数排列 nums 。

如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为 半有序排列 。你可以执行多次下述操作，直到将 nums 变成一个 半有序排列 ：

选择 nums 中相邻的两个元素，然后交换它们。
返回使 nums 变成 半有序排列 所需的最小操作次数。

排列 是一个长度为 n 的整数序列，其中包含从 1 到 n 的每个数字恰好一次。

涉及知识点

数组

解决思路

秒答题

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        index1=nums.index(1)
        indexn=nums.index(len(nums))
        if indexn<index1:
            return index1+len(nums)-1-indexn-1
        else:
            return index1+len(nums)-1-indexn

2717.半有序排列（1296）

给你一个下标从 0 开始、长度为 n 的整数排列 nums 。

如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为 半有序排列 。你可以执行多次下述操作，直到将 nums 变成一个 半有序排列 ：

选择 nums 中相邻的两个元素，然后交换它们。
返回使 nums 变成 半有序排列 所需的最小操作次数。

排列 是一个长度为 n 的整数序列，其中包含从 1 到 n 的每个数字恰好一次。

涉及知识点

数组

解决思路

秒答题

class Solution:
    def semiOrderedPermutation(self, nums: List[int]) -> int:
        index1=nums.index(1)
        indexn=nums.index(len(nums))
        if indexn<index1:
            return index1+len(nums)-1-indexn-1
        else:
            return index1+len(nums)-1-indexn

1366.通过投票对团队排名（1626）

现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。

排名规则如下：

参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。
给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。

请你返回能表示按排名系统 排序后 的所有团队排名的字符串。

涉及知识点

排序

解决思路

自定义一个排序思路，我们对每个字母的各位置进行计数，然后定义一个排序方式，先按字典序排序，如果相同则按ASCII码排序。

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        m = len(votes[0])
        cnts = defaultdict(lambda: [0] * m)
        for vote in votes:
            for i, ch in enumerate(vote):
                cnts[ch][i] -= 1  # 改成负数（相反数），方便比大小
        return ''.join(sorted(cnts, key=lambda ch: (cnts[ch], ch)))

3270.求出数字答案（1205）

给你三个 正 整数 num1 ，num2 和 num3 。

数字 num1 ，num2 和 num3 的数字答案 key 是一个四位数，定义如下：

一开始，如果有数字 少于 四位数，给它补 前导 0 。
答案 key 的第 i 个数位（1 <= i <= 4）为 num1 ，num2 和 num3 第 i 个数位中的 最小 值。
请你返回三个数字 没有 前导 0 的数字答案。

涉及知识点

数学

解决思路

秒答题

class Solution:
    def generateKey(self, num1: int, num2: int, num3: int) -> int:
        result=0
        i=1
        while num1!=0 and num2!=0 and num3!=0:
            n1=num1%10
            n2=num2%10
            n3=num3%10
            num1=num1//10
            num2=num2//10
            num3=num3//10
            n=min(n1,n2,n3)
            result+=i*n
            i*=10
        return result

3095.或值至少K的最短子数组1（1369）

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。

涉及知识点

位操作

解决思路

按题目要求做就行，比如我们拿到nums[3]，我们去遍历nums[2]、nums[1]、nums[0]，不断进行或等于操作，通过贪心策略进行遍历找到目前nums[3]与之前的数的或所能产生的最小值。把nums遍历完即得到答案。因为子数组是连续的，并且或操作是越或越大，有单调性，要用滑动窗口也行。不过需要个栈来存储或的结果，因为或不存在逆运算，在去除窗口左端点时会遇到一点麻烦。

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = inf
        for i, x in enumerate(nums):
            if x >= k:
                return 1
            j = i - 1
            while j >= 0 and nums[j] | x != nums[j]:
                nums[j] |= x
                if nums[j] >= k:
                    ans = min(ans, i - j + 1)
                j -= 1
        return ans if ans < inf else -1

声明

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