Leetcode-day4【88】【167】【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-1j = n-1k = m + n -1while j >= 0:if i == -1: # 此时nums2剩余的数直接填充到nums1前部nums1[k] = nums2[j]j -= 1elif nums2[j] >= nums1[i]:nums1[k] = nums2[j]j -= 1elif nums2[j] < nums1[i]:nums1[k] = nums1[i]i -= 1k -= 1

官方给出的：

class Solution:def merge(self, nums1, m, nums2, n):# 尾插入法 if (n < 1):returnif (m < 1):nums1[0:n] = nums2[0:n]returnk = m + n - 1i = m - 1j = n - 1while k >= 0:if (nums1[i] > nums2[j] and i >= 0) or (j < 0 and i >= 0):nums1[k] = nums1[i]k -= 1i -= 1if (nums2[j] >= nums1[i] and j >= 0) or (i < 0 and j >=0):nums1[k] = nums2[j] k -= 1j -= 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 = 0j = len(numbers) - 1while True:sum_ij = numbers[i] + numbers[j]if sum_ij == target:breakif sum_ij > target:j -= 1else:i += 1return [i+1, j+1]

125. 验证回文串

题目

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

解题思路

双指针对撞。isalnum()函数用于判断字符串是否只包含字母数字字符。lower()函数用于返回字符串的小写形式。

class Solution:def isPalindrome(self, s: str) -> bool:i=0j=len(s)-1while i < j:if not s[i].isalnum():i += 1continueif not s[j].isalnum():j -= 1continueif s[i].lower() != s[j].lower():return Falseelse:i += 1j -= 1return True   

345. 反转字符串中的元音字母

题目

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

解题思路

同样采用对撞指针。

class Solution:def reverseVowels(self, s: str) -> str:i = 0j = len(s) - 1vowels = ['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 += 1j -= 1else:j -= 1else:i += 1return ''.join(s_list)