leetcode-189. 旋转数组

leetcode-189. 旋转数组原题链接给定一个数组,将数组中的元素向右移动 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]题解

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接
给定一个数组,将数组中的元素向右移动 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]

题解一

  1. 翻转
class Solution { 
   
public:
    void rotate(vector<int>& nums, int k) { 
   
        k %= nums.size();
        reverse(nums,0,nums.size() - 1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.size()-1);
    }
    void reverse(vector<int>&a,int l,int r){ 
   
        if(l>= r)return;
        for(int i = 0;i <= (r - l) / 2;i ++){ 
   
            int t = a[l + i];
            a[l + i] = a[r - i];
            a[r - i] = t;
        }
    }
};
  1. 环状
class Solution { 
   
public:
    void rotate(vector<int>& nums,int k) { 
   
        k %= nums.size();
        int g = gca(nums.size(),k);
        for(int i = 0;i < g;i ++){ 
   
            int t = nums[i];
            int current = i;
            do{ 
   
                int next = (current + k) % nums.size();
                int a  = nums[next];
                nums[next] = t;
                current = next;
                t = a;
            }while(current != i);
        }
    }
    int lca(int a,int b){ 
   
        return a * b / lca(a,b);
    }
    int gca(int a,int b){ 
   
        return b == 0 ? a : gca(b, a % b);
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • 视频编码的常见参数基本概念 –bit rate / frame rate /sample rate等等

    视频编码的常见参数基本概念 –bit rate / frame rate /sample rate等等码率:Bit Rate,指视频或音频文件在单位时间内使用的数据流量,该参数的单位通常是Kbps,也就是千比特每秒。通常2000kbps~3000kbps就已经足以将画质效果表现到极致了。码率参数与视频文件最终体积大小有直接性的关系。  混合码率:Overall Bit Rate,指视频文件中视频和音频混合后的整体平均码率。一般描述一个视频文件的码率都是指OBR,如新浪播客允许的OBR上

  • 高德地图marker的遮挡问题

    高德地图marker的遮挡问题高德地图marker的遮挡问题varmarker=newAMap.Marker({position:[longitude,latitude,],map:map,icon:startIcon,});marker.on(“mouseover”,function(e){e.t

  • IDEA开发工具使用 git 创建项目、拉取分支、合并分支「建议收藏」

    IDEA开发工具使用 git 创建项目、拉取分支、合并分支「建议收藏」工作中多人使用版本控制软件协作开发,常见的应用场景归纳如下:假设小组中有两个人,组长小张,组员小袁场景一:小张创建项目并提交到远程Git仓库场景二:小袁从远程Git仓库上获取项目源码场景三:小袁修改了部分源码,提交到远程仓库场景四:小张从远程仓库获取小袁的提交场景五:小袁接受了一个新功能的任务,创建了一个分支并在分支上开发场景六:小袁把分支提交到远程Git仓库场景七:小张获取小袁提交的分支场景八:…

  • Windows搭建Ldap服务器

    Windows搭建Ldap服务器Windows搭建Ldap服务器RerferenceSofewareLdapServer安装包openldap-2.2.29-db-4.3.29-openssl-0.9.8a-win32_Setup.exeLdap客户端LdapAdmin.exe安装一路next到install即可。配置文件1slapd.conf2找到include./schema/c

  • ipx防水等级表_说明知识运用的方法

    ipx防水等级表_说明知识运用的方法“××”是两位数字,第一位表示对固体的防护等级,第二位表示对液体的防护等级。固体防护等级有7个等级;液体防护等级有9个等级;防尘等级(固体防护等级有7个等级)0:没有保护1:防止大的固体侵入2:防止中等大小的固体侵入3:防止小固体进入侵入4:防止物体大于1mm的固体进入5:防止有害的粉尘堆积6:完全防止粉尘进入防水等级(液体防护等级有9个…

  • python3菜鸟教程笔记「建议收藏」

    python3菜鸟教程笔记「建议收藏」python2和python3的一些差异:*print函数变了,python3中的print函数必须要加括号*xrange函数合并到了range中,2到5的序列可以直接用range(2,5

发表回复

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

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