1410. HTML 实体解析器

1410. HTML 实体解析器

他人的题解用的双指针

import re


class Solution:
    def entityParser(self, text: str) -> str:
        c = {'&quot;': '"', '&apos;': '\'', '&amp;': '&', '&gt;': '>', '&lt;': '<', '&frasl;': '/'}
        text = re.split(r'(&quot;|&apos;|&amp;|&gt;|&lt;|&frasl;)', text)
        for i in range(len(text)):
            if text[i] in c:
                text[i] = c[text[i]]
        return ''.join(text)

LCP 52. 二叉搜索树染色

LCP 52. 二叉搜索树染色

从最后的操作往前，遇到红色的直接加1并结束，遇到蓝色的直接结束。

import bisect

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:
        vals = []
        self.get_data(root, vals)
        ans = 0
        for i in range(len(ops) - 1, -1, -1):
            index0 = bisect.bisect_left(vals, ops[i][1])
            index1 = bisect.bisect_right(vals, ops[i][2])
            if ops[i][0] == 1:
                ans += index1 - index0
            vals[index0: index1] = []
        return ans

    def get_data(self, root: Optional[TreeNode], val: list):
        if root.left:
            self.get_data(root.left, val)
        val.append(root.val)
        if root.right:
            self.get_data(root.right, val)

304. 二维区域和检索 - 矩阵不可变

304. 二维区域和检索 - 矩阵不可变

一维前缀和

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        # self.matrix = matrix
        self.prefix_sum = [[0 for i in range(len(matrix[j]) + 1)] for j in range(len(matrix))]
        for i in range(len(matrix)):
            num = 0
            for j in range(len(matrix[i])):
                num += matrix[i][j]
                self.prefix_sum[i][j] = num
        # print(self.prefix_sum)

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        ans = 0
        for i in range(row1, row2 + 1):
            ans += self.prefix_sum[i][col2] - self.prefix_sum[i][col1 - 1]
        return ans

二维前缀和

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.pre_sum = [[0 for i in range(len(matrix[j]) + 1)] for j in range(len(matrix))]
        self.pre_sum.append([0 for i in range(len(matrix[0]) + 1)])
        for i in range(len(matrix)):
            num = 0
            for j in range(len(matrix[i])):
                num += matrix[i][j]
                self.pre_sum[i][j] = num + (self.pre_sum[i - 1][j] if i - 1 >= 0 else 0)

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        ans = self.pre_sum[row2][col2] - self.pre_sum[row2][col1 - 1] - self.pre_sum[row1 - 1][col2] + self.pre_sum[row1 - 1][col1 - 1]
        return ans

LCR 021. 删除链表的倒数第 N 个结点

LCR 021. 删除链表的倒数第 N 个结点

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length = 0
        pointer = head
        while pointer:
            length += 1
            pointer = pointer.next
        if length - n == 0:
            return head.next
        pointer = head
        for i in range(length - n - 1):
            pointer = pointer.next
        pointer.next = pointer.next.next
        return head

852. 山脉数组的峰顶索引

852. 山脉数组的峰顶索引

二分法

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        start = 0
        end = len(arr) - 1
        index = (start + end) // 2
        while not (arr[index - 1] < arr[index] and arr[index] > arr[index + 1]):
            if arr[index - 1] < arr[index] < arr[index + 1]:  # left
                start = index
                index = (start + end) // 2
            else:
                end = index
                index = (start + end) // 2
        return index