leetcode热题 HOT 100刷题笔记（2）

leetcode热题 HOT 100第二部分题解，按照题目序号排列。

二叉树的层序遍历

正常的层序遍历操作即可，但是需要记录每一层节点的数量。

# 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

从前序与中序遍历序列构造二叉树

常规题，需要借助前序遍历将中序遍历一分为二，然后进行递归操作。但凡是涉及到递归函数，我们就得设计好递归函数的参数和返回值。函数的返回值为根节点，函数的参数为三个，一个为根节点在前序序列中的索引，剩下两个分别为左右边界，用来确定对应的中序序列的范围。由于是重建二叉树，因此每次都需要创建一个新的节点，并且还需要主要根节点在前序序列中的位置。

# 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

二叉树展开为链表

题目要求直接对链表进行修改，注意最终修改完成的链表应该是先序遍历的顺序来的，并且每个节点的左节点都为空。如果我们结果按照左-根-右的顺序来操作的话，就直接丢失右子树的信息。因此我们需要按照右=根-左的顺序来，具体实现的时候需要用一个全局变量来保存前一个子节点。

# 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

二叉树中的最大路径和

每次在选择路径的时候都要优先选择较大的，对于节点a这里可以设计一个递归函数，返回的是max(a.left.val, a.right.val) + a.val，当然还得考虑到要大于0，因此最终返回的是max(max(a.left.val, a.right.val) + a.val, 0)，每一次选择完路径后需要计算当前节点取得的最大值：当前节点+左子树+右子树。每一次递归都要计算一下，整个递归结束后就可以得到全局的最大值了。整个的递归函数表示的是当前节点是往左走，还是往右走，还是都不要。最终的结果是通过全局变量来保存的，每次递归的时候都更新一下。

# 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

最长连续序列

这一题要求时间复杂度为O(n)，因此很自然的想法是需要利用额外的空间来进行加速查找，我们可以将原数组变成一个集合，然后通过判断i，i+1，i+2这样的方式来进行判断，这样的话就可以让判断过程变成O（1）复杂度，注意这里还有一个优化的技巧，如果一个当前元素-1已经在集合李出现过的话，那么就可以跳过这个元素，直接进行下一步判断，因为这种情况一定在之前就已经判断过了。

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

只出现一次的数字

异或操作即可。

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

单词拆分

直观的想法还是用DFS，但是需要进行剪枝，同样我们需要思考一下递归过程中重复运算的情况，比如我们在前面的递归中已经知道了某个字串是不符合题意的，那么在后序的过程中我们只需要判断一下即可，不需要进行递归运算了。递归需要设计好参数和返回值。

解法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：
我们需要使用一个字典来保存中间状态，因此我们需要设计好返回值，对于一个字符串，我们在每一个位置上进行切分，如果中间有一种可以那么我们就返回True，如果所有的可能都不行，那么最后就返回False，中间的状态用Dict来保存，需要注意递归出口，当为空的时候就返回True。整个递归函数dfs(c, Dict)表示单词c是否可拆分，可拆分就返回True，不可拆分就返回False，Dict用来存储中间单词的状态（可拆分或者不可拆分）。
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的优化写法，这种写法更符合记忆化搜索的基本思路：
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, {})

环形链表

使用一个额外的数据结构来判断是否访问到了重复的链表节点。

使用快慢指针让其中一个节点先跑一步即可，并且让快指针移动速度更快，判断是否为空的时候只需要对快指针进行判断即可。

解法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

环形链表 II

先找环，再去找相交点，这一题在287题的第二种解法中做过。快慢指针相遇是非常简单的，因为跑的快的一定可以追上跑得慢的，我们可以根据环内相遇的点和入环的第一个点，将整个链表分成3段，之后我们可以证明，将快指针重新放在开头，可以保证快慢指针一定可以在入环的第一个节点相遇，但是这题需要注意，由于我的快指针比慢指针多跑一步，因此我们需要重新将快指针放置在第一个节点之前。

# 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（最近最少使用）算法是操作系统里一种常用的算法。该算法要求在O（1）的时间内进行读取，因此需要使用字典这个数据结构，该算法要求记录哪些元素最近被更新过，因此每次在更新数据之后需要把更新过后的数据放在最近的位置，并且要求在O（1）的时间内完成这一操作，因此这里需要使用到双向链表这样的数据结构。将两者结合起来：我们需要用到一个字典加上双向链表的结构。字典中的基本结构（key，value）value表示一个链表节点，而链表节点结构为：key, value, pre, next。这里的value表示节点存储的值，pre表示指向前一个节点的指针，next表示指向后一个节点的指针，key和字典里的key是一样的，需要特别注意这个key，链表节点里还要存储key的原因：在进行删除操作的时候是先找到对应的链表节点来进行删除，最终删除的时候是需要删除字典里的键值对，因此在链表节点里也保存了对应的key。
参考：https://leetcode-cn.com/problems/lru-cache/solution/shu-ju-jie-gou-fen-xi-python-ha-xi-shuang-xiang-li/

这一题的难点在于链表的添加和删除操作，记得不能随意调换相应的步骤。
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 #这四步需要注意，不能随意调换
            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)

排序链表

链表的排序属于链表的基本操作，一般用归并排序。这里的代码我是参考的这个：
https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-zed-65536/ 写的比较清晰。在合并两个节点的时候使用了一个小技巧：添加了头节点，这样就不用考虑两个链表中首节点的大小了。

# 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)

最小栈

要求在常数时间内取得最小值，那这个栈就必须是有顺序的。但是原有栈的结构不能破坏，因此可以使用一个备用的栈。在具体实现的代码的时候需要注意栈是否为空。

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()

乘积最大子数组

直观看上去应该是DP。
并且与最大子序列和类似，但不同的是，一个负数乘以一个负数可能会变成正数，同样一个正数乘以负数可能会变成一个负数，因此我们还需要维护一个最小的状态转移方程：
$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]$
这里同样有一个优化的技巧：状态压缩dp，用两个变量只保存前一轮的状态，这样可以减少空间复杂度。

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

相交链表

由于链表的长度不一致需要手动让两个链表在相同的位置节点来进行比较。比较笨的办法就是统计两个链表的长度，然后计算出两个链表的长度差m，最后让长的链表先走m步，再一起比较即可。官方题解给了一种比较好的方法，让先走到终点的链表转到另一个链表上，然后再一起比较。

# 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

多数元素

摩尔投票法

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

打家劫舍

需要写出状态转移方程，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

岛屿数量

传统的DFS，在走完一个岛屿后将其标记成2，这种题与求不同路径不一样，这种题只需要走完即可，而求不同路径的问题中，同一条路径需要进行标记，防止重复走，但是在不同的路径中却要标记回来。

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

反转链表

链表的基本操作。

# 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

课程表

这一题是典型的拓扑排序，由于需要按顺序输出所有的节点，因此最好使用BFS来遍历全图，维护一个队列，将入度为0的节点全部入队列，再将入度为0的节点出队列，然后将其相邻的节点入度全部都减1，如果有入度为0的节点则入队列即可，如果所有节点都可以正常输出则说明可以完成所有课程的学习。这题的重点是如何使用合适的数据结构来存储图的信息，如果只需要使用拓扑排序的话，我们用两个表就可以完成以上任务，一个表用来存储每一个节点的入度信息，另一个表用来存储每一个节点的后继节点信息。

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

实现 Trie (前缀树)

高级数据结构，前缀树也叫字典树，字典树的深度取决于最大的单词长度，关于字典树的详细介绍：参考 https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/ 比较好理解。在python中字典树就一个嵌套的字典。包括像决策树在python的具体实现也是一个嵌套字典。字典树的具体实现比较简单，但还是有一些细节需要注意，在插入单词的时候需要在最末端加上终止符，判断一个字符串是否是前缀很简答，但是在查找单词的时候需要注意，在末端一定要存在相应的终止符才说明有这个完整的单词，否者只是前缀。

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)

数组中的第K个最大元素

标准的topk问题，排序或者建一个堆。python提供的库函数要比手写的快排要快，这一点要注意。现在有两种办法，一种是直接手写排序，另一种是采用类快排，这样会快一点。
快排参考：https://blog.csdn.net/elma_tww/article/details/86164674

建立一个大顶堆，并且保证堆的元素个数不超过length - k + 1个，但这个方法不是通用的，还是维护一个小顶堆最好，元素数量不超过k个。注意我们在求前k个最大元素的时候，是需要维护一个最小堆的，在求前k个最小元素的时候，需要维护一个最大堆，这一点需要清楚。求第k个最小元素，也可以维护最小堆，保证堆的元素个数不超过length - k + 1个。建立堆的时间复杂度为Nlog(k)，k为堆的元素个数。，当然这个复杂度只是一个近似的表示，还有一些常数项没有写出来。

堆是一颗满二叉树，通过索引可以将数组和堆对应起来。第i个数是根节点，第2i个数是其左节点，第2i+1个数是其右节点。

从头开始建一个堆和把一个现成的数组变成堆是不一样的：数组变成堆是从第一个非叶子节点（数组中的最后一个数）开始自底向上递归；已经建成了堆，又来一个数，就先加在最后面，然后自底向上递归。

解法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: #这里有等号，因为一个数是不需要排序的
                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，如果一个点的左边、上边、左上这三个方向上出现了一个0都不行，因此需要取最小，在具体实现上dp数组需要给左边和上面额外加一层。还有一种思考方式就是要求新添加的一行与一列都为1，这样边长才能为加1。为什么dp数组要和原数组错开一位呢，因为这样方便处理边界条件，这样想的话就发现前面的状态转移方程就比较好理解了。

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

翻转二叉树

很简单的递归操作。

# 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

回文链表

判断一个链表是否属于回文序列，题目要求不借助外部空间来完成这一任务。我看官方题解给的第一种方法是额外定义一个数组来存储链表节点，很简单但是这种方法显然不满足题目要求。
直接反转链表也是不行的，也需要借助外部空间。现在直接借助快慢指针来找到链表的中间点，然后再将链表的前半段半段链表进行反转，再和后半段链表进行比较（注意根据快慢指针停止的条件不同，我们可以判断出链表长度的奇、偶数）。在遍历前半段链表的同时可以同时反转链表，由于这里的快慢节点的起始位置存在差异，因此我们最终的前半段链表和后半段链表的头节点需要根据奇数、偶数来进行一些调整。

# 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

二叉树的最近公共祖先

比较直接解法是记录从根节点到这两个节点的路径，然后选择出这两条路径的公共部分即可。

利用递归关系，比如p或q在当前节点的左子树且p或q在当前节点的右子树，那么当前节点就是这两个节点的公共祖先。但是这种递归写法一定要注意，递归函数在不同条件下会有不同的含义。

还有一种最笨的办法，就是用一个字典记录每一个节点的父节点，然后找到从根节点到这两个节点的路径，最后找到公共部分即可。

解法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

除自身以外数组的乘积

题目要求在o(n)的时间内，并且不能使用除法。解决办法就是错开一位进行连乘。

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

滑动窗口最大值

这里需要建立一个双端队列，并且这个队列是非递增的。为什么要维护一个双端队列，一个端口的队列行不行？因为滑动窗口在移动的过程中，两端的状态都会进行更新，所以需要双端队列。为什么要维护一个非增的队列，如果维护一个非递减的队列的话，滑动窗口在往右移动的过程中，如果当前元素小于队尾元素，则无法进入队列，这样会导致信息丢失。
这一题需要注意的细节是，队列为空的情况，代码中一共有四处判断队列是否为空的情况。

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

暴力法就不多说了，比较直观的写法是对每一行进行二分操作。看了题解发现了一种比较好的办法直接从右上角进行逼近，时间复杂度为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

完全平方数

比较直观的做法就是使用DFS进行暴力搜索，把所有的可能都暴力一边，然后选出最小的那种情况。或者可以使用简单的DP来进行求解：
$dp[i] = min(dp[i], dp[i - j*j] + 1)$
dp[i]表示i需要的最少平方数个数，j表示所有小于sqrt(i)的可能值。
DFS的解法效率太低，本质上和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的个数，然后直接对数组中为0的元素进行操作，操作次数为count次。
解法二：第一种方法还可以优化，可以使用双指针来进行操作。
解法三：借用快排的思想，将不为0和为0的数字进行交换。这个是解法二在写法上的一种优化。

解法一：
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

寻找重复数

比较常用的思路：利用Map来计数，排序也可以，但是题目的要求比较严格，题目提供了二分查找和快慢指针两种解法。二分的话需要转换一下思路，以[1,3,4,2,2]为例，1 + 5 // 2 = 3，而小于等于3的元素有4个，这说明在[1, 3]这个区间里一定存在重复的数字，注意这个[1,3]是指的下标区间，不是原数组，这个得区别一下，因此我们在更新状态的时候与一般的二分查找不一样，并且循环终止的条件也不一样。

利用循环链表的快慢指针来解决。nums[i]表示第一个i节点指向第nums[i]个节点，这样就可以形成一个环形链表了。

解法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：
先找到环，再去找具体的重合点。但是这个题的难点在于起点的初始化，注意这三个初始化条件。
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

二叉树的序列化与反序列化

给定了空节点的话，可以只用一种序列来确定树的结构，这一题采用简单的中序遍历即可。
在序列化的过程中，空的节点也需要入栈，再用一个列表存储每个节点的值即可，空节点的值为null。在反序列化的过程中，同样需要根据给定的列表重建一个队列，但是空的节点就不需要入队列了。注意题目中给定的序列是字符串，需要自己处理一下。

# 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))

最长上升子序列

经典的动态规划问题，与此类似的还有最长公共子序列，注意这里的是严格意义上地上升，并且注意子序列和子串的区别，官方题解写的比较好：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
这种题与最大子串和非常类似，最终的结果是在dp数组中的最大值。但是原始的方法还有待优化的空间。状态转移方程：
$dp[i] = max(dp[i], dp[j] + 1)$ ，j表示i之前的元素，时间复杂度为O(n2)。
采用贪心加二分的策略：维护一个新的数组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的状态稍微有点复杂，状态有点多。由于存在买入、卖出、冷冻这三个动作，因此会存在三个状态：不持有股票且没有卖出，持有股票，不持有股票且卖出。那么我们就可以得到相应的状态转移方程，dp[i]表示第i天能够获得的最大利润，dp[i][0]表示第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])

戳气球

我个人认为这一题的难度还是较高的，这样题其实属于经典的DP问题，不过是换了一个皮。与这个比较类似的有：给定一个矩阵链做乘法，要求乘法次数最少，这个原始问题的DP方程很好写，因为从理解上没有啥困难。但这个题不一样，需要我们转换一下思路，我们先给出状态转移方程：

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

这个的dp[i][j]表示从i到j之间能够取得的最大数值，这里要注意这里是开区间，然后我们需要将这两部分合起来，由于最后这两部分的气球都扎完了，最终只剩下nums[i]，nums[k]，nums[j]这三个气球了，相乘加起来即可，由于这个状态转移方程表示的是开区间，因此我们在实现的时候需要在左右两边加上1。关于初始化的问题，当i=j时，dp[i][j]=0，j=i+1的时候，dp[i][j]=0，在具体的实现的时候，我们需要注意一下，先将长度为2的区间求出来，才能求区间为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+剪枝。贪心的思想好说，尽量先找大的来兑换，但是这种会出现问题，因此我们还是需要遍历所有的路径来寻找一个最小值。如果每次只找一个硬币的话会超时，第一种解法就是这样。我们需要一次尽可能多找硬币，如果超了的话再退回即可，因此这里需要好好设计递归函数的参数，这里我参考的是：https://leetcode-cn.com/problems/coin-change/solution/322-by-ikaruga/，将硬币的索引也加入到参数中，每次选则硬币的数量为1到差额/当前硬币的面值，再通过当前用的硬币数量大于当前的最小值来进行剪枝。

解法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)表示在已经兑换出面额为route，已经使用的硬币数量为count的情况下，最终完成任务所需要的最少硬币数量（包含前面已经使用的count个数硬币）。Dict[res] = num表示的含义是在当前已经兑换出res的面额条件下，兑换amount-res面额最少需要的硬币数量为num。之所以这样设计的原因是可以有很多种不同的分支到达res这个条件，但是后面兑换amount-res面额最少需要的硬币数量这个分支是一样的。那Dict[res] = num可不可以用来表示在当前已经兑换出res的面额条件下，完成整个任务最少需要的硬币数量为num？这个是不可以的，因为res之后的分支是一样的，但是到达res之前的分支却有多种，因此如果一定要Dict表示这一含义，就还需要对key进行一下区分。可以这样写：Dict[(count, res)] = num表示在已经兑换出面额为res，已经使用的硬币数量为count的情况下，最终完成任务所需要的最少硬币数量（包含前面已经使用的count个数硬币）。这个题目有一种变种，比如给每一种面额的硬币数量加一个限制，那这一样的话，我们的key除了记录当前已经兑换出的面额总数，还需要记录剩余的硬币数量，因为到达res这个分支每一种使用的硬币数量可能不同，会导致后面剩余的硬币数量发生变化。

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: #这里是整个算法的关键，后面由于大面额硬币的数量减少，最终用到硬币是一定会增加的，因此可以直接剪掉。
                    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的另一种写法：
可以将数据更新放在for循环里，但这种写法我不推荐，代码臃肿且易出错。
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

需要设计好递归关系，基本的递归关系是祖先与子孙们之和与儿子们之和的大小比较。递归函数表示当前节点下能够偷到的最大钱数，参数只有一个。普通的递归写法容易超时，需要特殊处理一下，我们可以让递归函数返回两个值，一个表示取当前节点能够获得最大值，另一个表示不取当前节点能够获得的最大值，这样的话只需要两个递归分支即可。

解法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：（记忆化搜索：用参数保存中间的结果）
错误写法：
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)#使用中间变量来保存结果，只有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))

比特位计数

题目要求在0（n）的时间复杂度内，因此这一题只能使用位运算。比较巧妙的一种做法是用DP的思想：
$dp[i] = dp[i>>1] + i\&1$

这里要注意python中位运算的优先级，位运算的优先级是最低的，因此要加上括号。
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个高频元素

最直接的解法就是用字典来计数，之后再来排序，但这个时间复杂度是显然不符合题目要求的。

建立一个最小堆，求前 k 大，用小根堆，求前 k 小，用大根堆。面试的时候如果说反了会挂，其实这一点很好理解，以最小堆为例，当堆的元素个数超过了k个，就把堆顶元素出队列，这样就保证每次都把当前最小的元素给排除了，最终剩下的k个元素一定是最大的，同理大顶堆也是这样的。对于这一道题，需要建立一个map来计数，然后通过最小堆来进行维护。

解法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函数。
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)

字符串解码

这一题由于括号会进行嵌套，因此在外面的括号反倒要最后处理，所以这里需要借助栈来进行处理，我个人觉得这一题不很好写，栈里面保存的是字符串的信息和对应的数字信息，参考：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

除法求值

这一题使用图的做法比较好，我看题解有用并查集做的，我个人觉得这样意义不大。题目中的输入就是相当于给定了两个节点和之间权重，因此可以利用这些数据直接建立一个图，而最后的输出也是要计算两个节点之间的权重，因此相当于给定了起点和终点要求路径乘积，所以用深搜最直接。这一题的关键是如何存储图的信息，可以使用一个二阶嵌套的字典来存储两个节点和其权重信息。
关于DFS需要好好设计一下，整个递归函数表示a到b之间的路径乘积，当a==b的时候就返回1，当a和b之间没有路径的时候就返回-1，因此在递归的时候需要判断一下后面是否存在路径，如果后面存在路径则说明a和b都可以找到路径，后面的递归都可以终止了，如果一直没有找到那么说明这两个点之间不存在路径，返回-1即可。我们还可以在参数中设计一个visited数组来存储已经走过的节点，防止重复遍历。

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

根据身高重建队列

这一题其实就是典型的逆序数概念，题目要求根据逆序数把原来的数组进行还原，按照正常的想法：如果我们优先安排小的，后面的元素就比较难安排，因此我们需要优先安排大的元素，并且存在相同元素的话，我们优先安排第二维较小的，因此这一题本质上就是一个排序问题。

这里需要强调一下，python排序函数非常死板，非要传入1, 0, -1这三个数，其中1表示要交换数字，这一点与C语言有很大的区别。
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.给数组做一个逆序排序，这样能更快地到达终点。2. 当找到合适的路径后，直接把其余的分支给剪掉。3. 最终一点，题目给了一个98个1和1个100这样的极端数据，通过判断最大的元素是否大于总和的一半来硬核剪枝。
这一题有一种比较好的办法就是将数组处理成字典这种数据结构，键值对表示元素和其出现的次数，比如{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

一种直观的方法就是把每一个节点的父子关系存储起来，然后进行暴力搜索即可。

双递归，我们需要设计一个递归函数用来记录以当前节点为根节点能够找到满足题意的路径条数，由于树的每一个节点都需要这样操作因此这是一个双递归的操作。

解法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)

找到字符串中所有字母异位词

这种题是经典的滑动窗口题，参考：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/，一句话总结双指针，加上双字典。

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

找到所有数组中消失的数字

一般情况下可以借助字典或者集合来解决，但是题目要求在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务。由于该数组里的每一个元素的大小在1-n之间，通常情况下我们可以使用一个定长的数组来记录这些元素出现的次数，考虑到题目要求不能使用额外空间，因此我们就直接在原数组钟进行修改操作，有一个细节就是将对应位置的元素取反，这样可以不用破坏原有数组的信息（再次取反就可以还原原来的数组）。

解法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做一个异或运算操作，再来看该数二进制表示中0的个数。

解法一：
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

目标和

同样是利用搜索，设计参数的时候需要添加一个索引，表示现在使用到了第几个元素。

可以利用记忆化搜索来进行剪枝叶，但是这种方法很难想。

我个人在设计递归函数的时候不喜欢设计返回值，其实这是一种投机取巧的办法。
解法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：
我们需要想清楚在递归过程中有哪些是重复计算的，比如我们在使用了i个元素且当前和为a的情况下，我们是可以得到还有多少种情况可以满足题意的，因此我们只需要把这一过程记录下来，在后序的过程中，如果再遇到这种情况就不要递归运算，只需要读取就可以了。需要特别注意返回值，如果字典中存在相应的结果直接返回即可，如果不存在那么就判断是否等于S，如果等于就返回1，否则返回0。dfs(route, index, Dict)表示在当前和为route的情况下，使用了index个元素还能够有多少种情况满足题意，Dict用来存储中间状态。Dict的key需要好好说一下，Dict[route] = num表示在当前和为route的情况下，还能有多少种情况满足题意，但这种写法是错误的，因为到达res这个分支有很多种情况，可能用了2个元素，也可能用了3个元素，剩下的和是一定的，但是剩下的元素数量由前面分支来确定，因此需要使用Dict[(route, index)] = num这种写法，来保证记录的是唯一的分支状态。

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, {})

把二叉搜索树转换为累加树

递归含义：设计递归函数需要弄清该递归函数的返回值，也就是该递归函数的表示含义。这个递归函数返回的是根节点。
递归关系：遍历树的顺序应该是：右子树，根节点，左子树。在这个顺序上在进行节点值的更新操作。
递归终点：当前根节点为空则终止。

错误的代码：错误的原因是没有对右节点进行更新操作。
# 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

二叉树的直径

这个题可以转换成求二叉树的高度，二叉树的直径等价于左右子树的高度+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的子数组

暴力法是很容易想到的，固定一边然后对另一边进行枚举，时间复杂度为O（n2），显然这种效率是不高的。由于这一题是求子数组的和，因此我们可以事先将对应的前缀和存储在字典里，然后查询就可以了，两个前缀和相减就可以得到中间一段连续的序列。

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

最短无序连续子数组

从左到右找到最后一个破坏递增的数字下标；从右到左找到最后一个破坏递减的数字下标。

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

任务调度器

调度问题，比较直观的做法是用贪心算法。次数数多的任务优先安排，假设间隔为n，那么我们以n+1个不同的任务为一个单元，通过这样的方式来安排所有的任务。

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我们需要设计好状态转移方程，dp[i][j]代表从i位置到j位置之前的字符串，那么我们可以很容易的得出相应的状态转移方程：

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

在具体实现的时候需要注意，因为状态转移方程是从后往前运算的，因此在实现的时候需要从后往前算，并且在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

每日温度

建立一个递减的栈，将栈中小于当前节点的元素全部出栈，并且计算相应结果，接着再让当前元素入栈。

动态规划，从前往后不方便计算，但是从后往前就好算了，我们需要从第i+1天推出第i天的结果，有一个比较明显的结论是，如果T[i+1] > T[i]那么res[i] = 1，然后跳出循环，否则如果res[i+1]=0，那么res[i]一定为0，然后跳出循环，如果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