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]); } } }};新聞熱點
疑難解答
