Leetcode Rotating Array (Little White Solution)

The idea of solving the problem

The violence method rotates 1 position at a time, and the rotation k times is the correct answer.

The rotation is also achieved using the front node, and the update of the forward node is also achieved by the temp variable.

Here focus on how to complete the backward movement of a current stage encountered the problem do not drill horn tip, violence law can solve the law of violence.

code

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; //更新前驱结点
			}
		}
    }
}

The inversion method is very practical

This method is based on the fact that when we rotate the array k times, k%n tail elements are moved to the head, and the remaining elements move backwards in turn.

1, reverse can put k%n elements first in front, only need to the array 0 to k-1 range of inversion can get the desired order;

2, reverse the remaining k-1 to n-1 elements, that is, to achieve the elements in turn to move back;

3, go to the important here k may exceed the length of the array, and if exactly equal to the length of the array is equal to the unchanged so 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--;
        }
    }
}

Ring replacement

Think of but when the code is implemented, you encounter a dead loop when n%k-0 and you can't think of a solution.

The following is the code provided by leitcode, cleverly using a double loop loop to solve the embarrassment I can not solve, the core code is the same, the outer loop must be the array length at this time.

Using count to control the number of outer cycles, the inner loop is exactly what I didn't expect. There's been a lot of improvement in coding.

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);
        }
    }
}

Recommended lessons:

Java: 23-day zero base fully started

Basic tutorial for Java engineers

MySQL Zero Basics Getting Started