两数之和 II - 输入有序数组

双指针法解这种问题简直不能太赞!本来困的不行,做了这道题就觉得能清醒一点了!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
i = 0
j = len(numbers) - 1
while i < j:
if numbers[i] + numbers[j] < target:
i += 1
elif numbers[i] + numbers[j] > target:
j -= 1
else:
return [i+1, j+1]

Sum of Square Numbers

这道题需要考虑到j不可能大于sqrt(c),毕竟平方和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def judgeSquareSum(self, c):
"""
:type c: int
:rtype: bool
"""
i = 0
j = int(c ** 0.5)
while i <= j:
sum_of = i ** 2 + j ** 2
if sum_of == c:
return True
elif sum_of < c:
i += 1
else:
j -= 1
return False

反转字符串中的元音字母

明显的双指针法,爽歪歪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
vowels = {'a', 'e', 'i', 'o', 'u'}
i = 0
j = len(s) - 1
slist = list(s)
while i < j:
if slist[i].lower() not in vowels:
i += 1
continue
if slist[j].lower() not in vowels:
j -= 1
continue
slist[i], slist[j] = slist[j], slist[i]
i += 1
j -= 1
return "".join(slist)

680. Valid Palindrome II

这道题分为两步,首先双指针到两个元素不等的地方,然后再判断删除一个元素之后能不能回文,如果能,就为True,否则为False,所以可以直接返回。注意数组索引的结束界限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
# 双指针判断,当出现不等的情况时,进行两种情况的判断,看是否通过删除一个元素可以形成回文
i = 0
j = len(s) - 1
while i < j:
if s[i] != s[j]:
return self.is_palindrome(s[i:j]) or self.is_palindrome(s[i+1:j+1])
i += 1
j -= 1
return True
def is_palindrome(self, s):
i = 0
j = len(s) - 1
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True

88. 合并两个有序数组

有时候反着想会更容易些,注意逻辑判断以及指针的更新。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
# 从后往前
i = m - 1
j = n - 1
index = m + n - 1
while i >= 0 or j >= 0:
if j < 0:
nums1[index] = nums1[i]
i -= 1
elif i < 0:
nums1[index] = nums2[j]
j -= 1
elif nums1[i] >= nums2[j]:
nums1[index] = nums1[i]
i -= 1
else:
nums1[index] = nums2[j]
j -= 1
index -= 1

141. 环形链表

快慢指针法,一个指针走一步,一个指针走两步,如果出现相等,就是有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return False
ptr1 = head
ptr2 = head.next
while ptr1 and ptr2 and ptr2.next:
if ptr1 == ptr2:
return True
ptr1 = ptr1.next
ptr2 = ptr2.next.next
return False

524. 通过删除字母匹配到字典里最长单词

双指针,一个指针遍历s,一个指针来遍历字典字符串,必须字典字符串的指针走完才算数,否则就是不合格。如果两个指针的字母不想等,则将s指针加一,直到匹配完成。另外输出需要以字典顺序,所以一开始需要对字典排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def findLongestWord(self, s, d):
"""
:type s: str
:type d: List[str]
:rtype: str
"""
d.sort()
res = ''
for word in d:
i = j = 0
while j < len(word):
if i >= len(s):
break
if s[i] == word[j]:
i += 1
j += 1
else:
i += 1
else:
if len(word) > len(res):
res = word
return res