前言
在軟體工程師和程式設計的工作或面試的過程中不會總是面對到只有簡單邏輯判斷或計算的功能，此時就會需要運用到演算法和資料結構的知識。本系列文將整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 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: Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
Constraints:
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
Each element in the array appears twice except for one element which appears only once.
本題考驗主要給定一個非空陣列，希望找出只出現一個的某個元素，其餘元素皆出現兩次。
Solution
參考方法一：排序兩兩比較法
透過排序後元素以兩個為單位兩兩比較，直到出現不相等的元素，若最後剩下一個單個元素則最後一個元素為唯一值。
範例程式碼：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 事先排序
nums.sort()
nums_length = len(nums)
# 當輸入長度小於 3 則取首個元素
if nums_length < 3:
return nums[0]
index = 0
# 排序後鄰近元素兩兩比較看是否有不同，若有則為唯一值
while index < nums_length - 2:
if nums[index] != nums[index + 1]:
return nums[index]
else:
# 以兩個單位往後移動
index += 2
# 最後一個元素
return nums[-1]
參考方法二：集合交叉比對法
利用集合特性，將排序後的列表透過 Python 串列切片的方式將元素平均分為奇偶索引數列，取兩個集合的差即可得到單一個元素（其餘皆有重複值）。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 事先排序
nums.sort()
# 奇數索引串列和偶數索引串列轉為集合後取差集
single_num_set = set(nums[::2]) - set(nums[1::2])
# 將 set 轉為 list 取出第一個元素
return list(single_num_set)[0]
加一
Problem: Plus One
Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Example 3:
Input: digits = [0]
Output: [1]
Constraints:
1 <= digits.length <= 100
0 <= digits[i] <= 9
本題為給定一個非空陣列，代表一個非負數值，每一個陣列元素代表整數中一個一個位數，目標為取得在該基礎上加一後結果值。
Solution
參考方法一：轉換數字加一
將問題簡化為簡單的數學問題，先將列表的每一個位數組合成完整數字後加一，再分割回整數串列。
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
digits = [str(digit) for digit in digits]
# 將串列位數組成整數
num = int(''.join(digits))
# 整數加一
num += 1
# 將整數轉為字串後分割為位數串列
plus_digits = [int(digit) for digit in list(str(num))]
return plus_digits
參考方法二：顛倒順序法加一
由於反轉後再加一可以簡化問題，所以將列表進行反轉後加一並處理進位問題，再回復為整數串列。
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
digits.reverse()
# 確認是否進位
flag = True
# 逐一判斷位數是否為 9，若是則需要進位否則單純累加一
for index in range(len(digits)):
if flag == True:
if digits[index] == 9:
digits[index] = 0
else:
digits[index] += 1
flag = False
# 若尾數為零代表需要進位
if digits[-1] == 0:
digits.append(1)
# 回復原方向
digits.reverse()
return digits
總結
以上介紹了常見的程式解題陣列相關問題，本系列文將持續整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 Python）。需要注意的是 Python 本身內建的操作方式、資料型別結構和其他程式語言可能不同，文中所列的不一定是最好的解法，讀者可以自行嘗試在時間效率和空間效率運用上取得最好的平衡點。
