2487. 从链表中移除节点

2487. 从链表中移除节点

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        head = self.reverse(head)
        node = head
        max_val = head.val
        ans = ListNode()
        res = ans
        while node:
            if node.val >= max_val:
                max_val = node.val
                ans.next = node
                ans = ans.next
            node = node.next
        ans.next = None
        return self.reverse(res.next)

    def reverse(self, head):
        prev = None
        current = head
        while current is not None:
            next_node = current.next  # 保存当前节点的下一个节点
            current.next = prev  # 将当前节点的指针指向前一个节点
            prev = current  # 更新前一个节点为当前节点
            current = next_node  # 更新当前节点为下一个节点
        return prev  # 返回新的头节点

944. 删列造序

944. 删列造序

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        m = len(strs)
        n = len(strs[0])
        ans = 0
        for i in range(n):
            for j in range(m - 1):
                if strs[j][i] > strs[j + 1][i]:
                    ans += 1
                    break
        return ans

1003. 检查替换后的词是否有效

1003. 检查替换后的词是否有效

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i, c in enumerate(s):
            if c == 'c':
                if len(stack) >= 2 and stack[-1] == 'b' and stack[-2] == 'a':
                    stack.pop()
                    stack.pop()
                else:
                    return False
            else:
                stack.append(c)
        return not bool(stack)

class Solution:
    def isValid(self, s: str) -> bool:
        while s != '':
            tmp_s = s
            s = s.replace('abc', '')
            if tmp_s == s:
                return False
        return True

363. 矩形区域不超过 K 的最大数值和

363. 矩形区域不超过 K 的最大数值和

二分法，$O(m^2nlogn)$

import bisect


class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        max_val = float('-inf')
        for i in range(len(matrix)):  # 枚举上边界
            sum_ = [0 for i in range(len(matrix[0]))]  # 列和
            for j in range(i, len(matrix)):  # 枚举下边界
                for c in range(len(matrix[0])):
                    sum_[c] += matrix[j][c]

                sorted_sums = [0]
                s = 0  # 前缀和
                for c in sum_:  # 枚举左边界
                    s += c
                    index = bisect.bisect_left(sorted_sums, s - k)
                    if index < len(sorted_sums):
                        max_val = max(max_val, s - sorted_sums[index])
                    bisect.insort(sorted_sums, s)
        return max_val

二维前缀和，$O(m^2n^2)$

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                matrix[i][j] += matrix[i - 1][j] if i - 1 >= 0 else 0
                matrix[i][j] += matrix[i][j - 1] if j - 1 >= 0 else 0
                matrix[i][j] -= matrix[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else 0
        max_val = float('-inf')
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                val = self.calc(matrix, i, j, k)
                if val > max_val:
                    max_val = val
                if max_val == k:
                    return max_val
        return max_val

    def calc(self, matrix, i, j, k):
        max_val = float('-inf')
        for m in range(len(matrix) - i):
            for n in range(len(matrix[m]) - j):
                area = matrix[i + m][j + n]
                area -= matrix[i + m][j - 1] if i + m >= 0 and j - 1 >= 0 else 0
                area -= matrix[i - 1][j + n] if j + n >= 0 and i - 1 >= 0 else 0
                area += matrix[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else 0
                if max_val < area <= k:
                    max_val = area
        return max_val

78. 子集

78. 子集

迭代

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

    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.recursion(nums, 0)
        return self.ans

    def recursion(self, nums, cur):
        if cur == len(nums):
            self.ans.append(self.tmp[:])
            return
        self.tmp.append(nums[cur])
        self.recursion(nums, cur + 1)
        self.tmp.pop()
        self.recursion(nums, cur + 1)

二进制

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        num = 2 ** len(nums)
        ans = []
        for i in range(num):
            tmp = []
            for j in range(i.bit_length()):
                if (i >> j) & 0b1 == 0b1:
                    tmp.append(nums[j])
            ans.append(tmp)
        return ans