文章目录
- 88. 合并两个有序数组
- 题目
- 解题思路
- 解题思路【学习】
- 尾插入法
- 167. 两数之和 II - 输入有序数组
- 题目
- 解题思路
- 125. 验证回文串
- 题目
- 解题思路
- 345. 反转字符串中的元音字母
- 题目
- 解题思路
88. 合并两个有序数组
题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
解题思路
类似于插入排序的思路，将nums2中的元素从左到右依次取出，放在nums1数组的有效位（不包括填充0）的后一位，然后依次向前比较，比前面的数小就交换，直到满足升序要求为止。（可能是简单题目吧，这次解题所花的时间还挺少的hhh。）
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.
"""
for i in range(n):
nums1[m+i] = nums2[i]
for j in range(m+i, 0, -1):
if nums1[j] < nums1[j-1]:
nums1[j], nums1[j-1] = nums1[j-1], nums1[j]
else:
break
解题思路【学习】
尾插入法
顾名思义，从数组尾部开始进行元素的插入。定义i、j、k三个索引，判断nums2[j]与nums1[i]的大小，nums2[j]>=nums1[i]则将nums2[j]插入到nums1[k]（尾部），然后j、k前移；nums2[j]<nums1[i]则将nums1[i]插入到nums1[k]，然后i、k前移。
理解后，我写的解法：
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.
"""
i = m-1
j = n-1
k = m + n -1
while j >= 0:
if i == -1: # 此时nums2剩余的数直接填充到nums1前部
nums1[k] = nums2[j]
j -= 1
elif nums2[j] >= nums1[i]:
nums1[k] = nums2[j]
j -= 1
elif nums2[j] < nums1[i]:
nums1[k] = nums1[i]
i -= 1
k -= 1
官方给出的：
class Solution:
def merge(self, nums1, m, nums2, n):
# 尾插入法
if (n < 1):
return
if (m < 1):
nums1[0:n] = nums2[0:n]
return
k = m + n - 1
i = m - 1
j = n - 1
while k >= 0:
if (nums1[i] > nums2[j] and i >= 0) or (j < 0 and i >= 0):
nums1[k] = nums1[i]
k -= 1
i -= 1
if (nums2[j] >= nums1[i] and j >= 0) or (i < 0 and j >=0):
nums1[k] = nums2[j]
k -= 1
j -= 1
167. 两数之和 II - 输入有序数组
题目
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
解题思路
双指针，很简单。直接上代码：
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i = 0
j = len(numbers) - 1
while True:
sum_ij = numbers[i] + numbers[j]
if sum_ij == target:
break
if sum_ij > target:
j -= 1
else:
i += 1
return [i+1, j+1]
125. 验证回文串
题目
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
解题思路
双指针对撞。isalnum()函数用于判断字符串是否只包含字母数字字符。lower()函数用于返回字符串的小写形式。
class Solution:
def isPalindrome(self, s: str) -> bool:
i=0
j=len(s)-1
while i < j:
if not s[i].isalnum():
i += 1
continue
if not s[j].isalnum():
j -= 1
continue
if s[i].lower() != s[j].lower():
return False
else:
i += 1
j -= 1
return True
345. 反转字符串中的元音字母
题目
给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。
解题思路
同样采用对撞指针。
class Solution:
def reverseVowels(self, s: str) -> str:
i = 0
j = len(s) - 1
vowels = ['a', 'e', 'i', 'o', 'u']
s_list = list(s)
while i < j:
if s[i].lower() in vowels:
if s[j].lower() in vowels:
s_list[i], s_list[j] = s_list[j], s_list[i]
i += 1
j -= 1
else:
j -= 1
else:
i += 1
return ''.join(s_list)
