DAY 28
1
Software Development

## [Day 28] 從LeetCode學演算法 - 0189. Rotate Array (Easy)

``````Question:
Given an array, rotate the array to the right by k steps, where k is non-negative.
``````
``````Example 1:
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
``````
``````Example 2:
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
``````
``````Note:
Try to come up with 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?
``````

(這兩個解法筆者列在Python的註解中供讀者參閱)

[1,2,3,4,5,6,7] and k = 3 -> [5,6,7,1,2,3,4]

1. 整個陣列進行反轉
2. 前k個數進行反轉
3. 後l-k個數進行反轉

(例: [1,2,3,4]->[4,2,3,1]->[4,3,2,1])
Java的部分的兩數交換需要宣告一個暫存值tmp(temp)，
Python的部分則可直接使用a, b = b, a的方式進行交換。

Java:

``````class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length < 2) return;
int len = nums.length;
k = k % len;

reverse(nums, 0, nums.length - k - 1);
reverse(nums, nums.length - k, nums.length - 1);
reverse(nums, 0, nums.length - 1);
}

private void reverse(int[] nums, int i, int j) {
int tmp = 0;
while(i < j) {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++;
j--;
}
}
}
``````

Python:

``````class Solution:
def rotate(self, nums: List[int], k: int) -> None:
def numReverse(start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
k, n = k % len(nums), len(nums)
if k:
numReverse(0, n - 1)
numReverse(0, k - 1)
numReverse(k, n - 1)
'''
# Not in-place solution
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
l = len(nums)
k %= l
if k > 0:
nums[0:l] = nums[-k:] + nums[:-k]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
l = len(nums)
k %= l
if k > 0:
nums[:] = (nums + nums)[l-k:l-k+l]
'''
``````

「時間/空間複雜度？」
(O(N), O(1)(如果是使用3次reverse的方法))

「如不限制空間複雜度必須O(1)？」
(可以參照上面Python程式碼中註解的做法)

0198. House Robber (Easy)

### 1 則留言

0
hyj1116
iT邦新手 4 級 ‧ 2019-09-29 17:09:23

Desolve iT邦新手 5 級 ‧ 2019-09-29 18:37:32 檢舉

Hi~