2024.4.7力扣刷题记录-数组篇刷题记录2

本文主要是介绍2024.4.7力扣刷题记录-数组篇刷题记录2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、665. 非递减数列

遍历， 模拟进行修改。不会，来自题解（. - 力扣（LeetCode））。心路历程简直和他说得一模一样，后面对原代码进行修改的时候，没有想到可以模拟修改的过程。多对前修改少对后修改，防止后面更麻烦。

class Solution:def checkPossibility(self, nums: List[int]) -> bool:# 遍历， 模拟进行修改cnt = 0n = len(nums)for i in range(1, n):if nums[i] < nums[i - 1]:cnt += 1if i == 1 or nums[i] >= nums[i - 2]:nums[i - 1] = nums[i - 2]else:nums[i] = nums[i - 1]return cnt <= 1

二、283. 移动零

1.双指针， 模拟（两次遍历）

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""# 双指针， 模拟now = 0for pre in nums:if pre != 0:nums[now] = prenow += 1n = len(nums)while now < n:nums[now] = 0now += 1

2.一次遍历，参考快排。来自题解（. - 力扣（LeetCode））。来自评论1（. - 力扣（LeetCode））和评论2（. - 力扣（LeetCode））的解释很透彻。

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""# 一次遍历，参考快排# 时复O(n)now = 0for pre in nums:if pre:pre, nums[now] = nums[now], prenow += 1

3.一次遍历优化。来自评论（. - 力扣（LeetCode）），全方位优化。

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""# 一次遍历优化if not nums:return now = 0for pre in range(len(nums)):if nums[pre] != 0:if pre > now:# 道理同，i==j时不用交换nums[now] = nums[pre]nums[pre] = 0now += 1

三、189. 轮转数组

1.遍历，指针（环状替换）。时复O(n), 空复O(1)。

class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""# 遍历，指针# 时复O(n), 空复O(1)if k == 0 or not nums:returnn = len(nums)cnt = 0     # 标记修改的个数，防止如当n，k均为偶数时，只更改偶数，局部更改pre_idx = 0     while cnt != n:pre = nums[pre_idx]     #将初始位置的值存储起来i = (pre_idx - k) % n   #第一个被改变位置将要储存的值的下标idx = pre_idx   #将要改变的位置，既然值已经被存储起来了，就第一个被改变while i != pre_idx:nums[idx] = nums[i]idx = ii = (idx - k) % n   #指针移动cnt += 1        #记录个数nums[idx] = pre     #最后一个被改变的赋值为提前储存的值cnt += 1pre_idx += 1    #移动，作用如cnt

2.数组翻转。来自官方题解（. - 力扣（LeetCode）），妙啊！！时复O(n), 空复O(1)。

class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""# 数组翻转# 时复O(n), 空复O(1)if k == 0 or not nums:returnn = len(nums)nums.reverse()  #reverse()在原序列上修改# 翻转原序列部分值nums[0:k%n] = reversed(nums[0:k%n])nums[k%n:] = reversed(nums[k%n:])

注意python中翻转的方法。

3.纯粹的python切片语法。来自题解（. - 力扣（LeetCode）），自己加了一些注释。

class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""# 纯粹的python切片语法n = len(nums)# 这里不能是nums = ，必须是nums[:] =# 只有切片才能原地修改# nums[:] = nums[-k%n:] + nums[:-k%n]# 值是不等的，只是一个是正下标一个是负下标，代表的位置相同# 另外，%结果的正负取决于除数。nums[:] = nums[(-k)%n:] + nums[:(-k)%n]

完

感谢你看到这里！一起加油吧！

 

这篇关于2024.4.7力扣刷题记录-数组篇刷题记录2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---