24. 两两交换链表中的节点
解题思路：链表题大部分需要一个虚拟节点（哨兵节点）。
对于本题，就是需要在最前面，维护一个虚拟节点-head-head.next的结构，然后修改虚拟节点的指针到第二个节点，head节点的指针指向后续节点，第二个节点的指针指向head节点，这样交换了节点，同时虚拟节点的指针也是指向更新后的头节点的。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next: return head
# 初始化哨兵节点
dummyNode = ListNode(0) # 在头节点前面加一个虚拟节点，形成tmep-head-head.next的形式
dummyNode.next = head
temp = dummyNode # 赋值给虚拟头节点
# 当存在至少两个节点时
while temp.next and temp.next.next:
# 设置第一个节点和第二个节点
node_1 = temp.next
node_2 = temp.next.next
# 首先将虚拟节点的指针指向第二个节点
temp.next = node_2
# 将第一个节点的指针指向后续链表的节点
node_1.next = node_2.next # 跟后面的续上
# 将第二个节点的指针指向第一个节点，实现交换
node_2.next = node_1
# 这时的顺序是temp-node2-node1-后续
# 为了维护该顺序，将node1作为temp
temp = node_1
# 使用temp逐个交换节点对，但是temp用完了，是到最后了，不是头节点
# dummyNode.next才是头节点
return dummyNode.next
70. 爬楼梯
相似题：322. 零钱兑换
解题思路：一次只能走1或2步，所以当前步的方案数是由前两个的可能方案数决定的。
状态转移方程： f(n) = f(n-1)+f(n-2)
class Solution:
def climbStairs(self, n: int) -> int:
# 状态数组
dp = [n+1 for _ in range(n+1)]
# 根据题意，可以得到前两个肯定都是1
dp[0], dp[1] = 1, 1
# 状态转移方程： f(n) = f(n-1)+f(n-2)
# 持续更新
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
滚动数组的方式，也只需要维护三个元素，n-2,n-1,n，每次循环都往前移动一位
class Solution:
def climbStairs(self, n: int) -> int:
# 滚动数组，初始化n-2,n-1,n
p,q,r = 0,0,1
# 遍历n，滚动
for i in range(1, n+1):
# n-2往前移动
p = q
# n往前移动
q = r
# 新的n的值由前两个决定
r = p + q
return r
53. 最大子数组和
依旧是动态规划。
求的是最大子数组和，可以先假设每个数字都是可能的最大子数组的最后一位，可以先拿两个举例。
nums = [1,-2,4,3]
1可能是最后一位，那么最大子数组和就是1
-2，最大子数组和就是1+(-2)= -1，这当然不是，应该是max(-1, 1)=1
4，就是4
所以可以得到状态转移方程,dp是nums的辅助列表，存储当前的最大和的
dp[i] = max(nums[i] + dp[i-1], nums[i])
也可以理解为如果dp[i-1]<=0,那么就没必要看它的，当前状态就看当前的值就行
代码如下
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 辅助列表
dp = [0] * len(nums)
dp[0] = nums[0]
# 遍历
for i in range(1, len(nums)):
# dp[i] = max(dp[i-1]+nums[i], nums[i])
if dp[i-1] > 0:
dp[i] = dp[i-1]+nums[i]
else:
dp[i] = nums[i]
return max(dp)
也可以这样，直接更新Nums
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
m = nums[0] # 取出第一个元素
a = [] # 结果列表
# 从第二个索引到最后一个进行遍历
for i in range(1, len(nums)):
# 如果第一个元素为正，那就有累加的价值，那么第二个索引的值就是当前值加上第一个索引的值
if nums[i-1]>0:
nums[i]=nums[i]+nums[i-1]
# 如果当前的前一个元素不为正，那就没有累加的必要，直接返回当前元素值
# 把每个元素都添加到结果列表，这样就是有了局部累加的和，还有不累加的自己的值
a.append(nums[i])
# 把第一个元素也添加进来
a.append(m)
# 返回最大值
return max(a)
46. 全排列
递归+回溯。
解题思路：固定第一个元素，遍历可能的其他元素的排列；固定第二个元素，遍历可能的其他元素的排列。
递归终止条件：
深度搜索到底了，也就是起始点==len(nums)
递归的参数：
每次移动一步，找下一个可能的元素
递归主体：
将当前元素和起点元素交换，使得当前元素作为新的排列的起点； 递归（参数+1），将第二个元素作为新的后序排列的起点，直到遍历完成；
撤销交换，恢复原状。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# 递归函数，初始化第一个索引
def dfs(first = 0):
# 终止条件，如果深度搜索到底了，就返回当前交换后的nums的副本，如果不这样，就会引用内存的值
if first == n:
output.append(nums[:])
# 遍历以每个数字开头的情况
for i in range(first, n):
# 将当前的元素和开头的元素交换，使得此次以当前元素作为开头
nums[first], nums[i] = nums[i], nums[first]
# 固定当前元素为起始，深度搜索剩余元素组成的排列情况，此时Nums已经是由当前元素开头的了
dfs(first+1)
# 以当前元素为开头尝试深度搜索完成后，撤销该操作，还原nums
nums[first], nums[i] = nums[i], nums[first]
# 数组长度，结果列表
n = len(nums)
output = []
# 开启递归
dfs()
return output
22. 括号生成
解题思路：
递归+回溯
参数：可能的组合temp，左括号数量left，右括号数量right
终止条件：字符串长度等于2n
主体：当左括号不够时，递归加深；右括号不够时，递归加深
是的，你的理解是正确的。在递归的过程中，每一步都是在探索所有可能的括号组合。通过先经过
left < n的条件来添加左括号，再经过
right < left
来添加右括号，直到达到结束条件，我们就能确保探索到所有有效的括号组合。这个过程可以通过一步一步回顾来更好地理解：
向下递归：首先，递归尝试添加尽可能多的左括号（
left < n），直到不再能添加为止（即左括号数量达到n）。转向添加右括号：当不能再添加左括号时，开始尝试添加右括号（
right < left），因为只有当已经有左括号在前面，我们才能添加右括号来与之匹配。达到结束条件：当左右括号都添加完毕，即
cur的长度达到2*n时，表示找到了一个有效的括号组合，将其添加到结果列表中。回溯：完成当前递归分支后，递归会回到上一个状态，尝试另一种括号的添加方式，这可能涉及撤销上一步添加的右括号并尝试在其他位置添加，或者撤销一个左括号的添加并换成右括号。
逐层返回：通过回溯和逐层返回，递归函数会继续探索所有未尝试过的括号添加位置，直到所有可能的组合都被探索过。
整个过程是通过递归函数的调用栈来维护的，每一层的递归调用都会尝试一个不同的括号添加方式，并通过回溯来撤销这些尝试，从而确保能探索到所有可能的组合。这种方法的优点是它自然而然地遵循了有效括号组合的规则，同时也避免了重复和无效的尝试。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def generate(temp, left, right):
# 终止条件
if len(temp) == 2*n:
res.append(temp)
# 如果左括号数量没够，继续加左边的
if left < n:
generate(temp+'(', left+1, right)
# 如果加完后发现右括号数量没够，继续加右边的
if right < left:
generate(temp+')', left, right+1)
# 字符串组合初始化
temp = ''
left, right = 0, 0
res = [] # 结果列表
generate(temp, left, right)
return res
39. 组合总和
思路：
排序（可选）：首先，可以对candidates进行排序。虽然题目并未要求结果有序，排序有助于提前终止不必要的搜索。回溯：使用回溯算法遍历所有可能的组合。从candidates的第一个数字开始，尝试将其加入到当前组合中，然后递归地调用自身来处理剩余的数字。在每一步中，我们可以选择“使用当前数字”或“跳过当前数字”。
剪枝：如果当前组合的和大于target，则停止进一步搜索这个分支，因为加入更多的数字只会使和增大。如果和正好等于target，则将当前组合添加到结果列表中。
避免重复组合：为了避免生成重复的组合，当我们在同一层递归中遇到相同的数字时，应该跳过这些重复的数字。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start, path, target):
# 终止条件1 找到可行路径
if target == 0:
res.append(path[:]) # 保存的副本
# 终止条件2 不可能找到可行路径
if target < 0:
return
for i in range(start, len(candidates)):
# 尝试选择当前数字作为元素
path.append(candidates[i])
# 递归，可以重复选择
backtrack(i, path, target-candidates[i])
# 撤销，回溯
path.pop()
# 结果列表
res = []
backtrack(0, [], target)
return res
93. 复原 IP 地址
解题思路：递归加回溯
可以画一个n叉树，假设每个索引都可能是子序列的起点，递归检查是否满足条件，如果不满足就撤销回退，继续递归检查。
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = [] # 结果列表
temp = [] # 子序列数字
def backtrack(index):
# 只能被完全切割为4段
if len(temp) == 4 and index == len(s): # 找到了，终止
res.append('.'.join(temp))
if len(temp) > 4: # 找错了，false
return
# 遍历，假设每个位置都可能是起点
for i in range(index, len(s)):
# 初始化每个区间
sub = s[index: i+1]
# 检测是否符合条件
if int(sub) > 255: # 当前索引切割失败，不符合数据区间
continue
# 如果是'00'这些，就会被第二个条件检查出来
if int(sub) == 0 and i != index: # 检测是否是前导0
continue
# 如果是'08'这些，就会被检测出来
if int(sub) > 0 and s[index] == '0':
continue
# 经典递归加回溯
temp.append(s[index: i+1])
backtrack(i + 1)
temp.pop() # 还原
backtrack(0)
return res
