轮转数组[脑筋急转弯|发现规律]

前言

通过轮转数组，考察找规律的能力，以及递归找路径。

一、轮转数组

二、题解

1、空间快解

//用空间快解
class Rotate2 {public void rotate(int[] nums, int k) {int len = nums.length;int[] arr = new int[len];System.arraycopy(nums, 0, arr, 0, nums.length);for (int i = 0; i < nums.length; i++) nums[(i + k) % nums.length] = arr[i];}}

2、找规律

/*
len = 6; k = 4
cur : -->---->  target: ---->-->
reverse cur : <----<--
reverse sub : ---->-->*/class Rotate3 {//观其移动前、移动、移动后的联系和规律。/*len = 6; k = 4; > 表示元素呈现的方向。cur : -->---->  target: ---->-->reverse cur : <----<--reverse sub : ---->-->*/public void rotate(int[] nums, int k) {//获取有效的kint len = nums.length;k %= len;reverse(nums, 0, len - 1);reverse(nums, 0, k - 1);reverse(nums, k, len - 1);}private void reverse(int[] nums, int begin, int end) {for (int i = 0; i < end - begin + 1 >>> 1; i++) {int temp = nums[begin + i];nums[begin + i] = nums[end - i];nums[end - i] = temp;}}}

3、找路径

//轮转数组
public class Rotate {/*target:将数组元素整体向前移动k位。1-将元素向前移动k位，移动nums.len位就回到了原来的地方，所以应该移动k = k % nums.len位。2-将元素向前移动k位，就会占到别人的位置，必须先把别人的位置移走，直至回到起始位置。所以这是一个找路径问题，找打最后一个位置位起始位置，记录起始值，然后依次回溯覆盖。bug1:可能有些数字不会被遍历到，所以可采用count计数来统计已经交换了多少次，若一轮下来，count<len，则从第二个数开始交换，直至count = len*/public void rotate(int[] nums, int k) {//获取有效移动步数int len = nums.length;k %= len;//用递归栈找路径int beginVal = nums[begin];while (count < len) {//先把初始值取出来，让该值被覆盖。nums[findPath(nums, (begin + k) % nums.length, k)] = beginVal;beginVal = nums[(++begin) % nums.length];count++;}}int begin = 0, count = 1;private int findPath(int[] nums, int cur, int k) {if (begin == cur || count == nums.length) return cur;count++;nums[findPath(nums, (cur + k) % nums.length, k)] = nums[cur];return cur;}
}

总结

1）多观察，多思考，找到问题中的规律。

参考文献

[1] LeetCode 翻转数组
[2] LeetCode 官方题解