【算法】力扣第 288 场周赛（最短代码）

文章目录

• [6037. 按奇偶性交换后的最大数字](https://leetcode-cn.com/problems/largest-number-after-digit-swaps-by-parity/)
• [2232. 向表达式添加括号后的最小结果](https://leetcode-cn.com/problems/minimize-result-by-adding-parentheses-to-expression/)
• [6039. K 次增加后的最大乘积](https://leetcode-cn.com/problems/maximum-product-after-k-increments/)
• [2234. 花园的最大总美丽值](https://leetcode-cn.com/problems/maximum-total-beauty-of-the-gardens/)
• 总结

6037. 按奇偶性交换后的最大数字

奇数偶数分别排序，再写回，两行搞定

class Solution:
    def largestInteger(self, num: int) -> int:
        nums1,nums2=sorted([int(x) for x in str(num) if x in '13579'])  ,sorted([int(x) for x in str(num) if x in '02468'])      
        return int(''.join(map(str,[nums1.pop() if int(x)&1 else nums2.pop() for x in str(num)])))

2232. 向表达式添加括号后的最小结果

暴力遍历每个可以加括号的位置，用eval计算结果，取最小值

下面是六弦爷的两行解法，非常漂亮

class Solution:
    def minimizeResult(self, expression: str) -> str:
        n, pi = len(expression), expression.index('+')
        return min(((expression[:li] + '*(' + expression[li:ri] +')*' + expression[ri:]).strip('*')  for li, ri in product(range(pi), range(pi + 2, n + 1))), key = eval).replace('*', '')

6039. K 次增加后的最大乘积

优先队列，三行解法👇

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        for _ in range(k): heapq.heapreplace(nums, nums[0] + 1)
        return [*accumulate(nums,func=lambda total,element:total*element%1000000007)][-1]

2234. 花园的最大总美丽值

按照灵茶山大佬的提示：

1. 贪 心 ： 让 较 大 的 flowers [ i ] 增 加 至 target ， 其 余 的 flowers 的 最 小 值 尽 量 大 。
   

   
   

   贪心：让较大的\textit{flowers}[i] 增加至 \textit{target}，其余的 \textit{flowers}的最小值尽量大。
   

   
   

   贪心：让较大的flowers[i]增加至target，其余的flowers的最小值尽量大。
   

   
   

2. 枚 举 flowers 的 后 缀 ， 让 这 些 花 园 的 花 增 加 至 target ， 同 时 我 们 需 要 求 出 flowers 的 最 长 前 缀 （ 设 其 长 为 x ） ， 满 足 前 缀 中 的 花 园 的 花 都 能 增 加 至 flowers [ x − 1 ] 朵 。
   

   
   

   枚举 \textit{flowers} 的后缀，让这些花园的花增加至 \textit{target}，同时我们需要求出 \textit{flowers}的最长前缀（设其长为 x），满足前缀中的花园的花都能增加至\textit{flowers}[x-1]朵。
   

   
   

   枚举flowers的后缀，让这些花园的花增加至target，同时我们需要求出flowers的最长前缀（设其长为x），满足前缀中的花园的花都能增加至flowers[x−1]朵。
   

   
   

因此，可以安排下面的代码，7行搞定

class Solution:
    def maximumBeauty(self, nums: List[int], k: int, t: int, f: int, p: int) -> int:
        nums,n,pre,idx = sorted(nums),len(nums),[*accumulate([0]+sorted(nums))],bisect_left(sorted(nums), t)-1

        helper=lambda i,x:my_bisect([],x,lo=nums[0],hi=t,key=lambda mid:(ind:=min(i, bisect_left(nums, mid)))*(mid)-pre[ind])-1
        
        res,cur = (n - idx - 1)*f + helper(idx + 1, k)*p,0
        for i in range(idx,-1,-1):
            if (cur:=cur+t-nums[i]) > k:break    
            res = max(res,(n - i)*f + helper(i, k - cur)*p*(i > 0))
            
        return f*n if idx==-1 else res

其中带key二分是python3.10新引入的方法，大家可以通过下面的源码进行理解:

def my_bisect(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(i, x) will
    insert just after the rightmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < a[mid]:
                hi = mid
            else:
                lo = mid + 1
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < key(mid):
                hi = mid
            else:
                lo = mid + 1
    return lo

总结

推荐学习：

• T1：pop()+列表推导式
• T2：product
• T3：accumulate 或者reduce
• T4：带key二分

本次周赛一共2+2+3+7=14行，完成【20行完成周赛】的目标！