算法题 - 简书

栈

有效的括号

方法一：如果输入的是括号的左边，则入栈，否则判断栈顶是否匹配，不符合则无效，匹配则弹出，最终如果栈为空则说明有效，代码如下：

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        l2r = {"(": ")", "[": "]", "{": "}"}
        r2l = {v: k for k, v in l2r.items()}
        for c in s:
            if c in l2r:
                stack.append(c)
            else:
                if not stack or stack[-1] != r2l[c]:
                    return False
                stack.pop()
        return len(stack) == 0

方法二：将匹配的括号全部替换成空，最后如果为空字符串则有效，代码如下：

class Solution:
    def isValid(self, s: str) -> bool:
        li = ["()", "[]", "{}"]
        while any([c in s for c in li]):
            for c in li:
                s = s.replace(c, "")
        return s == ""

栈的压入、弹出序列

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        l = len(pushed)
        if l != len(popped):
            return False
        p = 0
        stack = []
        for ele in pushed:
            stack.append(ele)
            while p < l and stack and stack[-1] == popped[p]:
                stack.pop()
                p += 1
        return p == l

包含min函数的栈

方法一：创建两个栈，一个栈用来压入最新的数据，另一个栈是单调递减栈，只存入当前最小的值，代码如下：

class MinStack:

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

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.mstack:
            self.mstack.append(x)
        else:
            self.mstack.append(min(self.mstack[-1], x))

    def pop(self) -> None:
        self.mstack.pop()
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def min(self) -> int:
        return self.mstack[-1]

每日温度

可以通过维护一个单调递减栈来解决，一旦遇到大于栈顶的值，则将栈内容全部弹出，否则加入栈，代码如下：

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

链表

删除链表中的节点

这题有点特殊，他只给了要删除的节点作为参数，而没给完整的链表，因此我们无法获取到下一个节点。这时候我们可以将当前节点变成他的下一个节点，然后将下一个节点删了即可，示例：

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

返回倒数第 k 个节点

一般倒序的问题都可以结合栈来解决：先将内容都存进栈，然后即可倒序取值，但使用该方法有个很明显的缺点就是浪费空间：必须将这之前的数据都存到栈当中。因此本题还可以使用快慢指针来解决：快指针的起点比慢指针多k-1步，当快指针到终点时，慢指针刚才到达目标点，示例：

class Solution:
    def kthToLast(self, head: ListNode, k: int) -> int:
        slow = fast = head
        n = k
        while n > 0:
            fast = fast.next
            n -= 1
        while fast:
            fast = fast.next
            slow = slow.next
        return slow.val

链表的中间结点

可以使用快慢指针实现：快指针走两步，慢指针走一步，当快指针到终点时，慢指针刚好到中间，示例：

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

环形链表

使用快慢指针来解决：慢指针每次走一步，快指针每次走两步，那么如果存在环，他们必然会相遇（因为快指针每次都比慢指针快一步，假如存在环，快指针迟早会回到慢指针的前面重新追赶，并且每次只能缩小一步的距离，所以最终肯定会使得两个指针在同一个位置相遇）：

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

更多快慢指针的使用参考：https://www.jianshu.com/p/21b4b8d7d31b

看到还有别的比较有意思的解法：

修改节点的值，当遇到相同的，说明已经走过了：

class Solution(object):
    def hasCycle(self, head):
        while head:
            if head.val == 'bjfuvth':
                return True
            else:
                head.val = 'bjfuvth'
            head = head.next
        return False

当然这种要求设置的值肯定是之前就不存在于链表内部的值

因为循环引用的数据无法转JSON格式，因此存在环则转格式会失败，代码如下：

var hasCycle = function(head) {
    try{
        JSON.stringify(head);
    }
    catch(e){
        return true;
    }
    return false;
};

反转链表

迭代实现：逆序可以通过栈来实现，示例：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        stack = []
        while head:
            stack.append(head)
            head = head.next
        res = stack[-1]
        while stack:
            head = stack.pop()
            if not stack:
                break
            stack[-1].next = None
            head.next = stack[-1]
        return res

递归实现：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        self.res = None if head.next else head
        self.reverse(head, head.next)
        return self.res

    def reverse(self, p, c):
        if not c:
            return
        if c.next:
            self.reverse(c, c.next)
        else:
            self.res = c
        p.next = None
        c.next = p

双指针实现：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

相交链表

两个链表如果相交，那么最后相交的一段长度一定是相同的，那么目标就是让他们前面能走相同的长度到达第一个相交点，例如链表A长度为5，链表B长度为8，假如最后一段相交的长度为3，那么A需要走2步到，B需要走5步到，为了能够让他们两同时到第一个相交点，那么需要让B提前走3步，这样两个再同时走两步就到达相交点了，所以步骤如下：

算出链表A和B的长度
算出两个链表长度的差值，并让链表长的那一个提前走差值长的步数
两个链表开始同时走，如果存在相交点就说明相交

代码如下：

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A = headA
        B = headB
        l1 = l2 = 0
        # 计算两个链表的长度
        while A is not None:
            A = A.next
            l1 += 1
        while B is not None:
            B = B.next
            l2 += 1
        # 计算长度差值
        l = l1 - l2
        # 让长的链表先走几步
        if l > 0:
            while l > 0:
                headA = headA.next
                l -= 1
        else:
            while l < 0:
                headB = headB.next
                l += 1
        # 判断相交节点
        while headA is not None and headB is not None:
            if headA is headB:
                return headA
            headA = headA.next
            headB = headB.next
        return None

上面的思想还可以再简化一下：让链表A和B同时走，并且如果链表A走完则继续走链表B，同理链表B走完就走链表A，如果有相交，那么必然最终会走到一起，代码如下：

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a is not b:
            # 这里的判断条件应该是当前节点是否为None，而不是下一个节点是否为None
            # 否则不相交的话则会永远不为None，而无法退出循环
            a = a.next if a else headB
            b = b.next if b else headA
        return a

哈希表

和为K的子数组-基于hash表实现线性查找

class Solution:
    def subarraySum(self, nums, k: int) -> int:
        num = 0
        count = 0
        l = len(nums)
        di = {0:1}

        for i in range(l):
            num += nums[i]
            if num - k in di:
                count += di.get(num - k, 0)
            di[num] = di.get(num, 0) + 1
        return count

堆

数据流中的第K大元素

可以维护一个尺寸为K的小顶堆，当长度小于K时直接添加值，当长度大于K时，若值比堆顶元素大，则直接将值覆盖堆顶元素，否则不进行操作，代码示例如下：

class Heap:
    def __init__(self, k: int, nums):
        self.k = k
        self.heap = [None] * k
        self.index = 0
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        if not self.size_check():
            if val < self.get():
                return self.get()
            self.heap[0] = val
            self.sift_down()
        else:
            self.heap[self.index] = val
            self.sift_up()
            self.index += 1
        return self.get()

    def sift_up(self):
        cur = self.index
        parent = self.get_parent(self.index)
        while not self.is_root(cur):
            if self.compare(self.heap[parent], self.heap[cur]):
                break
            self.heap[parent], self.heap[cur] = self.heap[cur], self.heap[parent]
            cur = parent
            parent = self.get_parent(cur)

    def sift_down(self):
        cur = 0
        while self.has_child(cur):
            left = self.left_child(cur)
            child = None
            if self.has_node(left):
                child = left
            right = self.right_child(cur)
            if not child or (self.has_node(right) and self.compare(self.heap[right], self.heap[left])):
                child = right
            if self.compare(self.heap[child],  self.heap[cur]):
                self.heap[child], self.heap[cur] = self.heap[cur], self.heap[child]
                cur, child = child, cur
            else:
                break

    def get(self):
        return self.heap[0]
    def compare(self, e1, e2):
        return e1 < e2
    @property
    def size(self):
        return len(self.heap)
    def size_check(self):
        if self.index >= self.size:
            return False
        return True
    def is_root(self, v):
        return v == 0
    def get_parent(self, v):
        return (v - 1) // 2
    def has_node(self, i):
        return i < self.index
    def has_child(self, i):
        return self.left_child(i) < self.index
    def left_child(self, i):
        return 2 * i + 1
    def right_child(self, i):
        return 2 * i + 2
    def __str__(self):
        return str(self.heap)

class KthLargest:
    def __init__(self, k: int, nums):
        self.heap = Heap(k, nums)

    def add(self, val: int) -> int:
        return self.heap.add(val)

树

对称二叉树

递归思路：同时遍历左边和右边，如果值不等，就说明不对称：

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def isSame(root1, root2):
            if root1 is None and root2 is None:
                return True
            elif root1 is None or root2 is None:
                return False
            elif root1.val == root2.val:
                return isSame(root1.left, root2.right) and isSame(root1.right, root2.left)
        return isSame(root, root)

迭代思路：层序遍历，判断每一层是否都是回文：

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        res = True
        queue = [(root, 0)]
        di = {}
        while queue:
            node, layer = queue.pop(0)
            di.setdefault(layer, []).append(node.val if node != None else None)
            if node:
                queue.extend([(node.left, layer + 1), (node.right, layer + 1)])
        for k in di:
            if di[k] != di[k][::-1]:
                res = False
        return res

相同的树

递归思路：如果两个节点都为空则相同；只有一个节点为空，则不同；都不为空，则满足两个节点值相同，且左节点都相同，右节点也都相同，则相同，代码如下：

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def isSame(root1, root2):
            if root1 is None and root2 is None:
                return True
            elif root1 is None or root2 is None:
                return False
            elif root1.val == root2.val:
                return isSame(root1.left, root2.left) and isSame(root1.right, root2.right)
            else:
                return False
        return isSame(p, q)

二叉树的最近公共祖先

方法一：递归判断是否在某个节点中，是则说明该节点时公共祖先，否则从根节点开始递归查找，代码如下：

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        def inRoot(root, node):
            if root is None:
                return False
            if root is node:
                return True
            return inRoot(root.left, node) or inRoot(root.right, node)

        def dfs(root, p, q):
            if inRoot(root, p) and inRoot(root, q):
                self.res = root
                dfs(root.left, p, q)
                dfs(root.right, p, q)
        
        if root is None:
            return
        if inRoot(p, q):
            return p
        if inRoot(q, p):
            return q
        self.res = root
        dfs(root, p, q)
        return self.res

上面代码可以简化如下：

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 and not right:
            return
        elif not left:
            return right
        elif not right:
            return left
        return root

二叉搜索树与双向链表

方式一：将所有节点通过中序存到一个list当中，然后修改指向，代码如下：

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def midOrder(root):
            if root is None:
                return
            midOrder(root.left)
            res.append(root)
            midOrder(root.right)
        res = []
        midOrder(root)
        l = len(res)
        if l < 1:
            return root
        for i in range(l):
            res[i].left = res[i - 1]
            res[i].right = res[(i + 1) % l]
        return res[0]

方式二：通过记录前驱节点来修改指向，代码如下：

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def midOrder(cur):
            if cur is None:
                return
            midOrder(cur.left)
            cur.left = self.pre
            if self.pre:
                self.pre.right = cur
            else:
                self.head = cur
            self.pre = cur
            midOrder(cur.right)
        if root is None:
            return
        self.pre = None
        midOrder(root)
        self.head.left = self.pre
        self.pre.right = self.head
        return self.head

二叉搜索树的后序遍历序列

方法一：根据后序遍历的特点，最后一个为根节点，然后可以从左边的子节点中找到第一个比根节点大的，那么之后的都应该比根节点大，代码如下：

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if not postorder:
            return True
        parent = postorder[-1]
        childs = postorder[:-1]
        l = len(childs)
        res = l
        for i in range(l):
            if childs[i] > parent:
                res = i
                break
        for child in childs[res:]:
            if child < parent:
                return False
        left = childs[:res]
        right = childs[res:]
        return self.verifyPostorder(left) and self.verifyPostorder(right)

重建二叉树

方法一：根据前序和中序构建时，可以得知前序的第一个是根节点，然后找到在中序中的索引，那么就可以拆分哪些属于左子树，哪些属于右子树，代码如下：

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

对称的二叉树

方法一：拿自己和自己比，判断自己的左边和自己的右边是否相等，代码如下：

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def isSame(n1, n2):
            if n1 is None and n2 is None:
                return True
            if n1 is None or n2 is None:
                return False
            if n1.val != n2.val:
                return False
            return isSame(n1.left, n2.right) and isSame(n1.right, n2.left)
        return isSame(root, root)

树的子结构

方法一：如果B是A的子结构，则A包含B，所以B一定是A的某一部分，代码如下：

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def dfs(r1, r2):
            if r2 is None:
                return True
            if r1 is None:
                return False
            return r1.val == r2.val and dfs(r1.left, r2.left) and dfs(r1.right, r2.right)
        
        if B is None or A is None:
            return False
        return dfs(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

其中dfs中r2为None则说明r2已经遍历完了，那么肯定是r1的一部分，所以返回True，而r1为None且r2不为None则说明r1遍历完了，但r2还有，说明r2肯定不是r1的一部分

并查集

等式方程的可满足性

可以通过并查集来解决：将所有相等的并到同一个集合，然后再判断所有不相等的左右两个值是否在同一个集合，如果都不在则返回True，否则返回False，代码如下：

class Solution:
    def equationsPossible(self, equations) -> bool:
        uf = UnionFind()
        judges = []
        for equ in equations:
            v1, exp, v2 = equ[0], equ[1:-1], equ[-1]
            if exp == "==":
                # 先将所有相等的并到同一个集合
                uf.union(v1, v2)
            else:
                # 不相等的等会儿在并查集创建完成后进行判断
                judges.append((v1, v2))
        for v1, v2 in judges:
            # 如果自身不等于自身，肯定不成立
            if v1 == v2:
                return False
            # 如果两者在同一个集合，则不成立
            if uf.judge(v1, v2):
                return False
        return True

class UnionFind:
    """实现一个快查找型并查集"""
    def __init__(self):
        self._set = {}
        # 用字典来对并查集进行管理
        self.index = 1
    def find(self, v):
        return self._set.get(v)
    def union(self, v1, v2):
        pv1 = self.find(v1)
        pv2 = self.find(v2)
        if pv1 and pv2:
            tmp = self._set[v2]
            for k, v in self._set.items():
                if v == tmp:
                    self._set[k] = self._set[v1]
        elif not pv1 and not pv2:
            self._set[v1] = self._set[v2] = self.index
            self.index += 1
            return
        elif not pv2:
            self._set[v2] = self._set[v1]
        else:
            self._set[v1] = self._set[v2]
    def judge(self, v1, v2):
        """判断两个内容是否在同一集合，如果都没有加入过并查集，说明也不在同一集合"""
        pv1 = self.find(v1)
        pv2 = self.find(v2)
        if not pv1 and not pv2:
            return False
        return pv1 == pv2

二分

实现 `pow(x, n)`，即计算 x 的 n 次幂函数

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0 or x == 1:
            return x
        num = 1
        i = abs(n)
        while i > 0:
            if (i % 2 != 0):
                num *= x
            x *= x
            i //= 2
        return num if n > 0 else 1 / num

将有序数组转换为二叉搜索树

通过二分，每次将中间的作为父节点，然后左右两边同时按同样的规则递归找父节点作为子节点，代码示例：

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return
        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

在排序数组中查找数字 I

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        
        def count(l, mid, r):
            pl = mid - 1
            pr = mid + 1
            res = 1
            while pl >= l:
                if nums[pl] != target:
                    break
                pl -= 1
                res += 1
            while pr <= r:
                if nums[pr] != target:
                    break
                pr += 1
                res += 1
            return res

        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            num = nums[mid]
            if num == target:
                return count(l, mid, r)
            elif num > target:
                r = mid - 1
            else:
                l = mid + 1
        return 0

递归

全排列问题

def perm(li, x, y):
    if x == y:  #遍历一趟完成
        print(li)
    else:
        for i in range(x, y+1):
            li[x], li[i] = li[i], li[x] #对调位置，同时固定当前位置
            perm(li, x+1, y)    #把对调后的列表传入，对下一个位置进行固定和对调
            li[x], li[i] = li[i], li[x] #对调完成后回来

x = [1,2,3]
perm(x, 0, len(x)-1)

参考

https://www.cnblogs.com/zyoung/p/6764371.html

排列组合实现

def arrange(n, m):
    if m <= 0:
        return 1
    return n * arrange(n - 1, m - 1)

def combin(n, m):
    return arrange(n, m) / arrange(m, m)

print([arrange(10, i) for i in range(10)])
print([combin(10, i) for i in range(10)])
# c(n, m) = a(n, m) / a(m, m)

归并排序

def gb(li, low, high):
    if low < high:
        mid = (low + high) // 2
        gb(li, low, mid)
        gb(li, mid+1, high)
        x(li, low, high)
        print(li)

def x(li, low, high):
    y = li[low:high+1]
    y.sort()    #具体排序应该使用two pointers实现，这里模拟
    li[low:high+1] = y

li = [1,5,4,3,6,2,7,0]
gb(li, 0, len(li)-1)

可以看到每趟结果：

[1, 5, 4, 3, 6, 2, 7, 0]
[1, 5, 3, 4, 6, 2, 7, 0]
[1, 3, 4, 5, 6, 2, 7, 0]
[1, 3, 4, 5, 2, 6, 7, 0]
[1, 3, 4, 5, 2, 6, 0, 7]
[1, 3, 4, 5, 0, 2, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7]

记忆化

区域和检索 - 数组不可变

题目的关键是数组不可变，且多次调用，因此可以设置缓存机制，即提前计算好需要的内容，举例：

class NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums
        l = len(self.nums)
        self.li = [None] * l
        if not self.li:
            return
        self.li[0] = self.nums[0]
        for n in range(1, l):
            self.li[n] = self.li[n - 1] + self.nums[n]

    def sumRange(self, i: int, j: int) -> int:
        if i == 0:
            return self.li[j]
        return self.li[j] - self.li[i] + self.nums[i]

贪心

找硬币

有四种硬币，希望找最少的硬币：

coin = [1, 5, 20 ,25]
res = []

def count_greedy(n):
    i = len(coin) - 1
    while n > 0:
        while n >= coin[i]:
            res.append(coin[i])
            n = n - coin[i]
        i -= 1

count_greedy(41)
print(res)

背包问题

给定物品数量，背包承重量以及物品的重量和价值，假设物品可以拆开加入，那么求背包的东西总价值最高是多少，那么此时可以通过贪心算法，将物品单位价值（价值/重量）从高到低排序，然后依次加入到背包，代码如下：

# 5 8
# 3 5 1 2 2
# 4 5 2 1 3

# n, v = 5, 8
# wc = [(2.0, 1, 2), (1.5, 2, 3), (1.3333333333333333, 3, 4), (1.0, 5, 5), (0.5, 2, 1)]

n, v = [int(i) for i in input().split()]    #数量，总重量
w = input().split() #物品重量
c = input().split() #物品价值
wc = [ (int(c)/int(w), int(w), int(c)) for w, c in list(zip(w, c))]
wc.sort(reverse=True)

result = 0
for each in wc:
    if v == 0:
        break
    if each[1] <= v:
        result += each[2]
        v -= each[1]
    else:
        result += each[0]*v
        v = 0
print(result)

两地调度

https://leetcode-cn.com/problems/two-city-scheduling/

目标：越少花钱越好
思路：先全部选A，然后计算每个人B-A的差价，差价越大说明越不应该选B，然后按差价排序，选出B-A差价最小的前N个，将A替换成B
代码：

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        l = len(costs)
        nums = 0
        di = {}
        for index, each in enumerate(costs):
            nums += each[0]
            di[index] = each[1] - each[0]
        b_a = sorted(di.keys(), key=di.get)
        for i in range(l // 2):
            nums += -costs[b_a[i]][0] + costs[b_a[i]][1]
        return nums

动态规划

找硬币

有四种硬币，希望找最少的硬币：

coin = [1, 5, 20 ,25]

def count_dp(n):
    if n < 0:
        return 1000000
    if n in coin:
        return 1
    return min(*[count_dp(n - i) for i in coin]) + 1
    # 每个硬币的数量最小值 = 减去一堆硬币后的最小值 + 1
print(count_dp(41))

基于迭代实现：

coin = [1, 5, 20 ,25]

def count_dp(n):
    li = [0]*(n+1)
    for i in range(1, n+1):
        tmp = []
        for each in coin:
            if i - each >= 0:
                tmp.append(li[i-each])
        li[i] = min(tmp) + 1
    return li[n]

print(count_dp(41))

展示所选面额：

coin = [1, 5, 20 ,25]

def count_dp(n):
    li = [0]*(n+1)
    # 存放最少所需硬币数
    sel = []
    # 存放当前添加的硬币面值
    for i in range(1, n+1):
        tmp = []
        tmp_coin = []
        for each in coin:
            if i - each >= 0:
                tmp.append(li[i-each])
                tmp_coin.append(each)
        li[i] = min(tmp) + 1
        sel.append(tmp_coin[tmp.index(min(tmp))])
    
    show_coin(sel, len(sel) - 1)
    return li[n]

def show_coin(li, n):
    """展示面额所取的值"""
    res = []
    i = n
    while i > 0:
        res.append(li[i])
        i -= li[i]
    print(res)

print(count_dp(39))

找不同路径

解答

对于每一个点：假设从起点走到其左边的那个点有x种方式，从起点走到其上面的那个点有y种方式，那么走到当前这个点就有x+y种方式，因此状态方程为：dp[m][n] = dp[m-1][n] + dp[m][n-1]，代码如下：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0]* n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 1
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

注：
也可以通过递归实现，但要记忆化搜索，否则复杂度太大，举例：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        self.m = m
        self.n = n
        self.di = {}
        return self.count(1, 1)

    def count(self, x, y):
        if (x, y) in self.di:
            return self.di[(x, y)]
        if x > self.m or y > self.n:
            return 0
        if x == self.m and y == self.n:
            return 1
        self.di[(x, y)] = self.count(x+1, y) + self.count(x, y+1)
        return self.di[(x, y)]

如下图，计算一条总和最大的路径的值

# 5
# 5
# 8 3
# 12 7 16
# 4 10 11 6
# 9 5 3 9 4

# li = []
# for each in range(int(input())):
#   li.append([int(i) for i in input().split()])

li = [[5], [8, 3], [12, 7, 16], [4, 10, 11, 6], [9, 5, 3, 9, 4]]

for i in range(len(li)-2, -1, -1):
    for j in range(len(li[i])):
        li[i][j] = max(li[i+1][j], li[i+1][j+1]) + li[i][j]
        #每行的最值等于下一行的最值加自身
        #比如倒二行的第一个，最值等于max(9, 5)+4
print(li)

结果为：
[[44], [35, 39], [27, 27, 36], [13, 15, 20, 15], [9, 5, 3, 9, 4]]

最大连续子序列和

给定一个序列，求其中一段和最大的序列，例如序列：[-2, 11, -4, 13, -5, -2]，那么和最大的一段就是从第二个到第四个的值的和（11-4+13=20）

https://leetcode-cn.com/problems/maximum-subarray/
先使用暴力法：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        self.nums = nums
        self.maxn = None
        self.divide(0, len(nums))
        return self.maxn

    def divide(self, left, right):
        for i in range(right):
            for j in range(right):
                if left + i < right - j:
                    self.maxn = max(sum(self.nums[left + i: right - j]), self.maxn) if self.maxn != None else sum(self.nums[left + i: right - j])

该方法简单暴力，但很明显：在特别长的输入数据中，必然会超时，于是可以使用动态规划来解决问题：
通过动态规划分析可以得到每一个到当前位置的最大值等于max(前面的最大值与自身的和, 自身)，例如第二个位置的最大值等于：max(-2+11, 11)，即11，到第三个的最大值等于max(11-4, -4)即7，所以得到代码如下：

li = [-2, 11, -4, 13, -5, -2]

for i in range(len(li)-1):
    li[i+1] = max(li[i]+li[i+1], li[i+1])
    #到第n位的最值等于,max(前一位的最值+自身,自身)
print(li)
print(max(li))

结果为：
[-2, 11, 7, 20, 15, 13]
20

动态规划题解如下：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] = nums[i] + max(nums[i-1], 0)
            # 这里把nums[i]提出来了，和上面的其实一样的
        return max(nums)

最长上升子序列

动态规划题解：

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

给两个序列s1、s2，求其中最长的公共子序列，可以不连续，比如：sadstory和adminsorry，那么最长的就是adsory，也就是6
通过动态规划，可以设置一个行为s1长，列为s2长的二维表li来存放第i行j列的最长公共子序列长度，则当前位置如果s1[i]和s2[j]的值一样，长度就为左上角的+1，即li[i-1][j-1]+1，如果不一样，就为左边和上边的取最大值，即max(li[i-1][j], li[i][j-1])，因此题解如下：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1 = len(text1)
        l2 = len(text2)
        if l1 == 0 or l2 == 0:
            return 0
        dp = [[0] * (l2 + 1) for _ in range(l1 + 1)]
        for i in range(l1 + 1):
            dp[i][0] = 0
        for i in range(l2 + 1):
            dp[0][i] = 0
        for i in range(1, l1 + 1):
            for j in range(1, l2 + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[l1][l2]

0-1背包问题

背包问题的解决方法一般有两种，一种是贪心算法，另一种则是动态规划，而对于0-1背包问题，贪心算法算出的结果往往可能不是最优解，具体参考：
https://blog.csdn.net/qq_16234613/article/details/52235082
因此采用动态规划才是最优算法：承重为j的最优值等于遍历所有物品后的max(承重为j的值, 承重为j-自身重量+自身值)，得到代码如下：

# 5 8
# 3 5 1 2 2
# 4 5 2 1 3

n, v = 5, 8
#5个物品，承重为8
w = [3, 5, 1, 2, 2]
#物品重量
c = [4, 5, 2, 1, 3]
#物品价值
li = [0]*(v+1)
#承重从0到8的最优值

for i in range(1, n):
    j = v
    while j >= w[i]:
        li[j] = max(li[j], li[j-w[i]]+c[i])
        j -= 1
print(li)
print(max(li))

结果为：
[0, 2, 3, 5, 5, 6, 7, 8, 10]
#背包承重为0时最高价值为0；为1时最高价值为2；为2时最高价值为3...；为8时最高价值为10
10

剪绳子

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            maxv = 0
            for j in range(1, i):
                maxj = max(j * (i - j), j * dp[i - j])
                if maxj > maxv:
                    maxv = maxj
            dp[i] = maxv
        return dp[-1]

上面的代码可以简化如下：

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        return dp[-1]

滑动窗口

和为s的连续正数序列

方法一：暴力法，枚举所有的结果，代码如下：

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        l = target // 2 + 2
        for i in range(1, l):
            tmp = i
            j = i
            while tmp < target:
                j += 1
                tmp += j
            if tmp == target:
                res.append(list(range(i, j + 1)))
        return res

方法二：滑动窗口，窗口不断右移，代码如下：

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        pl = pr = 1
        r = target // 2 + 1
        res = []
        count = 0
        while pl <= r:
            while count < target:
                count += pr
                pr += 1
            while count > target:
                count -= pl
                pl += 1
            if count == target:
                res.append(list(range(pl, pr)))
                count -= pl
                pl += 1
        return res

数学

只出现一次的数字（异或/去重）

由于异或运算遵循下面规则：

a ^ b = 0, a == b
0 ^ a = a
a ^ b ^ c = a ^ c ^ b

因此可以用异或进行解答：

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

也可以使用集合去重：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return sum(set(nums))*2 - sum(nums)

DFS

适合求排列组合、集合的场景

字母大小写全排列

可以通过dfs遍历：如果是大写字母，则添加将其变成和不变成小写字母遍历的情况；如果是小写字母，则...；否则（数字）就添加不改变的情况
代码实现：

class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        S = S.lower()
        l = len(S)
        res = set()
        def dfs(i, s):
            if i == l:
                res.add(s)
                return
            if S[i].islower():
                dfs(i + 1, s + S[i].upper())
            if S[i].isupper():
                dfs(i + 1, s + S[i].lower())
            dfs(i + 1, s + S[i])
        dfs(0, "")
        return list(res)

二进制手表

将所有灯当做10位数的二进制，对应位置分别为指定值，在边界范围内dfs遍历情况，实现：

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        sel = [1,2,4,8,1,2,4,8,16,32]
        res = []
        def dfs(n, h, m, i):
            if n == 0:
                res.append((h, m))
                return
            if i >= 10:
                return
            if i < 4:
                if h + sel[i] < 12:
                    dfs(n - 1, h + sel[i], m, i + 1)
            else:
                if m + sel[i] < 60:
                    dfs(n - 1, h, m + sel[i], i + 1)

            dfs(n, h, m, i + 1)
            
        dfs(num, 0, 0, 0)
        return list(map(lambda item: f'{item[0]}:{item[1]:02}', res))

字符串的排列

方法一：dfs全排列，代码如下：

class Solution:
    def permutation(self, s: str) -> List[str]:
        def dfs(c, s):
            if len(c) == l:
                res.add(c)
                return
            for i in range(len(s)):
                dfs(c + s[i], s[:i] + s[i + 1:])
        l = len(s)
        res = set()
        dfs("", s)
        return list(res)

N 皇后

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        
        def place(row, col):
            for i in range(n):
                # 同一行、列不能有
                if mat[row][i] == "Q" or mat[i][col] == "Q":
                    return False
                # 斜线上不能有
                for j in range(n):
                    if (i - j == row - col or i + j == row + col) and mat[i][j] == "Q":
                        return False
            return True
        
        def travel(row):
            # 如果最后一行也放置完成，说明放置完成
            if row == n:
                res.append(["".join(m) for m in mat])
                return
            # 回溯每一列
            for i in range(n):
                # 如果当前列不能放，则寻找下一列
                if not place(row, i):
                    continue
                # 如果当前列能放，那么放入后，递归寻找下一行放置的位置
                mat[row][i] = "Q"
                travel(row + 1)
                # 上一个结果放置完成后，继续寻找下一种情况
                mat[row][i] = "."

        # 初始化棋盘
        mat = [["."] * n for _ in range(n)]
        # 从第一行开始放置
        res = []
        travel(0)
        return res

迷宫问题

maze = [
   [1,1,1,1,1,1,1,1,1,1],  #迷宫，1代表墙，0代表通路
   [1,0,0,1,0,0,0,1,0,1],
   [1,0,0,1,0,0,0,1,0,1],
   [1,0,0,0,0,1,1,0,0,1],
   [1,0,1,1,1,0,0,0,0,1],
   [1,0,0,0,1,0,0,0,0,1],
   [1,0,1,0,0,0,1,0,0,1],
   [1,0,1,1,1,0,1,1,0,1],
   [1,1,0,0,0,0,0,0,0,1],
   [1,1,1,1,1,1,1,1,1,1],
]

dirs = [
   lambda x, y : (x+1, y), #按右左上下方向找路
   lambda x, y : (x-1, y),
   lambda x, y : (x, y-1),
   lambda x, y : (x, y+1)
]

def mpath(x1, y1, x2, y2):  #起点和终点
   stack = []
   stack.append((x1, y1))
   while len(stack) > 0:
      curNode = stack[-1] #栈顶记录当前位置
      if curNode[0] == x2 and curNode[1] == y2:   #到达终点
         print("The path is {0}".format(stack))
         return True
      for dir in dirs:    #循环找四个方向
         nextNode = dir(curNode[0], curNode[1])  #判断是否通路
         if maze[nextNode[0]][nextNode[1]] == 0:
            stack.append(nextNode)
            maze[nextNode[0]][nextNode[1]] = -1 #走过的路防止重走
            break
      else:   #循环结束都没有
         maze[curNode[0]][curNode[1]] = -1
         stack.pop() #当前路是死路，回退
   print("Nothing")
   return False

mpath(1,1,8,8)

多指针

验证回文字符串 Ⅱ

思路：设定双指针，一个指向头，一个指向尾。因为最多允许删除一个字符，因此头尾判断时，如果头和尾的字符相同，则各往中间走一步，否则判断头或尾删除一个以后是否回文

class Solution:
    def validPalindrome(self, s: str) -> bool:
        sr = s[::-1]
        if s == sr:
            return True
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                tmpl = s[:left] + s[left + 1:]
                tmpr = s[:right] + s[right + 1:]
                return tmpl == tmpl[::-1] or tmpr == tmpr[::-1]
        return True

判断子序列

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if s == "":
            return True
        if t == "":
            return False
        ps = 0
        pt = 0
        ls = len(s)
        lt = len(t)
        while ps < ls and pt < lt:
            if s[ps] == t[pt]:
                ps += 1
            pt += 1
        if ps != ls:
            return False
        return True

和为s的两个数字

方法一：双指针，一个在最左，一个在最右，两个不断往中间走，代码如下：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        l = 0
        r = len(nums) - 1
        while l < r:
            n = nums[l] + nums[r]
            if n == target:
                return [nums[l], nums[r]]
            elif n < target:
                l += 1
            else:
                r -= 1
        return []

丑数

方法一：定义三个指针，分别标记经过的2/3/5倍数的丑数，代码如下：

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        if n <= 1:
            return n
        p2 = p3 = p5 = 0
        res = [1]
        for i in range(n - 1):
            res.append(min(res[p2] * 2, res[p3] * 3, res[p5] * 5))
            if res[-1] % 2 == 0:
                p2 += 1
            if res[-1] % 3 == 0:
                p3 += 1
            if res[-1] % 5 == 0:
                p5 += 1
        return res[-1]

其他

除自身以外数组的乘积

可以定义两个数组，分别存放某一个位置的左边和右边的乘积，然后交叉相乘即可，代码如下：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left = [1]
        right = [1]
        l = len(nums)
        for i in range(1, l):
            left.append(left[i - 1] * nums[i - 1])
            right.append(right[i - 1] * nums[l - i])
        return [left[i] * right[l - i - 1] for i in range(l)]

上面的代码实现的空间复杂度为O(n)，因此可以再优化如下：先定义一个结果数组存放返回结果，初始化所有的值都为1，然后遍历每个元素都和他左边的乘积相乘，然后再遍历他们和右边的乘积相乘，代码如下：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        l = len(nums)
        res = [1] * l
        left = right = 1
        for i in range(l):
            res[i] *= left
            left *= nums[i]
            res[l - i - 1] *= right
            right *= nums[l - i - 1]
        return res

虽然空间复杂度还是O(n)，但额外空间复杂度（除去返回结果的）则降到了O(1)