LeetCode Rotate Array「建议收藏」

LeetCode Rotate Array

大家好,又见面了,我是全栈君。

Rotate Array Total Accepted: 12759 Total Submissions: 73112 My Submissions Question Solution
Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

题意:循环数组,n代表数组的长度,k代表向右移动的次数。
解法一:

class Solution {
public:
    void rotate(int nums[], int n, int k) {
        if(n==0)return;
        k=k%n;//当k大于n的时候。n次循环会回到初始位置,因此,能够省略若干次
        if (k == 0) return;  
        int *s=new int[k];//为了一步到位的展开移动,申请k个额外空间用于保存被移出去的元素
        for(int i=0;i<k;++i)
            s[i]=nums[n-k+i];//保存被移出去的元素
        for(int j=n-k-1;j>=0;--j)
            nums[j+k]=nums[j];//移动
        for(int i=0;i<k;++i)
            nums[i]=s[i];//被移出的元素进行归位
        free(s);
    }
};

须要额外空间O(k%n)
33 / 33 test cases passed.
Status: Accepted
Runtime: 29 ms

解法二(网络获取):
三次翻转法,第一次翻转前n-k个。第二次翻转后k个,第三次翻转所有。

class Solution {
public:
    void rotate(int nums[], int n, int k) {
        if(n==0)return ;
        k=k%n;
        if(k==0)return ;
        reverse(nums,n-k,n-1);
        reverse(nums,0,n-k-1);
        reverse(nums,0,n-1);
    }
    void reverse(int nums[],int i,int j)
    {
        for(;i<j;++i,--j)
        {
            int t=nums[i];
            nums[i]=nums[j];
            nums[j]=t;
        }
    }
};

33 / 33 test cases passed.
Status: Accepted
Runtime: 26 ms

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115638.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 使用line_profiler查看api接口函数每行代码执行时间

    使用line_profiler查看api接口函数每行代码执行时间

  • 好用的mac录屏软件推荐:白菜录屏mac中文免费版[通俗易懂]

    好用的mac录屏软件推荐:白菜录屏mac中文免费版[通俗易懂]为大家推荐一款好用的mac录屏软件,白菜录屏forMac提供了全屏录制、区域录屏、麦克风录音、后期视频编辑、多格式视频导出、系统声音录制等功能,操作起来十分便捷,而且还是中文免费版,还在找mac录屏软件的朋友可以试试白菜录屏mac版哦!白菜录屏forMac官方介绍白菜录屏是一款小巧却功能强大的mac录屏软件。白菜录屏适用于制作教学视频的博主、录制网课的学生党、记录网络会议或演示的商务人士。白菜录屏formac主要功能全屏录制,区域录屏,支持高帧率,显示摄像头,后期视

  • 解决docker下载镜像速度过慢_docker image是什么

    解决docker下载镜像速度过慢_docker image是什么前言上一篇讲到pull镜像,但是pull镜像的时候下拉的速度实在感人,有什么解决办法吗?我们只需将docker镜像源修改为国内的将docker镜像源修改为国内的:在/etc/docker/d

  • Pytest(15)pytest分布式执行用例「建议收藏」

    Pytest(15)pytest分布式执行用例「建议收藏」前言平常我们功能测试用例非常多时,比如有1千条用例,假设每个用例执行需要1分钟,如果单个测试人员执行需要1000分钟才能跑完当项目非常紧急时,会需要协调多个测试资源来把任务分成两部分,于是执行时间

  • import啥意思_import怎么导入

    import啥意思_import怎么导入前言我们在开发项目时经常会进行导包有import*格式的,还有from*import*格式的,最后就会显示的很乱,那么有没有什么工具能对导包进行一键排序呢?答案是有的,使用isort工具i

  • phpstorm激活码2021[免费获取]

    (phpstorm激活码2021)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/ide…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号