周赛笔记230


一、统计匹配检索规则的物品数量

给你一个数组 items ,其中 items[i] = [typei, colori, namei] ,描述第 i 件物品的类型、颜色以及名称。

另给你一条由两个字符串 ruleKeyruleValue 表示的检索规则。

如果第 i 件物品能满足下述条件之一,则认为该物品与给定的检索规则 匹配

  • ruleKey == "type"ruleValue == typei
  • ruleKey == "color"ruleValue == colori
  • ruleKey == "name"ruleValue == namei
  • 统计并返回 匹配检索规则的物品数量
class Solution:
    def countMatches(self, items: List[List[str]], ruleKey: str, ruleValue: str) -> int:
        types=[i[0] for i in items]
        colors=[i[1] for i in items]
        names=[i[2] for i in items]
        ans=0
        if ruleKey == "type":
            ans+=sum([ruleValue==t for t in types])
        elif ruleKey == "color":
            ans+=sum([ruleValue==c for c in colors])
        else:
            ans+=sum([ruleValue==n for n in names])
        return ans

二、最接近目标价格的甜点成本

你打算做甜点,现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则:

  • 必须选择 一种 冰激凌基料。
  • 可以添加 一种或多种 配料,也可以不添加任何配料。
  • 每种类型的配料 最多两份

给你以下三个输入:

  • baseCosts ,一个长度为 n 的整数数组,其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
  • toppingCosts,一个长度为 m 的整数数组,其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
  • target ,一个整数,表示你制作甜点的目标价格。
    你希望自己做的甜点总成本尽可能接近目标价格 target 。

返回最接近 target 的甜点成本。如果有多种方案,返回 成本相对较低 的一种。

#暴力
class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:

        def dfs(k,m):
            if not m: 
                total.add(k)
                return
            dfs(k,m[1:])
            dfs(k+m[0],m[1:])
            dfs(k+2*m[0],m[1:])

        total=set()
        for base in baseCosts:
            dfs(base,toppingCosts)

        total=list(total)
        total.sort()

        ans=baseCosts[0]
        for a in total:
            if abs(a-target)<abs(ans-target):
                ans=a
        return ans

#真是好久没写代码了

三、通过最少操作次数使数组的和相等

给你两个长度可能不等的整数数组 nums1nums2 。两个数组中的所有值都在 16 之间(包含 16)。

每次操作中,你可以选择 任意 数组中的任意一个整数,将它变成 16 之间 任意 的值(包含 16)。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等,请返回 -1

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:

        t1,t2=sum(nums1),sum(nums2)
        if t1==t2: return 0
        if t1>t2: return self.minOperations(nums2, nums1)

        c1,c2=Counter(nums1),Counter(nums2)
        need=0
        diff=t2-t1
        for num in range(1,6):
            #print(num,diff)
            if num in c1:
                for _ in range(c1[num]):
                    need+=1
                    diff-=6-num
                    if diff<=0: break
            if diff<=0: break

            if 7-num in c2:
                for _ in range(c2[7-num]):
                    need+=1
                    diff-=6-num
                    if diff<=0: break
            if diff<=0: break

        return -1 if diff>0 else need

#6

四、车队 II

class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        res = []
        speed_pos_time =[[float('inf')] * 3]
        while cars:
            curr_pos, curr_speed = cars.pop()
            # print(curr_pos, curr_speed)
            # print(speed_pos_time)
            # print(res[::-1])
            if curr_speed <= speed_pos_time[0][0]:  # current speed is slower than the most slow speed int speed_list
                res.append(-1)
                speed_pos_time = [[curr_speed, curr_pos, float('inf')]]
            else:
                while speed_pos_time:
                    _s, _p, _t = speed_pos_time[-1]
                    if curr_speed <= _s:
                        speed_pos_time.pop()
                        continue
                    curr_time = (_p - curr_pos) / (curr_speed - _s)
                    if curr_time > _t:
                        speed_pos_time.pop()
                    else:
                        speed_pos_time.append([curr_speed, curr_pos, curr_time])
                        res.append(curr_time)
                        break
        return res[::-1]

# copy
class Solution:
    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
        def cal(car1, car2):
            if car1[1] <= car2[1]:
                return -1
            return (car2[0] - car1[0]) / (car1[1] - car2[1])

        queue = []
        n = len(cars)
        ans = [-1] * n

        mapping = {i: i - 1 for i in range(n)}

        for i in range(n - 1):
            tmp = cal(cars[i], cars[i + 1])
            if tmp != -1:
                heapq.heappush(queue, (tmp, i, i + 1))

        while queue:
            time, left, right = heapq.heappop(queue)
            if ans[left] != -1:
                continue
            ans[left] = time
            mapping[right] = mapping[left]
            if mapping[left] == -1:
                continue
            new = mapping[left]
            tmp = cal(cars[new], cars[right])
            if tmp != -1:
                heapq.heappush(queue, (tmp, new, right))

        return ans

# copy

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录