前言

在軟體工程師和程式設計的工作或面試的過程中不會總是面對到只有簡單邏輯判斷或計算的功能，此時就會需要運用到演算法和資料結構的知識。本系列文將整理程式設計的工作或面試入門常見的程式解題問題和讀者一起探討，研究可能的解決方式（主要使用的程式語言為 Python）。其中字串處理操作是程式設計日常中常見的使用情境，本文將從簡單的字串處理問題開始進行介紹。

要注意的是在 Python 的字串物件 str 是 immutable 不可變的，字串中的字元是無法單獨更改變換。

舉例來說，以下的第一個指定字元變數行為是不被允許的，但整體字串重新賦值指定另外一個字串物件是可以的：

name = 'Jack'

# 錯誤
name[0] = 'L'

# 正確
name = 'Leo'

執行結果：

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

常見問題

字串反轉

Problem: Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

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

You may assume all the characters consist of printable ascii characters.

範例：

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

題目意思為輸入為一個元素為字串的列表 list，將列表中的字串進行反轉後輸出。

Solution

1. 一般思路
   由於字串反轉為對稱對應，所以可以取中間軸線進行 for 迴圈迭代進行元素替換。

    # 字串長度為 5，中間軸為第三個元素 3
    name = 'Marry'
   
    """
    name => ['M', 'a', 'r', 'r', 'y']
    reverse_name => ['y', 'r', 'r', 'a', 'M']
   
    字串長度為 5，反轉為對稱對應
    name[0] 對應到 reverse_name[5 - 1]
    name[1] 對應到 reverse_name[4 - 1]
    name[2] 對應到 reverse_name[3 - 1]
    name[3] 對應到 reverse_name[2 - 1]
    name[4] 對應到 reverse_name[1 - 1]
    """
   

   參考寫法：

    class Solution:
        def reverseString(self, s: List[str]) -> None:
            """
            Do not return anything, modify s in-place instead.
            """
            length = len(s)
   
            if length < 2:
                return
   
            # length // 2 為取中間軸線整數進行迴圈（注意 index 從 0 開始）
            for i in range(length // 2):
                # 進行對稱替換
                s[i], s[length - i - 1] = s[length - i - 1], s[i]
            return
   

2. 使用 Python 內建函式思路
   在 Python 中 list 內建 reverse 函式（官方文件），可以直接進行反轉。

    class Solution:
        def reverseString(self, s: List[str]) -> None:
            """
            Do not return anything, modify s in-place instead.
            """
            # 將字串串列反轉後回傳
            s.reverse()
            return s
   

整數反轉

Problem Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.

Note:
Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Example 1:

Input: x = 123
Output: 321
Example 2:

Input: x = -123
Output: -321
Example 3:

Input: x = 120
Output: 21
Example 4:

Input: x = 0
Output: 0

Constraints:

-231 <= x <= 231 - 1

題目的意思輸入一個 32-bit 帶有符號（有正負號）的整數，回傳反轉過後的整數，注意若反轉結果大小超過限制則回傳 0。

Solution

1. 一般數學思路
   由於整數可以透過取除 10 的餘數得出尾數，每次將尾數新增到反轉結果後面後透過整除 10 將尾數去除，最後就會的到反轉整數（若有負值則可以先紀錄後改為正整數最後乘回來）。

   例如：
   123
   => 123 % 10 餘 3, 123 整除 10 為 12
   => 12 % 10 餘 2, 12 整除 10 為 1
   => 1 % 10 餘 1, 1 整除 10 為 0

   此時按照順序把餘數取出並乘上對應的 10 的倍數
   3 100 + 2 10 + 1 即為反轉整數

   以下我們使用 while 迴圈來達到反轉的計算：

    class Solution:
        def reverse(self, x: int) -> int:
            reverse_num = 0;
            # 限制範圍
            limit_floor = pow(-2, 31)
            limit_ceiling = pow(2, 31)
            minus = False
   
            if x < 0:
                x = abs(x)
                minus = True
            while x != 0:
                # 取餘數為每一個反轉數
                pop = x % 10;
                # 每次去除尾數
                x //= 10;
                # 一一加上去尾數
                reverse_num = int(reverse_num * 10 + pop)
   
            # 若結果超過限制回傳 0
            if reverse_num > limit_floor and reverse_num < (limit_ceiling - 1):
                # 若為負整數需要乘回來
                if minus:
                    return reverse_num * -1
                else:
                    return reverse_num
            else:
                return 0
   

2. 使用 Python 內建函式轉換成 list 反轉思路
   透過將整數轉成字串物件後使用 list 反轉來轉換反轉整數。

    class Solution:
        def reverse(self, x: int) -> int:
            raw_num = x
            # 限制範圍
            limit_floor = pow(-2, 31)
            limit_ceiling = pow(2, 31)
   
            # 將整數轉為字串串列使用 reverse 函式進行反轉
            num_list = [str(num) for num in str(abs(raw_num))]
            num_list.reverse()
            reverse_num = int(''.join(num_list))
   
            # 若結果超過限制回傳 0
            if reverse_num > limit_floor and reverse_num < (limit_ceiling - 1):
                if x < 0:
                    reverse_num = reverse_num * -1
                    return reverse_num
                else:
                    return return reverse_num
            else:
                return 0
   

總結

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