LeetCode笔记:Biweekly Contest 71

1. 题目一

给出题目一的试题链接如下:

1. 解题思路

这一题由于可以允许0在开头的情况,因此整体思路上还是比较简单的,只需要把4个数字取出来,然后把两个较小的数字放在十位数上,剩下的两个较大的数字放在个位数上即可。

2. 代码实现

给出python代码实现如下:

class Solution:
    def minimumSum(self, num: int) -> int:
        digits = []
        while num != 0:
            digits.append(num % 10)
            num = num // 10
        digits = sorted(digits)
        return 10*sum(digits[:2]) + sum(digits[2:])

提交代码评测得到:耗时43ms,占用内存13.8MB。

2. 题目二

给出题目二的试题链接如下:

1. 解题思路

这一题我的思路比较暴力就是了,直接把数据根据pivot分成三堆,然后重新组合即可。

2. 代码实现

给出python代码实现如下:

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        less = [x for x in nums if x < pivot]
        equal = [x for x in nums if x == pivot]
        large = [x for x in nums if x > pivot]
        return less + equal + large

提交代码评测得到:耗时2373ms,占用内存31.6MB。

3. 题目三

给出题目三的试题链接如下:

1. 解题思路

这一题其实比较直接,按照题意进行计算即可,唯一需要注意的是,由于秒钟可以达到99,因此有的时间可以有多种设置方式,需要比较一下两者的大小。

2. 代码实现

给出python代码实现如下:

class Solution:
    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:
        minute, second = targetSeconds // 60, targetSeconds % 60
        def get_cost(minute, second):
            digits = (f"{minute:02d}" + f"{second:02d}").lstrip("0")
            res, pre = 0, str(startAt)
            for ch in digits:
                res += pushCost
                if ch != pre:
                    res += moveCost
                pre = ch
            return res
        
        res = get_cost(minute, second) if minute < 100 else math.inf
        if minute > 0 and second + 60 < 100:
            res = min(res, get_cost(minute-1, second+60))
        return res

提交代码评测得到:耗时59ms,占用内存13.9MB。

4. 题目四

给出题目四的试题链接如下:

1. 解题思路

这一题的思路其实就是在中段选择一个分隔点,左侧选取n个最小的元素,右侧选取n个最大的元素,然后求差值即可。

因此,我们就是遍历中段的分隔点,然后分别统计左右的前n个最大或者最小的元素之和,然后进行求差即可。而前者这个数组的维护则可以通过堆排进行高效的实现。

2. 代码实现

给出python代码实现如下:

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) // 3
        left = [-x for x in nums[:n]]
        right = nums[-n:]
        ls, rs = sum(left), sum(right)
        heapq.heapify(left)
        heapq.heapify(right)
        
        cnt = [[ls, rs] for _ in range(n+1)]
        for i in range(n):
            heapq.heappush(left, -nums[n+i])
            lpop = heapq.heappop(left)
            cnt[i+1][0] = cnt[i][0] - nums[n+i] - lpop
            
            heapq.heappush(right, nums[2*n-1-i])
            rpop = heapq.heappop(right)
            cnt[n-1-i][1] = cnt[n-i][1] + nums[2*n-1-i] - rpop
        return -max(sum(x) for x in cnt)         

提交代码评测得到:耗时3545ms,占用内存46.3MB。

上一篇:Spring IOC容器初始化


下一篇:Java平台调试体系原理和实践整理 远程Debug