LCP 62. 交通枢纽

LCP 62. 交通枢纽

from collections import defaultdict


class Solution:
    def transportationHub(self, path: List[List[int]]) -> int:
        area: set = set()
        arrival = defaultdict(int)
        for i in range(len(path)):
            area.add(path[i][0])
            area.add(path[i][1])
        num_area = len(area)
        for i in range(len(path)):
            area.discard(path[i][0])
            arrival[path[i][1]] += 1

        if not area:
            return -1
        a = area.pop()
        if arrival[a] == num_area - 1:
            return a
        else:
            return -1

from collections import defaultdict


class Solution:
    def transportationHub(self, path: List[List[int]]) -> int:
        arrival: Dict[int, List] = defaultdict(list)
        start: set = set()
        lines: set = set()
        for i in range(len(path)):
            arrival[path[i][1]].append(path[i][0])
            start.add(path[i][0])
            lines.add(path[i][0])
            lines.add(path[i][1])
        for k, v in arrival.items():
            if len(v) == len(lines) - 1 and k not in start:
                return k
        return -1

2577. 在网格图中访问一个格子的最少时间

2577. 在网格图中访问一个格子的最少时间

两种方法：Dijkstra/二分答案+BFS（Python/Java/C++/Go）

import heapq


class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1
        dis = [[float('inf') for i in range(len(grid[j]))] for j in range(len(grid))]
        heap = [(0, 0, 0)]
        heapq.heapify(heap)
        while True:
            d, i, j = heapq.heappop(heap)
            if d > dis[i][j]:
                continue
            if i == len(grid) - 1 and j == len(grid[i]) - 1:
                return d
            neighbors = [[-1, 0], [1, 0], [0, -1], [0, 1]]
            for k in range(len(neighbors)):
                neighbors[k][0] += i
                neighbors[k][1] += j
            for x, y in neighbors:
                if 0 <= x < len(grid) and 0 <= y < len(grid[x]):
                    nd = max(d + 1, grid[x][y])
                    nd += (nd - x - y) % 2  # nd 必须和 x+y 同奇偶
                    if nd < dis[x][y]:
                        dis[x][y] = nd
                        heapq.heappush(heap, (nd, x, y))

447. 回旋镖的数量

447. 回旋镖的数量

from collections import defaultdict


class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for i in range(len(points)):
            cnt: Dict[int, int] = defaultdict(int)
            for j in range(len(points)):
                cnt[((points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2)] += 1
            for v in cnt.values():
                ans += v * (v - 1)
        return ans

1367. 二叉树中的链表

1367. 二叉树中的链表

from typing import Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque


class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        queue = deque([root])
        while queue:
            node = queue.pop()
            if self.dfs(node, head):
                return True
            if node.left:
                queue.appendleft(node.left)
            if node.right:
                queue.appendleft(node.right)
        return False

    def dfs(self, node: Optional[TreeNode], pointer: Optional[ListNode]):
        if node.val == pointer.val:
            if not pointer.next:
                return True
            ans = []
            if node.left:
                ans.append(self.dfs(node.left, pointer.next))
            if node.right:
                ans.append(self.dfs(node.right, pointer.next))
            return any(ans)
        else:
            return False

LCP 66. 最小展台数量

LCP 66. 最小展台数量

from collections import defaultdict


class Solution:
    def minNumBooths(self, demand: List[str]) -> int:
        has = defaultdict(int)
        for i in range(len(demand)):
            today_has = defaultdict(int)
            today_has.update(has)
            for j in range(len(demand[i])):
                if today_has[demand[i][j]] <= 0:
                    has[demand[i][j]] += 1
                else:
                    today_has[demand[i][j]] -= 1
        return sum(has.values())

2509. 查询树中环的长度

2509. 查询树中环的长度

向上寻找最近公共祖先

class Solution:
    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        ans = [0 for i in range(len(queries))]
        for i in range(len(queries)):
            node0 = queries[i][0]
            node1 = queries[i][1]
            res = 0
            while node0 != node1:
                if node0 > node1:
                    node0 //= 2
                else:
                    node1 //= 2
                res += 1
            ans[i] = res + 1
        return ans

二进制优化

class Solution:
    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        for i in range(len(queries)):
            node0 = queries[i][0]
            node1 = queries[i][1]
            if node0 < node1:
                node0, node1 = node1, node0
            d = node0.bit_length() - node1.bit_length()
            queries[i] = d + 2 * ((node0 >> d) ^ node1).bit_length() + 1
        return queries