LeetCode_189. Rotate Array
2024-08-30 05:00:45
189. Rotate Array
Easy
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input:[1,2,3,4,5,6,7]and k = 3
Output:[5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right:[7,1,2,3,4,5,6]
rotate 2 steps to the right:[6,7,1,2,3,4,5]rotate 3 steps to the right:
[5,6,7,1,2,3,4]
Example 2:
Input:[-1,-100,3,99]and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Note:
- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
package leetcode.easy;
public class RotateArray {
private static void print_arr(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println();
}
public void rotate1(int[] nums, int k) {
int temp, previous;
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;
}
}
}
public void rotate2(int[] nums, int k) {
int[] a = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
a[(i + k) % nums.length] = nums[i];
}
for (int i = 0; i < nums.length; i++) {
nums[i] = a[i];
}
}
public void rotate3(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);
}
}
public void rotate4(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 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--;
}
}
@org.junit.Test
public void test1() {
int[] nums1 = { 1, 2, 3, 4, 5, 6, 7 };
int k1 = 3;
int[] nums2 = { -1, -100, 3, 99 };
int k2 = 2;
print_arr(nums1);
rotate1(nums1, k1);
print_arr(nums1);
print_arr(nums2);
rotate1(nums2, k2);
print_arr(nums2);
}
@org.junit.Test
public void test2() {
int[] nums1 = { 1, 2, 3, 4, 5, 6, 7 };
int k1 = 3;
int[] nums2 = { -1, -100, 3, 99 };
int k2 = 2;
print_arr(nums1);
rotate2(nums1, k1);
print_arr(nums1);
print_arr(nums2);
rotate2(nums2, k2);
print_arr(nums2);
}
@org.junit.Test
public void test3() {
int[] nums1 = { 1, 2, 3, 4, 5, 6, 7 };
int k1 = 3;
int[] nums2 = { -1, -100, 3, 99 };
int k2 = 2;
print_arr(nums1);
rotate3(nums1, k1);
print_arr(nums1);
print_arr(nums2);
rotate3(nums2, k2);
print_arr(nums2);
}
@org.junit.Test
public void test4() {
int[] nums1 = { 1, 2, 3, 4, 5, 6, 7 };
int k1 = 3;
int[] nums2 = { -1, -100, 3, 99 };
int k2 = 2;
print_arr(nums1);
rotate4(nums1, k1);
print_arr(nums1);
print_arr(nums2);
rotate4(nums2, k2);
print_arr(nums2);
}
}
最新文章
- js中同步与异步请求方式
- MAC地址与IP地址的区别
- [VBS]遍历XML文档
- 百度地图开发 android App 数字签名（SHA1）获取办法
- LeetCode Sort Colors （技巧）
- 神器 Sublime Text 3 的一些常用快捷键
- Hibernate 配置详解(11)
- 【Java基础】【14正则表达式&常用工具类】
- spring中的@Bean是否一定要与@Configuration一起用
- CT ubuntu 16.04安装 adobe flash player
- 定义action的允许访问方式
- ModBus通信协议的【主从模式】
- Linux删除文件实现回收站功能
- 备份Android机上的照片
- scanf与printf
- sceneManager.loadscene加载场景时不会主动去加载场景的依赖包，要手动加载或添加场景到build setting列表中
- php prepare
- 最新phpcms v9.6.0 sql注入漏洞分析
- 监控之snmpd 服务
- 先安装ubuntu，后安装windows，修复启动grub