Rotate an array of n elements to the right by k steps.
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].
Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this PRoblem.
s思路： 1. 之前遇到过把matrix rotate,就是用到reverse。这里，也不例外想到reverse。例如：[1,2,3,4,5,6,7]，rotate后得到[5,6,7,1,2,3,4]。如何用reverse呢？把[1,2,3,4,5,6,7]先全部reverse成[7,6,5,4,3,2,1],然后把前3个数和后四个数分别再reverse即可！ 2. 刚才写的时候，思维不够细腻，潜意识或自发的思维已经默认k< n。实际上，没有这么要求，就可能大于n。 3. 这个方法就是比较系统的方法，没有去研究谁和谁交换，所以是top down的方法。有没有面向细节的方法呢？刚尝试的时候，发现一个。例如：[1,2,3,4,5,6,7],把1和5,2和6,3和7交换，交换k次，即：[5,6,7,4,1,2,3],注意看，我们把前三个数放在了正确的位置上，但后4个数仍然需要继续rotate，那么我们把数组起始位置变成3,长度变成7-3=4,k=k%4=3,继续交换：4和1交换，然后4和2交换，最后4和3交换，现在得到[5,6,7,1,2,3,4]，此时数组起始位置变成3+3=6,长度变成4-3=1，k=3%1=0,当k==0,说明rotate完成！ 4. 整个过程就是iterative的过程，这段时间我们多次遇到。一个问题不能一步解决，我们看是否有一个相同的过程可以应用在这个问题，通过多次使用一个方法，在这个过程中改变一些参数，最后解决问题。一般稍微复杂的问题，都不要期望一步到位，都是多次使用一个方法达到效果。这里就是每次更新需要rotate的序列的起始位置，长度，需要rotate的k!
//方法1：利用三次reverseclass Solution {public: void rotate(vector<int>& nums, int k) { //bug:k可能很大，又默认是在范围内 k%=nums.size(); reverse(nums.begin(),nums.end());//end()表示最后一个元素之外 reverse(nums.begin(),nums.begin()+k);//注意：nums.begin()+k表示第k+1个元素 reverse(nums.begin()+k,nums.end()); }};//方法2：利用多次swapclass Solution {public: void rotate(vector<int>& nums, int k) { int n=nums.size(); int start=0; for(;k%=n,k>0;n-=k,start+=k){//结束条件是k=k%n,k==0,说明已经rotate完成 for(int i=0;i<k;i++){ swap(nums[start+i],nums[start+i+n-k]); } } }};新闻热点
疑难解答
