2397. 被列覆盖的最多行数

2397. 被列覆盖的最多行数

回溯法，未剪枝

import copy
from typing import List


class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        info: List[List[int]] = [[] for i in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 1:
                    info[i].append(j)
        return self.recursion(info, set(), 0, numSelect, 0)

    def recursion(self, info: List[List[int]], selected: set, index: int, able_select: int, max_row):
        # 不选当前行
        max_row_without_select = max_row
        for i in range(index + 1, len(info)):
            max_row_without_select = max(
                self.recursion(info, copy.deepcopy(selected), i, able_select, max_row),
                max_row_without_select)
        # 选择当前行
        for i in range(len(info[index])):
            if info[index][i] in selected:
                continue
            able_select -= 1
            selected.add(info[index][i])
        max_row_with_select = max_row
        if able_select >= 0:
            max_row_with_select += 1
            for i in range(index + 1, len(info)):
                max_row_with_select = max(
                    self.recursion(info, copy.deepcopy(selected), i, able_select, max_row + 1),
                    max_row_with_select)
        # print(index, max(max_row_with_select, max_row_without_select))
        return max(max_row_with_select, max_row_without_select)

383. 赎金信

383. 赎金信

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        c = Counter(magazine)
        for char in ransomNote:
            c[char] -= 1
            if c[char] < 0:
                return False
        return True

876. 链表的中间结点

876. 链表的中间结点

快慢指针

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p0 = head
        p1 = head
        while p1.next:
            for i in range(2):
                if p1.next:
                    p1 = p1.next
                else:
                    break
            p0 = p0.next
        return p0

581. 最短无序连续子数组

581. 最短无序连续子数组

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        new_nums = nums[:]
        new_nums.sort()
        start = None
        for i in range(len(nums)):
            if new_nums[i] != nums[i]:
                start = i
                break
        end = None
        for i in range(len(nums) - 1, -1, -1):
            if new_nums[i] != nums[i]:
                end = i
                break
        if start is None and end is None:
            return 0
        return end - start + 1