论坛网站免费建设模板,光之翼可以做网站吗,烟台seo网站推广费用,ui是什么意思文章目录 88. 合并两个有序数组题目解题思路解题思路【学习】尾插入法 167. 两数之和 II - 输入有序数组题目解题思路 125. 验证回文串题目解题思路 345. 反转字符串中的元音字母题目解题思路 88. 合并两个有序数组
题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums… 文章目录 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[mi] nums2[i]for j in range(mi, 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 - 1167. 两数之和 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 [i1, j1]125. 验证回文串
题目
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s如果它是 回文串 返回 true 否则返回 false 。
解题思路
双指针对撞。isalnum()函数用于判断字符串是否只包含字母数字字符。lower()函数用于返回字符串的小写形式。
class Solution:def isPalindrome(self, s: str) - bool:i0jlen(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)
