摘要：题目旋转数组给定一个数组，将数组中的元素向右移动个位置，其中是非负数。例如将到反转将到反转全部翻转得到最后结果。这里要注意下还有这样的情况即大于数组长度的情况。次旋转次旋转转回来了次旋转次旋转转回来了次旋转所以这里的有效等于对数组长度求余。
题目： 旋转数组给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。示例：
输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4] 输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]思考：
这道题有一种巧妙地利用反转的做法。 首先将第0个到第k个元素反转，再将第k+1到末尾元素反转，最后再将全部元素反转即可。 例如：[1,2,3,4,5,6,7] k = 3 将0到3反转：[4,3,2,1,5,6,7] 将4到6反转：[4,3,2,1,7,6,5] 全部翻转：[5,6,7,1,2,3,4] 得到最后结果。 这里要注意下还有这样的情况：[1,2] k = 5 即k大于数组长度的情况。 这里可以发现数组旋转次数等于数组长度时，旋转后的数组与初始数组相同，转了一圈又回来了。 1次旋转：[2,1] 2次旋转: [1,2] 转回来了 3次旋转：[2,1] 4次旋转: [1,2] 转回来了 5次旋转：[2,1] 所以这里的有效k等于k对数组长度求余。实现：
class Solution {
public void rotate(int[] nums, int k) {
int length = nums.length;
k %= length;
reverse(nums, 0, length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, length - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/6891.html
摘要：题目最小移动次数使数组元素相等给定一个长度为的非空整数数组，找到让数组所有元素相等的最小移动次数。加一减一所以先求出最小的元素，在求出所有元素与最小元素的差值的和，即为最小移动次数。题目：最小移动次数使数组元素相等 给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。 复制代码 示例： 输入...
摘要：请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串和数字，该函数将返回左旋转两位得到的结果。 目录 第一题:左旋转字符串 解题思路: 画图解析: 代码实现: 第二题:轮转数组 解题思路: 画图解析: 代码实现: 第一题:左旋转字符串 LeetCode 剑指 Offer 58: 描述:...
摘要：先实现栈操作遍历链表，把每个节点都进中然后再遍历链表，同时节点依次出栈，二者进行比较。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无...
摘要：每日一题叉树的最大深度链接叉树的最大深度题目分析简单的搜索题目。只需要从根节点开始一下整个叉树就可以得到答案了。主要是对要理解和掌握叉树的遍历。代码作者作者 lee...
阅读 3303·2021-09-02 09:53
阅读 1595·2021-08-26 14:13
阅读 2608·2019-08-30 15:44
阅读 1186·2019-08-30 14:03
阅读 1768·2019-08-26 13:42
阅读 2881·2019-08-26 12:21
阅读 1209·2019-08-26 11:54
阅读 1808·2019-08-26 10:46
