2022-02-05 每日打卡:Leetcode第71场双周赛

2022-02-05 每日打卡:Leetcode第71场双周赛

写在前面

“这些事儿在熟练之后,也许就像喝口水一样平淡,但却能给初学者带来巨大的快乐,我一直觉得,能否始终保持如初学者般的热情、专注,决定了在做某件事时能走多远,能做多好。” 该系列文章由python编写,所刷题目共三个来源:之前没做出来的 ;Leetcode中等,困难难度题目; 周赛题目;某个专题的经典题目,所有代码已AC。每日1-3道,随缘剖析,希望风雨无阻,作为勉励自己坚持刷题的记录。

T1~T3

  • T1 拆分数位后四位数字的最小和:对于位数问题,可以使用字符串进行快速的划分和连接,字符串之间的相加减对应的就是每个位数之间的相加减。
  • T2 根据给定数字划分数组:partition操作是否保持有序取决于采用双指针or单指针。
  • T3 设置时间的最少代价:凡是给定数据范围,譬如此题中微波炉的时间设置为0~99,一定要在提交前测试一下边界,比如100的情况。

5987. 删除元素后和的最小差值

2022-02-05 每日打卡:Leetcode第71场双周赛
将 nums 拆分成两部分,划分位置区间为【n~2*n】,无论何种划分,最后取【左半部分的最小和(前缀最小和)】减去【右半部分的最大和(后缀最大和)】即为两部分和的最小差值。
枚举拆分位置(保证左右两部分至少有 n 个元素),所有差值的最小值就是答案。很多题并不是一下子就能出答案的,要接受适当的枚举。

from heapq import *

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) // 3
        
        left = [0 for _ in range(3 * n + 1)]        # 划分到第i个时,i左侧最小的n个数的和
        right = [0 for _ in range(3 * n + 1)]       # 划分到第i个时,i右侧最大的n个数的和
        
        # 每次要删除那个最大的数
        # 在0~2n的区域中保留最小的n个
        l_max = []                          
        for i in range(2 * n):
            left[i + 1] = left[i] + nums[i]
            heapq.heappush(l_max, -1 * nums[i])
            if n <= i:
                left[i + 1] -= -1 * l_max[0]
                heapq.heappop(l_max)

        # 每次要删除那个最小的数
        # 在n~3n的区域中保留最大的n个
        r_min = []   
        for i in range(3 * n - 1, n - 1, -1):
            right[i] = right[i + 1] + nums[i]
            heapq.heappush(r_min, nums[i])
            if i < 2 * n:
                right[i] -= r_min[0]
                heapq.heappop(r_min)
        
        # 有效的划分区间
        left, right = left[n:2*n+1], right[n:2*n+1]
        res = min(l-r for l,r in zip(left,right))
        return res
        
上一篇:2021_12_12自学笔记_Requests的基本使用和get请求


下一篇:python使用request封装请求,请求报错requests.exceptions.ReadTimeout: HTTPSConnectionPool(xxxx)