355. 设计推特

355. 设计推特

import json
from typing import List, Dict, Tuple
from collections import defaultdict
import heapq


class Twitter:
    def __init__(self):
        self.passage: Dict[int, List[Tuple[int, int]]] = defaultdict(list)
        self.user_follow: Dict[int, set] = defaultdict(set)
        self.time = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.passage[userId].append((tweetId, self.time))
        self.time += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        candidate_list = []
        candidate_list.extend(self.passage[userId])
        for follow in self.user_follow[userId]:
            candidate_list.extend(self.passage[follow][-10:])
        heapq.heapify(candidate_list)
        ans = heapq.nlargest(10, candidate_list, key=lambda x: x[1])
        return [ans[i][0] for i in range(len(ans))]

    def follow(self, followerId: int, followeeId: int) -> None:
        self.user_follow[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.user_follow[followerId].discard(followeeId)

1007. 行相等的最少多米诺旋转

1007. 行相等的最少多米诺旋转

from typing import List
from collections import Counter


class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        length = len(tops)
        tops_count = Counter(tops)
        bottoms_count = Counter(bottoms)
        total_count = sorted(list((tops_count + bottoms_count).items()), key=lambda x: x[1], reverse=True)
        top_change_times = 0
        bottom_change_times = 0
        min_change_times = float('inf')
        for i in range(len(total_count)):
            if total_count[i][1] < length:
                break
            for j in range(length):
                if tops[j] != total_count[i][0] and bottoms[j] != total_count[i][0]:
                    break
                if tops[j] != total_count[i][0]:
                    top_change_times += 1
                elif bottoms[j] != total_count[i][0]:
                    bottom_change_times += 1
            else:
                if min(top_change_times, bottom_change_times) < min_change_times:
                    min_change_times = min(top_change_times, bottom_change_times)
        return min_change_times if min_change_times != float('inf') else -1

1005. K 次取反后最大化的数组和

1005. K 次取反后最大化的数组和

import heapq


class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        for i in range(k):
            val = heapq.heappop(nums)
            heapq.heappush(nums, -val)
        return sum(nums)

2485. 找出中枢整数

2485. 找出中枢整数

class Solution:
    def pivotInteger(self, n: int) -> int:
        for i in range(n, 0, -1):
            if (n + i) * (n - i + 1) / 2 == (1 + i) * i / 2:
                return i
        return -1

1123. 最深叶节点的最近公共祖先

1123. 最深叶节点的最近公共祖先

class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        current_queue = [root]
        next_queue = []
        val_addr_map = {}
        father = {}
        while True:
            next_queue.clear()
            for i in range(len(current_queue)):
                val_addr_map[current_queue[i].val] = current_queue[i]
                if current_queue[i].left:
                    father[current_queue[i].left.val] = current_queue[i].val
                    next_queue.append(current_queue[i].left)
                if current_queue[i].right:
                    father[current_queue[i].right.val] = current_queue[i].val
                    next_queue.append(current_queue[i].right)
            if not next_queue:
                break
            current_queue = next_queue
            next_queue = []

        for i in range(len(current_queue)):
            current_queue[i] = current_queue[i].val
        current_queue = set(current_queue)
        while len(current_queue) != 1:
            new_queue = set()
            for node_val in current_queue:
                new_queue.add(father[node_val])
            current_queue = new_queue

        return val_addr_map[current_queue.pop()]