1691. 堆叠长方体的最大高度

1691. 堆叠长方体的最大高度 - 力扣（LeetCode）

动态规划

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        for cub in cuboids:
            cub.sort()
        cuboids.sort(reverse=True)
        height = [0 for i in range(len(cuboids))]
        for i in range(len(cuboids)):
            height[i] = cuboids[i][2]
            for j in range(i):
                if cuboids[i][1] <= cuboids[j][1] and cuboids[i][2] <= cuboids[j][2]:
                    height[i] = max(height[i], height[j] + cuboids[i][2])
        return max(height)


print(Solution().maxHeight([[50, 45, 20], [95, 37, 53], [45, 23, 12]]))
print(Solution().maxHeight([[7, 11, 17], [7, 17, 11], [11, 7, 17], [11, 17, 7], [17, 7, 11], [17, 11, 7]]))
print(Solution().maxHeight([[12, 76, 13], [68, 55, 30], [48, 85, 52], [91, 7, 41], [29, 65, 35]]))

LCR 069 山脉数组的峰顶索引

LCR 069. 山脉数组的峰顶索引 - 力扣（LeetCode）

二分法

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        start = 0
        end = len(arr)
        mid = int((end + start) / 2)
        while True:
            if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:
                break
            elif arr[mid - 1] < arr[mid] < arr[mid + 1]:
                start = mid
                mid = int((end + mid) / 2)
            elif arr[mid + 1] < arr[mid] < arr[mid - 1]:
                end = mid
                mid = int((mid + start) / 2)
        return mid

51. N 皇后

51. N 皇后

回溯法

import copy
from typing import List, Tuple


class Solution:
    def __init__(self):
        self.ans = []

    def solveNQueens(self, n: int) -> List[List[str]]:
        board = [['.' for i in range(n)] for j in range(n)]
        not_allow = set()
        self.solve(board, 0, not_allow)
        for i in range(len(self.ans)):
            for j in range(len(self.ans[i])):
                self.ans[i][j] = ''.join(self.ans[i][j])
        return self.ans

    def solve(self, board, now_row: int, not_allow_col: set):
        if now_row == len(board):
            self.ans.append(copy.deepcopy(board))
            return True
        for i in range(len(board)):
            if i in not_allow_col:
                continue
            board[now_row][i] = 'Q'
            not_allow_col.add(i)
            if not self.conflict(board, (now_row, i)):
                self.solve(board, now_row + 1, not_allow_col)
            not_allow_col.discard(i)
            board[now_row][i] = '.'


    def conflict(self, board: List[List[str]], pos: Tuple[int, int]):
        for i in range(len(board)):
            pos_r_t_x = pos[0] - i if pos[0] - i >= 0 else None
            pos_r_t_y = pos[1] + i if pos[1] + i < len(board) else None

            pos_l_t_x = pos[0] - i if pos[0] - i >= 0 else None
            pos_l_t_y = pos[1] - i if pos[1] - i >= 0 else None

            pos_r_b_x = pos[0] + i if pos[0] + i < len(board) else None
            pos_r_b_y = pos[1] + i if pos[1] + i < len(board) else None

            pos_l_b_x = pos[0] + i if pos[0] + i < len(board) else None
            pos_l_b_y = pos[1] - i if pos[1] - i >= 0 else None
            if i != 0:
                if pos_r_t_x is not None and pos_r_t_y is not None:
                    if board[pos_r_t_x][pos_r_t_y] == 'Q':
                        return True
                if pos_r_b_x is not None and pos_r_b_y is not None:
                    if board[pos_r_b_x][pos_r_b_y] == 'Q':
                        return True
                if pos_l_t_x is not None and pos_l_t_y is not None:
                    if board[pos_l_t_x][pos_l_t_y] == 'Q':
                        return True
                if pos_l_b_x is not None and pos_l_b_y is not None:
                    if board[pos_l_b_x][pos_l_b_y] == 'Q':
                        return True
        return False

面试题 10.11. 峰与谷

面试题 10.11. 峰与谷

排序+插入

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort(reverse=True)
        mid_pos = int(len(nums) / 2)
        if len(nums) % 2 == 0:
            mid_pos += 1
        insert_index = 1
        for i in range(len(nums) - 1, mid_pos - 1, -1):
            n = nums.pop()
            nums.insert(insert_index, n)
            insert_index += 2
        # print(nums)

2. 两数相加

2. 两数相加

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        prev_node = None
        root = None
        index = 0
        mark = 0
        while l1 or l2 or mark:
            l1_node_val = l1.val if l1 is not None else 0
            l2_node_val = l2.val if l2 is not None else 0
            val = l1_node_val + l2_node_val
            node = ListNode(((val + mark) % 10))
            mark = 1 if (val + mark) % 10 != (val + mark) else 0
            if index == 0:
                root = node
                prev_node = node
            else:
                prev_node.next = node
                prev_node = node
            index += 1
            l1 = l1.next if l1 is not None else None
            l2 = l2.next if l2 is not None else None
        return root