leetcode熱題 HOT 100刷題筆記（2）

leetcode熱題 HOT 100第二部分題解灰署，按照題目序號排列润樱。

二叉樹的層序遍歷

正常的層序遍歷操作即可瑰剃，但是需要記錄每一層節(jié)點的數(shù)量歪沃。

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        queue = [root]
        res = []
        while(queue):
            length = len(queue)
            temp = []
            for _ in range(length):
                node = queue.pop(0)
                temp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(temp)
        return res

二叉樹的最大深度

非常簡單的遞歸操作臣淤。

# 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
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

從前序與中序遍歷序列構(gòu)造二叉樹

常規(guī)題橄霉，需要借助前序遍歷將中序遍歷一分為二，然后進行遞歸操作邑蒋。但凡是涉及到遞歸函數(shù)姓蜂，我們就得設(shè)計好遞歸函數(shù)的參數(shù)和返回值。函數(shù)的返回值為根節(jié)點医吊，函數(shù)的參數(shù)為三個钱慢，一個為根節(jié)點在前序序列中的索引，剩下兩個分別為左右邊界卿堂，用來確定對應(yīng)的中序序列的范圍束莫。由于是重建二叉樹，因此每次都需要創(chuàng)建一個新的節(jié)點草描，并且還需要主要根節(jié)點在前序序列中的位置览绿。

# 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:
        Dict = {}
        for num in preorder:
            Dict[num] = inorder.index(num)
        def recursion(index, l, r):
            if l > r:
                return
            root = TreeNode()
            root.val = preorder[index]
            temp = Dict[preorder[index]]
            root.left = recursion(index + 1, l, temp - 1)
            root.right = recursion(index + temp - l + 1, temp + 1, r)
            return root
        res = recursion(0, 0, len(inorder) - 1)
        return res

二叉樹展開為鏈表

題目要求直接對鏈表進行修改，注意最終修改完成的鏈表應(yīng)該是先序遍歷的順序來的穗慕，并且每個節(jié)點的左節(jié)點都為空饿敲。如果我們結(jié)果按照左-根-右的順序來操作的話，就直接丟失右子樹的信息逛绵。因此我們需要按照右=根-左的順序來怀各，具體實現(xiàn)的時候需要用一個全局變量來保存前一個子節(jié)點。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.pre = None
        def dfs(root):
            if not root:
                return None
            dfs(root.right)
            dfs(root.left)
            root.right = self.pre
            root.left = None
            self.pre = root
        dfs(root)

買賣股票的最佳時機

簡單的DP术浪。

解法1：暴力（超時）
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [0]*len(prices)
        res = 0
        for i in range(1, len(prices)):
            for j in range(0, i):
                dp[i] = max(dp[i], prices[i] - prices[j])
            res = max(res, dp[i])
        return res

解法2：
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [0]*len(prices)
        res = 0
        for i in range(1, len(prices)):
            if dp[i-1] < 0:
                dp[i] = prices[i] - prices[i-1]
            else:
                dp[i] = prices[i] - prices[i-1] + dp[i-1]
            res = max(res, dp[i])
        return res

二叉樹中的最大路徑和

每次在選擇路徑的時候都要優(yōu)先選擇較大的瓢对，對于節(jié)點a這里可以設(shè)計一個遞歸函數(shù)，返回的是max(a.left.val, a.right.val) + a.val添吗，當然還得考慮到要大于0，因此最終返回的是max(max(a.left.val, a.right.val) + a.val, 0)份名，每一次選擇完路徑后需要計算當前節(jié)點取得的最大值：當前節(jié)點+左子樹+右子樹碟联。每一次遞歸都要計算一下妓美，整個遞歸結(jié)束后就可以得到全局的最大值了。整個的遞歸函數(shù)表示的是當前節(jié)點是往左走鲤孵，還是往右走壶栋，還是都不要。最終的結(jié)果是通過全局變量來保存的普监，每次遞歸的時候都更新一下贵试。

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

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

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.maxRoute = -inf
        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            self.maxRoute = max(self.maxRoute, root.val + left + right)
            return max(max(left + root.val, right + root.val), 0)
        dfs(root)
        return self.maxRoute

最長連續(xù)序列

這一題要求時間復(fù)雜度為O(n)，因此很自然的想法是需要利用額外的空間來進行加速查找凯正，我們可以將原數(shù)組變成一個集合毙玻，然后通過判斷i，i+1廊散，i+2這樣的方式來進行判斷桑滩，這樣的話就可以讓判斷過程變成O（1）復(fù)雜度，注意這里還有一個優(yōu)化的技巧允睹，如果一個當前元素-1已經(jīng)在集合李出現(xiàn)過的話运准，那么就可以跳過這個元素，直接進行下一步判斷缭受，因為這種情況一定在之前就已經(jīng)判斷過了胁澳。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res = 0
        A = set(nums)
        for num in nums:
            if num - 1 not in A:
                temp = 1
                while((num + 1) in A):
                    temp += 1
                    num += 1
                res = max(res, temp)
        return res

只出現(xiàn)一次的數(shù)字

異或操作即可。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res = res ^ num
        return res

單詞拆分

直觀的想法還是用DFS米者，但是需要進行剪枝韭畸，同樣我們需要思考一下遞歸過程中重復(fù)運算的情況，比如我們在前面的遞歸中已經(jīng)知道了某個字串是不符合題意的塘雳，那么在后序的過程中我們只需要判斷一下即可陆盘，不需要進行遞歸運算了。遞歸需要設(shè)計好參數(shù)和返回值败明。

解法1：超時
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        length = len(s)
        self.flag = 0
        def dfs(c):
            if not c:
                self.flag = 1
                return 
            for i in range(len(c)):
                if self.flag == 1:
                    return
                if c[:i+1] in wordDict:
                    dfs(c[i+1:])
        dfs(s)
        if self.flag == 1:
            return True
        else:
            return False

解法2：
我們需要使用一個字典來保存中間狀態(tài)隘马，因此我們需要設(shè)計好返回值，對于一個字符串妻顶，我們在每一個位置上進行切分酸员，如果中間有一種可以那么我們就返回True，如果所有的可能都不行讳嘱，那么最后就返回False幔嗦，中間的狀態(tài)用Dict來保存，需要注意遞歸出口沥潭，當為空的時候就返回True邀泉。整個遞歸函數(shù)dfs(c, Dict)表示單詞c是否可拆分，可拆分就返回True，不可拆分就返回False汇恤，Dict用來存儲中間單詞的狀態(tài)（可拆分或者不可拆分）庞钢。
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        def dfs(c, Dict):
            if not c:
                return True
            for i in range(len(c)):
                if c[:i+1] in wordDict:
                    if c[i+1:] not in Dict:
                        res2 = dfs(c[i+1:], Dict)
                        Dict[c[i+1:]] = res2
                    else:
                        res2 = Dict[c[i+1:]]
                    if res2:
                        return True
            Dict[c] = False
            return False

        return dfs(s, {})

解法2的優(yōu)化寫法，這種寫法更符合記憶化搜索的基本思路：
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        def dfs(c, Dict):
            if not c:
                return True
            if c in Dict:
                return Dict[c]
            else:
                for i in range(len(c)):
                    if c[:i+1] in wordDict:
                        res2 = dfs(c[i+1:], Dict)
                        Dict[c[i+1:]] = res2
                        if res2:
                            return True
                Dict[c] = False
                return False

        return dfs(s, {})

環(huán)形鏈表

使用一個額外的數(shù)據(jù)結(jié)構(gòu)來判斷是否訪問到了重復(fù)的鏈表節(jié)點因谎。

使用快慢指針讓其中一個節(jié)點先跑一步即可基括，并且讓快指針移動速度更快，判斷是否為空的時候只需要對快指針進行判斷即可财岔。

解法1：
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        A = set()
        start = head
        while(start):
            if start not in A:
                A.add(start)
            else:
                return True
            start = start.next
        return False

解法2：
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        slow = head
        fast = head.next
        while(slow != fast):
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

環(huán)形鏈表 II

先找環(huán)风皿，再去找相交點，這一題在287題的第二種解法中做過匠璧⊥┛睿快慢指針相遇是非常簡單的，因為跑的快的一定可以追上跑得慢的患朱，我們可以根據(jù)環(huán)內(nèi)相遇的點和入環(huán)的第一個點鲁僚，將整個鏈表分成3段，之后我們可以證明裁厅，將快指針重新放在開頭冰沙，可以保證快慢指針一定可以在入環(huán)的第一個節(jié)點相遇，但是這題需要注意执虹，由于我的快指針比慢指針多跑一步拓挥，因此我們需要重新將快指針放置在第一個節(jié)點之前。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return None
        slow = head
        fast = head.next
        while(fast and fast.next and slow != fast):
            slow = slow.next
            fast = fast.next.next
        if slow != fast:
            return None
        fast = None #一定要注意這個初始化條件袋励，保證快指針走的路徑為慢指針的兩倍侥啤。
        while(slow != fast):
            slow = slow.next
            if fast:
                fast = fast.next
            else:
                fast = head
        return slow

LRU緩存機制

LRU（最近最少使用）算法是操作系統(tǒng)里一種常用的算法。該算法要求在O（1）的時間內(nèi)進行讀取茬故，因此需要使用字典這個數(shù)據(jù)結(jié)構(gòu)盖灸，該算法要求記錄哪些元素最近被更新過，因此每次在更新數(shù)據(jù)之后需要把更新過后的數(shù)據(jù)放在最近的位置磺芭，并且要求在O（1）的時間內(nèi)完成這一操作赁炎，因此這里需要使用到雙向鏈表這樣的數(shù)據(jù)結(jié)構(gòu)。將兩者結(jié)合起來：我們需要用到一個字典加上雙向鏈表的結(jié)構(gòu)钾腺。字典中的基本結(jié)構(gòu)（key徙垫，value）value表示一個鏈表節(jié)點，而鏈表節(jié)點結(jié)構(gòu)為：key, value, pre, next放棒。這里的value表示節(jié)點存儲的值姻报，pre表示指向前一個節(jié)點的指針，next表示指向后一個節(jié)點的指針间螟，key和字典里的key是一樣的吴旋，需要特別注意這個key损肛，鏈表節(jié)點里還要存儲key的原因：在進行刪除操作的時候是先找到對應(yīng)的鏈表節(jié)點來進行刪除，最終刪除的時候是需要刪除字典里的鍵值對荣瑟，因此在鏈表節(jié)點里也保存了對應(yīng)的key荧关。
參考：https://leetcode-cn.com/problems/lru-cache/solution/shu-ju-jie-gou-fen-xi-python-ha-xi-shuang-xiang-li/

這一題的難點在于鏈表的添加和刪除操作，記得不能隨意調(diào)換相應(yīng)的步驟褂傀。
class LinkedNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.Dict = {}
        self.head = LinkedNode()
        self.tail = LinkedNode()
        self.head.next = self.tail
        self.tail.pre = self.head

    def move_node_to_tail(self, key: int):
        node = self.Dict[key]
        node.pre.next = node.next
        node.next.pre = node.pre

        node.pre = self.tail.pre
        node.next = self.tail
        self.tail.pre.next = node
        self.tail.pre = node

    def get(self, key: int) -> int:
        if key in self.Dict:
            self.move_node_to_tail(key)
            return self.Dict[key].value
        else:
            return -1


    def put(self, key: int, value: int) -> None:
        if key in self.Dict:
            self.Dict[key].value = value
            self.move_node_to_tail(key)
        else:
            if len(self.Dict) == self.capacity:
                self.Dict.pop(self.head.next.key)
                self.head.next = self.head.next.next 
                self.head.next.pre = self.head #這一步需要注意
            node = LinkedNode(key, value)
            self.Dict[key] = node
            node.pre = self.tail.pre #這四步需要注意，不能隨意調(diào)換
            node.next = self.tail
            self.tail.pre.next = node
            self.tail.pre = node

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

排序鏈表

鏈表的排序?qū)儆阪湵淼幕静僮骷忧冢话阌脷w并排序仙辟。這里的代碼我是參考的這個：
https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-zed-65536/ 寫的比較清晰。在合并兩個節(jié)點的時候使用了一個小技巧：添加了頭節(jié)點鳄梅，這樣就不用考慮兩個鏈表中首節(jié)點的大小了叠国。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head: ListNode) -> ListNode:

        def mergesort(head):
            if not head or not head.next:
                return head
            slow = head
            fast = head.next
            while(fast and fast.next):
                slow = slow.next
                fast = fast.next.next
            l1 = head
            l2 = slow.next
            slow.next = None
            left = mergesort(l1)
            right = mergesort(l2)
            return merge(left, right)

        def merge(l1, l2):
            p = ListNode()
            temp = p
            while(l1 and l2):
                if l1.val < l2.val:
                    temp.next = l1
                    l1 = l1.next
                else:
                    temp.next = l2
                    l2 = l2.next
                temp = temp.next
            if l1:
                temp.next = l1
            else:
                temp.next = l2
            return p.next

        return mergesort(head)

最小棧

要求在常數(shù)時間內(nèi)取得最小值，那這個棧就必須是有順序的戴尸。但是原有棧的結(jié)構(gòu)不能破壞粟焊，因此可以使用一個備用的棧。在具體實現(xiàn)的代碼的時候需要注意棧是否為空孙蒙。

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack_A = []
        self.stack_B = []


    def push(self, x: int) -> None:
        self.stack_A.append(x)
        if not self.stack_B:
            self.stack_B.append(x)
        elif x <= self.stack_B[-1]:
            self.stack_B.append(x)

    def pop(self) -> None:
        if self.stack_A:
            res = self.stack_A.pop()
            if res == self.stack_B[-1]:
                self.stack_B.pop()

    def top(self) -> int:
        if self.stack_A:
            return self.stack_A[-1]
        else:
            return None

    def getMin(self) -> int:
        if self.stack_B:
            return self.stack_B[-1]
        else:
            return None



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

乘積最大子數(shù)組

直觀看上去應(yīng)該是DP项棠。
并且與最大子序列和類似，但不同的是挎峦，一個負數(shù)乘以一個負數(shù)可能會變成正數(shù)香追，同樣一個正數(shù)乘以負數(shù)可能會變成一個負數(shù)，因此我們還需要維護一個最小的狀態(tài)轉(zhuǎn)移方程：
$maxdp[i] = max(nums[i], maxdp[i-1]*nums[i], mindp[i-1]*nums[i])$
$mindp[i] = min(nums[i], mindp[i-1]*nums[i], maxdp[i-1]*nums[i]$
這里同樣有一個優(yōu)化的技巧：狀態(tài)壓縮dp坦胶，用兩個變量只保存前一輪的狀態(tài)透典，這樣可以減少空間復(fù)雜度。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        minNum = nums[0]
        maxNum = nums[0]
        ans = nums[0]
        for i in range(1, len(nums)):
            max1 = maxNum
            min1 = minNum
            maxNum = max(max(nums[i], nums[i]*max1), nums[i]*min1)
            minNum = min(min(nums[i], nums[i]*min1), nums[i]*max1)
            ans = max(ans, maxNum)
        return ans

相交鏈表

由于鏈表的長度不一致需要手動讓兩個鏈表在相同的位置節(jié)點來進行比較顿苇。比較笨的辦法就是統(tǒng)計兩個鏈表的長度峭咒，然后計算出兩個鏈表的長度差m，最后讓長的鏈表先走m步纪岁，再一起比較即可凑队。官方題解給了一種比較好的方法，讓先走到終點的鏈表轉(zhuǎn)到另一個鏈表上蜂科，然后再一起比較顽决。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        l1 = headA
        l2 = headB
        while(l1 != l2):
            if l1:
                l1 = l1.next
            else:
                l1 = headB
            if l2:
                l2 = l2.next
            else:
                l2 = headA
        return l1

多數(shù)元素

摩爾投票法

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        for num in nums:
            if count == 0:
                res = num
            if num == res:
                count += 1
            else:
                count -= 1
        return res

打家劫舍

需要寫出狀態(tài)轉(zhuǎn)移方程，dp[i] = max(dp[i-1], dp[i-2] + nums[i])导匣，需要注意初始化條件才菠。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0], nums[1])
        dp = [0]*len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        res = 0
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
            res = max(res, dp[i])
        return res

島嶼數(shù)量

傳統(tǒng)的DFS，在走完一個島嶼后將其標記成2贡定，這種題與求不同路徑不一樣赋访，這種題只需要走完即可，而求不同路徑的問題中，同一條路徑需要進行標記蚓耽，防止重復(fù)走渠牲，但是在不同的路徑中卻要標記回來。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        length  = len(grid)
        width = len(grid[0])
        flags = [[0]*width for i in range(length)]
        def dfs(x, y):
            if x < 0 or x >length - 1 or y < 0 or y > width - 1:
                return
            if grid[x][y] == '0':
                return
            if flags[x][y] == 0:
                flags[x][y] = 1
                grid[x][y] = '2'
                for delta_x, delta_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    dfs(x + delta_x, y + delta_y)
            
        count = 0
        for i in range(length):
            for j in range(width):
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1
        return count

反轉(zhuǎn)鏈表

鏈表的基本操作步悠。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        newHead = None
        while(head):
            temp = head.next
            head.next = newHead
            newHead = head
            head = temp
        return newHead

課程表

這一題是典型的拓撲排序签杈，由于需要按順序輸出所有的節(jié)點，因此最好使用BFS來遍歷全圖鼎兽，維護一個隊列答姥，將入度為0的節(jié)點全部入隊列，再將入度為0的節(jié)點出隊列谚咬，然后將其相鄰的節(jié)點入度全部都減1鹦付，如果有入度為0的節(jié)點則入隊列即可，如果所有節(jié)點都可以正常輸出則說明可以完成所有課程的學(xué)習(xí)择卦。這題的重點是如何使用合適的數(shù)據(jù)結(jié)構(gòu)來存儲圖的信息敲长，如果只需要使用拓撲排序的話，我們用兩個表就可以完成以上任務(wù)秉继，一個表用來存儲每一個節(jié)點的入度信息祈噪，另一個表用來存儲每一個節(jié)點的后繼節(jié)點信息。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0]*numCourses
        successor = [[] for _ in range(numCourses)]
        for cur, pre in prerequisites:
            indegree[cur] += 1
            successor[pre].append(cur)
        queue = []
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        while(queue):
            temp = queue.pop(0)
            numCourses -= 1
            for node in successor[temp]:
                indegree[node] -= 1
                if indegree[node] == 0:
                    queue.append(node)
        if numCourses == 0:
            return True
        else:
            return False

實現(xiàn) Trie (前綴樹)

高級數(shù)據(jù)結(jié)構(gòu)尚辑，前綴樹也叫字典樹钳降，字典樹的深度取決于最大的單詞長度，關(guān)于字典樹的詳細介紹：參考 https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/ 比較好理解腌巾。在python中字典樹就一個嵌套的字典遂填。包括像決策樹在python的具體實現(xiàn)也是一個嵌套字典。字典樹的具體實現(xiàn)比較簡單澈蝙，但還是有一些細節(jié)需要注意吓坚，在插入單詞的時候需要在最末端加上終止符，判斷一個字符串是否是前綴很簡答灯荧，但是在查找單詞的時候需要注意礁击，在末端一定要存在相應(yīng)的終止符才說明有這個完整的單詞搂漠，否者只是前綴盯另。

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lookup = {}
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        Tree = self.lookup
        for c in word:
            if c not in Tree:
                Tree[c] = {}
            Tree = Tree[c]
        Tree['#'] = '#'
        
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        Tree = self.lookup
        for c in word:
            if c not in Tree:
                return False
            Tree = Tree[c]
        if '#' not in Tree:
            return False
        return True

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        Tree = self.lookup
        for c in prefix:
            if c not in Tree:
                return False
            Tree = Tree[c]
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

數(shù)組中的第K個最大元素

標準的topk問題蓄拣，排序或者建一個堆牡辽。python提供的庫函數(shù)要比手寫的快排要快，這一點要注意∨菲福現(xiàn)在有兩種辦法忍捡，一種是直接手寫排序形葬，另一種是采用類快排擦秽，這樣會快一點码荔。
快排參考：https://blog.csdn.net/elma_tww/article/details/86164674

建立一個大頂堆漩勤，并且保證堆的元素個數(shù)不超過length - k + 1個，但這個方法不是通用的缩搅，還是維護一個小頂堆最好越败，元素數(shù)量不超過k個。注意我們在求前k個最大元素的時候硼瓣，是需要維護一個最小堆的究飞，在求前k個最小元素的時候，需要維護一個最大堆堂鲤，這一點需要清楚噪猾。求第k個最小元素，也可以維護最小堆筑累，保證堆的元素個數(shù)不超過length - k + 1個。建立堆的時間復(fù)雜度為Nlog(k)丝蹭，k為堆的元素個數(shù)慢宗。，當然這個復(fù)雜度只是一個近似的表示奔穿，還有一些常數(shù)項沒有寫出來镜沽。

堆是一顆滿二叉樹，通過索引可以將數(shù)組和堆對應(yīng)起來贱田。第i個數(shù)是根節(jié)點缅茉，第2i個數(shù)是其左節(jié)點，第2i+1個數(shù)是其右節(jié)點男摧。

從頭開始建一個堆和把一個現(xiàn)成的數(shù)組變成堆是不一樣的：數(shù)組變成堆是從第一個非葉子節(jié)點（數(shù)組中的最后一個數(shù)）開始自底向上遞歸蔬墩；已經(jīng)建成了堆，又來一個數(shù)耗拓，就先加在最后面拇颅，然后自底向上遞歸。

解法1：
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[-k]

解法2：
from heapq import *
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heappush(heap, -num)
            if len(heap) > len(nums) + 1 - k:
                heappop(heap)
        return -heappop(heap)

解法3：
from heapq import *
import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def qucksort(nums, l, r):
            if l >= r: #這里有等號乔询，因為一個數(shù)是不需要排序的
                return
            else:
                rand = random.randint(l, r) #改進樟插，可以讓速度變快
                nums[l], nums[rand] = nums[rand], nums[l]
                temp = nums[l]
                i = l
                j = r
                while(i < j):
                    while(i < j and temp < nums[j]):
                        j -= 1
                    nums[i] = nums[j]
                    while(i < j and temp >= nums[i]):
                        i += 1
                    nums[j] = nums[i]
                nums[i] = temp
                qucksort(nums, l, i-1)
                qucksort(nums, i+1, r)
        qucksort(nums, 0, len(nums)-1)
        return nums[-k]

解法4：
類快排：
第k小
from heapq import *
import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        self.res = 0
        def qucksort(nums, l, r):
            if l > r: #注意這里沒有等號
                return
            else:
                rand = random.randint(l, r)
                nums[l], nums[rand] = nums[rand], nums[l]
                temp = nums[l]
                i = l
                j = r
                while(i < j):
                    while(i < j and temp < nums[j]):
                        j -= 1
                    nums[i] = nums[j]
                    while(i < j and temp >= nums[i]):
                        i += 1
                    nums[j] = nums[i]
                nums[i] = temp
                if i == k-1: #注意這里
                    self.res = nums[i]
                    return
                elif i > k-1:
                    qucksort(nums, l, i-1)
                else:
                    qucksort(nums, i+1, r)
        qucksort(nums, 0, len(nums)-1)
        return self.res

第k大
from heapq import *
import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        self.res = 0
        def qucksort(nums, l, r):
            if l > r:
                return
            else:
                rand = random.randint(l, r)
                nums[l], nums[rand] = nums[rand], nums[l]
                temp = nums[l]
                i = l
                j = r
                while(i < j):
                    while(i < j and temp < nums[j]):
                        j -= 1
                    nums[i] = nums[j]
                    while(i < j and temp >= nums[i]):
                        i += 1
                    nums[j] = nums[i]
                nums[i] = temp
                index = len(nums) - k #注意這里
                if i == index:
                    self.res = nums[i]
                    return
                elif i > index:
                    qucksort(nums, l, i-1)
                else:
                    qucksort(nums, i+1, r)
        qucksort(nums, 0, len(nums)-1)
        return self.res

最大正方形

說實話這題我是一點思路都沒有，看了題解也不是很懂竿刁，太菜了黄锤。dp[i+1][j+1]表示以matrix[i][j]為右下角的最大正方形，則有dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1食拜，如果一個點的左邊鸵熟、上邊、左上這三個方向上出現(xiàn)了一個0都不行负甸，因此需要取最小旅赢，在具體實現(xiàn)上dp數(shù)組需要給左邊和上面額外加一層齿桃。還有一種思考方式就是要求新添加的一行與一列都為1，這樣邊長才能為加1煮盼。為什么dp數(shù)組要和原數(shù)組錯開一位呢短纵，因為這樣方便處理邊界條件，這樣想的話就發(fā)現(xiàn)前面的狀態(tài)轉(zhuǎn)移方程就比較好理解了僵控。

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        length = len(matrix)
        width = len(matrix[0])
        dp = [[0]*(width + 1)for _ in range(length + 1)]
        res = -inf
        for i in range(length):
            for j in range(width):
                if matrix[i][j] == '1':
                    dp[i+1][j+1] = min(dp[i][j+1], min(dp[i][j], dp[i+1][j])) + 1
                res = max(res, dp[i+1][j+1])
        return res*res

翻轉(zhuǎn)二叉樹

很簡單的遞歸操作香到。

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

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        temp1 = root.right
        temp2 = root.left
        root.left = self.invertTree(temp1)
        root.right = self.invertTree(temp2)
        return root

回文鏈表

判斷一個鏈表是否屬于回文序列，題目要求不借助外部空間來完成這一任務(wù)报破。我看官方題解給的第一種方法是額外定義一個數(shù)組來存儲鏈表節(jié)點悠就，很簡單但是這種方法顯然不滿足題目要求。
直接反轉(zhuǎn)鏈表也是不行的充易，也需要借助外部空間」Ｆⅲ現(xiàn)在直接借助快慢指針來找到鏈表的中間點，然后再將鏈表的前半段半段鏈表進行反轉(zhuǎn)盹靴，再和后半段鏈表進行比較（注意根據(jù)快慢指針停止的條件不同炸茧，我們可以判斷出鏈表長度的奇、偶數(shù)）稿静。在遍歷前半段鏈表的同時可以同時反轉(zhuǎn)鏈表梭冠，由于這里的快慢節(jié)點的起始位置存在差異，因此我們最終的前半段鏈表和后半段鏈表的頭節(jié)點需要根據(jù)奇數(shù)改备、偶數(shù)來進行一些調(diào)整控漠。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow = head
        if not slow:
            return True
        fast = head.next
        if not fast:
            return True
        newHead = None
        while(fast and fast.next):
            temp = slow
            fast = fast.next.next
            slow = slow.next

            temp.next = newHead
            newHead = temp

        lastHead = slow.next
        if fast and not fast.next:
            slow.next = newHead
            newHead = slow

        while(newHead and lastHead):
            if newHead.val != lastHead.val:
                return False
            else:
                newHead = newHead.next
                lastHead = lastHead.next
        return True

二叉樹的最近公共祖先

比較直接解法是記錄從根節(jié)點到這兩個節(jié)點的路徑，然后選擇出這兩條路徑的公共部分即可悬钳。

利用遞歸關(guān)系盐捷，比如p或q在當前節(jié)點的左子樹且p或q在當前節(jié)點的右子樹，那么當前節(jié)點就是這兩個節(jié)點的公共祖先默勾。但是這種遞歸寫法一定要注意毙驯，遞歸函數(shù)在不同條件下會有不同的含義。

還有一種最笨的辦法灾测，就是用一個字典記錄每一個節(jié)點的父節(jié)點爆价，然后找到從根節(jié)點到這兩個節(jié)點的路徑，最后找到公共部分即可媳搪。

解法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 lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.path = None
        def dfs(root, route, target):
            if root == target:
                self.path = route + [root]
            if not root:
                return
            dfs(root.left, route + [root], target)
            dfs(root.right, route + [root], target)
            
        dfs(root, [], p)
        route_p = self.path
        dfs(root, [], q)
        route_q = self.path
        for i in range(min(len(route_p), len(route_q))):
            if route_p[i] != route_q[i]:
                return route_p[i-1]
        return route_p[min(len(route_p), len(route_q)) - 1]

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

除自身以外數(shù)組的乘積

題目要求在o(n)的時間內(nèi)铭段，并且不能使用除法。解決辦法就是錯開一位進行連乘秦爆。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        A = [1]*length
        B = [1]*length
        C = [1]*length
        for i in range(1, length):
            A[i] = A[i-1]*nums[i-1]
        for i in range(length-1, 0, -1):
            B[i-1] = B[i]*nums[i]
        for i in range(length):
            C[i] = A[i]*B[i]
        return C

滑動窗口最大值

這里需要建立一個雙端隊列序愚，并且這個隊列是非遞增的。為什么要維護一個雙端隊列等限，一個端口的隊列行不行爸吮？因為滑動窗口在移動的過程中芬膝，兩端的狀態(tài)都會進行更新，所以需要雙端隊列形娇。為什么要維護一個非增的隊列锰霜，如果維護一個非遞減的隊列的話，滑動窗口在往右移動的過程中桐早，如果當前元素小于隊尾元素癣缅，則無法進入隊列，這樣會導(dǎo)致信息丟失哄酝。
這一題需要注意的細節(jié)是友存，隊列為空的情況，代碼中一共有四處判斷隊列是否為空的情況陶衅。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = []
        res = []
        for i in range(k):
            if not queue or nums[i] <= queue[-1]:
                queue.append(nums[i])
            else:
                while(queue and queue[-1] < nums[i]):
                    queue.pop()
                queue.append(nums[i])
        res.append(queue[0])
        for i in range(k, len(nums)):
            if nums[i-k] == queue[0]:
                queue.pop(0)
            if not queue or nums[i] <= queue[-1]:
                queue.append(nums[i])
            else:
                while(queue and queue[-1] < nums[i]):
                    queue.pop()
                queue.append(nums[i])
            res.append(queue[0])
        return res

搜索二維矩陣 II

暴力法就不多說了屡立，比較直觀的寫法是對每一行進行二分操作〔缶看了題解發(fā)現(xiàn)了一種比較好的辦法直接從右上角進行逼近膨俐，時間復(fù)雜度為O(m+n)

解法1：
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        def find(a, target):
            left = 0
            right = len(a) - 1
            while(left <= right):
                mid = (left + right) // 2
                if a[mid] == target:
                    return True
                elif a[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return False
        for nums in matrix:
            if find(nums, target):
                return True
        return False

解法2：
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0:
            return False
        i = 0
        j = len(matrix[0]) - 1
        while(i < len(matrix) and j >= 0):
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] < target:
                i += 1
            else:
                j -= 1
        return False

完全平方數(shù)

比較直觀的做法就是使用DFS進行暴力搜索，把所有的可能都暴力一邊奕巍，然后選出最小的那種情況∪迨浚或者可以使用簡單的DP來進行求解：
$dp[i] = min(dp[i], dp[i - j*j] + 1)$
dp[i]表示i需要的最少平方數(shù)個數(shù)的止，j表示所有小于sqrt(i)的可能值。
DFS的解法效率太低着撩，本質(zhì)上和DP一樣诅福，這里就不提供了。
具體請參考：
https://blog.csdn.net/qq_41855420/article/details/88248959?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase

解法1：注意DP解法一定要注意初始化的方法拖叙。
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [99999999]*(n + 1)
        dp[0] = 0
        for i in range(1, n+1):
            j = 1
            while(j*j <= i):
                dp[i] = min(dp[i], dp[i - j*j] + 1)
                j += 1
        return dp[n]

移動零

解法一：需要用一個變量count保存一下0的個數(shù)氓润，然后直接對數(shù)組中為0的元素進行操作，操作次數(shù)為count次薯鳍。
解法二：第一種方法還可以優(yōu)化咖气，可以使用雙指針來進行操作。
解法三：借用快排的思想挖滤，將不為0和為0的數(shù)字進行交換崩溪。這個是解法二在寫法上的一種優(yōu)化。

解法一：
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                count += 1
        i = 0
        while(True):
            if count == 0:
                break
            if nums[i] == 0:
                del(nums[i])
                count -= 1
                nums.append(0)
                i = i - 1
            i += 1
        return nums

解法二斩松；
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[j] = nums[i]
                j += 1
        for i in range(j, len(nums)):
            nums[i] = 0
        return nums
    
解法三：
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[j], nums[i] = nums[i], nums[j]
                j += 1
        return nums

尋找重復(fù)數(shù)

比較常用的思路：利用Map來計數(shù)伶唯，排序也可以，但是題目的要求比較嚴格惧盹，題目提供了二分查找和快慢指針兩種解法乳幸。二分的話需要轉(zhuǎn)換一下思路瞪讼，以[1,3,4,2,2]為例，1 + 5 // 2 = 3粹断，而小于等于3的元素有4個符欠，這說明在[1, 3]這個區(qū)間里一定存在重復(fù)的數(shù)字，注意這個[1,3]是指的下標區(qū)間姿染，不是原數(shù)組背亥，這個得區(qū)別一下，因此我們在更新狀態(tài)的時候與一般的二分查找不一樣悬赏，并且循環(huán)終止的條件也不一樣狡汉。

利用循環(huán)鏈表的快慢指針來解決。nums[i]表示第一個i節(jié)點指向第nums[i]個節(jié)點闽颇，這樣就可以形成一個環(huán)形鏈表了盾戴。

解法1：
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while(left < right):
            mid = (left + right) // 2
            count = 0
            for num in nums:
                if num <= mid + 1:
                    count += 1
            if count > mid + 1:
                right = mid
            else:
                left = mid + 1
        return right + 1

解法2：
先找到環(huán)，再去找具體的重合點兵多。但是這個題的難點在于起點的初始化尖啡，注意這三個初始化條件。
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0] #注意初始化條件
        fast = nums[nums[0]] #注意初始化條件
        while(slow != fast):
            slow = nums[slow]
            fast = nums[nums[fast]]
        print(slow)
        
        fast = 0 #注意初始化條件剩膘，這個可以用公式證明
        while(slow != fast):
            slow = nums[slow]
            fast = nums[fast]
        
        return slow

二叉樹的序列化與反序列化

給定了空節(jié)點的話衅斩，可以只用一種序列來確定樹的結(jié)構(gòu)，這一題采用簡單的中序遍歷即可怠褐。
在序列化的過程中畏梆，空的節(jié)點也需要入棧，再用一個列表存儲每個節(jié)點的值即可奈懒，空節(jié)點的值為null奠涌。在反序列化的過程中，同樣需要根據(jù)給定的列表重建一個隊列磷杏，但是空的節(jié)點就不需要入隊列了溜畅。注意題目中給定的序列是字符串，需要自己處理一下极祸。

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

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return '[]'
        queue = [root]
        res = []
        while(queue):
            temp = queue.pop(0)
            if temp:
                if temp.left:
                    queue.append(temp.left)
                else:
                    queue.append(None)
                if temp.right:
                    queue.append(temp.right)
                else:
                    queue.append(None)
                res.append(str(temp.val))
            else:
                res.append('null')
        return '[' + ",".join(res) + ']'
    
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == '[]':
            return None
        res = data[1:-1].split(',')
        node = TreeNode(int(res[0]))
        queue = [node]
        i = 1
        while(queue):
            temp = queue.pop(0)
            if res[i] != 'null':
                temp.left = TreeNode(int(res[i]))
                queue.append(temp.left)
            else:
                temp.left = None
            if res[i+1] != 'null':
                temp.right = TreeNode(int(res[i+1]))
                queue.append(temp.right)
            else:
                temp.right = None
            i = i +2
        return node
   
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

最長上升子序列

經(jīng)典的動態(tài)規(guī)劃問題慈格，與此類似的還有最長公共子序列，注意這里的是嚴格意義上地上升遥金，并且注意子序列和子串的區(qū)別峦椰，官方題解寫的比較好：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
這種題與最大子串和非常類似，最終的結(jié)果是在dp數(shù)組中的最大值汰规。但是原始的方法還有待優(yōu)化的空間汤功。狀態(tài)轉(zhuǎn)移方程：
$dp[i] = max(dp[i], dp[j] + 1)$ ，j表示i之前的元素溜哮，時間復(fù)雜度為O(n2)滔金。
采用貪心加二分的策略：維護一個新的數(shù)組m色解，m[-1]盡可能小的話，那么m就會盡可能長餐茵，在給m尾部插入新的元素a的時候科阎，如果新元素a大于m[-1]的話，則將a直接插入m中忿族，否則通過二分查找锣笨，找到第一個大于a的元素，并將其替換道批。

解法1：
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = [1]*len(nums)
        res = 1
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
            res = max(res, dp[i])
        return res

解法2：
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        temp = []
        for num in nums:
            if not temp or num > temp[-1]:
                temp.append(num)
            else:
                l = 0
                r = len(temp) - 1
                cur = r 
                while(l <= r):
                    mid = (l + r) // 2
                    if num > temp[mid]:
                        l = mid + 1
                    elif num <= temp[mid]: #等于一定得加在這一行
                        r = mid - 1
                        cur = mid
                temp[cur] = num
        return len(temp)

最佳買賣股票時機含冷凍期

典型的DP問題错英，但是這個DP的狀態(tài)稍微有點復(fù)雜，狀態(tài)有點多隆豹。由于存在買入椭岩、賣出、冷凍這三個動作璃赡，因此會存在三個狀態(tài)：不持有股票且沒有賣出判哥，持有股票，不持有股票且賣出碉考。那么我們就可以得到相應(yīng)的狀態(tài)轉(zhuǎn)移方程塌计，dp[i]表示第i天能夠獲得的最大利潤，dp[i][0]表示第i天不持股且沒賣出的狀態(tài)侯谁，dp[i][1]表示第i天持有股票锌仅，dp[i][2]表示第i天不持股且當天賣出了。

$dp[i][0] = max(dp[i-1][0], dp[i-1][2]$

$dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])$

$dp[i][2] = dp[i-1][1] + prices[i]$

參考：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/fei-zhuang-tai-ji-de-dpjiang-jie-chao-ji-tong-su-y/

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        dp = [[0]*3 for i in range(len(prices))]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        dp[0][2] = 0
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][2])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
            dp[i][2] = dp[i-1][1] + prices[i]
        return max(dp[len(prices)-1][0], dp[len(prices)-1][2])

戳氣球

我個人認為這一題的難度還是較高的良蒸，這樣題其實屬于經(jīng)典的DP問題技扼，不過是換了一個皮伍玖。與這個比較類似的有：給定一個矩陣鏈做乘法嫩痰，要求乘法次數(shù)最少，這個原始問題的DP方程很好寫窍箍，因為從理解上沒有啥困難串纺。但這個題不一樣，需要我們轉(zhuǎn)換一下思路椰棘，我們先給出狀態(tài)轉(zhuǎn)移方程：

$dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]nums[k]nums[j]) (i < k < j)$

這個的dp[i][j]表示從i到j(luò)之間能夠取得的最大數(shù)值纺棺，這里要注意這里是開區(qū)間，然后我們需要將這兩部分合起來邪狞，由于最后這兩部分的氣球都扎完了祷蝌，最終只剩下nums[i]，nums[k]帆卓，nums[j]這三個氣球了巨朦，相乘加起來即可米丘，由于這個狀態(tài)轉(zhuǎn)移方程表示的是開區(qū)間，因此我們在實現(xiàn)的時候需要在左右兩邊加上1糊啡。關(guān)于初始化的問題拄查，當i=j時，dp[i][j]=0棚蓄，j=i+1的時候堕扶，dp[i][j]=0，在具體的實現(xiàn)的時候梭依，我們需要注意一下稍算，先將長度為2的區(qū)間求出來，才能求區(qū)間為3的所有情況睛挚，以此類推邪蛔。

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums.insert(0, 1)
        nums.append(1)
        length = len(nums)
        dp = [[0]*length for i in range(length)]
        for r in range(2, length):
            for i in range(length-r):
                j = i + r
                for k in range(i+1, j):
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])
        return dp[0][length-1]

零錢兌換

背包問題，本人實在不會用DP扎狱，只會用DFS+剪枝侧到。貪心的思想好說，盡量先找大的來兌換淤击，但是這種會出現(xiàn)問題匠抗，因此我們還是需要遍歷所有的路徑來尋找一個最小值。如果每次只找一個硬幣的話會超時污抬，第一種解法就是這樣汞贸。我們需要一次盡可能多找硬幣，如果超了的話再退回即可印机，因此這里需要好好設(shè)計遞歸函數(shù)的參數(shù)矢腻，這里我參考的是：https://leetcode-cn.com/problems/coin-change/solution/322-by-ikaruga/，將硬幣的索引也加入到參數(shù)中射赛，每次選則硬幣的數(shù)量為1到差額/當前硬幣的面值多柑，再通過當前用的硬幣數(shù)量大于當前的最小值來進行剪枝。

解法1：錯誤解法（超時）
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        self.res = 99999999
        length = len(coins)
        flags = [0]*length
        def dfs(route, count):
            if route > amount:
                return
            if route == amount:
                self.res = min(count, self.res)
                return
            for i in range(length):
                dfs(route + coins[i], count + 1)    
        if amount == 0:
            return 0
        dfs(0, 0)
        if self.res != 99999999:
            return self.res
        else:
            return -1

解法1的記憶化寫法：
dfs(route, count, Dict)表示在已經(jīng)兌換出面額為route楣责，已經(jīng)使用的硬幣數(shù)量為count的情況下竣灌，最終完成任務(wù)所需要的最少硬幣數(shù)量（包含前面已經(jīng)使用的count個數(shù)硬幣）。Dict[res] = num表示的含義是在當前已經(jīng)兌換出res的面額條件下秆麸，兌換amount-res面額最少需要的硬幣數(shù)量為num初嘹。之所以這樣設(shè)計的原因是可以有很多種不同的分支到達res這個條件，但是后面兌換amount-res面額最少需要的硬幣數(shù)量這個分支是一樣的沮趣。那Dict[res] = num可不可以用來表示在當前已經(jīng)兌換出res的面額條件下屯烦，完成整個任務(wù)最少需要的硬幣數(shù)量為num？這個是不可以的，因為res之后的分支是一樣的驻龟，但是到達res之前的分支卻有多種甸箱，因此如果一定要Dict表示這一含義，就還需要對key進行一下區(qū)分迅脐∩种常可以這樣寫：Dict[(count, res)] = num表示在已經(jīng)兌換出面額為res，已經(jīng)使用的硬幣數(shù)量為count的情況下谴蔑，最終完成任務(wù)所需要的最少硬幣數(shù)量（包含前面已經(jīng)使用的count個數(shù)硬幣）豌骏。這個題目有一種變種，比如給每一種面額的硬幣數(shù)量加一個限制隐锭，那這一樣的話窃躲，我們的key除了記錄當前已經(jīng)兌換出的面額總數(shù)，還需要記錄剩余的硬幣數(shù)量钦睡，因為到達res這個分支每一種使用的硬幣數(shù)量可能不同蒂窒，會導(dǎo)致后面剩余的硬幣數(shù)量發(fā)生變化。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        #coins.sort(reverse=True)

        length = len(coins)
        flags = [0]*length
        def dfs(route, count, Dict):
            if route > amount:
                return inf
            if route == amount:
                return count
            if route in Dict:
                return count + Dict[route]
            res = inf
            for i in range(length):
                temp = dfs(route + coins[i], count + 1, Dict)
                res = min(res, temp)
            Dict[route] = res - count
            return res
            
        res = dfs(0, 0, {})
        if res == inf:
            return -1
        return res

解法2：
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        self.res = 99999999
        length = len(coins)
        flags = [0]*length
        def dfs(route, count, index):
            if route == amount: #這兩個判斷條件不能交換荞怒，因為有可能在后一個硬幣取到滿足條件的情況洒琢。
                self.res = min(count, self.res)
                return
            if index == length: #如果到了最后一個硬幣還不滿足條件就可以終止了。
                return
            for i in range((amount - route) // coins[index], -1, -1):#需要取到0
                if i + count > self.res: #這里是整個算法的關(guān)鍵褐桌，后面由于大面額硬幣的數(shù)量減少衰抑，最終用到硬幣是一定會增加的，因此可以直接剪掉荧嵌。
                    break
                dfs(route + coins[index]*i, count + i, index + 1)    
        
        if amount == 0:
            return 0
        dfs(0, 0, 0)
        if self.res != 99999999:
            return self.res
        else:
            return -1  

解法2的另一種寫法：
可以將數(shù)據(jù)更新放在for循環(huán)里呛踊，但這種寫法我不推薦，代碼臃腫且易出錯啦撮。
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        self.res = 99999999
        length = len(coins)
        flags = [0]*length
        def dfs(route, count, index):
            if index == length:
                return
            for i in range((amount - route) // coins[index], -1, -1):
                if i + count > self.res:
                    break
                if route + coins[index]*i == amount:
                    self.res = min(count+i, self.res)
                elif route + coins[index]*i < amount:
                    dfs(route + coins[index]*i, count + i, index + 1)
                else:
                    continue    
        
        if amount == 0:
            return 0
        dfs(0, 0, 0)
        if self.res != 99999999:
            return self.res
        else:
            return -1

解法2的另一種寫法：
這種方法同樣不推薦谭网，將前面的兩個終止條件合并在一起了，因為可能只是用了一小部分硬幣就滿足題意了赃春，不用把所有的硬幣都遍歷到愉择。這種寫法會降低效率。
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        self.res = 99999999
        length = len(coins)
        flags = [0]*length
        def dfs(route, count, index):
            if index == length: #如果到了最后一個硬幣還不滿足條件就可以終止了聘鳞。
                if route == amount: #這兩個判斷條件不能交換薄辅，因為有可能在后一個硬幣取到滿足條件的情況要拂。
                    self.res = min(count, self.res)
                return
            for i in range((amount - route) // coins[index], -1, -1):#需要取到0
                if i + count > self.res:
                    break
                dfs(route + coins[index]*i, count + i, index + 1)    
        
        if amount == 0:
            return 0
        dfs(0, 0, 0)
        if self.res != 99999999:
            return self.res
        else:
            return -1

補充DP的寫法抠璃，DP的寫法和記憶化DFS是一樣的：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [inf]*(amount+1)
        dp[0] = 0
        for i in range(1, amount+1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin]+1)
        if dp[amount] != inf:
            return dp[amount]
        else:
            return -1

打家劫舍 III

需要設(shè)計好遞歸關(guān)系，基本的遞歸關(guān)系是祖先與子孫們之和與兒子們之和的大小比較脱惰。遞歸函數(shù)表示當前節(jié)點下能夠偷到的最大錢數(shù)搏嗡，參數(shù)只有一個。普通的遞歸寫法容易超時，需要特殊處理一下采盒，我們可以讓遞歸函數(shù)返回兩個值旧乞，一個表示取當前節(jié)點能夠獲得最大值，另一個表示不取當前節(jié)點能夠獲得的最大值磅氨，這樣的話只需要兩個遞歸分支即可尺栖。

解法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 rob(self, root: TreeNode) -> int:

        def recurrsion(root):
            if not root:
                return 0
            res1 = 0
            res2 = root.val
            if root.left:
                res1 += recurrsion(root.left)
                res2 += recurrsion(root.left.left) + recurrsion(root.left.right)

            if root.right:
                res1 += recurrsion(root.right)
                res2 += recurrsion(root.right.left) + recurrsion(root.right.right)

            return max(res1, res2)
        return recurrsion(root)

解法2：（記憶化搜索：用參數(shù)保存中間的結(jié)果）
錯誤寫法：
class Solution:
    def rob(self, root: TreeNode) -> int:
        def recurrsion(root):
            if not root:
                return 0, 0
            res1 = root.val + recurrsion(root.left)[1] + recurrsion(root.right)[1]
            res2 = max(recurrsion(root.left)[0] + recurrsion(root.right)[0], recurrsion(root.left)[1] + recurrsion(root.right)[1]) #這一步寫錯了
            return res1, res2
        return max(recurrsion(root))

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

class Solution:
    def rob(self, root: TreeNode) -> int:
        def recurrsion(root):
            if not root:
                return 0, 0
            res1 = root.val + recurrsion(root.left)[1] + recurrsion(root.right)[1]
            res2 = max(recurrsion(root.left)[0], recurrsion(root.left)[1]) + max(recurrsion(root.right)[0] , recurrsion(root.right)[1]) #同樣使用了6個遞歸分支，錯誤寫法
            return res1, res2
        return max(recurrsion(root))

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

class Solution:
    def rob(self, root: TreeNode) -> int:
        def recurrsion(root):
            if not root:
                return 0, 0
            temp1 = recurrsion(root.left)#使用中間變量來保存結(jié)果烦租，只有2個遞歸分支
            temp2 = recurrsion(root.right)
            res1 = root.val + temp1[1] + temp2[1]
            res2 = max(temp1[0], temp1[1]) + max(temp2[0] , temp2[1])
            return res1, res2
        return max(recurrsion(root))

比特位計數(shù)

題目要求在0（n）的時間復(fù)雜度內(nèi)延赌，因此這一題只能使用位運算。比較巧妙的一種做法是用DP的思想：
$dp[i] = dp[i>>1] + i\&1$

這里要注意python中位運算的優(yōu)先級叉橱，位運算的優(yōu)先級是最低的挫以，因此要加上括號。
class Solution:
    def countBits(self, num: int) -> List[int]:
        dp = [0]*(num + 1)
        for i in range(1, num + 1):
            dp[i] = dp[i>>1] + (i&1)
        return dp

前K個高頻元素

最直接的解法就是用字典來計數(shù)窃祝，之后再來排序掐松，但這個時間復(fù)雜度是顯然不符合題目要求的。

建立一個最小堆粪小，求前 k 大大磺，用小根堆，求前 k 小探膊，用大根堆量没。面試的時候如果說反了會掛，其實這一點很好理解突想，以最小堆為例殴蹄，當堆的元素個數(shù)超過了k個，就把堆頂元素出隊列，這樣就保證每次都把當前最小的元素給排除了啥刻，最終剩下的k個元素一定是最大的质欲，同理大頂堆也是這樣的。對于這一道題稽荧，需要建立一個map來計數(shù)，然后通過最小堆來進行維護工腋。

解法1：
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        Dict = {}
        for num in nums:
            if num not in Dict:
                Dict[num] = 1
            else:
                Dict[num] += 1
        def compare(x, y):
            if x[1] > y[1]:
                return 1
            elif x[1] == y[1]:
                return 0
            else:
                return -1
        Dict = sorted(Dict.items(), key = cmp_to_key(compare), reverse=True)
        res = []
        for i in range(k):
            res.append(Dict[i][0])
        return res

解法2：
python3貌似不是很好處理姨丈，鍵值對排序的問題，但是python3提供了一個nlargest函數(shù)擅腰。
from heapq import *
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        Map = {}
        for num in nums:
            if num not in Map:
                Map[num] = 1
            else:
                Map[num] += 1
        heap = []
        '''
        for x in Map.items():
            heappush(x, heap)
            if
        '''
        return nlargest(k, Map.keys(), Map.get)

字符串解碼

這一題由于括號會進行嵌套蟋恬，因此在外面的括號反倒要最后處理，所以這里需要借助棧來進行處理趁冈，我個人覺得這一題不很好寫歼争，棧里面保存的是字符串的信息和對應(yīng)的數(shù)字信息拜马，參考：https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
我個人認為這份題解寫的很巧妙，大家可以稍微記一下這份代碼（滑稽）沐绒。

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        res = ''
        number = 0
        for c in s:
            if c == '[':
                stack.append((res, number))
                res = ''
                number = 0
            elif c == ']':
                last_res, last_number = stack.pop()
                res = last_res + last_number*res
            elif '0' <= c and c <= '9':
                number = number*10 + int(c) 
            else:
                res += c
        return res

除法求值

這一題使用圖的做法比較好俩莽，我看題解有用并查集做的，我個人覺得這樣意義不大乔遮。題目中的輸入就是相當于給定了兩個節(jié)點和之間權(quán)重扮超，因此可以利用這些數(shù)據(jù)直接建立一個圖，而最后的輸出也是要計算兩個節(jié)點之間的權(quán)重蹋肮，因此相當于給定了起點和終點要求路徑乘積瞒津，所以用深搜最直接。這一題的關(guān)鍵是如何存儲圖的信息括尸，可以使用一個二階嵌套的字典來存儲兩個節(jié)點和其權(quán)重信息巷蚪。
關(guān)于DFS需要好好設(shè)計一下，整個遞歸函數(shù)表示a到b之間的路徑乘積濒翻，當a==b的時候就返回1屁柏，當a和b之間沒有路徑的時候就返回-1，因此在遞歸的時候需要判斷一下后面是否存在路徑有送，如果后面存在路徑則說明a和b都可以找到路徑淌喻，后面的遞歸都可以終止了，如果一直沒有找到那么說明這兩個點之間不存在路徑雀摘，返回-1即可裸删。我們還可以在參數(shù)中設(shè)計一個visited數(shù)組來存儲已經(jīng)走過的節(jié)點，防止重復(fù)遍歷阵赠。

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        Map = {}
        for (node1, node2), value in zip(equations, values):
            if node1 not in Map:
                Map[node1] = {node2: value}
            else:
                Map[node1][node2] = value
            if node2 not in Map:
                Map[node2] = {node1: 1/value}
            else:
                Map[node2][node1] = 1 / value
        def dfs(a, b, visited):
            if a == b:
                return 1
            for node in Map[a].keys():
                if node not in visited:
                    visited.append(node)
                    res = dfs(node, b, visited)
                    if res != -1:
                        return Map[a][node]*res
            return -1
            
        res = []
        for querie in queries:
            if querie[0] not in Map or querie[1] not in Map:
                res.append(-1.0)
            else:
                res.append(dfs(querie[0], querie[1], []))
        return res

根據(jù)身高重建隊列

這一題其實就是典型的逆序數(shù)概念涯塔，題目要求根據(jù)逆序數(shù)把原來的數(shù)組進行還原，按照正常的想法：如果我們優(yōu)先安排小的清蚀，后面的元素就比較難安排匕荸，因此我們需要優(yōu)先安排大的元素，并且存在相同元素的話枷邪，我們優(yōu)先安排第二維較小的榛搔，因此這一題本質(zhì)上就是一個排序問題。

這里需要強調(diào)一下东揣，python排序函數(shù)非常死板践惑，非要傳入1, 0, -1這三個數(shù)，其中1表示要交換數(shù)字嘶卧，這一點與C語言有很大的區(qū)別尔觉。
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        def compare(x, y):
            if x[0] < y[0] or (x[0] == y[0] and x[1] > y[1]):
                return 1
            elif x == y :
                return 0
            else:
                return -1
        temp = sorted(people, key=cmp_to_key(compare))
        res = []
        for num, index in temp:
            res.insert(index, (num, index))
        return res

分割等和子集

直觀上來看屬于暴力搜索即可，例如DFS這種就行脸候。官方題解給的都是用dp來解穷娱。這里使用DFS容易超時，需要加上一些特殊剪枝：1.給數(shù)組做一個逆序排序运沦，這樣能更快地到達終點泵额。2. 當找到合適的路徑后，直接把其余的分支給剪掉携添。3. 最終一點嫁盲，題目給了一個98個1和1個100這樣的極端數(shù)據(jù)，通過判斷最大的元素是否大于總和的一半來硬核剪枝烈掠。
這一題有一種比較好的辦法就是將數(shù)組處理成字典這種數(shù)據(jù)結(jié)構(gòu)羞秤，鍵值對表示元素和其出現(xiàn)的次數(shù)，比如{1：98左敌，100：1}這種瘾蛋，這題與322-零錢兌換這一題高度相似。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sumnum = sum(nums)
        if sumnum % 2 != 0:
            return False
        new_sort = sorted(nums)
        if new_sort[-1] > sumnum // 2:
            return False
        length = len(nums)
        flags = [0]*length
        self.end = 0
        nums.sort(reverse=True)
    
        def dfs(route):
            if self.end == 1:
                return
            if route > sumnum // 2:
                return 
            if route == sumnum // 2:
                self.end = 1
                return 
            for i in range(length):
                if self.end == 1:
                    return
                if flags[i] == 0:
                    flags[i] = 1
                    dfs(route + nums[i])
                    flags[i] = 0
        dfs(0)
        
        if self.end == 1:
            return True
        else:
            return False

路徑總和 III

一種直觀的方法就是把每一個節(jié)點的父子關(guān)系存儲起來矫限，然后進行暴力搜索即可哺哼。

雙遞歸，我們需要設(shè)計一個遞歸函數(shù)用來記錄以當前節(jié)點為根節(jié)點能夠找到滿足題意的路徑條數(shù)叼风，由于樹的每一個節(jié)點都需要這樣操作因此這是一個雙遞歸的操作取董。

解法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 pathSum(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0
        queue = [root]
        parents = {root: None}
        while(queue):
            temp = queue.pop()
            if temp.left:
                parents[temp.left] = temp
                queue.append(temp.left)
            if temp.right:
                parents[temp.right] = temp
                queue.append(temp.right)
        count = 0
        for node in parents:
            sumNum = 0
            temp = node
            while(temp):
                sumNum += temp.val
                temp = parents[temp]
                if sumNum == sum:
                    count += 1
        return count

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

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        def dfs(root):
            if not root:
                return 0
            res = pathCount(root, sum)
            a = dfs(root.left)
            b = dfs(root.right)
            return res + a + b
            
        def pathCount(root, sum):
            if not root:
                return 0
            sum = sum - root.val
            if sum == 0:
                res = 1
            else:
                res = 0
            return res + pathCount(root.left, sum) + pathCount(root.right, sum)
        
        return dfs(root)

找到字符串中所有字母異位詞

這種題是經(jīng)典的滑動窗口題，參考：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/无宿，一句話總結(jié)雙指針茵汰，加上雙字典。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        need = {}
        window = {}
        left = 0
        right = 0
        valid = 0
        res = []
        length = len(s)
        for c in p:
            if c not in need:
                need[c] = 1
            else:
                need[c] += 1
        while(right < length):
            c = s[right]
            right += 1
            if c not in window:
                window[c] = 1
            else:
                window[c] += 1
            if c in need:
                if window[c] == need[c]:
                    valid += 1
            while(right - left >= len(p)):
                if valid == len(need):
                    res.append(left)
                d = s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return res

找到所有數(shù)組中消失的數(shù)字

一般情況下可以借助字典或者集合來解決孽鸡，但是題目要求在不使用額外空間且時間復(fù)雜度為O(n)的情況下完成這個任務(wù)蹂午。由于該數(shù)組里的每一個元素的大小在1-n之間，通常情況下我們可以使用一個定長的數(shù)組來記錄這些元素出現(xiàn)的次數(shù)彬碱，考慮到題目要求不能使用額外空間画侣，因此我們就直接在原數(shù)組鐘進行修改操作，有一個細節(jié)就是將對應(yīng)位置的元素取反堡妒，這樣可以不用破壞原有數(shù)組的信息（再次取反就可以還原原來的數(shù)組）配乱。

解法1：借助集合或者字典方法嚴格來說是不太合格的算法。
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        res = []
        temp = set(nums)
        for num in range(1, len(nums) + 1):
            if num not in temp:
                res.append(num)
        return res

解法2：
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        res = []
        for num in nums:
            if num < 0:
                num = -num
            if nums[num - 1] > 0:
                nums[num - 1] = -nums[num - 1]
        for i in range(len(nums)):
            if nums[i] > 0:
                res.append(i + 1)
        return res

漢明距離

正常的化二進制操作皮迟。

先將a和b做一個異或運算操作搬泥，再來看該數(shù)二進制表示中0的個數(shù)。

解法一：
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        a = [0]*32
        b = [0]*32
        temp1 = x
        temp2 = y
        i = 0
        while(temp1):
            a[31 - i] = temp1 % 2
            temp1 = temp1 // 2
            i += 1
        i = 0
        while(temp2):
            b[31 - i] = temp2 % 2
            temp2 = temp2 // 2
            i += 1
        res = 0
        for i in range(31, -1, -1):
            if a[i] != b[i]:
                res += 1
        return res

解法二：
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        temp = x ^ y
        res = 0
        while(temp):
            if temp % 2 == 1:
                res += 1
            temp = temp // 2
        return res

目標和

同樣是利用搜索伏尼，設(shè)計參數(shù)的時候需要添加一個索引忿檩，表示現(xiàn)在使用到了第幾個元素。

可以利用記憶化搜索來進行剪枝葉爆阶，但是這種方法很難想燥透。

我個人在設(shè)計遞歸函數(shù)的時候不喜歡設(shè)計返回值沙咏，其實這是一種投機取巧的辦法。
解法1：
class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        length = len(nums)
        self.res = 0
        def dfs(route, count, index):
            if count == length:
                if route == S:
                    self.res += 1
                return
            dfs(route + nums[index], count + 1, index + 1)
            dfs(route - nums[index], count + 1, index + 1)
            
        dfs(0, 0, 0)
        return self.res

解法2：
我們需要想清楚在遞歸過程中有哪些是重復(fù)計算的班套，比如我們在使用了i個元素且當前和為a的情況下肢藐，我們是可以得到還有多少種情況可以滿足題意的，因此我們只需要把這一過程記錄下來吱韭，在后序的過程中吆豹，如果再遇到這種情況就不要遞歸運算，只需要讀取就可以了理盆。需要特別注意返回值痘煤，如果字典中存在相應(yīng)的結(jié)果直接返回即可，如果不存在那么就判斷是否等于S猿规，如果等于就返回1衷快，否則返回0。dfs(route, index, Dict)表示在當前和為route的情況下姨俩，使用了index個元素還能夠有多少種情況滿足題意烦磁，Dict用來存儲中間狀態(tài)。Dict的key需要好好說一下哼勇，Dict[route] = num表示在當前和為route的情況下都伪，還能有多少種情況滿足題意，但這種寫法是錯誤的积担，因為到達res這個分支有很多種情況陨晶，可能用了2個元素，也可能用了3個元素帝璧，剩下的和是一定的先誉，但是剩下的元素數(shù)量由前面分支來確定，因此需要使用Dict[(route, index)] = num這種寫法的烁，來保證記錄的是唯一的分支狀態(tài)褐耳。

class Solution:
    
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        length = len(nums)
        def dfs(route, index, Dict):
            if index == length:
                if route == S:
                    return 1
                else:
                    return 0 
            if (route, index) not in Dict:
                res = dfs(route+nums[index], index+1, Dict) + dfs(route-nums[index], index+1, Dict)
                Dict[(route, index)] = res
            else:
                res = Dict[(route, index)]
            return res
        return dfs(0, 0, {})

把二叉搜索樹轉(zhuǎn)換為累加樹

遞歸含義：設(shè)計遞歸函數(shù)需要弄清該遞歸函數(shù)的返回值，也就是該遞歸函數(shù)的表示含義渴庆。這個遞歸函數(shù)返回的是根節(jié)點铃芦。
遞歸關(guān)系：遍歷樹的順序應(yīng)該是：右子樹，根節(jié)點襟雷，左子樹刃滓。在這個順序上在進行節(jié)點值的更新操作。
遞歸終點：當前根節(jié)點為空則終止耸弄。

錯誤的代碼：錯誤的原因是沒有對右節(jié)點進行更新操作咧虎。
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        right = self.convertBST(root.right)
        if right:
            root.val += right.val
        left = self.convertBST(root.left)
        if left:
            left.val += root.val
        return root

正確的解法：用一個變量來存儲累加和
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.total = 0
    def convertBST(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        right = self.convertBST(root.right)
        self.total += root.val
        root.val = self.total
        left = self.convertBST(root.left)
        return root

二叉樹的直徑

這個題可以轉(zhuǎn)換成求二叉樹的高度，二叉樹的直徑等價于左右子樹的高度+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 diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.res = 0
        def getHeight(root):
            if not root:
                return 0
            L = getHeight(root.left)
            R = getHeight(root.right)
            self.res = max(self.res, L + R + 1)
            return max(L, R) + 1
        if not root:
            return 0
        getHeight(root)
        return self.res - 1

和為K的子數(shù)組

暴力法是很容易想到的征唬，固定一邊然后對另一邊進行枚舉，時間復(fù)雜度為O（n2）茁彭，顯然這種效率是不高的总寒。由于這一題是求子數(shù)組的和，因此我們可以事先將對應(yīng)的前綴和存儲在字典里尉间，然后查詢就可以了偿乖，兩個前綴和相減就可以得到中間一段連續(xù)的序列击罪。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        Dict = {0 : 1}
        res = 0
        s = 0
        for num in nums:
            s += num
            if s-k in Dict:
                res += Dict[s-k]
            if s in Dict:
                Dict[s] += 1
            else:
                Dict[s] = 1
        return res

最短無序連續(xù)子數(shù)組

從左到右找到最后一個破壞遞增的數(shù)字下標哲嘲；從右到左找到最后一個破壞遞減的數(shù)字下標。

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        maxNum = -99999999
        minNum = 99999999
        low = 0
        high = 0
        length = len(nums)
        for i in range(length):
            if nums[i] >= maxNum:
                maxNum = nums[i]
            else:
                high = i
            if nums[length-1-i] <= minNum:
                minNum = nums[length-1-i]
            else:
                low = length-1-i
        if high > low:
            return high - low + 1
        else:
            return 0

合并二叉樹

正常遍歷二叉樹即可媳禁。

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

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1:
            return t2
        if not t2:
            return t1
        t3 = TreeNode(t1.val + t2.val)
        t3.left = self.mergeTrees(t1.left, t2.left)
        t3.right = self.mergeTrees(t1.right, t2.right)
        return t3

任務(wù)調(diào)度器

調(diào)度問題眠副，比較直觀的做法是用貪心算法。次數(shù)數(shù)多的任務(wù)優(yōu)先安排竣稽，假設(shè)間隔為n囱怕，那么我們以n+1個不同的任務(wù)為一個單元，通過這樣的方式來安排所有的任務(wù)毫别。

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        temp = [0]*26
        res = 0
        for c in tasks:
            temp[ord(c)-ord('A')] += 1
        temp.sort()
        while(temp[-1] > 0):
            i = 0
            while(i <= n):
                if temp[-1] == 0:
                    break
                if i < 26 and temp[25-i] > 0:
                    temp[25-i] -= 1
                res += 1
                i += 1
            temp.sort()
        return res

回文子串

這是一個二階DP娃弓，對于DP我們需要設(shè)計好狀態(tài)轉(zhuǎn)移方程，dp[i][j]代表從i位置到j(luò)位置之前的字符串岛宦，那么我們可以很容易的得出相應(yīng)的狀態(tài)轉(zhuǎn)移方程：

$dp[i][j]=\left\{ \begin{aligned} & dp[i+1][j-1] & (dp[i]=dp[j]) \\ & False & (dp[i]!=dp[j]) \end{aligned} \right.$

在具體實現(xiàn)的時候需要注意台丛，因為狀態(tài)轉(zhuǎn)移方程是從后往前運算的，因此在實現(xiàn)的時候需要從后往前算砾肺，并且在dp[i]=dp[j]且j = i + 1的時候需要單獨判斷一下挽霉，因為這個時候dp[i+1][j-1]就變成空了。

class Solution:
    def countSubstrings(self, s: str) -> int:
        length = len(s)
        dp = [[0]*length for i in range(length)]
        for i in range(length):
            for j in range(length):
                if i == j:
                    dp[i][j] = 1
        res = 0
        for i in range(length-1, -1, -1):
            for j in range(i+1, length):
                if s[j] == s[i]:
                    if j == i+1:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = 0
                if dp[i][j] == 1:
                    res += 1
        return res + length

每日溫度

建立一個遞減的棧变汪，將棧中小于當前節(jié)點的元素全部出棧侠坎，并且計算相應(yīng)結(jié)果，接著再讓當前元素入棧裙盾。

動態(tài)規(guī)劃实胸，從前往后不方便計算，但是從后往前就好算了番官，我們需要從第i+1天推出第i天的結(jié)果童芹，有一個比較明顯的結(jié)論是，如果T[i+1] > T[i]那么res[i] = 1鲤拿，然后跳出循環(huán)假褪，否則如果res[i+1]=0，那么res[i]一定為0近顷，然后跳出循環(huán)生音，如果res[i+1]不為0宁否，那就和T[i+1+res[i+1]個元素進行比較。

解法1：
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        res = [0]*len(T)
        stack = []
        for i in range(len(T)):
            while(stack and T[stack[-1]] < T[i]):
                res[stack[-1]] = i - stack[-1]
                stack.pop()
            stack.append(i)
        return res

解法2：
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        res = [0]*len(T)
        for i in range(len(T) - 2, -1, -1):
            j = i + 1
            while(j <= len(T) - 1):
                if T[j] > T[i]:
                    res[i] = j - i
                    break
                elif res[j] == 0:
                    res[i] = 0
                    break
                j += res[j]
        return res