2304. 网格中的最小路径代价

2304. 网格中的最小路径代价

动态规划

class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        
        smallest_cost = [[float('inf') for i in range(len(grid[j]))] for j in range(len(grid))]
        for i in range(len(grid[0])):
            smallest_cost[0][i] = grid[0][i]
        for i in range(1, len(grid)):
            for j in range(len(grid[i])):
                for k in range(len(grid[i])):
                    smallest_cost[i][j] = min(moveCost[grid[i - 1][k]][j] + smallest_cost[i - 1][k], smallest_cost[i][j])
                smallest_cost[i][j] += grid[i][j]
        return min(smallest_cost[-1])

LCR 027. 回文链表

LCR 027. 回文链表

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        val = []
        pointer = head
        while pointer:
            val.append(pointer.val)
            pointer = pointer.next
        return val == val[::-1]

2006. 差的绝对值为 K 的数对数目

2006. 差的绝对值为 K 的数对数目

from collections import Counter


class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        nums_set = set(nums)
        nums_count = Counter(nums)
        ans = 0
        for item in nums_set:
            if item + k in nums_set:
                ans += nums_count[item] * nums_count[item + k]
        return ans

926. 将字符串翻转到单调递增

926. 将字符串翻转到单调递增

动态规划

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        dp0 = [0 for i in range(len(s) + 1)]
        dp1 = [0 for i in range(len(s) + 1)]
        for i in range(len(s)):
            if s[i] == '0':
                dp0[i] = dp0[i - 1]
                dp1[i] = min(dp1[i - 1], dp0[i - 1]) + 1
            else:
                dp0[i] = dp0[i - 1] + 1
                dp1[i] = min(dp1[i - 1], dp0[i - 1])
        return min(dp1[-2], dp0[-2])

2545. 根据第 K 场考试的分数排序

2545. 根据第 K 场考试的分数排序

class Solution:
    def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
        return sorted(score, key=lambda x: x[k], reverse=True)

LCP 72. 补给马车

LCP 72. 补给马车

class Solution:
    def supplyWagon(self, supplies: List[int]) -> List[int]:
        should_length = len(supplies) // 2
        supply = [supplies[i] + supplies[i + 1] for i in range(len(supplies) - 1)]
        while len(supplies) != should_length:
            min_index, min_value = min(enumerate(supply), key=lambda x: x[1])
            supplies[min_index] = min_value
            supplies.pop(min_index + 1)
            supply = [supplies[i] + supplies[i + 1] for i in range(len(supplies) - 1)]
        return supplies

79. 单词搜索

79. 单词搜索

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        word_c = set(word)
        board_c = set()
        for i in range(len(board)):
            for j in range(len(board[i])):
                board_c.add(board[i][j])
        if word_c - board_c:
            return False
        mark = [[False for j in range(len(board[i]))] for i in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[i])):
                if self.dfs(board, mark, i, j, word, 0):
                    return True
        return False

    def dfs(self, board, mark, x, y, word, index):
        if board[x][y] != word[index] or mark[x][y]:
            return False
        if index == len(word) - 1:
            return True
        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        for i in range(len(direction)):
            direction[i][0] += x
            direction[i][1] += y
            if 0 <= direction[i][0] < len(board) and 0 <= direction[i][1] < len(board[0]):
                if mark[direction[i][0]][direction[i][1]]:
                    continue
                mark[x][y] = True
                res = self.dfs(board, mark, direction[i][0], direction[i][1], word, index + 1)
                if res:
                    return True
                mark[x][y] = False
        return False