成人黄色影视,无码av随便看,av噜噜国产在线观看,国产婷婷一区二区,91久久免费视频,欧美爱爱网,全国男人天堂网,久久婷婷亚洲AV无码专区

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?旋轉(zhuǎn)數(shù)組，我們先來看題面：

https://leetcode-cn.com/problems/rotate-array/

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

題意

給定一個數(shù)組，將數(shù)組中的元素向右移動 k 個位置，其中 k 是非負數(shù)。

進階：

盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個問題。

你可以使用空間復(fù)雜度為 O(1) 的原地算法解決這個問題嗎？

示例

示例 1:

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

示例?2:

輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋: 
向右旋轉(zhuǎn) 1 步: [99,-1,-100,3]
向右旋轉(zhuǎn) 2 步: [3,99,-1,-100]

解題:3種解法，見下圖代碼注釋。

class?Solution?{
public:

????//解法1：翻轉(zhuǎn)，時間復(fù)雜度為O(n),空間復(fù)雜度為O(1)
????void?rotate_1(vector<int>& nums, int?k)?{
????????k%=nums.size();
????????reverse(nums.begin(),nums.end());//反轉(zhuǎn)整個字符串
????????reverse(nums.begin(),nums.begin()+k);//前k個字符反轉(zhuǎn)
????????reverse(nums.begin()+k,nums.end());//后面的字符反轉(zhuǎn)
????}
????
?????//解法2：雙重for,暴力數(shù)組旋轉(zhuǎn)k次,時間復(fù)雜度為O(k*n),空間復(fù)雜度為O(1)
?????void?rotate_2(vector<int>& nums, int?k)
?????{
?????????k%=nums.size();
?????????int?n=nums.size();
?????????for(int?i=0;i?????????{
?????????????int?temp=nums[n-1];//最后一個元素旋轉(zhuǎn)到最前面
?????????????for(int?j=n-1;j>0;--j)nums[j]=nums[j-1];
?????????????nums[0]=temp;//最后一個元素到底第一個元素的位置
?????????}
?????}
????
????//解法3：使用額外的數(shù)組，時間復(fù)雜度為O(n),空間復(fù)雜度為O(n)
????void?rotate_3(vector<int>& nums, int?k)
????{
????????vector<int> record(nums.size());
????????//將數(shù)組nums中的元素放到右移k個單位后的record數(shù)組
????????for(int?i=0;i????????????record[(i+k)%nums.size()]=nums[i];
????????nums.swap(record);
????}
????
};