前言

在軟體工程師和程式設計的工作或面試的過程中不會總是面對到只有簡單邏輯判斷或計算的功能，此時就會需要運用到演算法和資料結構的知識。本系列文將整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 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 a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Constraints:

0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in ascending order.

這個問題主要希望從一個給定排序的陣列中刪除重複的元素，取得新的陣列長度，並希望在不使用額外的記憶體空間下完成任務。一開始我們可以使用暴力解法就是逐一比較並提供一個暫存空間儲存比對的結果。但這樣可能會使用過多資源不符合題目的要求，所以我們可以嘗試使用雙指針的方式，透過兩個變數分別儲存依序比對的位置索引和需要刪除替換元素的位置索引，在 O(1) 記憶體空間的使用下得到結果。

Solution
參考方法：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 當串列長度為零，直接回傳零
        if not nums:
            return 0

        # 計算串列長度
        nums_len = len(nums)
        # 變數 j 為較快的右指標
        j = 1
        # 變數 i 為較慢的左的指標
        i = 1

        while j < nums_len:
            # 當發現索引 j 和前一項元素不同時，更新索引 i 的內容為索引 j 內容
            if nums[j] != nums[j - 1]:
                nums[i] = nums[j]
                # i 索引位置往右移
                i += 1
            # 每一次迴圈 j 索引位置往右移
            j += 1
        # 回傳索引 i，也就是新的串列長度
        return i

時間複雜度：O(n)，根據 nums 長度決定迴圈次數
空間複雜度：O(1)，只有常數空間儲存指標

最佳買賣股票時機

Problem: Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4

本題目主要是計算如何選擇某一天買進股票在未來某一個不同天賣出股票，可以獲得最大利潤，注意賣出價格需大於買入價格（若無法完成交易則為零）。

Solution
參考方法：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 初始化 min_price 為一個極大值 e^9
        inf = int(1e9)
        min_price = inf
        # 初始化 maxprofit 為 0
        max_profit = 0
        # 每次迴圈計算並更新最大利潤及最低買點
        for price in prices:
            max_profit = max(price - min_price, max_profit)
            min_price = min(price, min_price)
        return max_profit

透過迴圈取出 prices 串列，每次更新取得最低買點和最高利潤，最後回傳最大利潤值。

時間複雜度：O(n)，根據 prices 長度決定迴圈次數
空間複雜度：O(1)，只有常數空間儲存變數

總結

以上介紹了常見的程式解題陣列相關問題，本系列文將持續整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 Python）。需要注意的是 Python 本身內建的操作方式和其他程式語言可能不同，文中所列的不一定是最好的解法，讀者可以自行嘗試在時間效率和空間效率運用上取得最好的平衡點。