8.4 數字處理

504. Base 7

題目描述

給定一個十進制整數，求它在七進制下的表示。

輸入輸出範例

輸入一個整數，輸出一個字串，表示其七進制。

Input: 100
Output: "202"

在這個範例中，100 的七進制表示法來源於 100 = 2 * 49 + 0 * 7 + 2 * 1。

題解

進制轉換類型的題目，通常是利用除法和取模（mod）來進行計算，同時也要注意一些細節，如負數和零。如果輸出是數字類型而非字串，也需要考慮是否會超出整數上下界。

C++

string convertToBase7(int num) {
    if (num == 0) {
        return "0";
    }
    string base7;
    bool is_negative = num < 0;
    num = abs(num);
    while (num) {
        int quotient = num / 7, remainder = num % 7;
        base7 = to_string(remainder) + base7;
        num = quotient;
    }
    return is_negative ? "-" + base7 : base7;
}

Python

def convertToBase7(num: int) -> str:
    if num == 0:
        return "0"
    base7 = ""
    is_negative = num < 0
    num = abs(num)
    while num:
        quotient, remainder = num // 7, num % 7
        base7 = str(remainder) + base7
        num = quotient
    return "-" + base7 if is_negative else base7

複雜度分析

• 時間複雜度: $O(\log_7 n)$
  • 每次將 num 除以 7，最多執行 $O(\log_7 n)$ 次。
• 空間複雜度: $O(\log_7 n)$
  • 需要儲存 base7 字串，長度約為 $O(\log_7 n)$。

172. Factorial Trailing Zeroes

題目描述

給定一個非負整數，判斷它的階乘結果的結尾有幾個 0。

輸入輸出範例

輸入一個非負整數，輸出一個非負整數，表示輸入的階乘結果的結尾有幾個 0。

Input: 12
Output: 2

在這個範例中，12! = 479001600 的結尾有兩個 0。

題解

每個尾部的 0 由 2 × 5 = 10 而來，因此我們可以把階乘的每一個元素拆成質數相乘，統計有多少個 2 和 5。明顯的，質因子 2 的數量遠多於質因子 5 的數量，因此我們可以只統計階乘結果裡有多少個質因子 5。

C++

int trailingZeroes(int n) { 
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5); 
}

Python

def trailingZeroes(n: int) -> int:
    return 0 if n == 0 else n // 5 + trailingZeroes(n // 5)

複雜度分析

• 時間複雜度: $O(\log_5 n)$

  • 因為每次遞迴 n 都會除以 5，最多執行 $O(\log_5 n)$ 次。

• 空間複雜度: $O(\log_5 n)$（遞迴堆疊的深度）

  • 遞迴呼叫次數最多 $O(\log_5 n)$ 層。

415. Add Strings

題目描述

給定兩個由數字組成的字符串，求它們相加的結果。

輸入輸出範例

輸入是兩個字符串，輸出是一個整數，表示輸入的數字和。

Input: num1 = "99", num2 = "1"
Output: 100

因為相加運算是從後往前進行的，所以可以先翻轉字符串，再逐位計算。這種類型的題目考察的是細節，如進位、位數差等等。

題解

C++

string addStrings(string num1, string num2) {
    string added_str;
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    int len1 = num1.length(), len2 = num2.length();
    if (len1 <= len2) {
        swap(num1, num2);
        swap(len1, len2);
    }
    int add_bit = 0;
    for (int i = 0; i < len1; ++i) {
        int cur_sum =
            (num1[i] - ’0’) + (i < len2 ? num2[i] - ’0’ : 0) + add_bit;
        added_str += to_string(cur_sum % 10);
        add_bit = cur_sum >= 10;
    }
    if (add_bit) {
        added_str += "1";
    }
    reverse(added_str.begin(), added_str.end());
    return added_str;
}

Python

def addStrings(num1: str, num2: str) -> str:
    added_str = ""
    num1 = num1[::-1]
    num2 = num2[::-1]
    len1, len2 = len(num1), len(num2)
    if len1 <= len2:
        num1, num2 = num2, num1
        len1, len2 = len2, len1
    add_bit = 0
    for i in range(len1):
        cur_sum = int(num1[i]) + (int(num2[i]) if i < len2 else 0) + add_bit
        added_str += str(cur_sum % 10)
        add_bit = int(cur_sum >= 10)
    if add_bit:
        added_str += "1"
    return added_str[::-1]

複雜度分析

• 時間複雜度: $O(\max(m, n))$
  • 需要遍歷 num1 和 num2，最多遍歷 max(m, n) 位數。
• 空間複雜度: $O(\max(m, n))$
  • 儲存 added_str，最多 max(m, n) + 1 位（考慮進位）。

326. Power of Three

題目描述

判斷一個數字是否是 3 的次方。

輸入輸出範例

輸入一個整數，輸出一個布林值。

Input: n = 27
Output: true

題解

有兩種方法，一種是利用對數。設 log3 n = m，如果 n 是 3 的整數次方，那麼 m 一定是整數。

C++

bool isPowerOfThree(int n) {
    return fmod(log10(n) / log10(3), 1) == 0;
}

Python

def isPowerOfThree(n: int) -> bool:
    return n > 0 and math.fmod(math.log10(n) / math.log10(3), 1) == 0

另一種方法是，因為在 C++ int 範圍內 3 的最大次方是 $3^{19} = 1162261467$，如果 n 是 3 的整數次方，那麼 1162261467 除以 n 的餘數一定是零；反之亦然。然而對於 Python 來說，因為 int 理論上可以取無窮大，我們只能循環判斷。

C++

bool isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

Python

def isPowerOfThree(n: int) -> bool:
    if n <= 0:
        return False
    while n % 3 == 0:
        n //= 3
    return n == 1

複雜度分析

• 時間複雜度: $O(\log_3 n)$
  • n 每次都除以 3，最多執行 $O(\log_3 n)$ 次。
• 空間複雜度: $O(1)$
  • 只使用常數變數，沒有額外的空間需求。

50. Pow(x, n)

題目描述

計算 x 的 n 次方。

輸入輸出範例

輸入一個浮點數表示 x 和一個整數表示 n，輸出一個浮點數表示次方結果。

Input: x = 2.00000, n = 10
Output: 1024.00000

題解

利用遞迴，我們可以較為輕鬆地解決本題。注意邊界條件的處理。

C++

double myPow(double x, int n) {
    if (n == 0) {
        return 1;
    }
    if (x == 0) {
        return 0;
    }
    if (n == numeric_limits<int>::min()) {
        return 1 / (x * myPow(x, numeric_limits<int>::max()));
    }
    if (n < 0) {
        return 1 / myPow(x, -n);
    }
    if (n % 2 != 0) {
        return x * myPow(x, n - 1);
    }
    double myPowSqrt = myPow(x, n >> 1);
    return myPowSqrt * myPowSqrt;
}

Python

def myPow(x: float, n: int) -> float:
    if n == 0:
        return 1
    if x == 0:
        return 0
    if n < 0:
        return 1 / myPow(x, -n)
    if n % 2 != 0:
        return x * myPow(x, n - 1)
    myPowSqrt = myPow(x, n >> 1)
    return myPowSqrt * myPowSqrt

複雜度分析

• 時間複雜度: $O(\log n)$
  • 每次計算 n 都會減半 (n / 2)，最多執行 $O(\log n)$ 次。
• 空間複雜度: $O(\log n)$
  • 遞迴深度最多為 $O(\log n)$ 。