跳至主要内容

8.4 數字處理

504. Base 7​

題目描述​

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

輸入輸出範例​

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

Input: 100
Output: "202"

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

題解​

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

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;
}

172. Factorial Trailing Zeroes​

題目描述​

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

輸入輸出範例​

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

Input: 12
Output: 2

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

題解​

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

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

415. Add Strings​

題目描述​

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

輸入輸出範例​

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

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

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

題解​

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;
}

326. Power of Three​

題目描述​

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

輸入輸出範例​

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

Input: n = 27
Output: true

題解​

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

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

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

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

50. Pow(x, n)​

題目描述​

計算 x 的 n 次方。

輸入輸出範例​

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

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

題解​

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

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;
}