Authored by Tony Feng
Created on April 24th, 2022
Last Modified on April 24th, 2022
Task 1 - Q21. 调整数组顺序使奇数位于偶数前面
Question
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution: # Head & Tail
def exchange(self, nums: List[int]) -> List[int]:
i, j = 0, len(nums) - 1
while i < j: # Traverse the array from two sides
if nums[i] % 2 == 1:
i += 1
elif nums[j] % 2 == 0:
j -= 1
else:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
return nums
|
Solution 2
1
2
3
4
5
6
7
8
9
|
class Solution: # Fast & Slow
def exchange(self, nums: List[int]) -> List[int]:
slow = fast = 0
while fast < len(nums):
if nums[fast] % 2 == 1: # Find odd number and swap no matter what slow points to
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
fast += 1
return nums
|
Explanation
- Solution 1 & 2
- Time Complexity: O(N)
- Space Complexity: O(1)
Task 2 - Q57. 和为s的两个数字
Question
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if len(nums) <= 1:
return None
l, r = 0, len(nums)-1 # Head & Tail
while nums[r] > target: # Ignore the number who's larger than the target
r -= 1
while l < r:
if nums[l] + nums[r] > target:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
return [nums[l], nums[r]]
return None
|
Explanation
- Time Complexity: O(N)
- Space Complexity: O(1)
Task 3 - Q58,I. 翻转单词顺序
Question
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
要求：
- 为简单起见，标点符号和普通字母一样处理。
“I am a student. " ->“student. a am I”。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
" hello world! " -> “world! hello”
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
“a good example” -> “example good a”
Solution
1
2
3
4
|
class Solution:
def reverseWords(self, s: str) -> str:
# Use the built-in function of Python
return (" ").join(s.split()[::-1])
|
Explanation
- Time Complexity: O(N)
- Space Complexity: O(1)