LeetCode-双指针
LeetCode-双指针
LittlePanger
发布于 2020-04-14 15:54:21
发布于 2020-04-14 15:54:21
双指针
双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。
167.两数之和 II - 输入有序数组
两数之和 II - 输入有序数组 示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。解法：
使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
- 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
- 如果 sum > target，移动较大的元素，使 sum 变小一些；
- 如果 sum < target，移动较小的元素，使 sum 变大一些。
我的答案
class Solution:
def twoSum(self, numbers, target):
head = 0
tail = len(numbers) - 1
while 1:
num = numbers[head] + numbers[tail]
if num == target:
break
elif num > target:
tail -= 1
continue
elif num < target:
head += 1
continue
return [head, tail]633.两数平方和
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
示例:
输入: 5
输出: True
解释: 1 ** 2 + 2 ** 2 = 5
输入: 3
输出: False解法：
a^2 + b^2 = c
a = sqrt(c - b^2)
因a>0 所以 b的范围为(0~sqrt(c))答案：
class Solution:
def judgeSquareSum(self, c: int) -> bool:
head = 0
tail = int(c ** 0.5)
while head <= tail:
num = head ** 2 + tail ** 2
if c == num:
return True
elif num > c:
tail -= 1
else:
head += 1
return False345.反转字符串中的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例:
输入: "hello"
输出: "holle"
输入: "leetcode"
输出: "leotcede"解法：
使用双指针指向待反转的两个元音字符，一个指针从头向尾遍历，一个指针从尾到头遍历。
答案：
class Solution:
def reverseVowels(self, s: str) -> str:
lis = ["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"]
list_s = list(s)
head = 0
tail = len(list_s) - 1
while head < tail:
if list_s[head] not in lis:
head += 1
continue
elif list_s[tail] not in lis:
tail -= 1
continue
else:
list_s[head], list_s[tail] = list_s[tail], list_s[head]
head += 1
tail -= 1
continue
return "".join(list_s)680. 验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例:
输入: "aba"
输出: True
输入: "abca"
输出: True
解释: 你可以删除c字符。回文串问题，常用如下 Python 的解法
test = 'aba'
# 解一
print(test == test[::-1]) # True
# 解二
print(test == ''.join(reversed(test))) # Trueclass Solution:
def validPalindrome(self, s: str) -> bool:
p1, p2 = 0, len(s) - 1
while p1 < p2:
if s[p1] != s[p2]:
# 舍弃左字符
a = s[p1 + 1: p2 + 1]
# 舍弃右字符
b = s[p1:p2]
return a[::-1] == a or b[::-1] == b
p1 += 1
p2 -= 1
return True88. 合并两个有序数组
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]合并后排序
class Solution(object):
def merge(self, nums1, m, nums2, n):
nums1[:] = sorted(nums1[:m] + nums2)
# 指针方法
一般而言，对于有序数组可以通过 双指针法 达到O(n + m)O(n+m)的时间复杂度。
最直接的算法实现是将指针p1 置为 nums1的开头， p2为 nums2的开头，在每一步将最小值放入输出数组中。
由于 nums1 是用于输出的数组，需要将nums1中的前m个元素放在其他地方，也就需要 O(m)O(m) 的空间复杂度。
class Solution:
def merge(self, nums1: [int], m: int, nums2: [int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
# 做个备份
nums1_copy = nums1[:m]
nums1[:] = []
# 循环指针
p1, p2 = 0, 0
while p1 < m and p2 < n:
if nums1_copy[p1] <= nums2[p2]:
nums1.append(nums1_copy[p1])
p1 += 1
else:
nums1.append(nums2[p2])
p2 += 1
# 剩余的添加进去
if p1 < m:
nums1.extend(nums1_copy[p1:])
if p2 < n:
nums1.extend(nums2[p2:])141. 环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。解法：
使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
fast, slow = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False524. 通过删除字母匹配到字典里最长单词
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例:
输入:s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出: "apple"
输入:s = "abpcplea", d = ["a","b","c"]
输出: "a"本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录