1631. 最小体力消耗路径

1631. 最小体力消耗路径

可使用二分+BFS，并查集，这里使用优先队列，注意剪枝。

import heapq


class Solution:
    def __init__(self):
        self.direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        heap = [(0, 0, 0)]  # val, x, y
        heapq.heapify(heap)
        diff = [[float('inf') for i in range(len(heights[j]))] for j in range(len(heights))]
        while True:
            if not heap:
                break
            val, x, y, = heapq.heappop(heap)
            if x == len(heights) - 1 and y == len(heights[0]) - 1:
                return val
            for i in range(len(self.direction)):
                next_x = x + self.direction[i][0]
                next_y = y + self.direction[i][1]
                if next_x < 0 or next_x >= len(heights) or next_y < 0 or next_y >= len(heights[next_x]):
                    continue
                new_val = max(val, abs(heights[x][y] - heights[next_x][next_y]))
                if new_val < diff[next_x][next_y]:
                    diff[next_x][next_y] = new_val
                    heapq.heappush(heap, (new_val, next_x, next_y))

1534. 统计好三元组

1534. 统计好三元组

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        cnt = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                for k in range(j + 1, len(arr)):
                    if abs(arr[i] - arr[j]) <= a and abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
                        cnt += 1
        return cnt

1054. 距离相等的条形码

1054. 距离相等的条形码

贪心+优先队列

from collections import Counter
import heapq

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        heap = []
        c = Counter(barcodes)
        for k, v in c.items():
            heap.append((-v, k))
        heapq.heapify(heap)
        index = 0
        last_val = None
        while heap:
            cnt, val = heapq.heappop(heap)
            cnt = -cnt
            if val == last_val:
                new_cnt, new_val = heapq.heappop(heap)
                heapq.heappush(heap, (-cnt, val))
                cnt, val = new_cnt, new_val
                cnt = -cnt
            barcodes[index] = val
            cnt -= 1
            if cnt != 0:
                heapq.heappush(heap, (-cnt, val))
            index += 1
            last_val = val
        return barcodes

59. 螺旋矩阵 II

59. 螺旋矩阵 II

from typing import List


class Solution:
    def __init__(self):
        self.direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]

    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[-1 for i in range(n)] for j in range(n)]
        x, y = 0, 0
        next_idx = 0
        for i in range(1, n * n + 1):
            matrix[x][y] = i
            x += self.direction[next_idx][0]
            y += self.direction[next_idx][1]
            if x < 0 or x >= n or y < 0 or y >= n or matrix[x][y] != -1:
                x -= self.direction[next_idx][0]
                y -= self.direction[next_idx][1]
                next_idx += 1
                if next_idx == 4:
                    next_idx = 0
                x += self.direction[next_idx][0]
                y += self.direction[next_idx][1]
        # for item in matrix:
        #     print(item)
        return matrix

89. 格雷编码

89. 格雷编码

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = [0b0, 0b1]
        for i in range(1, n):
            tmp = []
            for j in range(len(ans) - 1, -1, -1):
                tmp.append(1 << i | ans[j])
            ans.extend(tmp)
        return ans

96. 不同的二叉搜索树

96. 不同的二叉搜索树

from functools import cache


class Solution:
    def numTrees(self, n: int) -> int:
        return self.recursion(n)

    @cache
    def recursion(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        cnt = 0
        for i in range(n):
            left = self.recursion(i)
            right = self.recursion(n - i - 1)
            if right and left:
                cnt += left * right
            elif right:
                cnt += right
            elif left:
                cnt += left
        return cnt