Solution to LeetCode 167 Two Sum II - Input Array Is Sorted, LeetCode 189 Rotate Array, LeetCode 283 Move Zeros, LeetCode 344 Reverse String, LeetCode 557 Reverse Words in a String III, LeetCode 977 Squares of a Sorted Array.
LeetCode 167
Two Sum II - Input Array Is Sorted (Medium) [link]
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
elif total < target:
left += 1
else:
right -= 1
return [-1, -1]
LeetCode 189
Rotate Array (Medium) [link]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k = k%n
nums[:] = nums[n-k:] + nums[:n-k]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k = k%n
def swap(l,r):
while l<r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
swap(0, n-k-1)
swap(n-k, n-1)
swap(0, n-1)
LeetCode 283
Move Zeros (Easy) [link]
Exchange right pointer (at zero) and the left pointer (at non zero).
Time complexity O(n). Space complexity O(1).
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
right, left = 0, 0
# while right < n:
for right in range(n):
if nums[right] != 0:
nums[right], nums[left] = nums[left], nums[right]
left += 1
right += 1
LeetCode 344
Reverse String (Easy) [link]
Time complexity O(n).
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left, right = 0, len(s)-1
while left < right:
s[left],s[right] = s[right],s[left]
left += 1
right -= 1
LeetCode 557
Reverse Words in a String III (Easy) [link]
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join([word[::-1] for word in s.split(" ")])
LeetCode 977
Squares of a Sorted Array (Easy) [link]
It takes O(nlogn) to sort the squared values directly.
It take O(n) by using double pointers.
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
neg = -1
for ind, num in enumerate(nums):
if num < 0:
neg = ind
else:
break
res = []
i, j = neg, neg + 1
while i >= 0 or j < n:
if i < 0:
res.append(nums[j]*nums[j])
j += 1
elif j == n:
res.append(nums[i]*nums[i])
i -= 1
elif nums[i] * nums[i] < nums[j] * nums[j]:
res.append(nums[i] * nums[i])
i -= 1
else:
res.append(nums[j]*nums[j])
j += 1
return res
