风澜

V1

2022/06/23阅读:17主题:全栈蓝

【起早贪黑练算法】做完这道题,我感觉可能与大厂无缘了...

一、前言

就在这个越黑凤高的夜晚,风澜正在奋指疾敲,噼里啪啦的打着二手键盘,刷着某扣。 突然,风澜旁光一扫,看到了一道算法题,盯了一会,发现这道题还是有点东西的。


二、题目

leetcode 轮转数组

给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

输入: 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]

代码模板:注:没有返回值,需要在nums原数组上移动
class Solution {
    public void rotate(int[] nums, int k) {
        
    }
}

小编一看,这小题呀,好做。随后风澜就一脸不屑的盯着这道题,开始了意气风发的解题过程。

三、尝试解题,被完虐

风澜想虽然题目需要返回原数组,但是还是可以迂回一下的吗,创建一个新数组,然后再复制回去就好了。

以下是风澜的思路:

  1. 创建一个新的数组,数组大小等于原数组(nums)大小。
  2. 把需要挪到数组前面的值,遍历出来,放到新数组的最前面,例:上面的 nums = [1,2,3,4,5,6,7], k = 3 先把后三个5、6、7遍历出来,放到新数组的前三位 新数组=[5,6,7, , , , ]。
  3. 把剩下的值,顺序的放到新数组的后几位,例:上面例子中剩下的值1、2、3、4放到新数组的后4位 新数组=[5,6,7,1,2,3,4]。

说罢,风澜就开始写了,最终写成的代码是这样的。

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;

        int[] res = new int[len];

        int j = 0;

        for(int i=k;i>0;i--){
            res[j] = nums[len - i];
            j++;
        }
        for(int n = 0;n<len-k;n++){
            res[j] = nums[n];
            j++;
        }
        System.arraycopy(res,0,nums,0,len);
    }
}

写完这段代码,风澜没急着提交,心里想,就这种小题,还用提交?看着就对,提交的都是心虚。

但是为了刷题率,还是妥协了一下,毕竟吃饭要吃七分饱,否则会太骄傲。随手就点了一下提交。

What? 哪错了?

随后风澜在脑子里过了一遍这个用例,果然数组溢出了...

那咋办呢?一看表,马上半夜12点了,今天这题过不去,我怕我也过不去了。 随后风澜就祭出了神器,看官方题解


四、正解

随后题解的第一句,我们可以使用额外的数组来将每个元素放至正确的位置,看到这句,风澜想,看来自己还是有点东西,和官方想的一样。官方完整解答如下:

我们可以使用额外的数组来将每个元素放至正确的位置。用 nn 表示数组的长度,我们遍历原数组,将原数组下标为 ii 的元素放至新数组下标为 (i+k)\bmod n(i+k)modn 的位置,最后将新数组拷贝至原数组即可。

随后风澜按照题解写了答案。

class Solution {
    public void rotate(int[] nums, int k) {
       int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            res[(i + k) % n] = nums[i];
        }
        System.arraycopy(res, 0, nums, 0, n);
    }
}

随手一点运行,竟然过了。

随后风澜又仔细的盯了盯这个解法,不得不说,真简单啊...

兄弟们,你们说,我是不是与大厂无缘了啊........

今天到这吧,洗洗睡了。

原创不易,给个三连吧!!

微信搜一搜:云下风澜 学习、面试资料、深度内容、源码阅读、性能优化、行业秘闻、职业规划应有尽有。

分类:

后端

标签:

后端

作者介绍

风澜
V1