leetcode-java/src/RotateArray189.java at master · fluency03/leetcode-java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/**
 * Rotate an array of n elements to the right by k steps.
 *
 * For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated
 * to [5,6,7,1,2,3,4].
 *
 * Note:
 * Try to come up as many solutions as you can, there are at least 3 different
 * ways to solve this problem.
 *
 * Hint:
 * Could you do it in-place with O(1) extra space?
 * Related problem: Reverse Words in a String II
 *
 */


publicclassRotateArray189 {
publicvoidrotate(int[] nums, intk) {
intkk = k % nums.length;
if (kk == 0) return;

boolean[] visited = newboolean[nums.length];
for (inti=0; i<nums.length; i++) {
if (visited[i]) continue;
intj = i;
intr = nums[j];
while (true) {
intnextIndex = (j+k) % nums.length;
inttemp = nums[nextIndex];
nums[nextIndex] = r;
visited[nextIndex] = true;
r = temp;
j = nextIndex;
if (j == i) break;
 }
 }
 }

/**
 * https://leetcode.com/problems/rotate-array/solution/
 */
publicvoidrotate2(int[] nums, intk) {
int[] a = newint[nums.length];
for (inti = 0; i < nums.length; i++) {
a[(i + k) % nums.length] = nums[i];
 }
for (inti = 0; i < nums.length; i++) {
nums[i] = a[i];
 }
 }

/**
 * https://leetcode.com/problems/rotate-array/solution/
 */
publicvoidrotate3(int[] nums, intk) {
k = k % nums.length;
intcount = 0;
for (intstart = 0; count < nums.length; start++) {
intcurrent = start;
intprev = nums[start];
do {
intnext = (current + k) % nums.length;
inttemp = nums[next];
nums[next] = prev;
prev = temp;
current = next;
count++;
 } while (start != current);
 }
 }

/**
 * https://leetcode.com/problems/rotate-array/solution/
 */
publicvoidrotate4(int[] nums, intk) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
 }
publicvoidreverse(int[] nums, intstart, intend) {
while (start < end) {
inttemp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
 }
 }


publicvoidrotate5(int[] nums, intk) {
if (nums == null || nums.length <= 1) return;
intlen = nums.length;

k = k % len;
if (k == 0) return;
intcount = 0;
for (inti=0; i<k && count < len; i++) {
count += cipher(nums, k, i, len);
 }
 }

privateintcipher(int[] nums, intk, intstart, intlen) {
intres = 0;
inti = start;
intpre = nums[i];
do {
i = (i + k) % len;
intold = nums[i];
nums[i] = pre;
pre = old;
res++;
 } while (i != start);
returnres;
 }


}