3. 輪轉數組

給定一個整數數組?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 <= nums.length <= 105
• 231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

題解

使用反轉數組的方法。

別人的解答：

nums = "----->-->"; k =3
result = "-->----->";reverse "----->-->" we can get "<--<-----"
reverse "<--" we can get "--><-----"
reverse "<-----" we can get "-->----->"
this visualization help me figure it out :)

看圖就能理解了。

反轉數組可以定義兩個指針bg, ed,一個指向數組開始，一個指向數組末尾，交換它們直到重合或相交。

class Solution {
public:void reverse(vector<int>& nums, int bg, int ed) {while(bg < ed) {swap(nums[bg], nums[ed]);bg ++;ed --;}}void rotate(vector<int>& nums, int k) {int n = nums.size();k %= n;reverse(nums, 0, n - 1);reverse(nums, 0, k - 1);reverse(nums, k, n - 1);}
};

4. 除自身以外數組的乘積

給你一個整數數組?nums，返回 數組?answer?，其中?answer[i]?等于?nums?中除?nums[i]?之外其余各元素的乘積?。

題目數據?保證?數組?nums之中任意元素的全部前綴元素和后綴的乘積都在??32 位?整數范圍內。

請?**不要使用除法，**且在?O(n)?時間復雜度內完成此題。

示例 1:

輸入: nums =[1,2,3,4]輸出:[24,12,8,6]

示例 2:

輸入: nums = [-1,1,0,-3,3]
輸出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• 30 <= nums[i] <= 30
• 輸入?保證?數組?answer[i]?在?32 位?整數范圍內

**進階：**你可以在?O(1)?的額外空間復雜度內完成這個題目嗎？（ 出于對空間復雜度分析的目的，輸出數組?不被視為?額外空間。）

題解

非常明顯的做法是建立一個前綴積數組，一個后綴積數組。輸出的時候輸出它們的乘積即可。

前綴積數組 f[i]，表示以 i - 1 結尾的前綴積

后綴積數組 g[i]，表示以 i + 1 結尾的后綴積

那么 f[i + 1] = f[i] * nums[i] , g[i - 1] = g[i] * nums[i]

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1), g(n + 1);f[0] = 1;g[n - 1] = 1;for(int i = 0; i < n; i ++ ) {f[i + 1] = f[i] * nums[i];}for(int i = n - 1; i > 0; i -- ) {g[i - 1] = g[i] * nums[i];}vector<int> ans(n);for(int i = 0; i < n; i ++ ) {ans[i] = f[i] * g[i];}return ans;}
};

由于輸出數組不計入空間復雜度，所以還可以繼續優化。先把輸出數組當作?L?數組來計算，然后再動態構造?R?數組得到結果。

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> ans(n);ans[0] = 1;for(int i = 1; i <= n; i ++ ) {ans[i] = ans[i - 1] * nums[i - 1];}int r = 1;for(int i = n - 1; i >= 0; i --) {ans[i] = ans[i] * r;r *= nums[i];}return ans;}
};