2020-2-27 刷题记录

今天,又只做了三道.....

0X00 leetcode 做了 3 道

• leetcode 87. Scramble String
• leetcode 1. Two Sum
• leetcode 536. Construct Binary Tree from String

0X01 每道题的小小总结

87. Scramble String

这道题初看上去真的很难,但是理解动态规划的做法以后,就稍微简单一点了

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        # 区间型动态规划
        # 按长度去写
        if len(s1) != len(s2): return False
        if s1 == s2: return True
        m = len(s1)
        dp = [[[False for _ in range(m+1)] for _ in range(m)] for _ in range(m)]
        

        # len 1
        for x in range(m):
            for y in range(m):
                dp[x][y][1] = s1[x] == s2[y]
        

        for l in range(2, m+1):
            # 长度 - 长度要注意!
            # 长度 - 长度 一般要加 1
            for x in range(m - l + 1):
                for y in range(m - l + 1):
                    for k in range(1, l):
                        if dp[x][y][k] and dp[x+k][y+k][l-k]:
                            dp[x][y][l] = True
                            break
                        
                        if dp[x][y + l - k][k] and dp[x+k][y][l-k]:
                            dp[x][y][l] = True
                            break
         

        return dp[0][0][m]

简单来说就是:

dp[i][j][k] 代表着 s[i:i+k] 和 s[j:j+k] 是不是 Scramble String

判断标准就是遍历子串

所有的子串对中有一个子串对满足 Scramble String 那该串就是 Scramble String

1. Two Sum

....这个题坑在重复元素的处理

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        m = {}
        for idx, n in enumerate(nums):
            if n not in m: m[n] = [idx]
            else: m[n].append(idx)
            reset = target - n
            if reset in m:
                if reset == n:
                    if len(m[n]) > 1: return [m[n][0], m[n][1]]
                    else: continue
                return [m[n][0], m[reset][0]]

536. Construct Binary Tree from String

我*** 这个题

卡了我好久,唉,太菜了,,,,也没啥,,做之前要考虑清楚

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def str2tree(self, s: str) -> TreeNode:
        if s == "": return None
        def construct(x, y):
            if x > y: return None
            idx = s.find("(", x, y)
            if idx == -1:
                root = TreeNode(s[x:y])
                return root
            root = TreeNode(s[x:idx])

            stack = []
            rightIdx = y
            for i in range(idx, y):
                if s[i] == "(":
                    stack.append(s[i])
                elif s[i] == ")":
                    stack.pop()
                    if len(stack) == 0:
                        rightIdx = i
                        break

            root.left = construct(idx+1, rightIdx)
            root.right = construct(rightIdx+2, y-1)
            return root
        
        return construct(0, len(s))