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)


相关推荐

  • mysql 查找配置文件 my.ini 位置方法

    mysql 查找配置文件 my.ini 位置方法见:https://blog.csdn.net/mayor125/article/details/54140454https://jingyan.baidu.com/article/7e4409531f75292fc0e2efe7.html个人备注:不显示文件类型时,my.ini文件名就叫作my,文件属性才显示ini。找到my文件看属性就知道是不是my…

  • linux内外网配置_服务器内网ip

    linux内外网配置_服务器内网ip1、/etc/sysconfig/network-scripts/ifcfg-eth0创建这个文件里面的内容如下TYPE=“Ethernet”  BOOTPROTO=“none”  DEFROUTE=“yes”  IPV4_FAILURE_FATAL=“no”  NAME=“eth1”  DEVICE=“eth1”  ONBOOT=“yes”  IPADDR=“192.168…

  • LoadRunner11实操压力测试-一步一步慢慢来

    LoadRunner11实操压力测试-一步一步慢慢来录制脚本、修改脚本、运行脚本、测试结果

  • 常见的预测模型及算法「建议收藏」

    常见的预测模型及算法「建议收藏」如果得到一份数据集,任务是要预测出一系列的值,而在预测任务中,我们大多数都采用的是拟合的方法,这篇文字主要介绍三种预测方法时间序列分析,灰色预测模型,神经网络。时间序列分析时间序列也叫动态序列,数据是按时间和数值性成的序列。而时间序列分析有三种作用,大致可以描述为描述过去,分析规律,预测将来。接下来将会讲到三种模型(季节分解,指数平滑,ARIMA模型)。一般情况下时间序列的数值变化规律有四种…

  • pytest的使用_pytest怎么指定部分用例执行

    pytest的使用_pytest怎么指定部分用例执行Pytest执行用例规则Pytest在命令行中支持多种方式来运行和选择测试用例1.对某个目录下所有的用例pytest2.对模块中进行测试pytesttest_mod.py3.对文件夹进行

  • cubieboard 用户 密码 root「建议收藏」

    cubieboard 用户 密码 root「建议收藏」因为不是超级用户root,所以你进行任何操作都要使用sudo在命令的前面。启用root的方法:sudopasswdroot输入新的root密码2次,确认后。就激活了root账户,就可以使用root登录,以后就具备了最高权限。先解除root锁定,为root用户设置密码#sudopasswdPassword:EnternewUNIXpasswo

发表回复

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

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