vue做电商网站,王烨雄,在线制作网站公章,手机如何安装wordpress这里写目录标题 一、75. 颜色分类二、80. 删除有序数组中的重复项 II三、125. 验证回文串四、189. 轮转数组 一、75. 颜色分类
提示 中等
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums #xff0c;原地对它们进行排序#xff0c;使得相同颜色的元素相邻#xff… 这里写目录标题 一、75. 颜色分类二、80. 删除有序数组中的重复项 II三、125. 验证回文串四、189. 轮转数组 一、75. 颜色分类
提示 中等
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums 原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1
输入nums [2,0,2,1,1,0] 输出[0,0,1,1,2,2] 示例 2
输入nums [2,0,1] 输出[0,1,2]
思路快速排序
def fast_sort(nums):if len(nums) 1:return numspovit nums[0]left []right []for i in range(1, len(nums)):if nums[i] povit:left.append(nums[i])else:right.append(nums[i])return fast_sort(left) [povit] fast_sort(right)nums [2, 0, 2, 1, 1, 0]
print(fast_sort(nums))二、80. 删除有序数组中的重复项 II
中等 932 相关企业 给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。 不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1 输入nums [1,1,1,2,2,3] 输出5, nums [1,1,2,2,3] 解释函数应返回新长度 length 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。
示例 2 输入nums [0,0,1,1,1,1,2,3,3] 输出7, nums [0,0,1,1,2,3,3] 解释函数应返回新长度 length 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
def test(nums):slow2fast2while fastlen(nums):if nums[fast]!nums[slow-2]:nums[slow]nums[fast]fast1slow1else:fast1return slownums[0,0,1,1,1,1,2,3,3]
print(test(nums))三、125. 验证回文串
简单
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s如果它是 回文串 返回 true 否则返回 false 。
示例 1 输入: s “A man, a plan, a canal: Panama” 输出true 解释“amanaplanacanalpanama” 是回文串。 示例 2 输入s “race a car” 输出false 解释“raceacar” 不是回文串。 示例 3 输入s 输出true 解释在移除非字母数字字符之后s 是一个空字符串 “” 。 由于空字符串正着反着读都一样所以是回文串。
s A man, a plan, a canal: Panama
ress.replace( ,).replace(,,).replace(:,).lower()
print(res)
def test2(s):left0rightlen(s)-1while leftright:if s[left]s[right]:left1right-1else:return Falsereturn True
sraceacar
print(test2(s))四、189. 轮转数组
提示 中等
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
示例 1:
输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2:
输入nums [-1,-100,3,99], k 2 输出[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
解题思路 三次翻转先整体翻转然后根据K的位置前后局部翻转。
class Solution:def rotate(self,nums,k):kk%len(nums)self.reverse(nums,0,len(nums)-1)self.reverse(nums,0,k-1)self.reverse(nums,k,len(nums)-1)def reverse(self,nums,start,end):while startend:nums[start],nums[end]nums[end],nums[start]start1end-1nums[1,2,3,4,5,6,7]
k3
SSolution()
S.rotate(nums, k)
print(nums)
