leetcode旋轉(zhuǎn)數(shù)組（小白解題）

解題思路

暴力法每次旋轉(zhuǎn)1個(gè)位置, 旋轉(zhuǎn)k次即為正確答案。

旋轉(zhuǎn)的時(shí)候也是利用前驅(qū)結(jié)點(diǎn)來實(shí)現(xiàn)的, 前驅(qū)結(jié)點(diǎn)的更新也借助temp變量。

這里重點(diǎn)體會(huì)如何完成向后移動(dòng)一次目前階段遇到題目不要鉆牛角尖, 暴力法能解就暴力法。

代碼

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é)點(diǎn)初始為最后一個(gè)結(jié)點(diǎn)
			for (int j = 0; j < nums.length; j++) {
				temp = nums[j]; //先保存當(dāng)前結(jié)點(diǎn)
				nums[j]=previous;
				previous=temp; //更新前驅(qū)結(jié)點(diǎn)
			}
		}
    }
}

反轉(zhuǎn)法 很實(shí)用

這個(gè)方法基于這個(gè)事實(shí)：當(dāng)我們旋轉(zhuǎn)數(shù)組 k 次，k%n 個(gè)尾部元素會(huì)被移動(dòng)到頭部, 剩下的元素依次向后移動(dòng)。

1、反轉(zhuǎn)可以把k%n個(gè)元素先放到前面，只需要對(duì)數(shù)組進(jìn)行 0到k-1范圍內(nèi)的反轉(zhuǎn)就可以得到想要的順序；

2、反轉(zhuǎn)剩下的k-1到n-1個(gè)元素即實(shí)現(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可能會(huì)查過數(shù)組長度造成錯(cuò)誤
		//1、反轉(zhuǎn)數(shù)組
		reverse(nums,0,n-1);
        //2、前k個(gè)反轉(zhuǎn),后n-k個(gè)反轉(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)狀替換

想到了但是代碼實(shí)現(xiàn)的時(shí)候遇到了當(dāng) n%k==0的時(shí)候死循環(huán)而想不到解決的辦法。

以下是leetcode提供的代碼，巧妙的用了雙循環(huán)循環(huán)解決了我不能解決的尷尬，核心代碼都是一樣的，外循環(huán)的此時(shí)必定是數(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);
        }
    }
}

推薦好課：

Java：23天零基礎(chǔ)完全入門

Java工程師基礎(chǔ)教程

MySQL零基礎(chǔ)入門