資訊專欄INFORMATION COLUMN
摘要：題目旋轉數組給定一個數組，將數組中的元素向右移動個位置，其中是非負數。例如將到反轉將到反轉全部翻轉得到最后結果。這里要注意下還有這樣的情況即大于數組長度的情況。次旋轉次旋轉轉回來了次旋轉次旋轉轉回來了次旋轉所以這里的有效等于對數組長度求余。
題目： 旋轉數組給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。示例：
輸入: [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] 輸入: [-1,-100,3,99] 和 k = 2 輸出: [3,99,-1,-100] 解釋: 向右旋轉 1 步: [99,-1,-100,3] 向右旋轉 2 步: [3,99,-1,-100]思考：
這道題有一種巧妙地利用反轉的做法。 首先將第0個到第k個元素反轉，再將第k+1到末尾元素反轉，最后再將全部元素反轉即可。 例如：[1,2,3,4,5,6,7] k = 3 將0到3反轉：[4,3,2,1,5,6,7] 將4到6反轉：[4,3,2,1,7,6,5] 全部翻轉：[5,6,7,1,2,3,4] 得到最后結果。 這里要注意下還有這樣的情況：[1,2] k = 5 即k大于數組長度的情況。 這里可以發現數組旋轉次數等于數組長度時，旋轉后的數組與初始數組相同，轉了一圈又回來了。 1次旋轉：[2,1] 2次旋轉: [1,2] 轉回來了 3次旋轉：[2,1] 4次旋轉: [1,2] 轉回來了 5次旋轉：[2,1] 所以這里的有效k等于k對數組長度求余。實現：
class Solution {
public void rotate(int[] nums, int k) {
int length = nums.length;
k %= length;
reverse(nums, 0, length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, length - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/6891.html
摘要：題目最小移動次數使數組元素相等給定一個長度為的非空整數數組，找到讓數組所有元素相等的最小移動次數。加一減一所以先求出最小的元素，在求出所有元素與最小元素的差值的和，即為最小移動次數。題目：最小移動次數使數組元素相等 給定一個長度為 n 的非空整數數組，找到讓數組所有元素相等的最小移動次數。每次移動可以使 n - 1 個元素增加 1。 復制代碼 示例： 輸入...
摘要：請定義一個函數實現字符串左旋轉操作的功能。比如，輸入字符串和數字，該函數將返回左旋轉兩位得到的結果。 目錄 第一題:左旋轉字符串 解題思路: 畫圖解析: 代碼實現: 第二題:輪轉數組 解題思路: 畫圖解析: 代碼實現: 第一題:左旋轉字符串 LeetCode 劍指 Offer 58: 描述:...
摘要：先實現棧操作遍歷鏈表，把每個節點都進中然后再遍歷鏈表，同時節點依次出棧，二者進行比較。 ?作者簡介：大家好，我是車神哥，府學路18號的車神? ?個人主頁：應無...
摘要：每日一題叉樹的最大深度鏈接叉樹的最大深度題目分析簡單的搜索題目。只需要從根節點開始一下整個叉樹就可以得到答案了。主要是對要理解和掌握叉樹的遍歷。代碼作者作者 lee...
閱讀 3469·2021-09-02 09:53
閱讀 1792·2021-08-26 14:13
閱讀 2750·2019-08-30 15:44
閱讀 1313·2019-08-30 14:03
閱讀 1962·2019-08-26 13:42
閱讀 3014·2019-08-26 12:21
閱讀 1302·2019-08-26 11:54
閱讀 1899·2019-08-26 10:46
