LeetCode100 -- Day3
1. 回溯：46、78、17
1. 回溯：通过深度优先搜索（DFS）的策略来遍历所有可能的解空间，当遇到不符合条件的情况时，就返回上一步（回溯），尝试其他路径。
2. 实现思路
（1）定义解空间：确定问题的解形式（如一个数组或一个字符串序列）。
（2）确定约束条件：在解空间中，有些路径可能不符合要求，需要跳过。
（3）深度优先搜索：递归或迭代地构建候选解，并在构建过程中检查约束条件。
（4）回溯：当构建到某一步发现不能继续满足条件时，就回退到上一步，选择其他路径。
3. 基本模板：
def backtrack(路径, 选择列表):if 满足结束条件:结果.append(路径.copy()) # 注意：如果直接添加路径，后面修改会影响结果，所以用拷贝returnfor 选择 in 选择列表:做出选择backtrack(路径, 选择列表) # 递归撤销选择
（1）46 全排列
class Solution(object):def permute(self, nums): def backtrack(cur_result, nums_remain):""" 没有选择，说明已经完成一个排列 """if not nums_remain:## 浅拷贝：创建一个与cur_result内容相同的新列表，避免后续操作影响已保存的结果results.append(cur_result[:])return""" 遍历所有可选择元素 """for i in range(len(nums_remain)):""" 做出选择：将当前元素添加到cur_result """num = nums_remain[i]cur_result.append(num)""" 更新剩余可选择的元素（移除当前元素） """cur_nums_remain = nums_remain[:i]+nums_remain[i+1:] ## 新列表：[0,i)+[i+1,n)""" 递归处理下一层选择 """backtrack(cur_result, cur_nums_remain)""" 撤销选择(回溯) """cur_result.pop()results=[]backtrack([],nums)return results（2）78 子集
方法一：回溯
class Solution(object):def subsets(self, nums):def backtrack(start,cur_result):results.append(cur_result[:])for i in range(start,len(nums)):cur_result.append(nums[i])backtrack(i+1,cur_result)cur_result.pop()results=[]backtrack(0,[])return results执行流程示例（nums = [1,2]）：
初始调用: backtrack(0, [])- 添加 [] → results = [[]]- 遍历 i=0: 选择1 → [1]- 递归: backtrack(1, [1])- 添加 [1] → results = [[], [1]]- 遍历 i=1: 选择2 → [1,2]- 递归: backtrack(2, [1,2])- 添加 [1,2] → results = [[], [1], [1,2]]- 回溯: 移除2 → [1]- 回溯: 移除1 → []- 遍历 i=1: 选择2 → [2]- 递归: backtrack(2, [2])- 添加 [2] → results = [[], [1], [1,2], [2]]方法二：迭代法
class Solution(object):def subsets(self, nums):results=[[]]for num in nums:# 存储当前元素生成的新子集cur_result = [] # 遍历原有子集for result in results:""" 创建新子集 = 原子集 + 当前元素 """cur_result.append(result + [num])# 将新子集添加到结果中results.extend(cur_result)return resultsappend vs extend：
append：将整个对象作为一个元素添加到列表的末尾
extend：将可迭代对象中的每个元素逐个添加到列表的末尾
引申：90 子集②（可能存在重复元素）
class Solution(object):def subsetsWithDup(self, nums):"""回溯"""def backtrack(start, cur_result):if cur_result not in results:results.append(cur_result[:])for i in range(start,len(nums)):cur_result.append(nums[i])backtrack(i+1,cur_result)cur_result.pop()results=[]nums=sorted(nums)backtrack(0,[])return results"""迭代"""results=[[]]nums = sorted(nums)for num in nums:cur_result=[]for result in results:cur_set = result+[num]if cur_set not in results:cur_result.append(cur_set)results.extend(cur_result)return results（3）17 电话号码的字母组合
方法一：回溯
class Solution(object):def letterCombinations(self, digits):mapping = {'2': 'abc','3': 'def','4': 'ghi','5': 'jkl','6': 'mno','7': 'pqrs','8': 'tuv','9': 'wxyz'}if not digits: return []def backtrack(now,cur_result):""" 已经找到全部digit对应的字母 """if now==len(digits):results.append(cur_result)return """ 当前digit对应的字母们 """cur_letter=mapping[digits[now]]""" 递归处理下一个数字 """for letter in cur_letter:backtrack(now+1,cur_result+letter)results=[]backtrack(0,"")return results方法二：迭代
if not digits: return []results=[""]for digit in digits:cur_result=[]for result in results:for letter in mapping[digit]:cur_result.append(result + letter)results = cur_resultreturn results2. 滑动窗口：3、438
滑动窗口处理字符问题：
1. 适合处理：
（1）区间统计（无重复字符的最长子串、统计字符串中包含特定字符模式的数量、计算最多包含K个不同字符的子串数量）
（2）模式匹配（字母异位词、最小覆盖子串、字符串排列问题）
（3）字符频率（字符频率满足特定条件的最小子串、特定模式计数问题）
（4）优化问题（满足条件的最小最长子串）
2. 实现模板
（1）变长窗口问题
def variable_length(s):left = 0for right in range(len(s)):update_state(s[right]) # 添加右边字符""" 收缩窗口直到满足条件 """while not condition_satisfied():remove_state(s[left])left += 1update_result() # 更新结果（可能求最大/最小）（2）固定窗口问题
def fixed_length(s, k):""" 初始化窗口状态 """for i in range(k):update_state(s[i])""" 检查初始窗口 """if check_state(): record_result(0)""" 滑动窗口 """for i in range(k, len(s)):remove_state(s[i-k]) # 移除最左侧字符update_state(s[i]) # 添加新字符if check_state(): record_result(i-k+1)
（1）3 无重复字符的最长子串→变长窗口问题
class Solution(object):def lengthOfLongestSubstring(self, s):charset = set()left=0max_len=0for right in range(len(s)):while s[right] in charset:charset.remove(s[left])left+=1charset.add(s[right])max_len = max(max_len, right-left+1)return max_len（2）438 找到字符串中所有字母异位词→固定窗口问题
from collections import defaultdict
class Solution(object):def findAnagrams(self, s, p):p_len,s_len = len(p),len(s)if s_len<p_len: return []## 字符计数器p_count = defaultdict(int)for char in p:p_count[char] += 1window = defaultdict(int)results=[] """ 处理第一个窗口并检查 """for right in range(p_len):window[s[right]] += 1if window==p_count:results.append(0)""" 开始滑动窗口 """for right in range(p_len,s_len):left_char = s[right-p_len]window[left_char] -= 1## 避免数量为0的字符干扰判断if window[left_char]==0:del window[left_char]right_char = s[right]window[right_char] += 1if window==p_count:results.append(right-p_len+1)return results3. 子串：560
（1）560 和为K的子数组
定义 prefix[i] 表示数组从开头到索引 i 的元素和。
对于每个结束位置 j，找到起始位置 i 使得 prefix[j] - prefix[i] = k
→ 只需要统计每个结束位置前，有多少个起始位置满足 prefix[i] = prefix[j] - k
class Solution(object):def subarraySum(self, nums, k):prefix_count={0:1} ## 空数组和为0count,cur_sum = 0,0for num in nums:""" 更新当前位置的前缀和 """cur_sum += num""" 查找需要的前缀和值 """count += prefix_count.get(cur_sum-k,0)""" 更新当前前缀和的计数 """prefix_count[cur_sum] = prefix_count.get(cur_sum,0) + 1return count 引申：前缀和
通过对原始数组进行预处理，构建新的"前缀和数组"，能够快速计算任意区间的元素和。
（1）构建前缀和数组，将原始数组转化为累加和数组
（2）将原始问题转化为前缀和数组上的计算，并使用辅助数据结构优化查询
哈希表（用于计数、快速查找）
双指针（处理非负数组）
二分搜索（处理有序前缀和）
4. 数组：53、56
（1）53 最大子数组和
方法一：贪心
cur_sum：当前连续子数组的和。如果 cur_sum+nums[i]＜nums[i] → 从当前元素开始重新加和（否则再怎么加也是比从当前开始要小）
class Solution(object):def maxSubArray(self, nums):n=len(nums)cur_sum=0max_sum=float('-inf')if n==1: return nums[0]for i in range(n):if cur_sum+nums[i] < nums[i]:cur_sum = 0cur_sum += nums[i]max_sum = max(max_sum, cur_sum)return max_sum方法二：动规
dp[i]：以第 i 个元素结尾的连续子数组的最大和
状态转移方程：dp[i] = max( dp[i-1]+nums[i], dp[i] )
class Solution(object):def maxSubArray(self, nums):n=len(nums)if n==1: return nums[0]dp=[float('-inf')]*ndp[0]=nums[0]for i in range(1,n):dp[i] = max( dp[i-1]+nums[i], nums[i] )return max(dp)（2）56 合并区间
class Solution(object):def merge(self, intervals):results=[]""" 对区间按起始位置排序 """intervals.sort(key=lambda x: x[0])for interval in intervals:""" 如果当前区间与已合并区间不重叠(当前区间的start大于已合并区间的end) """if not results or interval[0]>results[-1][1]:results.append(interval)""" 如果重合→更新已合并区间的end值 """else:results[-1][1]=max(interval[1],results[-1][1])return results