Q1. Valid Digit Number

📘 題目敘述

給定一個整數 n 和一個數字 x。

如果一個數字同時滿足以下兩個條件，就算是 valid：

• 它至少包含一次數字 x
• 它的第一位數不能是 x

請判斷 n 是否為 valid。

如果是，回傳 true；否則回傳 false。

條件限制

• 0 <= n <= 10^5
• 0 <= x <= 9

🧠 解題思路

我這題的做法就是直接照題意檢查兩件事：

• 第一位數是不是 x
• 其他位數裡有沒有出現 x

如果第一位數就是 x，那一定不合法，可以直接回傳 false。

否則我再去檢查剩下的位數，只要有任何一位等於 x，就回傳 true。

這份寫法的重點是把「第一位數」和「後面其他位數」分開處理。

所有變數

• f：n 的第一位數

🪜 主要流程步驟

1. 先找出 n 的第一位數

我先用一個變數 f 複製 n：

int f = n;

然後一直除以 10，直到它變成個位數為止：

while (f > 9) {
    f /= 10;
}

這樣最後留下來的 f，就是 n 的第一位數。

2. 如果第一位數就是 x，直接回傳 false

題目規定 valid number 不能以 x 開頭。

所以如果：

if (f == x) {
    return false;
}

那就直接不合法，不需要再往後檢查。

3. 再檢查後面的位數有沒有出現 x

如果第一位數不是 x，我就開始檢查其他位數。

• 每次先看目前最後一位 n % 10
• 如果它剛好等於 x，就代表數字裡有出現 x，而且不是第一位，所以符合條件，直接回傳 true
• 否則就把最後一位去掉，繼續檢查前一位

這裡用 while (n > 9)，代表最後不會檢查到最前面那一位。

因為最前面那位前面已經單獨檢查過，而且如果它等於 x，早就直接回傳 false 了。

4. 如果都沒找到，就回傳 false

如果後面所有位數都掃完，還是沒有看到 x，

那就代表這個數字雖然不是以 x 開頭，但也沒有包含任何 x，所以不合法。

最後回傳 false。

⏱️ 複雜度

設 d 為 n 的位數。

• 時間複雜度：O(d)
  我最多掃過數字的每一位一次。
• 空間複雜度：O(1)
  只用了固定數量的變數。

💻 程式碼實作

class Solution {
public:
    bool validDigit(int n, int x) {
        int f = n;
        while (f > 9) {
            f /= 10;
        }
        if (f == x) {
            return false;
        }
        while (n > 9) {
            if (n % 10 == x) {
                return true;
            }
            n /= 10;
        }
        return false;
    }
};

🔗 題目連結

https://leetcode.com/contest/biweekly-contest-181/problems/valid-digit-number/