当前位置： 首页 > news >正文

OA 公司网站 铁道建设报,网站报备流程,长沙生活信息网,电子商务网站建设与维护考试数组 / 字符串快慢指针#xff08;双指针#xff09;总结88. 合并两个有序数组27. 移除元素26. 删除有序数组中的重复项80. 删除有序数组中的重复项 II Boyer-Moore 投票算法169. 多数元素扩展#xff1a;寻找 n/3 多数元素 翻转法189. 轮转数组 贪心121. 买卖股票的最佳时机… 数组 / 字符串快慢指针双指针总结88. 合并两个有序数组27. 移除元素26. 删除有序数组中的重复项80. 删除有序数组中的重复项 II Boyer-Moore 投票算法169. 多数元素扩展寻找 n/3 多数元素 翻转法189. 轮转数组 贪心121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II55. 跳跃游戏45. 跳跃游戏 II274. H 指数 前缀 / 后缀238. 除自身以外数组的乘积134. 加油站 双指针125. 验证回文串 滑动窗口矩阵哈希表380. O(1) 时间插入、删除和获取随机元素 二叉树104. 二叉树的最大深度100. 相同的树226. 翻转二叉树 分治回溯 数组 / 字符串 快慢指针双指针总结 “快慢指针” 主要用于 数组的原地修改问题避免额外空间开销同时保证 O(n) 线性时间复杂度。 题目题目要求快指针 i慢指针 p合并两个有序数组nums1 和 nums2 归并排序遍历 nums1 nums2从后向前合并指向 nums1 末尾填充较大值移除元素nums 中移除 val保持相对顺序遍历 nums查找非 val 元素记录下一个非 val 元素存放位置删除有序数组中的重复项只保留 1个相对顺序不变遍历 nums查找不同的元素记录下一个唯一元素存放位置删除有序数组中的重复项 II只保留 最多 2 个遍历 nums查找满足出现≤2次的元素记录下一个可存放元素的位置 快慢指针的核心思路 遍历数组快指针 i 负责遍历数组找到符合条件的元素如不同于前一个元素、出现次数不超过 2 次等将其存放到正确的位置p 负责记录符合条件的元素存放位置最终 p 代表新的数组长度

1. 合并两个有序数组 下面两行代码就可以解决 nums1[m:] nums2 # 把 nums2 拼接到 nums1 从下标 m 开始后面 nums1.sort() # 默认升序排序不过还是规规矩矩用双指针法写一下吧 class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None:Do not return anything, modify nums1 in-place instead.# 指针分别指向 nums1 和 nums2 的最后一个有效元素p1, p2 m - 1, n - 1# 指针 p 指向合并后数组的最后一个位置p m n - 1# 从后往前合并while p1 0 and p2 0:if nums1[p1] nums2[p2]:nums1[p] nums1[p1]p1 - 1else:nums1[p] nums2[p2]p2 - 1p - 1# 如果 nums2 还有剩余元素填充到 nums1while p2 0:nums1[p] nums2[p2]p2 - 1p - 127. 移除元素 class Solution:def removeElement(self, nums: List[int], val: int) - int:# 维护一个慢指针 k 指向下一个存放非 val 元素的位置k 0 # 遍历数组for num in nums:if num ! val: # 只有当元素不等于 val 时才放入 nums[k] 位置nums[k] numk 1 # k 向前移动return k # 返回新的数组长度26. 删除有序数组中的重复项 class Solution:def removeDuplicates(self, nums: List[int]) - int:# 慢指针 k 记录下一个存放唯一元素的位置k 1 # 遍历数组for i in range(1, len(nums)):if nums[i] ! nums[i - 1]: # 只有当当前元素不等于前一个元素时才存入nums[k] nums[i]k 1 # 移动慢指针return k # 返回唯一元素的个数80. 删除有序数组中的重复项 II class Solution:def removeDuplicates(self, nums: List[int]) - int:Do not return anything, modify nums in-place instead.if len(nums) 2:return len(nums) # 数组长度小于等于2时直接返回# 指针 p 记录下一个存放元素的位置p 2for i in range(2, len(nums)):if nums[i] ! nums[p - 2]: # 只有当 nums[i] ≠ nums[p-2] 时才可以保留nums[p] nums[i]p 1 # 递增存放位置return p # p 就是去重后的数组长度Boyer-Moore 投票算法 Boyer-Moore 投票算法Boyer-Moore Voting Algorithm 是一种用于在 数组中寻找出现次数超过 ⌊n/2⌋ 的元素即 多数元素的高效算法。 该算法的 时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( 1 ) O(1) O(1)只需要一次遍历和常数级额外空间非常高效。 若一个元素出现超过 n/2 次它的 票数净增量一定是正的。其他元素的 抵消票数永远无法超过多数元素的总数。这样多数元素的 最终 count 绝对不会归零即使在过程中 count 可能降为零换新的 candidate 后最终的 candidate 仍然是多数元素。 169. 多数元素 可以使用 Boyer-Moore 投票算法 来 高效找出多数元素。该算法的时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( 1 ) O(1) O(1)。 核心思想抵消计数如果某个元素是多数元素出现次数 ⌊n/2⌋那么它最终一定会成为 唯一剩下的候选人。计数规则遇到相同的元素count 1遇到不同的元素count -1。当 count 0 时换一个候选人。 由于 多数元素的出现次数超过 ⌊n/2⌋即使被其他元素抵消也最终会留在 candidate 里。 class Solution:def majorityElement(self, nums: List[int]) - int:Boyer-Moore 投票算法candidate None # 维护一个 候选元素count 0 # 计数器for num in nums:if count 0:candidate num # 选择新的候选多数元素count (1 if num candidate else -1) # 增加票数 或 抵消票数return candidate # 因为题目说多数元素一定存在最终 candidate 即为结果扩展寻找 n/3 多数元素 如果需要找 出现次数超过 n/3 的元素则可以维护 两个候选人 和 两个计数器 class Solution:def majorityElement(self, nums: List[int]) - List[int]:candidate1, candidate2, count1, count2 None, None, 0, 0for num in nums:if count1 0:candidate1, count1 num, 1elif count2 0:candidate2, count2 num, 1elif num candidate1: # 投票给候选人 1count1 1elif num candidate2: # 投票给候选人 2count2 1else: # 没有投票给两个候选人中的任何一人count1 - 1count2 - 1# 第二遍遍历检查候选人是否真的超过 n/3return [c for c in (candidate1, candidate2) if nums.count© len(nums) // 3]翻转法 翻转法中交换变量使用 a, b b, a本质上是 元组打包tuple packing 元组解包tuple unpacking它的底层实现依赖于栈操作引用变更不会创建新的对象只是 交换变量指向的内存地址。 ROT_TWO 是 Python 字节码中的一个栈操作指令用于 交换栈顶的两个元素。 case ROT_TWO: {PyObject *top STACK_POP(); // 取出栈顶元素指针引用PyObject *second STACK_POP(); // 取出次栈顶元素指针引用STACK_PUSH(top); // 先压入原来的栈顶STACK_PUSH(second); // 再压入原来的次栈顶DISPATCH(); }PyObject *top 和 PyObject *second 只是指向原来 Python 对象的指针并没有创建新的对象。STACK_POP() 只是修改了栈指针而不是拷贝对象。STACK_PUSH() 只是把相同的指针重新放回去没有额外的内存分配。 因此交换是 “原地” 进行的不涉及对象复制或新分配。 189. 轮转数组 翻转法 利用 三次反转 完成 原地修改时间 O ( n ) O(n) O(n)空间 O ( 1 ) O(1) O(1)高效且简洁。 class Solution:def rotate(self, nums: List[int], k: int) - None:Do not return anything, modify nums in-place instead.n len(nums)k k % n # 防止 k 大于 n取模优化# 定义反转函数def reverse(start: int, end: int):while start end:nums[start], nums[end] nums[end], nums[start]start 1end - 1reverse(0, n - 1) # 反转整个数组reverse(0, k - 1) # 反转前 k 个元素reverse(k, n - 1) # 反转后 n-k 个元素贪心

2. 买卖股票的最佳时机 先考虑最简单的 暴力遍历即枚举出所有情况并从中选择最大利润。时间复杂度为 O ( N 2 ) O(N^2) O(N2) 。考虑到题目给定的长度范围 1≤prices.length≤10^5需要思考更优解法。 由于卖出肯定在买入后所以 从前往后遍历维护一个最小价格 min_price肯定是碰到越小价格更有可能利润更大。由于要求最大利润所以 维护一个最大利润 max_profit当天的利润就是当天的价格减去遇到的最低价 price - min_price遇到更高利润就更新。 class Solution:def maxProfit(self, prices: List[int]) - int:min_price, max_profit float(inf), 0 # 最低价格最高利润for price in prices:min_price min(min_price, price) # 更新最低价格max_profit max(max_profit, price - min_price) # 更新最高利润return max_profit122. 买卖股票的最佳时机 II 基本思路所有上涨交易日都买卖赚到所有利润所有下降交易日都不买卖绝不亏钱。 class Solution:def maxProfit(self, prices: List[int]) - int:max_profit 0for i in range(1, len(prices)):if prices[i] - prices[i-1] 0:max_profit prices[i] - prices[i-1] # 累积 盈利return max_profit55. 跳跃游戏 思路尽可能到达最远位置。如果能到达某个位置那一定能到达它前面的所有位置。 class Solution:def canJump(self, nums: List[int]) - bool:n len(nums)max_index 0 # 记录最远可跳跃的位置for i in range(n):if i max_index: # 无法到达 i 位置就无法到达最后下标return Falsemax_index max(max_index, nums[i] i) # 更新最远位置if max_index n-1:return True45. 跳跃游戏 II 贪心策略每次选择能跳得最远的位置从而尽可能减少跳跃的次数。维护当前跳跃区间在每一步会有一个“当前区间”它表示 从当前跳跃开始能够到达的最远位置。在区间内更新最远可以跳到的位置。跳跃次数每次更新最远的位置后意味着完成了一次跳跃需要跳到下一个区间。 class Solution:def jump(self, nums: List[int]) - int:jumps 0 # 跳跃次数current_end 0 # 当前跳跃区间的右端farthest 0 # 能跳到的最远位置# 遍历数组跳跃的次数for i in range(len(nums) - 1): # 不需要遍历最后一个位置farthest max(farthest, i nums[i]) # 更新最远可以到达的位置# 如果当前已经到达了当前跳跃区间的右端if i current_end:jumps 1 # 需要跳跃一次current_end farthest # 更新跳跃区间的右端# 如果当前跳跃区间的右端已经超过了最后一个位置直接返回跳跃次数if current_end len(nums) - 1:return jumpsreturn jumps274. H 指数 排序首先将 citations 数组按 从大到小排序。遍历排序后的数组从第一个元素开始检查每个元素是否满足条件 citations[i] i 1其中 i 1 是当前论文的排名。最大 h 值最终最大的 i 1 使得 citations[i] i 1 即为 h 指数。 class Solution:def hIndex(self, citations: List[int]) - int:citations.sort(reverseTrue) # 对引用次数进行降序排序# 遍历已排序的 citations 数组找到最大 h 指数for i in range(len(citations)):if citations[i] i 1: # 论文 i 1 应该有 citations[i] 次引用return i # 返回 h 指数return len(citations) # 如果所有的论文的引用次数都满足返回数组长度前缀 / 后缀

3. 除自身以外数组的乘积 可以分两步来完成这个任务 前缀积首先计算每个位置的前缀积即从数组的最左侧到当前位置之前所有元素的乘积。这可以通过一个临时数组 answer 来实现其中 answer[i] 表示 nums[0] 到 nums[i-1] 的乘积。 后缀积然后计算每个位置的后缀积即从数组的最右侧到当前位置之后所有元素的乘积。这可以通过另一个临时变量 right 来实现直接从右到左更新 answer 数组。
   class Solution:def productExceptSelf(self, nums: List[int]) - List[int]:n len(nums)# 初始化答案数组answer [1] * n# 计算前缀积存入 answer 数组left_product 1for i in range(n):answer[i] left_productleft_product * nums[i]# 计算后缀积直接更新 answer 数组right_product 1for i in range(n-1, -1, -1):answer[i] * right_productright_product * nums[i]return answer134. 加油站 双指针

4. 验证回文串 c.lower() 将字符 c 转换为小写。c.isalnum() 判断字符 c 是否是字母或数字。如果是字母或数字就保留该字符否则跳过。通过 字符串的切片操作 [::-1] 获取字符串 filtered_s 的反转版本。 class Solution:def isPalindrome(self, s: str) - bool:# 只保留字母和数字并转换为小写filtered_s .join(c.lower() for c in s if c.isalnum())# 比较正着读和反着读是否相同return filtered_s filtered_s[::-1]双指针利用 两个指针从字符串的两端开始同时向中间移动检查字符是否相等同时跳过所有非字母和数字的字符。 class Solution:def isPalindrome(self, s: str) - bool:# 初始化左右指针left, right 0, len(s) - 1while left right:# 跳过非字母数字字符while left right and not s[left].isalnum():left 1while left right and not s[right].isalnum():right - 1# 比较字符忽略大小写if s[left].lower() ! s[right].lower():return False# 移动指针left 1right - 1return True滑动窗口 矩阵 哈希表

5. O(1) 时间插入、删除和获取随机元素 基本思路是结合使用 哈希表字典和 列表数组。 插入操作 insert(val) 用一个哈希表val - index来 记录每个元素的值及其在列表中的位置。这样查找和删除元素时都能在 O ( 1 ) O(1) O(1) 时间内完成。列表 list 用来存储元素以便可以 快速地随机获取一个元素。 删除操作 remove(val) 需要从列表中删除一个元素并且保证其他元素的顺序尽量不被破坏同时保持 O ( 1 ) O(1) O(1) 的时间复杂度。可以通过 将要删除的元素与列表中的最后一个元素交换位置然后从哈希表中删除该元素。这样删除操作的时间复杂度是 O ( 1 ) O(1) O(1)。 随机获取操作 getRandom()利用 列表的下标来随机访问元素时间复杂度是 O ( 1 ) O(1) O(1)。 import randomclass RandomizedSet:def init(self):# 哈希表存储值及其索引列表存储值self.val_to_index {}self.list []def insert(self, val: int) - bool:if val in self.val_to_index:return False # 如果已经存在返回 False# 插入操作将元素添加到列表末尾并在哈希表中记录该值和索引self.val_to_index[val] len(self.list)self.list.append(val)return Truedef remove(self, val: int) - bool:if val not in self.val_to_index:return False # 如果元素不存在返回 False# 找到元素的索引index self.val_to_index[val]# 将要删除的元素与最后一个元素交换位置last_element self.list[-1]self.list[index] last_elementself.val_to_index[last_element] index# 删除该元素self.list.pop()del self.val_to_index[val]return Truedef getRandom(self) - int:return random.choice(self.list) # 随机返回列表中的一个元素# Your RandomizedSet object will be instantiated and called as such:

   obj RandomizedSet()

   param_1 obj.insert(val)

   param_2 obj.remove(val)

   param_3 obj.getRandom()二叉树

6. 二叉树的最大深度 # Definition for a binary tree node.

   class TreeNode:

   def init(self, val0, leftNone, rightNone):

   self.val val

   self.left left

   self.right right

   class Solution:def maxDepth(self, root: Optional[TreeNode]) - int:# 如果当前节点为空返回深度 0if not root:return 0# 递归计算左子树和右子树的最大深度left_depth self.maxDepth(root.left)right_depth self.maxDepth(root.right)# 当前节点的深度是左右子树深度的最大值 1return max(left_depth, right_depth) 1100. 相同的树 class Solution:def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) - bool:if not p and not q: # 两棵树都为空return Trueelif not p or not q: # 只有一棵树为空return Falseif p.val ! q.val: # 两棵树都不空但节点值不同return False# 两棵树都不空且节点值相同递归比较return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)226. 翻转二叉树 分治 回溯