解题思路
暴力法每次旋转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);
}
}
}推荐好课：
