转轮数组

1、题目要求

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

输入: 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、题解

 1 class Solution {
 2 public:
 3     void rotate(vector<int>& nums, int k) {
 4        vector<int>lunzhuan;
 5        if(k > 0)
 6        {
 7           for(int i = 0; i < nums.size(); ++i)
 8           {
 9             if(i < k)
10             {
11                 lunzhuan.push_back(nums[nums.size()+i-k]);
12             }
13             else
14             {
15                 lunzhuan.push_back(nums[i-k]);
16             }
17           }
18            nums.swap(lunzhuan);   
19        }
20           
21     }
22 };

报错：可能存在k大于数组长度，如果 k 大于 nums 的长度，直接使用 k 会导致索引越界。旋转等效次数应该是 k % nums.size()

增加 k %= nums.size();

 1 class Solution {
 2 public:
 3     void rotate(vector<int>& nums, int k) {
 4        vector<int>lunzhuan;
 5        k %= nums.size();
 6        if(k > 0)
 7        {
 8           for(int i = 0; i < nums.size(); ++i)
 9           {
10             if(i < k)
11             {
12                 lunzhuan.push_back(nums[nums.size()+i-k]);
13             }
14             else
15             {
16                 lunzhuan.push_back(nums[i-k]);
17             }
18           }
19            nums.swap(lunzhuan);   
20        }
21           
22     }
23 };

方法二、

 1 class Solution {
 2 public:
 3     void rotate(vector<int>& nums, int k) {
 4       int n = nums.size();
 5       k %= nums.size();
 6       reverse(nums.begin(),nums.end());
 7       reverse(nums.begin(),nums.begin()+k);
 8       reverse(nums.begin()+k,nums.end());     
 9     }
10 };

问题1：reverse函数的使用说明

在 C++ 中，reverse() 函数接受两个迭代器作为参数，分别表示反转区间的开始和结束。

这个区间遵循半开半闭的原则，即包含起始位置的元素，但不包含结束位置的元素。因此，当你调用

reverse(nums.begin(), nums.begin() + k);

时，它会反转从 nums.begin() 开始的 k 个元素，实际上反转的是 [0, k-1] 的索引区间。

紧接着，当你调用

reverse(nums.begin() + k, nums.end());

时，意图是反转从索引 k 到数组末尾的元素。由于区间是左闭右开的，因此这个调用实际上反转的是从 k 开始到 n-1 （其中 n 是 nums.size()）的元素，即索引区间 [k, n-1]。

问题2：reverse(nums.begin(), nums.end())的原理　　

reverse() 函数和大多数 STL 算法遵循半开半闭区间原则（即，包括开始迭代器指向的元素，但不包括结束迭代器指向的元素）。这种设计允许算法能够以统一的方式处理空容器和非空容器，同时简化了边界条件的处理。

当我们调用 reverse(nums.begin(), nums.end()); 时，实际上是要反转从 nums.begin() 开始到 nums.end() 之前的所有元素。这里的 nums.end() 并不指向数组的最后一个元素，而是指向最后一个元素之后的“假想”位置。因此，即便按照半开半闭的原则，这个范围仍然涵盖了数组中的所有元素。

简而言之，nums.end() 并不指向任何实际的元素，而是作为一个标记，表示数组末尾元素的下一个位置。这就是为什么 reverse(nums.begin(), nums.end()); 能够反转整个数组而不漏掉最后一个元素的原因。