环形数组的一般操作
环形数组的遍历, 本质上是对长度取模错位操作
vector<int> arr = {1,2,3,4,5};
int n = arr.size();
int i = 0;
while (true) {
// 在环形数组中转圈
print(arr[i % n]);
++i;
}
189.轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1: 输入: nums = [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]示例 2: 输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
分析:
1.向右旋转有个 k 个位置的效果有个先分步反转然后整体反转的等效作用方式, 把反转过程分解成分开2个部分反转结果的反转;
2.理解过程如下:
数组是 ——->—> k = 3 (1)
翻转完成的效果是 —>——-> (2)
这个可以怎么从效果 (1) 到效果 (2) 呢? 我们可以分别将整个数组分成两个部分分别反转j
——-> 反转后得到 <——-
—> 反转后得到 <—
然后我们现在得到的是 <——-<— (3)
我们发现我们要的 (2) 和 现在得到的(3) 是个对称图形, 如果对 (3) 整体翻转一下, 就得到了我们要的 (2) 的效果
2.一开始额外判断一下 k 是否是 nums.size() 的倍数, 可以直接取模, 化简运算
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
if (len <= 0) {
return;
}
k %= len;
if (k == 0) {
return;
}
reverse(nums.begin(), nums.end() - k);
reverse(nums.end() - k, nums.end());
reverse(nums.begin(), nums.end());
return;
}
};
转载请注明来源 goldandrabbit.github.io