|
3 | 3 | importjava.util.ArrayList; |
4 | 4 | importjava.util.List; |
5 | 5 |
|
6 | | -importstaticcom.fishercoder.solutions._189.Solution2.rotate_naive; |
7 | | - |
8 | 6 | /** |
9 | 7 | * 189. Rotate Array |
10 | | - * |
11 | | - * Rotate an array of n elements to the right by k steps. |
12 | | - * 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]. |
13 | | - * */ |
14 | | - |
15 | | -publicclass_189 { |
16 | | - |
17 | | -publicstaticclassSolution1 { |
18 | | -publicvoidrotate(int[]nums,intk) { |
19 | | -intlen =nums.length; |
20 | | -int[]tmp =newint[len]; |
21 | | -for (inti =0;i <len;i++) { |
22 | | -tmp[(i +k) %len] =nums[i]; |
23 | | - } |
24 | | -for (inti =0;i <len;i++) { |
25 | | -nums[i] =tmp[i]; |
26 | | - } |
27 | | - } |
28 | | - } |
29 | 8 |
|
30 | | -publicstaticclassSolution2 { |
31 | | -/** |
32 | | - * My original idea and got AC'ed. |
33 | | - * One thing to notice is that when k > nums.length, we'll continue to rotate_naive the array, it just becomes k -= nums.length |
34 | | - */ |
35 | | -publicstaticvoidrotate_naive(int[]nums,intk) { |
36 | | -if (k ==0 ||k ==nums.length) { |
37 | | -return; |
38 | | - } |
39 | | -if (k >nums.length) { |
40 | | -k -=nums.length; |
41 | | - } |
42 | | -List<Integer>tmp =newArrayList(); |
43 | | -inti =0; |
44 | | -if (nums.length -k >=0) { |
45 | | -i =nums.length -k; |
46 | | -for (;i <nums.length;i++) { |
47 | | -tmp.add(nums[i]); |
48 | | - } |
49 | | - }else { |
50 | | -i =nums.length -1; |
51 | | -for (;i >=0;i--) { |
52 | | -tmp.add(nums[i]); |
53 | | - } |
| 9 | + Given an array, rotate the array to the right by k steps, where k is non-negative. |
54 | 10 |
|
55 | | - } |
56 | | -for (i =0;i <nums.length -k;i++) { |
57 | | -tmp.add(nums[i]); |
58 | | - } |
59 | | -for (i =0;i <tmp.size();i++) { |
60 | | -nums[i] =tmp.get(i); |
61 | | - } |
62 | | - } |
63 | | - } |
| 11 | + Example 1: |
| 12 | + Input: [1,2,3,4,5,6,7] and k = 3 |
| 13 | + Output: [5,6,7,1,2,3,4] |
| 14 | + Explanation: |
| 15 | + rotate 1 steps to the right: [7,1,2,3,4,5,6] |
| 16 | + rotate 2 steps to the right: [6,7,1,2,3,4,5] |
| 17 | + rotate 3 steps to the right: [5,6,7,1,2,3,4] |
64 | 18 |
|
65 | | -publicstaticvoidmain(String...strings) { |
66 | | -// int k = 1; |
67 | | -// int[] nums = new int[]{1,2,3}; |
68 | | -// int[] nums = new int[]{1}; |
69 | | -// int[] nums = new int[]{1,2}; |
| 19 | + Example 2: |
| 20 | + Input: [-1,-100,3,99] and k = 2 |
| 21 | + Output: [3,99,-1,-100] |
| 22 | + Explanation: |
| 23 | + rotate 1 steps to the right: [99,-1,-100,3] |
| 24 | + rotate 2 steps to the right: [3,99,-1,-100] |
70 | 25 |
|
71 | | -// int k = 3; |
72 | | -// int[] nums = new int[]{1,2}; |
| 26 | + Note: |
| 27 | + Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem. |
| 28 | + Could you do it in-place with O(1) extra space? |
73 | 29 |
|
74 | | -// int k = 2; |
75 | | -// int[] nums = new int[]{1,2}; |
| 30 | + * */ |
76 | 31 |
|
77 | | -intk =4; |
78 | | -int[]nums =newint[]{1,2,3}; |
| 32 | +publicclass_189 { |
79 | 33 |
|
80 | | -// int k = 2; |
81 | | -// int[] nums = new int[]{-1}; |
82 | | -rotate_naive(nums,k); |
| 34 | +publicstaticclassSolution1 { |
| 35 | +publicvoidrotate(int[]nums,intk) { |
| 36 | +intlen =nums.length; |
| 37 | +int[]tmp =newint[len]; |
| 38 | +for (inti =0;i <len;i++) { |
| 39 | +tmp[(i +k) %len] =nums[i]; |
| 40 | + } |
| 41 | +for (inti =0;i <len;i++) { |
| 42 | +nums[i] =tmp[i]; |
| 43 | + } |
83 | 44 | } |
| 45 | + } |
84 | 46 |
|
| 47 | +publicstaticclassSolution2 { |
| 48 | +/** |
| 49 | + * My original idea and got AC'ed. |
| 50 | + * One thing to notice is that when k > nums.length, we'll continue to rotate_naive the array, it just becomes k -= nums.length |
| 51 | + */ |
| 52 | +publicstaticvoidrotate_naive(int[]nums,intk) { |
| 53 | +if (k ==0 ||k ==nums.length) { |
| 54 | +return; |
| 55 | + } |
| 56 | +if (k >nums.length) { |
| 57 | +k -=nums.length; |
| 58 | + } |
| 59 | +List<Integer>tmp =newArrayList(); |
| 60 | +inti =0; |
| 61 | +if (nums.length -k >=0) { |
| 62 | +i =nums.length -k; |
| 63 | +for (;i <nums.length;i++) { |
| 64 | +tmp.add(nums[i]); |
| 65 | + } |
| 66 | + }else { |
| 67 | +i =nums.length -1; |
| 68 | +for (;i >=0;i--) { |
| 69 | +tmp.add(nums[i]); |
| 70 | + } |
| 71 | + } |
| 72 | +for (i =0;i <nums.length -k;i++) { |
| 73 | +tmp.add(nums[i]); |
| 74 | + } |
| 75 | +for (i =0;i <tmp.size();i++) { |
| 76 | +nums[i] =tmp.get(i); |
| 77 | + } |
| 78 | + } |
| 79 | + } |
85 | 80 | } |