[数据结构与算法]leetcode：87场双周赛总结 = 思维贪心专场

分析

这个需要注意前缀和的时候要补一个0
然后两种不相交的情况
相交的话start取max end取min
好一道恶心模拟

ac code

class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        months = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        preSum = list(accumulate(months))
        #print(preSum)
        def getDay(s):
            mm, dd = map(int, s.split('-'))
            #print(mm, dd, preSum[mm - 1], preSum[mm - 1] + dd)
            return preSum[mm - 1] + dd
        
        a_start = getDay(arriveAlice)
        a_end = getDay(leaveAlice)
        b_start = getDay(arriveBob)
        b_end = getDay(leaveBob)
        
        #print(a_start, a_end)
        #print(b_start, b_end)
        if a_start > b_end or a_end < b_start:
            return 0
        else:
            return min(a_end, b_end) - max(a_start, b_start) + 1

分析

双指针简单贪心匹配

ac code

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        cnt = 0
        players.sort()
        trainers.sort()
        n, m = len(players), len(trainers)
        i, j = 0, 0
        while i < n and j < m:
            if players[i] <= trainers[j]:
                cnt += 1
                i += 1
                j += 1
            else:
                j += 1
        
        return cnt

分析

逆向统计最大值（全部异或）
然后正向双指针记录30位的一个数组curr，一旦符合就挪动l这个样子
直到不符合为止继续挪动r
注意要用curr记录每个位的个数，方便挪动的时候增加删除
然后根据curr得出一个十进制的结果即可，大于1的只算1

Ac code

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        n = len(nums)
        target = [0] * n
        for i in range(n - 1, -1, -1):
            if i == n - 1:
                target[i] = nums[i]
            else:
                target[i] = target[i + 1] | nums[i]
        #print(target)
        
        ans = [1] * n
        curr = [0] * 30
        l = 0
        
        for r in range(n):
            tmp = bin(nums[r])[2:].zfill(30)
            for i, v in enumerate(tmp):
                if v == '1':
                    curr[i] += 1
            curr_num = 0
            for i in range(30):
                if curr[i] >= 1:
                    curr_num += pow(2, 29 - i)
            #print(l, r, curr_num, target[l], curr)
            while l <= r and curr_num == target[l]:
                #print(l, r, curr_num, curr)
                ans[l] = r - l + 1
                tmp = bin(nums[l])[2:].zfill(30)
                for i, v in enumerate(tmp):
                    if v == '1':
                        curr[i] -= 1
                curr_num = 0
                for i in range(30):
                    if curr[i] >= 1:
                        curr_num += pow(2, 29 - i)
                l += 1
        
        return ans

分析

我们要考虑最坏的情况
什么是最坏的情况呢？
1.先弄完全部负收益的交易，然后再来一个cost最大的cost的正收益的
2.先弄完差一个的全部负收益的交易，然后再来一个负收益的cost剪掉
我们可以先把总的负收益算出来
然后分两种情况遍历（正收益，负收益），看看在当前负收益的情况下加上一个cost哪个最大即可

Ac code

class Solution:
    def minimumMoney(self, transactions: List[List[int]]) -> int:
        # 最坏情况：
        # 在拿完所有负收益后，再来一个正收益的
        # 在拿完除当前负收益的其他负收益后，再来当前负收益的

        # 所有负收益的总和
        tot_bad = 0
        for cost, cashback in transactions:
            if cost > cashback:
                tot_bad += cost - cashback
        
        # 本质就是一个贪心greedy
        ans = 0
        for cost, cashback in transactions:
            # 如果是一个正收益的
            # 负收益总和 + 当前cost
            if cost <= cashback:
                ans = max(ans, tot_bad + cost)
            # 如果是一个负收益的
            # 负收益总和 - 当前负收益 + 当前cost
            else:
                ans = max(ans, tot_bad - (cost - cashback) + cost)
        
        return ans

总结

第一题恶心模拟，细节要注意
第三题，不能直接异或，要用30位数组记录，但多了30可以忍受的
第四题，怎么样的情况才是最坏的，先计算总的负收益，然后枚举交易，对于正收益的和负收益的要分类塔伦
正收益直接看cost，负收益的话要在总的负收益里面去掉当前的再看cost