Drafts of Leetcode July 2022

2022年7月力扣.

❗ 💛 241. 为运算表达式设计优先级

想法1: eval()可以直接计算带括号的表达式, 想办法加括号; 想法2: DP, 每次判断一个运算符, 但要储存一个运算了的子字符串集合, 否则可能会算重. (对于输入expression = "2*3-4*5", ((2*3)-(4*5)) = -14这一结果代表了两种运算顺序), 这里我每一次找的运算符是最先运算的, 从题解来看, 应该要找最后运算的运算符

Python/Golang 分治算法 - 江不知

class Solution:  # DC三步走, 解法非常优雅
    def diffWaysToCompute(self, input: str) -> List[int]:
        if input.isdigit():
            print('input is digit, return {}'.format([int(input)]))
            return [int(input)]  # 如果只有数字，直接返回
        res = []
        for i, char in enumerate(input):
            if char in ['+', '-', '*']:  # 1.分解：遇到运算符，计算左右两侧的结果集
                left = self.diffWaysToCompute(input[:i])  # 2.解决：diffWaysToCompute 递归函数求出子问题的解
                right = self.diffWaysToCompute(input[i+1:])
                for l in left:  # 3.合并：根据运算符合并子问题的解
                    for r in right:
                        if char == '+': res.append(l + r)
                        elif char == '-': res.append(l - r)
                        else: res.append(l * r)
                print('input: {}, i: {}, char: {}, left: {}, right: {}, res: {}'.format(input, i, char, left, right, res))
        return res

写两个例子例子: expression = "2-1-1", expression = "2*3-4*5", 便于理解.

input: expression = "2-1-1"
output: [0, 2]
explaination:
((2-1)-1) = 0 
(2-(1-1)) = 2

algorithm stdout:
input is digit, return [2]
input is digit, return [1]
input is digit, return [1]
input: 1-1, i: 1, char: -, left: [1], right: [1], res: [0]
input: 2-1-1, i: 1, char: -, left: [2], right: [0], res: [2]

input is digit, return [2]
input is digit, return [1]
input: 2-1, i: 1, char: -, left: [2], right: [1], res: [1]
input is digit, return [1]
input: 2-1-1, i: 3, char: -, left: [1], right: [1], res: [2, 0]

input: expression = "2*3-4*5"
output: [-34,-14,-10,-10,10]
explaination:
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

algorithm stdout:
input is digit, return [2]
input is digit, return [3]
input is digit, return [4]
input is digit, return [5]
input: 4*5, i: 1, char: *, left: [4], right: [5], res: [20]
input: 3-4*5, i: 1, char: -, left: [3], right: [20], res: [-17]
input is digit, return [3]
input is digit, return [4]
input: 3-4, i: 1, char: -, left: [3], right: [4], res: [-1]
input is digit, return [5]
input: 3-4*5, i: 3, char: *, left: [-1], right: [5], res: [-17, -5]
input: 2*3-4*5, i: 1, char: *, left: [2], right: [-17, -5], res: [-34, -10]

input is digit, return [2]
input is digit, return [3]
input: 2*3, i: 1, char: *, left: [2], right: [3], res: [6]
input is digit, return [4]
input is digit, return [5]
input: 4*5, i: 1, char: *, left: [4], right: [5], res: [20]
input: 2*3-4*5, i: 3, char: -, left: [6], right: [20], res: [-34, -10, -14]  # 注意这里由于左右两侧都是两个数字, 因此只会在结果中增加一项, DC的思想避免了排列的重复问题

input is digit, return [2]
input is digit, return [3]
input is digit, return [4]
input: 3-4, i: 1, char: -, left: [3], right: [4], res: [-1]
input: 2*3-4, i: 1, char: *, left: [2], right: [-1], res: [-2]
input is digit, return [2]
input is digit, return [3]
input: 2*3, i: 1, char: *, left: [2], right: [3], res: [6]
input is digit, return [4]
input: 2*3-4, i: 3, char: -, left: [6], right: [4], res: [-2, 2]
input is digit, return [5]
input: 2*3-4*5, i: 5, char: *, left: [-2, 2], right: [5], res: [-34, -10, -14, -10, 10]

🛠 str.isdigit()

Return True if all characters in the string are digits and there is at least one character, False otherwise. Digits include decimal characters and digits that need special handling, such as the compatibility superscript digits. This covers digits which cannot be used to form numbers in base 10, like the Kharosthi numbers. Formally, a digit is a character that has the property value Numeric_Type=Digit or Numeric_Type=Decimal. 如果字符串中的所有字符都是数字且至少有一个字符，则返回True，否则返回False。数字包括十进制字符和需要特殊处理的数字，如兼容上标数字。这包括那些不能用来组成以10为基数的数字的数字，如Kharosthi数字。从形式上看，数字是一个具有Numeric_Type=Digit或Numeric_Type=Decimal属性值的字符。

Python String isdigit() Method: 三种类型的示例

[Python/Java/TypeScript/Go] 区间DP - Benhao

❤ ==871. 最低加油次数==

在学PPO, 摸了.

🎯 第 300 场周赛 - NIO 蔚来

12 / 18, 1731 / 6792.

💛 556. 下一个更大元素 III

数学 - Carlos

class Solution:  # 从后到前遍历下标-i, 再遍历-i后的所有下标-j, 一旦发现-i对应的元素小, 就可以换, 之后把后面的元素倒序排列即可
    def nextGreaterElement(self, n: int) -> int:
        str_n = str(n)
        for i in range(2, len(str_n) + 1):
            temp = [(j, x) for j in range(1, i) if (x:=str_n[-j]) > str_n[-i]]
            if temp:
                j = min(temp, key=lambda x: x[1])[0]
                former = [str_n[-_] for _ in range(i, len(str_n) + 1)[::-1] if _ != i] + [str_n[-j]]
                latter = sorted([str_n[-i]] + [str_n[-_] for _ in range(1, i) if _ != j])
                return result if (result := eval(''.join(former + latter))) < 2 ** 31 else -1
        return -1

💚 1200. 最小绝对差

排序后np.diff - Carlos

class Solution:  # 暴力组合TLE
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        return sorted([[_[0], _[1]] if _[0] < _[1] else [_[1], _[0]] for _ in itertools.combinations(arr, 2) if abs(_[0] - _[1]) == v], key=lambda x: x[0]) if (v := min(abs(a - b) for a, b in itertools.combinations(arr, 2))) else []

import numpy as np
class Solution:  # 发现排序后结果只会在相邻的两元组中出现
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        diff = np.diff(arr)
        return [[arr[_], arr[_ + 1]] for _ in range(len(arr) - 1) if diff[_] == v] if (v := min(diff)) else []

[Python/Java/TypeScript/Go] 排序模拟 - Benhao

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        m, ans = inf, []
        for a, b in pairwise(sorted(arr)):
            if (cur := b - a) < m: m, ans = cur, [[a, b]]  # 若差更小, 则重置ans
            elif cur == m: ans.append([a, b])  # 若与差相等, 则在ans中添加元素
        return ans