LeetCode冲刺：Day36

ArslanTu 发布于 2022-12-13 1,091 次阅读

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

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

用三个数组， flag 记录原数字每一位的奇偶性， odd 记录每一位中为奇数的数字， even 记录每一位中为偶数的数字。将奇数、偶数数组按降序排序，然后根据每一位的奇偶性填入最大的数即可。

代码

class Solution:
    def largestInteger(self, num: int) -> int:
        odd = []
        even = []
        flag = []
        while num > 0:
            cur = num % 10
            num = int(num / 10)
            if (cur & 1) == 0:
                even.append(cur)
                flag.insert(0, 0)
            else:
                odd.append(cur)
                flag.insert(0, 1)
        odd.sort(reverse=True)
        even.sort(reverse=True)
        i = 0
        j = 0
        for k in range(len(flag)):
            if flag[k] == 0:
                num = num * 10 + even[i]
                i += 1
            else:
                num = num * 10 + odd[j]
                j += 1
        return num

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

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

看起来好像很复杂，但看到表达式最长为10，显然可以暴力枚举。

先把左右数字分开，然后遍历每一对括号的情况即可。

代码

class Solution:
    def minimizeResult(self, expression: str) -> str:
        plusPos = expression.find("+")
        num_1 = expression[0: plusPos]
        num_2 = expression[plusPos + 1: len(expression)]
        m = len(num_1)
        n = len(num_2)
        ans = int(num_1) + int(num_2)
        lc = 0
        rc = 0
        for i in range(m):
            leftMul = int(num_1[0: i]) if num_1[0: i] != '' else 1
            leftSum = int(num_1[i: m])
            for j in range(n):
                rightMulti = int(num_2[n - j: n]) if num_2[n - j: n] != '' else 1
                rightSum = int(num_2[0: n - j])
                cur = (leftSum + rightSum) * leftMul * rightMulti
                if cur < ans:
                    ans, lc, rc = cur, i, j
        ans = num_1[0: lc] + "(" + num_1[lc: m] + "+" + num_2[0: n - rc] + ")" + num_2[n - rc: n]
        return ans

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

难度

Easy
Medium
Hard

完成情况

独立完成
参考思路
参考答案

思路

使用小根堆，每次最小值加一。参考这篇

代码

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        MOD = 1000000007
        heapify(nums)
        while k:
            heapreplace(nums, nums[0] + 1)
            k -= 1
        ans = 1
        for num in nums:
            ans = (ans * num) % MOD
        return ans