1038. 从二叉搜索树到更大和树

1038. 从二叉搜索树到更大和树

class Solution:
    def __init__(self):
        self.sum_max = 0
        
    def bstToGst(self, root: TreeNode) -> TreeNode:
        self.search(root)
        return root

    def search(self, node):
        if node.right:
            self.search(node.right)
        self.sum_max += node.val
        node.val = self.sum_max
        if node.left:
            self.search(node.left)

1754. 构造字典序最大的合并字符串

1754. 构造字典序最大的合并字符串

class Solution:
    def largestMerge(self, word1: str, word2: str) -> str:
        merge = []
        i, j, n, m = 0, 0, len(word1), len(word2)
        while i < n or j < m:
            if i < n and word1[i:] > word2[j:]:
                merge.append(word1[i])
                i += 1
            else:
                merge.append(word2[j])
                j += 1
        return ''.join(merge)

1870. 准时到达的列车最小时速

1870. 准时到达的列车最小时速

import math


class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
        if hour <= len(dist) - 1:
            return -1
        if hour != int(hour):
            max_speed = math.ceil(max(dist[i] / (hour - int(hour)) for i in range(len(dist))))
        else:
            max_speed = int(max(dist))
        min_speed = 1
        while min_speed < max_speed:
            mid_speed = min_speed + (max_speed - min_speed) // 2
            h = self.calc_hour(dist, mid_speed)
            if h <= hour:
                max_speed = mid_speed
            else:
                min_speed = mid_speed + 1
        return min_speed

    def calc_hour(self, dist, speed):
        hour = 0
        ceil = math.ceil
        for i in range(len(dist) - 1):
            hour += ceil(dist[i] / speed)
        hour += dist[-1] / speed
        return hour

1385. 两个数组间的距离值

1385. 两个数组间的距离值

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        cnt = 0
        for i in arr1:
            for j in arr2:
                if abs(i - j) <= d:
                    break
            else:
                cnt += 1
        return cnt

1624. 两个相同字符之间的最长子字符串

1624. 两个相同字符之间的最长子字符串

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        c = {}
        for i in range(len(s)):
            if s[i] not in c:
                c[s[i]] = [0, i, i]
            c[s[i]][0] += 1
            c[s[i]][2] = i
        ans = -1
        for k, v in c.items():
            if v[0] < 2:
                continue
            ans = max(ans, v[2] - v[1] - 1)
        return ans

461. 汉明距离

461. 汉明距离

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        cnt = 0
        while x or y:
            cnt += int(x & 0b1 != y & 0b1)
            x >>= 1
            y >>= 1
        return cnt