1460. 通过翻转子数组使两个数组相等

1460. 通过翻转子数组使两个数组相等

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        return sorted(target) == sorted(arr)

1606. 找到处理最多请求的服务器

1606. 找到处理最多请求的服务器

使用 heapq 实现优先队列。

import heapq
import bisect


class Solution:
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
        server_calc_times = {i: 0 for i in range(k)}
        server_busy_until = [[0, i] for i in range(k)]  # busy server
        available = []  # 可用 server
        heapq.heapify(server_busy_until)
        heapq.heapify(available)
        busiest_server = []
        busiest_server_calc_times = -1
        for i in range(len(arrival)):
            now_time = arrival[i]
            # 更新 available
            while True:
                if not server_busy_until:
                    break
                server_busy_until_pop = heapq.heappop(server_busy_until)
                if server_busy_until_pop[0] <= now_time:
                    heapq.heappush(available, i + (server_busy_until_pop[1] - i) % k)
                else:
                    heapq.heappush(server_busy_until, server_busy_until_pop)
                    break
            
            if available:
                server = heapq.heappop(available) % k
                server_calc_times[server] += 1
                heapq.heappush(server_busy_until, [now_time + load[i], server])
            else:
                continue
            if server_calc_times[server] > busiest_server_calc_times:
                busiest_server = [server]
                busiest_server_calc_times = server_calc_times[server]
            elif server_calc_times[server] == busiest_server_calc_times:
                busiest_server.append(server)
        return busiest_server

432. 全 O(1) 的数据结构

432. 全 O(1) 的数据结构

双向链表 + 哈希表

from typing import Dict


class Node:
    def __init__(self, key, cnt, prev_node=None, next_node=None):
        self.cnt = cnt
        self.keys = {key}
        self.prev_node: Node = prev_node
        self.next_node: Node = next_node


class AllOne:
    def __init__(self):
        self.hash_table: Dict[str: Node] = {}
        self.head = Node(key='', cnt=0)
        self.tail = Node(key='', cnt=float('inf'))
        self.head.next_node = self.tail
        self.tail.prev_node = self.head

    def del_empty_node(self, node: Node):
        node.prev_node.next_node = node.next_node
        node.next_node.prev_node = node.prev_node

    def inc(self, key: str) -> None:
        if key in self.hash_table:
            node = self.hash_table[key]
            node.keys.discard(key)
            new_cnt = node.cnt + 1
            if new_cnt == node.next_node.cnt:
                node.next_node.keys.add(key)
                self.hash_table[key] = node.next_node
            else:
                new_node = Node(key=key, cnt=new_cnt)
                new_node.next_node = node.next_node
                new_node.prev_node = node
                node.next_node = new_node
                new_node.next_node.prev_node = new_node
                self.hash_table[key] = new_node
            if not node.keys:
                self.del_empty_node(node)
        else:
            if self.head.next_node.cnt == 1:
                self.head.next_node.keys.add(key)
                self.hash_table[key] = self.head.next_node
            else:
                new_node = Node(key=key, cnt=1)
                new_node.next_node = self.head.next_node
                new_node.prev_node = self.head
                self.head.next_node = new_node
                new_node.next_node.prev_node = new_node
                self.hash_table[key] = new_node

    def dec(self, key: str) -> None:
        node = self.hash_table[key]
        node.keys.discard(key)
        new_cnt = node.cnt - 1
        if new_cnt != 0:
            if new_cnt == node.prev_node.cnt:
                node.prev_node.keys.add(key)
                self.hash_table[key] = node.prev_node
            else:
                new_node = Node(key=key, cnt=new_cnt)
                new_node.next_node = node
                new_node.prev_node = node.prev_node
                node.prev_node = new_node
                new_node.prev_node.next_node = new_node
                self.hash_table[key] = new_node
        else:
            self.hash_table.pop(key)
        if not node.keys:
            self.del_empty_node(node)

    def getMaxKey(self) -> str:
        return list(self.tail.prev_node.keys)[0]

    def getMinKey(self) -> str:
        return list(self.head.next_node.keys)[0]

598. 范围求和 II

598. 范围求和 II

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        row_min = m
        col_min = n
        for i in range(len(ops)):
            if ops[i][0] < row_min:
                row_min = ops[i][0]
            if ops[i][1] < col_min:
                col_min = ops[i][1]
        return row_min * col_min

2144. 打折购买糖果的最小开销

2144. 打折购买糖果的最小开销

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(reverse=True)
        ans = 0
        for i in range(len(cost)):
            if i % 3 == 0:
                ans += cost[i]
            elif i % 3 == 1:
                ans += cost[i]
        return ans