温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

leetcode旋转数组问题怎么解决

发布时间:2022-02-24 17:32:43 来源:亿速云 阅读:284 作者:iii 栏目:开发技术

本篇内容介绍了“leetcode旋转数组问题怎么解决”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

解题思路

暴力法每次旋转1个位置, 旋转k次即为正确答案。

旋转的时候也是利用前驱结点来实现的, 前驱结点的更新也借助temp变量。

这里重点体会如何完成向后移动一次目前阶段遇到题目不要钻牛角尖, 暴力法能解就暴力法。

代码
class Solution {
    public void rotate(int[] nums, int k) {
        int previous;
		int temp;
		for (int i = 0; i < k; i++) {
			previous = nums[nums.length-1];  //前驱结点初始为最后一个结点
			for (int j = 0; j < nums.length; j++) {
				temp = nums[j]; //先保存当前结点
				nums[j]=previous;
				previous=temp; //更新前驱结点
			}
		}
    }
}

反转法 很实用

这个方法基于这个事实:当我们旋转数组 k 次,k%n 个尾部元素会被移动到头部, 剩下的元素依次向后移动。

1、反转可以把k%n个元素先放到前面,只需要对数组进行 0到k-1范围内的反转就可以得到想要的顺序;

2、反转剩下的k-1到n-1个元素即实现了元素依次后移;

3、前往要主义此处的k有可能超出数组长度,而如果恰等于数组长度就等于没变所以k=k%n。

class Solution {
    public void rotate(int[] nums, int k) {
		int n = nums.length;  
        k %= n; //k可能会查过数组长度造成错误
		//1、反转数组
		reverse(nums,0,n-1);
        //2、前k个反转,后n-k个反转
		reverse(nums,0,k-1);
		reverse(nums,k,n-1);
    }
    //反转数组 用这种写法可以方便的反转任意区间的数组 也很使用
	public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

环状替换

想到了但是代码实现的时候遇到了当 n%k==0的时候死循环而想不到解决的办法。

以下是leetcode提供的代码,巧妙的用了双循环循环解决了我不能解决的尴尬,核心代码都是一样的,外循环的此时必定是数组长度。

用count来控制外循环次数,内循环一镜到底都是我没有想到的。在编码方面还有很大提高。

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        int count = 0;
        for (int start = 0; count < nums.length; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % nums.length;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }
}

“leetcode旋转数组问题怎么解决”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI