力扣算法面试150题——个人笔记——复习用

双指针第一题125. 验证回文串https://leetcode.cn/problems/valid-palindrome/题目内容如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个回文串。字母和数字都属于字母数字字符。给你一个字符串s如果它是回文串返回true否则返回false。示例 1 输入: s A man, a plan, a canal: Panama 输出true 解释amanaplanacanalpanama 是回文串。 示例 2 输入s race a car 输出false 解释raceacar 不是回文串。 示例 3 输入s 输出true 解释在移除非字母数字字符之后s 是一个空字符串 。 由于空字符串正着反着读都一样所以是回文串。提示1 s.length 2 * 105s仅由可打印的 ASCII 字符组成思路两个指针初始化一根指向开头一根指向结尾。若左指针对应内容不为单词则右移1右指针同理若对应内容不为单词则左移1若开头等于结尾则左边右移1右边左移1。结束判定当左指针右指针时代码class Solution: def isPalindrome(self, s: str) - bool: # 先全部转小写 s s.lower() # 双指针 i 0 j len(s)-1 while ij: # 若当前指向内容不为字母则移动指针 if not s[i].isalnum(): i 1 continue if not s[j].isalnum(): j - 1 continue if s[i] ! s[j]: return False i 1 j - 1 return True第二题392. 判断子序列https://leetcode.cn/problems/is-subsequence/题目内容给定字符串s和t判断s是否为t的子序列。字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。进阶如果有大量输入的 S称作 S1, S2, ... , Sk 其中 k 10亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码示例 1 输入s abc, t ahbgdc 输出true 示例 2 输入s axc, t ahbgdc 输出false提示0 s.length 1000 t.length 10^4两个字符串都只由小写字符组成。思路两个字符串s和t分别用一根指针i和j。若i指向内容等于j指向内容则i右移1j右移1若i指向内容不等于j指向内容则i不动j右移1。因此。分析发现不管怎么样j都会右移1而i不一定。那么最终结束的判定条件就是i能否等于len(s)若等于则True否则False附也可以使用for循环的方式遍历t然而时间复杂度更高效率不及双指针。代码class Solution: def isSubsequence(self, s: str, t: str) - bool: i 0 j 0 lengs len(s) lengt len(t) # while 循环判定范围 while ilengs-1 and jlengt-1: if s[i] t[j]: i 1 # j 指针不管怎么样都要右移 j 1 # 结束条件 if i lengs: return True else: return False“进阶”思路目前的版本双指针法的时间复杂度是 O(∣s∣∣t∣)如果有 K 个 s需要匹配总时间复杂度就是 O(K⋅∣t∣)。当 K 很大且 t 很长时每次都要遍历一遍 t效率就很低了。可以先对 t 进行一次预处理建立一个“索引”。再用二分查找匹配若能找到则更新位置找不到则返回False第三题167. 两数之和 II - 输入有序数组https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/题目内容给你一个下标从1开始的整数数组numbers该数组已按非递减顺序排列请你从数组中找出满足相加之和等于目标数target的两个数。如果设这两个数分别是numbers[index1]和numbers[index2]则1 index1 index2 numbers.length。以长度为 2 的整数数组[index1, index2]的形式返回这两个整数的下标index1和index2。你可以假设每个输入只对应唯一的答案而且你不可以重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。示例 1 输入numbers [2,7,11,15], target 9 输出[1,2] 解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2] 。 示例 2 输入numbers [2,3,4], target 6 输出[1,3] 解释2 与 4 之和等于目标数 6 。因此 index1 1, index2 3 。返回 [1, 3] 。 示例 3 输入numbers [-1,0], target -1 输出[1,2] 解释-1 与 0 之和等于目标数 -1 。因此 index1 1, index2 2 。返回 [1, 2] 。提示2 numbers.length 3 * 104-1000 numbers[i] 1000numbers按非递减顺序排列-1000 target 1000仅存在一个有效答案思路一个数组两个指针分别指向头和尾因为数组提前说好了非递减顺序排列且只对应唯一解。也就是说右边的数字一定是大于等于左边的数字的。因此若当前值目标值右指针左移1同理若当前值目标值那么左指针右移1。代码class Solution: def twoSum(self, numbers: List[int], target: int) - List[int]: i 0 j len(numbers) - 1 while i j: if numbers[i] numbers[j] target: i1 elif numbers[i] numbers[j] target: j-1 else: return [i1,j1]第四题11. 盛最多水的容器https://leetcode.cn/problems/container-with-most-water/题目内容给定一个长度为n的整数数组height。有n条垂线第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明你不能倾斜容器。示例 1 输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。 示例 2 输入height [1,1] 输出1提示n height.length2 n 1050 height[i] 104思路一个数组两个指针分别指向头和尾。能盛多少水就看长 * 宽。长就是两个指针对应的内容的最小值min(height)宽就是两根指针的距离j-i,更新条件就是判断左右的高低左边低就往右移动因为宽边小了想要最终的面积更大必须移动短的那一根如果短的板不动的话取到的水永远不会比上次多同理右边低就往左移知道ij结束。最终返回max_ans即为最大值。代码class Solution: def maxArea(self, height: List[int]) - int: i 0 j len(height)-1 ans 0 while ij: # 最终的面积 ans max(ans, min(height[i],height[j]) * (j-i)) if height[i]height[j]: i1 else: j-1 return ans第五题15. 三数之和https://leetcode.cn/problems/3sum/题目内容给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为0且不重复的三元组。注意答案中不可以包含重复的三元组。示例 1 输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 解释 nums[0] nums[1] nums[2] (-1) 0 1 0 。 nums[1] nums[2] nums[4] 0 1 (-1) 0 。 nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意输出的顺序和三元组的顺序并不重要。 示例 2 输入nums [0,1,1] 输出[] 解释唯一可能的三元组和不为 0 。 示例 3 输入nums [0,0,0] 输出[[0,0,0]] 解释唯一可能的三元组和为 0 。提示3 nums.length 3000-105 nums[i] 105思路先对整个列表从小到大排序然后固定一个数i对于剩下的两个数双指针分别指向头ji1和尾kn-1先对i进行去重第一次尝试写的时候犯的错漏了 i接着进行计算若三数之和小于0则左指针右移因为j的左侧一定都比当前的值小同理若三数之和大于0则右指针左移因为k的右侧一定都比当前的值大若等于0则记录答案。然后左右指针各自均移动。值得注意的是第一次尝试写的时候犯的错在记录完答案并移动左右指针之后还要对j、k去重。且这一步必须在记录完答案之后进行。否则会导致漏掉某些解。即去重逻辑应该是在找到一个有效三元组之后为了寻找下一个可能解时才执行。在没有确定当前组合是否有效之前不应该随意跳过指针。代码class Solution: def threeSum(self, nums: list[int]) - list[list[int]]: # 先从小到大排序便于后续使用双指针 newnums sorted(nums) n len(nums) ans [] for i in range(n-2): # i 去重 if i0 and newnums[i] newnums[i-1]: continue # 双指针分别指向头和尾 j i 1 k n - 1 while jk: # 结果小于0则左指针右移 if newnums[i]newnums[j]newnums[k]0: j1 # 结果大于0则右指针左移 elif newnums[i]newnums[j]newnums[k]0: k-1 else: # 记录结果 ans.append([newnums[i], newnums[j], newnums[k]]) j1 k-1 # 进一步j、k去重 while jk and newnums[j] newnums[j-1]: j1 while jk and newnums[k] newnums[k1]: k-1 return ans