2582. 递枕头

2582. 递枕头

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        x = time % (n + n - 2)
        if x <= n - 1:
            return x + 1
        else:
            return (n - 1) - (x - (n - 1)) + 1

309. 买卖股票的最佳时机含冷冻期

309. 买卖股票的最佳时机含冷冻期

状态机

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        n = len(prices)
        # dp[i][0]: 手上持有股票的最大收益
        # dp[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
        # dp[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
        dp = [[0] * 3 for _ in range(n)]
        dp[0][0] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i])
            dp[i][1] = dp[i - 1][0] + prices[i]
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2])
        return max(dp[n - 1][1], dp[n - 1][2])

1358. 包含所有三种字符的子字符串数目

1358. 包含所有三种字符的子字符串数目

双指针

from collections import defaultdict
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        ans = 0
        p0 = 0
        count = defaultdict(int)
        for p1 in range(len(s)):
            count[s[p1]] += 1
            while True:
                if count['a'] > 0 and count['b'] > 0 and count['c'] > 0:
                    ans += len(s) - p1
                    count[s[p0]] -= 1
                    p0 += 1
                else:
                    break
        return ans

面试题 16.13. 平分正方形

面试题 16.13. 平分正方形

要平分两个正方形，则平分线一定是两个正方形中点的连线

class Solution:
    def cutSquares(self, square1: List[int], square2: List[int]) -> List[float]:
        pos_square1 = [square1[0] + square1[2] / 2, square1[1] + square1[2] / 2]
        pos_square2 = [square2[0] + square2[2] / 2, square2[1] + square2[2] / 2]
        if pos_square1[0] == pos_square2[0]:
            return [
                pos_square1[0],
                min(square1[1], square2[1]),
                pos_square2[0],
                max(square1[1] + square1[2], square2[1] + square2[2])
            ]
        else:
            k = (pos_square2[1] - pos_square1[1]) / (pos_square2[0] - pos_square1[0])
            b = pos_square1[1] - pos_square1[0] * k
            res = [0, 0, 0, 0]
            if abs(k) > 1:  # 上边与下边相交
                res[1] = min(square1[1], square2[1])
                res[0] = (res[1] - b) / k
                res[3] = max(square1[1] + square1[2], square2[1] + square2[2])
                res[2] = (res[3] - b) / k
            else:  # 左边与右边相交
                res[0] = min(square1[0], square2[0])
                res[1] = res[0] * k + b
                res[2] = max(square1[0] + square1[2], square2[0] + square2[2])
                res[3] = res[2] * k + b
            if res[0] > res[2]:
                res[0], res[1], res[2], res[3] = res[2], res[3], res[0], res[1]
            return res

LCR 155. 将二叉搜索树转化为排序的双向链表

LCR 155. 将二叉搜索树转化为排序的双向链表

中序遍历

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

class Solution:
    def __init__(self):
        self.head = None
        self.prev_node = None

    def treeToDoublyList(self, root: 'Node'):
        if root is None:
            return None
        self.process(root)
        self.prev_node.right = self.head
        self.head.left = self.prev_node
        return self.head

    def process(self, node):
        if node is None:
            return
        self.process(node.left)
        if self.prev_node is not None:
            self.prev_node.right = node
            node.left = self.prev_node
            self.prev_node = node
        else:
            self.head = node
            self.prev_node = node
        self.process(node.right)

2466. 统计构造好字符串的方案数

2466. 统计构造好字符串的方案数

动态规划

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        dp = [0] * (high + 1)
        dp[0] = 1
        for i in range(high + 1):
            if i >= zero:
                dp[i] += dp[i - zero]
                dp[i] %= 10 ** 9 + 7
            if i >= one:
                dp[i] += dp[i - one]
                dp[i] %= 10 ** 9 + 7
        return sum(dp[low: high + 1]) % (10 ** 9 + 7)