題目資訊

題目編號: 2843
題目連結: Count Symmetric Integers
主題: Math, Enumeration

題目敘述

您有兩個正整數 low 和 high。

一個由 $2 * n$ 位數字組成的整數 x 是對稱的，如果 x 的前 $n$ 個數字之和等於 x 的後 $n$ 個數字之和。奇數位數的數字永遠不會是對稱的。

返回範圍 [low, high]內的對稱整數的數量。

範例 1:

輸入: low = 1, high = 100
輸出: 9
解釋: 在 1 到 100 之間有 9 個對稱整數：11, 22, 33, 44, 55, 66, 77, 88 和 99。

範例 2:

輸入: low = 1200, high = 1230
輸出: 4
解釋: 在 1200 到 1230 之間有 4 個對稱整數：1203, 1212, 1221 和 1230。

約束條件:

$1 \leq \text{{low}} \leq \text{{high}} \leq 10^4$

直覺

這個問題要求識別並計數在給定範圍內的「對稱」整數。一個「對稱」整數被定義為其位數為偶數且其位數前半部分的總和等於後半部分的總和。挑戰在於高效地確定在指定範圍內哪些數字具備這個特性。我們的初步思路涉及系統地評估範圍內的每一個整數，分析每個數字的位數結構，並計算必要的總和以驗證對稱性。

解法

解決這個問題的方法包括遍歷範圍 ([low, high]) 內的每個整數，並檢查其是否符合對稱的標準。解法包含以下步驟：

輔助函數 isSymmetric:
- 此函數接受一個整數 num 並判斷它是否是對稱的。
- 確定長度: 使用公式 $length = \log_{10}(num) + 1$ 計算 num 的總位數。
- 檢查偶數性: 對稱數字必須具有偶數的位數。如果長度為奇數，則立即返回 false，因為這樣的數字不可能是對稱的。
- 計算總和: 對於位數為偶數的 num，步驟如下：
  - 初始化 sum 變量為零。
  - 後半部分的總和: 提取並求和 num 的最後 $n$ 位數字（其中 $n$ 為 num 的長度的一半）。這是通過迭代取 num 除以 10 的餘數，將其添加到 sum，然後將 num 除以 10 來實現的。
  - 前半部分的總和: 使用相同的迭代技術從先前計算的總和中減去前 $n$ 位數字的總和。如果結果 sum 為零，則表示兩部分的總和相等，表示對稱。
- 如果 sum 為零，則返回 true，否則返回 false。
主函數 countSymmetricIntegers:
- 初始化計數器 symmetricCount 為零。
- 遍歷範圍 ([low, high]) 內的每個整數 i。
  - 使用輔助函數 isSymmetric 檢查每個數字：
    - 如果 isSymmetric(i) 返回 true，則增加 symmetricCount。
- 最後，返回 symmetricCount 的值，這表示在指定範圍內找到的對稱整數的總數。

此直接的暴力法保證評估給定範圍內的所有整數的對稱性，藉助輔助函數來簡化並封裝根據位數總和確定對稱性的邏輯。

程式碼

C++

class Solution {
public:
    // 檢查給定的數字是否對稱的函數
    bool isSymmetric(int num) {
        int length = log10(num) + 1; // 計算數字的長度
        int sum = 0;
        
        // 如果長度是奇數，則數字不可能是對稱的
        if (length % 2 != 0) 
            return false;
        
        // 計算最後n位數字的和
        for (int i = 0; i < length / 2; i++) {
            sum += num % 10;
            num /= 10;
        }
        
        // 減去最前面n位數字的和
        for (int i = 0; i < length / 2; i++) {
            sum -= num % 10;
            num /= 10;
        }
        
        // 如果兩個和相等，則該數字是對稱的
        return sum == 0;
    }
    
    // 計算給定範圍[low, high]內對稱整數的函數
    int countSymmetricIntegers(int low, int high) {
        int symmetricCount = 0;

        // 遍歷給定範圍內的每個數字
        for (int i = low; i <= high; i++) {
            // 如果數字是對稱的，則計數加一
            if (isSymmetric(i)) 
                symmetricCount++;
        }

        return symmetricCount; // 返回對稱數字的總數
    }
};

Python

class Solution:
    # 檢查給定數字是否為對稱數的函數
    def isSymmetric(self, num: int) -> bool:
        length = int(log10(num)) + 1  # 計算數字的長度
        sum = 0
        
        # 如果長度是奇數，則數字不可能是對稱的
        if length % 2 != 0:
            return False
        
        # 計算最後 n 位數字的總和
        for i in range(length // 2):
            sum += num % 10
            num //= 10
        
        # 減去前 n 位數字的總和
        for i in range(length // 2):
            sum -= num % 10
            num //= 10
        
        # 如果前後位數的和相等，則數字是對稱的
        return sum == 0
    
    # 計算給定範圍 [low, high] 中對稱數的函數
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        symmetricCount = 0

        # 迭代給定範圍內的每一個數字
        for i in range(low, high + 1):
            # 如果數字是對稱的，遞增計數
            if self.isSymmetric(i):
                symmetricCount += 1

        return symmetricCount  # 返回對稱數字的總計數

複雜度分析

時間複雜度: $O(n \cdot d)$
countSymmetricIntegers 函數的時間複雜度為 $O(n \cdot d)$ ，其中 $n$ 是 high 和 low 之間的差 (即 $n = \text{{high}} - \text{{low}} + 1$ )，而 $d$ 是該範圍內最大數字的位數。這是因為對於範圍 [low, high] 中的每個數字，會調用 isSymmetric 函數，該函數需要處理高達 $d/2$ 的數位兩次——一次用於求和最後 $n$ 位數，另一次用於減去前 $n$ 位數。因此，每次調用 isSymmetric 都需要 $O(d)$ 的時間，且有 $n$ 次如此的調用，從而導致總時間複雜度為 $O(n \cdot d)$ 。
空間複雜度: $O(1)$
空間複雜度為 $O(1)$ ，因為唯一使用的額外空間是幾個整數變數，而且這不依賴於輸入的大小。該函數不利用任何隨著輸入大小而縮放的數據結構。

CS Note
En

Leetcode 2843. Count Symmetric Integers

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析