LeetCode分类刷题之双指针(首尾指针)
LeetCode题目太多了,每天随便选题刷没有针对性,效率也很低,今天做了明天就忘了解法。分类刷题效率高,且解题思路形成套路可以更好的举一反三,时间有限的情况下非常推荐分类刷题。
本文及后面的记录文章,所有解法均使用python。
暴力解法是所有思路的起点。
目录
1.两数之和-有序数组(python中数组对应列表,栈也可对应列表)
1.两数之和-有序数组(python中数组对应列表,栈也可对应列表)
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
解题思路:首先题目说给定升序数组,那么肯定有比暴力更好的方法,一般会想到二分法,此题思路类似,用头尾指针来计算两数之和sum,如sum<target,则说明头指针的数值偏小需向右移动,如sum>target则说明尾指针数值偏大需向左移动。两个指针都逐渐向对方移动,也可称为首尾指针。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
# 特殊情况处理
if not numbers: return []
start, end = 0, len(numbers)-1 #头尾指针
while start < end: #保证尾指针在头指针后边
_sum = numbers[start] + numbers[end]
if _sum < target: #小于目标值,首指针后移
start += 1
elif _sum > target: #大于目标值,尾指针前移
end -= 1
else: #等于目标值,返回结果
return [start + 1, end + 1]
return []
2.两数的平方和
https://leetcode-cn.com/problems/sum-of-square-numbers/
解题思路:思路与上一题类似,找到两个数的平方和等于target,默认在一个1-n的升序数组中寻找两个数满足条件,问题的关键转化到了n如何确定,观察一下可以发现,n接近target开方的数值,然后就可以采用双指针来确定两个数了。
class Solution:
def judgeSquareSum(self, c: int) -> bool:
assert c >= 0
start, end = 0, int(sqrt(c)) #设置首尾指针
while start <= end:
_sum = start **2 + end **2
if _sum > c: end -= 1
elif _sum < c: start += 1
else: return True
return False
3.反转字符串中元音字母
https://leetcode-cn.com/problems/reverse-vowels-of-a-string/
解题思路:此题同样是头尾行动,有一个问题就是如何判断字母是不是元音字母,这里可以创建一个元音字母set集合,用in来判断字母是不是集合中的元素。
class Solution:
def reverseVowels(self, s: str) -> str:
if len(s)<1: return s
s = list(s)
start, end = 0, len(s)-1
vowels = set('aeiouAEIOU')
while start < end:
if s[start] in vowels and s[end] in vowels:
s[start], s[end] = s[end], s[start]
start += 1
end -= 1
elif s[start] in vowels: end -= 1
elif s[end] in vowels: start += 1
else:
start +=1
end -= 1
return ''.join(s)
4.验证回文串
https://leetcode-cn.com/problems/valid-palindrome/
解题思路:基本原理与之前题目一样,区别在于对字符串的处理,lower() 方法转换字符串中所有大写字符为小写,isalnum() 方法检测字符串是否由字母和数字组成。先用isalnum() 判断是不是字母,再用lower()忽略大小写。
class Solution:
def isPalindrome(self, s: str) -> bool:
if len(s) <= 1: return True
start, end = 0, len(s)-1
while start < end:
if s[start].isalnum() and s[end].isalnum():
if s[start].lower() == s[end].lower():
start += 1
end -=1
continue
else: return False
elif s[start].isalnum(): end -= 1
elif s[end].isalnum() : start += 1
else:
start += 1
end -= 1
return True
5.验证回文字符串(加强版)
https://leetcode-cn.com/problems/valid-palindrome-ii/
解题思路:与上一题的区别在于可以删除一个字符再来判断是否为回文字符串,并且删除字符有两种情况,一种是删除头指针的一个字符start+1,一种是删除尾指针的一个字符end-1。
class Solution:
def validPalindrome(self, s: str) -> bool:
if len(s) < 2: return True
def isPalindrome(s, start, end):
while start < end:
if s[start] == s[end]:
start += 1
end -= 1
continue
else: return False
return True
start, end = 0, len(s)-1
while start < end:
if s[start] == s[end]:
start += 1
end -= 1
continue
else:
return isPalindrome(s, start+1, end) or isPalindrome(s, start, end-1)
return True
6.反转字符串
解题思路:这题没啥好说的,首尾指针原地交换
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
start, end = 0, len(s)-1
while start < end:
s[start], s[end] = s[end], s[start]
start += 1
end -= 1
7.盛最多水的容器
https://leetcode-cn.com/problems/container-with-most-water/
解题思路:题目实际上求的是最大面积,思路可以是先使横轴长度最长,也就是双指针end-start,然后依次移动指针高度最小的来更新面积,同时注意更新面积的写法。
class Solution:
def maxArea(self, height: List[int]) -> int:
ml = 0
start, end = 0, len(height)-1
while start < end:
temp = min(height[start], height[end])*(end - start)
ml = max(temp, ml)
if height[start] >= height[end]:
end -= 1
else:
start += 1
return ml
本文地址:https://blog.csdn.net/hesongzefairy/article/details/107659722
推荐阅读
-
【LeetCode18】【双指针】每日一题day32
-
LeetCode 刷题 [C++] [面试题 17.09]. 第 k 个数 (动态规划 + 三指针)
-
LeetCode刷题(188)~环形链表 II【哈希|快慢指针】
-
LeetCode刷题(189)~链表的中间结点【快慢指针】
-
LeetCode刷题: 【876】链表的中间结点(快慢指针)
-
LeetCode分类刷题之双指针(首尾指针)
-
【亡羊补牢】挑战数据结构与算法 第74期 LeetCode 75. 颜色分类(双指针)
-
LeetCode双指针题小总结-(LeetCode344、LeetCode345、LeetCode125、LeetCode167、LeetCode11)(简单题)
-
leetcode之哈希法与双指针法求多数之和
-
LeetCode 刷题 [C++] [面试题 17.09]. 第 k 个数 (动态规划 + 三指针)