1.递归:

70, 爬楼梯

初始值：f(1) = 1，f(2) = 2

class Solution:
    def climbStairs(self, n: int) -> int:
        a,b=1,1
        for _ in range(n-1):
            a , b= b, a+b
        return b

112. 路径总和

递归（深度优先搜索）DFS（Depth First Search）

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == targetSum
        return self.hasPathSum(root.left, targetSum- root.val) or self.hasPathSum(root.right, targetSum- root.val)

用堆栈的方式解决：

栈：用一个列表表示[]

进栈：stack.append()

出栈 out=stack.pop()

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        stack = [(root, root.val)]
        while stack:
            node,s = stack.pop()
            if not node.left and not node.right:
                if s == targetSum:
                    return True
            if node.right:
                stack.append((node.right, s + node.right.val))
            if node.left:
                stack.append((node.left, s + node.left.val))
        return False

2.分治:

23. 合并 K 个升序链表

解题思路：

首先将K个列表合并的问题简化为2个有序列表合并的问题merge_two

生成一个dummy的node用于记录两个列表的合并，

        比较两个列表的当前节点，L1和L2。选择较小的那个，将新键node的next附加到较小的那个节点，并把Lx节点往后推移一个

        然后再把cur往后推移一个，继续循环

        如果有一个表结束了，那么直接把剩下的附加上

对于K个这样的表，采取分治的方法。分别合并[left，mid]和[mid+1, right]的子集合，然后把这两个left和right表再合并

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        return self.merge_range(lists, 0, len(lists)-1)

    def merge_two(self,L1, L2):
        dummy = ListNode(0)
        cur= dummy
        while L1 and L2:
            if L1.val <= L2.val:
                cur.next = L1
                L1  = L1.next
            else:
                cur.next = L2
                L2  = L2.next
            cur = cur.next
        cur.next = L1 if L1 else L2
        return dummy.next
    def merge_range(self, lists, left, right):
        if left == right:
            return lists[left]
        mid = (left+right) // 2
        L1 = self.merge_range(lists, left, mid)
        L2 = self.merge_range(lists, mid+1, right)
        return self.merge_two(L1,L2)

3.单调栈:

739. 每日温度

思路：

创建一个栈用于存放天数id，每新加一天的温度，就和栈顶天数的温度比较，如果比栈顶温度高，则弹出那天的id，其answer就是和当前天数id的差值。

走出这个循环后，将当天的id加入stack。

操作： 

栈： stack=[]

栈顶： stack[-1]

出栈：stack.pop()

入栈：stack.append(i)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0]*n
        stack = []

        for i , temp in enumerate(temperatures):
            while stack and temp > temperatures[stack[-1]]:
                idx = stack.pop()
                ans[idx] = i -idx
            stack.append(i)
        return ans

4，并查集

547.省份数量

结题思路：主要是构建一个parent和rank的数组结构。对于connected的城市，找到其parent节点。在遍历完上三角后，求出unique的parent节点的数量，即为省份数量

class unionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    
    def find(self, x):
        # 寻找根节点
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        # 直到self.parent[x] == x，也就是根节点的id
        return self.parent[x]

    def union(self, x, y):
        # 合并函数
        px, py = self.find(x), self.find(y)
        if px == py: # 根节点相同
            return
        # 两个城市相连，但是还未合并时：按秩合并
        # 把低的树挂到高的树下面，这样不会增加树的高度
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py # 小的挂到大的上
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else: # 两个rank一样 # 如果高度相等，任意挂一边，并把高度 +1
            self.parent[py] = px
            self.rank[px] += 1 

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:

        n = len(isConnected)
        uf = unionFind(n)
        for i in range(n):
            for j in range(i + 1, n):  # 上三角即可，避免重复
                if isConnected[i][j] == 1:
                    uf.union(i, j)
        # 统计不同的根节点数量
        return len(set(uf.find(i) for i in range(n)))

5，滑动窗口

209，长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路：设置left边界和right边界，不断平移right边界，记录框选区域的和，当框选区域的和超过target时，就右移left边界，直到right边界达到最右侧。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums) # 用于记录最短长度
        left =0
        curr_sum = 0
        min_len = n+1 
        for right in range(n):
            curr_sum += nums[right]
            while curr_sum >= target: # 如果超过target，则去掉左侧
                min_len = min(min_len, right-left+1)
                curr_sum -= nums[left]
                left+=1 # 左侧边界右移
        return min_len if min_len <= n else 0

6，前缀和

724，寻找数组的 中心下标

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

思路：先求出数组总长，然后用left来记录左侧所有数的和，并不断右移，直到left的值等于right数的和。

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        left = 0 # 左侧数的和

        for i, x in enumerate(nums):
            if left == total - left - x:
                return i
            else:
                left += x
        return -1

7，差分

1094，拼车

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips ,  trips[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

思路：这题很简单。只需要记录车行驶的路程。以及在每个节点上下车的diff情况，然后对diff遍历前缀和并与capacity比较即可。

trips = [[2, 1, 5], [3, 3, 7]]
capacity = 4

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # 创建位置数组和diff数组
        maxPos = 0
        for num, start, end in trips:
            maxPos = max(maxPos, end)
        diff = [0] * (maxPos + 1)

        # 记录每个上下节点，车上人数的变化
        for num, start, end in trips:
            diff[start] += num
            diff[end] -= num

        # 计算前缀和
        current = 0
        for x in diff:
            current += x
            if current > capacity:
                return False

        return True

8，拓扑排序

210，课程表II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

• 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

思路：

BFS ： Breadth First Search 的缩写，中文叫广度优先搜索

思路：创建一个graph，用于记录所有课程的后继课程。创建一个indegree数组，用于基于所有课程的前置课程个数。

创建一个队列，放入所有入度为0（可以直接学习）的课程。用head从前往后输出值，输出的值放入学习顺序的数组order。并把该课程的后续课程的入度减一。如果后续课程入度减到0，则将其加入到队列末尾。一直将该队列遍历完即可。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 建图与入度
        graph = [[] for _ in range(numCourses)] # graph 存放课程id的后续课程next
        indegree = [0] * numCourses # 课程id的入度，代表还需要学习的前置课程数量

        for a, b in prerequisites:
            graph[b].append(a) # 加入后续课程
            indegree[a] += 1

        # 手写一个简单队列（用列表）
        queue = []
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i) # 初始化可以学的课程（入度为0
                
        head = 0  # 用 head 指针代替 popleft，提高性能
        order = [] 

        # BFS 拓扑排序
        while head < len(queue): # 遍历列队列
            course = queue[head]
            head += 1
            order.append(course) # 学习顺序

            # 所有直接后继课程入度减一
            for nxt in graph[course]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt) # 入度为0时表示可以学习了，加入队列

        # 判断是否完成所有课程
        if len(order) == numCourses:
            return order
        return []