前言
在軟體工程師和程式設計的工作或面試的過程中不會總是面對到只有簡單邏輯判斷或計算的功能，此時就會需要運用到演算法和資料結構的知識。本系列文將整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 Python）。其中字串處理操作是程式設計日常中常見的使用情境，本文繼續將從簡單的陣列和串列處理問題開始進行介紹。
要注意的是在 Python 並無 Array 陣列的資料型別，主要會使用 List 串列進行說明。不過，相對於一般程式語言的 Array 陣列，Python 串列 List 具備許多彈性和功能性。
舉例來說，切片 slicing 就是 Python List 非常方便的功能，可以很方便的取出指定片段的子串列：
names = ['Jack', 'Joe', 'Andy', 'Kay', 'Eddie']
sub_names = names[2:4]
print(sub_names)
執行結果：
['Andy', 'Kay']
常見問題
旋轉陣列
Problem: Remove Duplicates from Sorted Array
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], 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: nums = [-1,-100,3,99], 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]
Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
Follow up:
Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?
本題考驗主要希望將陣列移動 k 個位置，盡可能思考多種解決方案，而空間複雜度盡量可以使用 O(1) 方式進行。
Solution
參考方法一：反轉串列法
由於 Python 在反轉串列上十分方便，且追加元素於最後比起平移整個串列更方便。先翻轉串列並將 k 數量的首值 pop 出來，append 到串列的尾端，最後再將串列反轉。
# Input [1,2,3,4,5,6,7]
# k = 3
[7, 6, 5, 4, 3, 2, 1]
[6, 5, 4, 3, 2, 1, 7]
[5, 4, 3, 2, 1, 7, 6]
[4, 3, 2, 1, 7, 6, 5]
[5, 6, 7, 1, 2, 3, 4]
範例程式碼：
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 若長度小於 2 則不用移動
if len(nums) < 2:
return nums
# 避免 k 大於 nums 長度，若大於代表移動一輪，故取餘數
k = k % len(nums)
# 由於正方向整個串列往後移動較困難，將串列反轉比較方便
nums.reverse()
for _ in range(k):
# 將翻轉後的串列 index 0 值取出放到最後面（移動位置）
rotate_item = nums.pop(0)
nums.append(rotate_item)
nums.reverse()
return nums
參考方法二：區塊移動法
主要透過將需移動位置的區塊整塊移動到前面，其餘整塊往後移動來取得移動後結果。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) < 2:
return nums
# 避免 k 大於 nums 長度，若大於代表移動一輪，故取餘數
k = k % len(nums)
num_length = len(nums)
# 移動 k 位置的區塊
move_nums = nums[num_length - k:]
# 其餘往後移動
nums[k:] = nums[:num_length - k]
# 將移動 k 位置的區塊放到最前面
nums[:k] = move_nums
return nums
另外，注意的是若要使用迴圈逐一移動位置的暴力法雖然簡單直觀，但有可能因為輸入過大會造成所花的時間過長。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) < 2:
return nums
k = k % len(nums)
for _ in range(k):
# 將最後的值取出
rotate_item = nums.pop()
# 將首個位置以後的值往後移動
nums[1:] = nums[:]
# 將首值更改為最後的值
nums[0] = rotate_item
return nums
存在重複
Problem: Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
本題為給定一個整數陣列，判斷是否存在重複字串，若有則回傳 True，若每個數字都不重複則回傳 False。
Solution
參考方法一：排序後比較法
透過將串列先排序後可以比較若相鄰的元素相同代表有重複元素。
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
# 先行排序
nums.sort()
# 比較相鄰元素是否相同
for index in range(len(nums) - 1):
if nums[index] == nums[index + 1]:
return True
return False
參考方法二：集合長度比較法
在 Python 中若取集合後的長度和原來串列長度相同則代表沒有重複值。
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
if len(set(nums)) == len(nums):
return False
else:
return True
另外，同樣要注意的是若要使用迴圈逐一移動位置的暴力法雖然簡單直觀，但有可能因為輸入過大會造成所花的時間過長。
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
for index, item in enumerate(nums):
if item in nums[index + 1:]:
return True
return False
總結
以上介紹了常見的程式解題陣列相關問題，本系列文將持續整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 Python）。需要注意的是 Python 本身內建的操作方式和其他程式語言可能不同，文中所列的不一定是最好的解法，讀者可以自行嘗試在時間效率和空間效率運用上取得最好的平衡點。
