0208leetcode刷題5道python

1208

題目描述：
給你兩個長度相同的字串，s 和 t，
將 s 中的第 i 個字符變到 t 中的第 i 個字符需要 |s[i] - t[i]| 的開銷（開銷可能為 0），也就是兩個字符的 ASCII 碼值的差的絕對值，
用于變更字串的最大預算是 maxCost，在轉化字串時，總開銷應當小于等于該預算，這也意味著字串的轉化可能是不完全的，
如果你可以將 s 的子字串轉化為它在 t 中對應的子字串，則回傳可以轉化的最大長度，
如果 s 中沒有子字串可以轉化成 t 中對應的子字串，則回傳 0，

示例：

解答：

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        left = right = 0
        res = 0
        n = len(s)
        tmpcost = 0
        while right < n:
            tmpcost += abs(ord(s[right])-ord(t[right]))
            if tmpcost > maxCost:
                tmpcost -= abs(ord(s[left])-ord(t[left]))
                left += 1
            right += 1
            res = max(res, right - left)
        return res

劍指offer07

題目描述：
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，

示例：

解答：

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

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        loc=inorder.index(preorder[0])
        root=TreeNode(preorder[0])
        root.left=self.buildTree(preorder[1:loc+1],inorder[:loc])
        root.right=self.buildTree(preorder[loc+1:],inorder[loc+1:])
        return root

劍指offer55-I

題目描述：
輸入一棵二叉樹的根節點，求該樹的深度，從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度，

示例：

解答：

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        L=self.maxDepth(root.left)+1
        R=self.maxDepth(root.right)+1
        return max(L,R)

劍指offer55-II

題目描述：
輸入一棵二叉樹的根節點，判斷該樹是不是平衡二叉樹，如果某二叉樹中任意節點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹，

示例：

解答：

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

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.treeHeight(root)>=0
    
    def treeHeight(self,root):
        if not root:
            return 0
        leftHeight=self.treeHeight(root.left)
        rightHeight=self.treeHeight(root.right)
        if leftHeight>=0 and rightHeight>=0 and abs(leftHeight-rightHeight)<=1:
            return max(leftHeight,rightHeight)+1
        else:
            return -1

劍指offer57-II

題目描述：
輸入一個正整數 target ，輸出所有和為 target 的連續正整數序列（至少含有兩個數），
序列內的數字由小到大排列，不同序列按照首個數字從小到大排列，

示例：

解答：

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res=[]
        l,r=1,2
        while l<r:
            a=[]
            sum=(l+r)*(r-l+1)/2
            if sum<target:
                r+=1
            elif sum>target:
                l+=1
            else:
                for i in range(l,r+1):
                    a.append(i)
                res.append(a)
                l+=1
                r+=1
        return res