<LeetCode天梯>Day005 旋转数组 (切片法) | 初级算法 | Python

简介: <LeetCode天梯>Day005 旋转数组 (切片法) | 初级算法 | Python

今天在学校监考校招(赚点零花钱,低保和劳务一月没发了,哎),继续刷题吧!~


今天再和车神哥一起来提升自己的Python编程和面试能力吧,刷天梯~


以下为我的天梯积分规则:


每日至少一题:一题积分+10分

若多做了一题,则当日积分+20分(+10+10)

若做了三道以上,则从第三题开始算+20分(如:做了三道题则积分-10+10+20=40;做了四道题则积分–10+10+20+20=60)


初始分为100分

若差一天没做题,则扣积分-10分(周六、周日除外注:休息)

坚持!!!


初级算法

刷题目录

数组


image.png

image.png

题干

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。


进阶版:


尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。

你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

示例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]


分析:


我这里想到的是用冒泡的思想,一个一个的往后移动,但是超出了时间范围,运行是可以运行的。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        while k > 0:
            k -= 1
            for i in range(n-1, 0, -1):
                nums[i-1], nums[i] = nums[i], nums[i-1]

遇到最后几个超大型的数组时,会戎机,超出时间限制。

然后咱们再优化优化一下看看:

是否可以用对数组的切片来实现旋转,切片成两部分,然后再反过来拼接起来,其实就一句

nums[:] = nums[n-k:] + nums[:n-k]

然鹅,发现自己还是太年轻了,没有考虑到,如果数组数少于移动次数,那么就会不满足上述情况,所以就不能做切片。

我们再优化优化,用nums的个数个K的数取余数,看是否k大于len(nums),咱们再加一条判断试试

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        kk = k % n # 取余数
        nums[:] = nums[n-kk:] + nums[:n-kk]

image.png

效果虽然不是最好,但是Python说是yyds,一点已不为过吧~

image.png

image.png


相关文章
|
2月前
|
算法 数据安全/隐私保护 开发者
马特赛特旋转算法:Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心,由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器,具有超长周期和高维均匀性,适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组,经状态更新和输出提取生成随机数,代码简单高效。
119 63
|
3月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
49 0
|
5月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
5月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
5月前
|
前端开发
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
3月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
27 4
|
3月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
26 0
Leetcode第三十三题(搜索旋转排序数组)
|
3月前
|
索引 Python
Python 高级编程:深入探索字符串切片
在Python中,字符串切片功能强大,可灵活提取特定部分。本文详细介绍切片技巧:基本切片、省略起始或结束索引、使用负数索引、设定步长及反转字符串等。此外,还介绍了如何结合其他操作进行切片处理,如先转换大小写再提取子串。 来源:https://www.wodianping.com/yeyou/2024-10/48238.html
50 4
|
3月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
79 0