解題思路
暴力法每次旋轉(zhuǎn)1個位置, 旋轉(zhuǎn)k次即為正確答案。
旋轉(zhuǎn)的時候也是利用前驅(qū)結(jié)點來實現(xiàn)的, 前驅(qū)結(jié)點的更新也借助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]; //前驅(qū)結(jié)點初始為最后一個結(jié)點
for (int j = 0; j < nums.length; j++) {
temp = nums[j]; //先保存當前結(jié)點
nums[j]=previous;
previous=temp; //更新前驅(qū)結(jié)點
}
}
}
}反轉(zhuǎn)法 很實用
這個方法基于這個事實：當我們旋轉(zhuǎn)數(shù)組 k 次，k%n 個尾部元素會被移動到頭部, 剩下的元素依次向后移動。
1、反轉(zhuǎn)可以把k%n個元素先放到前面，只需要對數(shù)組進行 0到k-1范圍內(nèi)的反轉(zhuǎn)就可以得到想要的順序；
2、反轉(zhuǎn)剩下的k-1到n-1個元素即實現(xiàn)了元素依次后移；
3、前往要主義此處的k有可能超出數(shù)組長度，而如果恰等于數(shù)組長度就等于沒變所以k=k%n。
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n; //k可能會查過數(shù)組長度造成錯誤
//1、反轉(zhuǎn)數(shù)組
reverse(nums,0,n-1);
//2、前k個反轉(zhuǎn),后n-k個反轉(zhuǎn)
reverse(nums,0,k-1);
reverse(nums,k,n-1);
}
//反轉(zhuǎn)數(shù)組 用這種寫法可以方便的反轉(zhuǎn)任意區(qū)間的數(shù)組 也很使用
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--;
}
}
}環(huán)狀替換
想到了但是代碼實現(xiàn)的時候遇到了當 n%k==0的時候死循環(huán)而想不到解決的辦法。
以下是leetcode提供的代碼，巧妙的用了雙循環(huán)循環(huán)解決了我不能解決的尷尬，核心代碼都是一樣的，外循環(huán)的此時必定是數(shù)組長度。
用count來控制外循環(huán)次數(shù)，內(nèi)循環(huán)一鏡到底都是我沒有想到的。在編碼方面還有很大提高。
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);
}
}
}推薦好課：
