415. 字符串相加
解题思路：
将竖式加法实现，从个位开始相加。需要处理两个点：两个数加起来大于10的进位；两个数不一样长。
第一个需要新建一个进位变量，每次加完对10整除，得到进位；
第二个需要判断指针位置是否不存在，不存在则置为0.
步骤：
1.新建结果字符串、进位变量、指向两个字符串尾部的指针。
2.建立while循环，循环体内提取两个字符串的同位置数字，这里处理第二个难点；
3.处理进位，更新进位变量，计算当前位得到的值。
4.将当前位的值添加到结果字符串前面，形成结果。
python">class Solution:def addStrings(self, num1: str, num2: str) -> str:# 结果字符串res = ''# 进位carry = 0# 双指针，指向两个字符串的末尾index1, index2 = len(num1)-1, len(num2)-1# 从个位开始相加while index1 >= 0 or index2 >= 0 or carry:# 第一个字符串的某一位的数字，如果不够长，就置为0x = int(num1[index1]) if index1 >= 0 else 0y = int(num2[index2]) if index2 >= 0 else 0# 计算当前位的值value = (x+y+carry) % 10# 计算进位carry = (x+y+carry) // 10# 将当前位的值转为字符串加进结果字符串的前面res = str(value) + res# 移动指针，向前一位index1 -= 1index2 -= 1return res239. 滑动窗口最大值
最初的想法：直接模拟，结果当然是超时，是O(nk）的复杂度。
python">from collections import dequeclass Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:if not nums:return []if k == 1:return nums# 初始化滑动窗口temp = nums[:k]# 结果列表res = [max(temp)]for i in range(k, len(nums)):# 滑动窗口移除第一个元素temp.pop(0)# 添加当前元素到最后temp.append(nums[i])# 计算当前窗口最大值max_num = max(temp)# 添加到结果列表res.append(max_num)return res解题方法
将滑动窗口实现为双向队列，队列中存储索引，维护队列的第一个元素为窗口内最大值的索引，在每个窗口内取出第一个元素，在数组中访问即可得到每个滑动窗口内的最大值。
步骤：
1.初始化双向队列，结果列表
2.遍历数组。
- 首先检查是否满足滑动窗口范围，否则就移除一次窗口最左边的元素；
- 然后循环检查队列的尾部对应的数组元素是不是比当前遍历到的数组元素小，小的话就移除，因为我们要的是最大的。这样就构造了窗口内第一个元素对应的数组元素是最大值。
- 队列添加当前元素的索引；
- 如果已经遍历了k次，说明第一个滑动窗口已经形成，可以直接添加队列的首个元素对应的数组元素到结果列表。
python">from collections import dequeclass Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:if not nums:return []if k == 1:return nums# 初始化滑动窗口，双向队列dep = deque()# 结果列表res = []for i in range(len(nums)):# 滑动窗口移除出超出窗口范围的索引if dep and dep[0] < i-k+1:dep.popleft()# 移除窗口中所有小于当前元素的索引while dep and nums[dep[-1]] < nums[i]:dep.pop()# 添加当前元素的索引到窗口dep.append(i)# 这个时候对于到索引k-1的位置，已经初始化了一个滑动窗口，dep=[3,-1]if i >= k-1:res.append(nums[dep[0]])return res3. 无重复字符的最长子串
解题思路：
快慢双指针，逐步扩大窗口，维护一个只有不重复元素的窗口；
判断不重复的方法：哈希表，每个元素都只有一个计数（每次遍历都检查一遍）
每次循环都更新长度。
步骤：
1.初始化快慢双指针，结果变量，哈希表
2.循环条件：快指针没有遍历完数组
3.循环体：
- 将快指针指向元素添加进哈希表（本身有则加1，无则设1）；
- 内置循环检查当前元素是否在哈希表内重复，循环条件是当前元素的值>1，如果是，则将慢指针指向元素技术减1，代表窗口缩减；移动慢指针；
- 更新长度变量；
- 移动快指针。
python">class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 初始化快慢指针，最大长度，记录字符数的哈希表slow, fast, res = 0,0,0_dict = {}# 如果快指针还没遍历完成while fast < len(s):# 如果快指针指向的元素不在字典，添加if s[fast] not in _dict:_dict[s[fast]] = 1else:_dict[s[fast]] += 1# 检查当前元素是否有重复。重复则移动左指针while _dict[s[fast]] >= 2:_dict[s[slow]] -= 1# 如果删完了，就直接移除这个元素# 这一步没必要，因为要是后面有新的这个元素，会自动# if _dict[s[slow]] == 0:# del _dict[s[slow]]slow += 1# 更新长度res = max(res, fast-slow+1)# 移动右指针fast += 1return res718. 最长重复子数组
解题思路1：滑动窗口
将两个数组对齐，考虑所有可能的对齐方式，每种方式都计算出公共数组长度，得到最长的长度。
算法步骤
定义辅助函数
max_len：
- 这个函数用来计算当
nums1从索引i开始和nums2从索引j开始对齐时的最长公共子数组的长度。- 输入参数包括
nums1，nums2，起始索引i和j。- 在这个函数中，初始化
cur_len为0（当前匹配的连续长度）和max_len为0（遍历过程中遇到的最长匹配长度）。遍历数组元素：
- 使用一个循环，同时遍历
nums1和nums2，从i和j开始。- 如果
nums1[i]等于nums2[j]，增加cur_len并更新max_len。- 如果不相等，则将
cur_len重置为0。返回最长公共子数组长度：
- 当某次对齐检查完成后，函数返回这次对齐的最长重复子数组长度。
遍历所有可能的对齐方式：
- 在主函数中，首先遍历
nums1，对每个可能的起始位置i，调用max_len函数，把nums2的起始位置设置为0。- 然后遍历
nums2，对每个可能的起始位置i，调用max_len函数，这次把nums1的起始位置设置为0。更新和返回结果：
- 在主函数中，用变量
res来保存遇到的最长的重复子数组长度。- 每次调用
max_len后，用返回值更新res。- 最终返回
res，它是两个数组所有对齐方式中最长重复子数组的长度。
python">class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:# 滑动窗口# 求以某个数组为开始的公共子数组def max_len(nums1, nums2, i, j):n1,n2= len(nums1), len(nums2)max_len = 0 # 全局最长cur_len = 0 # 局部长度while i < n1 and j < n2:# 如果有公共元素，就增加局部长度，更新最长长度if nums1[i] == nums2[j]:cur_len += 1max_len = max(max_len, cur_len)else:cur_len = 0i += 1j += 1return max_lenn1, n2 = len(nums1), len(nums2)res = 0 # 最终的最长长度for i in range(n1):res = max(res,max_len(nums1,nums2,i,0))for i in range(n2):res = max(res,max_len(nums1,nums2,0,i))return res解题思路2：动态规划
1.阶段划分：以子数组结尾部分划分。
2.状态定义：二维数组，dp[i][j]是以nums1[i-1]，nums2[j-1]为结尾的最长子数组长度
3.状态转移方程：如果nums1[i-1] == nums2[j-1]，则dp[i][j]=dp[i-1][j-1]+1；
否则，为0
4.状态初始化：默认以 nums1[i - 1] 结尾和 nums2[j - 1] 结尾的最长公共子数组长度为 0，dp[i][j]=0。
5.最终结果：取矩阵的最大的dp[i][j]作为结果
python">class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:# 动态规划size1, size2 = len(nums1), len(nums2)# 结果res = 0# 状态矩阵dp = [[0 for _ in range(size2+1)] for _ in range(size1+1)]# 遍历矩阵，for i in range(1,size1+1):for j in range(1,size2+1):# 状态转移if nums1[i-1] == nums2[j-1]:dp[i][j] = dp[i-1][j-1] + 1# 获取最大值if dp[i][j] > res:res = dp[i][j]return res
83. 删除排序链表中的重复元素
解题思路：
因为已经排好序了，所以只用关注当前和下一个节点，如果值相等，就把当前节点的指针指向下下个节点；否则，移动到下一个节点，继续比较。
步骤：
1.初始化指针节点，指向头结点
2.创建while循环，条件是指针节点和下一个节点都非空
3.循环体：如果两个节点值相同，则跳过下一个节点；否则，移动指针节点到下一个节点，这样就算是1-1-1-1-2也不怕。
4.返回头节点。
python"># Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:# 指针节点cur_node = headwhile cur_node and cur_node.next:# 两个节点重复，将当前元素的指针指向下下个元素if cur_node.val == cur_node.next.val:cur_node.next = cur_node.next.nextelse:# 否则，移动到下一个节点cur_node = cur_node.next# 返回头节点return head82. 删除排序链表中的重复元素 II
跟上一题的不同在于要把所有重复的元素删除，上一题还保留呢。
解题思路：
为了防止头结点也是重复元素，需要设置一个哑结点，指向头结点；
然后判断相邻的两个节点是否重复。如果重复，就将相邻的前一个元素另存为临时变量，并且循环判断相邻的后一个元素和其后的元素是否重复，重复则移动临时变量到下一个节点；
临时变量退出循环后，其下一个元素是与前面的任意元素都不重复的，因此将指针指向临时变量的下一个元素。
如果不重复，则移动指针到下一个元素。
代码分析
哑节点（Dummy Node）:
- 创建一个哑节点
dummy_head并将其next指针指向链表的头部head。这样做的好处是可以方便地处理头部可能为重复节点需要删除的情况。初始化指针:
cur指针初始化为dummy_head。这个指针用于遍历链表，并且指向当前考虑的节点的前一个节点，以便于进行节点的删除操作。循环遍历链表:
- 使用
while循环遍历链表。条件cur.next and cur.next.next确保cur后至少有两个节点，这是检测重复的前提条件。检测并跳过重复节点:
- 如果
cur.next.val等于cur.next.next.val，说明找到了重复的节点。- 内部
while循环 (while temp and temp.next and temp.val == temp.next.val) 用于跳过所有重复的节点。temp
指针从当前重复节点的第一个节点开始，一直移动到这组重复节点的最后一个节点。- 之后，通过
cur.next = temp.next将最后一个重复节点的下一个节点（非重复节点或None）连接到cur的next，从而跳过了所有重复的节点。移动指针:
- 如果当前的两个节点不相等，即
cur.next.val不等于cur.next.next.val，则直接将cur指针向前移动一位（cur = cur.next）。这表明当前节点没有重复，可以安全地保留。返回修改后的链表:
- 返回
dummy_head.next，这是删除重复节点后链表的新头部。示例
给定链表
1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5，该算法将工作如下：
- 初始时，
dummy_head -> 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5。cur指向1，发现2重复，跳过所有2。- 然后
cur指向3，再次发现4重复，跳过所有4。- 最终，链表变为
1 -> 3 -> 5。
python"># Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:# 创建虚拟节点dummy_head = ListNode(0)dummy_head.next = head# 创建指针cur = dummy_head# 当指针节点的下一个和下下个都存在while cur.next and cur.next.next:# 如果这两个节点相同if cur.next.val == cur.next.next.val:# 将第二个节点保存temp = cur.next# 只要一直跟后面有重复，就不断更新节点while temp and temp.next and temp.val == temp.next.val:temp = temp.next# 这个时候得到的下一个节点是与前面的节点不重复的# 将其与伪节点相连cur.next = temp.nextelse:# 不重复，就移动节点cur = cur.next# 返回伪节点的下一个节点，也就是头节点return dummy_head.next206. 反转链表在这里插入代码片
解题思路：
遍历链表。
首先将链表最后一个节点看作指向null；
每次遍历，将当前节点修改指向到前驱节点，将前驱节点更新为第一个节点。
步骤：
1.初始化前驱节点为null，指针。
2.创建循环，只要指针不为空
3.循环体：
因为下面要修改当前节点的指针，所以先创建一个临时变量存储其后继节点；
修改当前节点的指针指向前驱节点；
将前驱节点更新为当前节点；
移动指针到原始的后继节点（临时变量）
4.最终得到的前驱节点就是反转后的头节点
python"># Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:# 前驱节点pre = None# 指针cur = headwhile cur:# 暂存后继节点temp = cur.next# 将当前节点的指针指向前驱节点cur.next = pre# 将当前节点作为下一个前驱节点pre = cur# 移动指针，到下一个节点cur = tempreturn pre
