Solution to JZ 5 & LeetCode 189.
JZ 5
Replace space with “%20” (Easy) [link]
Time complexity O(n), space complexity O(n).
class Solution:
def replaceSpace(self , s: str) -> str:
res = []
for char in s:
if char == ' ':
res.append("%20")
else:
res.append(char)
return "".join(res)
LeetCode 189
Rotate Array (Medium). [link]
Three steps to rotate an array on itself: 1) reverse the elements of the original array. 2) Reverse the element from 0 to k-1, 3) reverse the elements from k to length -1. The time complexity O(n). The space complexity O(1).
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: None Do not return anything, modify nums in-place instead.
"""
length = len(nums)
k %= length
nums.reverse()
nums[:k] = list(reversed(nums[:k]))
nums[k:length] = list(reversed(nums[k:length]))
Without reversed() function in Python.
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: None Do not return anything, modify nums in-place instead.
"""
length = len(nums)
k %= length
def rotate_array(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
rotate_array(nums, 0, length - 1)
rotate_array(nums, 0, k - 1)
rotate_array(nums, k, length - 1)
