遍历, 模拟进行修改。不会,来自题解(. - 力扣(LeetCode))。心路历程简直和他说得一模一样,后面对原代码进行修改的时候,没有想到可以模拟修改的过程。多对前修改少对后修改,防止后面更麻烦。
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
# 遍历, 模拟进行修改
cnt = 0
n = len(nums)
for i in range(1, n):
if nums[i] < nums[i - 1]:
cnt += 1
if 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 = 0
for pre in nums:
if pre != 0:
nums[now] = pre
now += 1
n = len(nums)
while now < n:
nums[now] = 0
now += 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 = 0
for pre in nums:
if pre:
pre, nums[now] = nums[now], pre
now += 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 = 0
for pre in range(len(nums)):
if nums[pre] != 0:
if pre > now:
# 道理同,i==j时不用交换
nums[now] = nums[pre]
nums[pre] = 0
now += 1
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:
return
n = 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 = i
i = (idx - k) % n #指针移动
cnt += 1 #记录个数
nums[idx] = pre #最后一个被改变的赋值为提前储存的值
cnt += 1
pre_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:
return
n = 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]
完
感谢你看到这里!一起加油吧!