📘 題目敘述
給你一個整數 n。
若某數字的各位數字階乘總和等於它本身，則稱為 digitorial。請判斷 n 的任意排列（不能有前導 0）是否能形成 digitorial 數字。
條件限制
1 <= n <= 10^9
🧠 解題思路
我不用枚舉所有排列，而是比較數字 multiset：
- 先算出
n的各位階乘和sum。 - 分別統計
n與sum的每個數字出現次數。 - 若 0~9 次數完全相同，代表
sum是n的某個排列，回傳 true。
所有變數
fact：0~9 階乘表sum：n的各位數字階乘總和k：n的副本a、b：分別記錄n與sum的數字次數
🪜 主要流程步驟
1. 建立階乘表
先準備 fact[10] 供 O(1) 查詢 digit!。
2. 計算 sum
用 k 掃描 n 每一位，累加 fact[digit] 得到 sum。
3. 統計次數並比較
分別統計到 a[] 和 b[]，全部相等就回傳 true。
⏱️ 複雜度
- 時間複雜度：
O(d)（d為位數） - 空間複雜度：
O(1)
💻 程式碼實作
class Solution {
public:
bool isDigitorialPermutation(int n) {
int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int sum = 0;
int k = n;
while (k > 0) {
sum += fact[k % 10];
k /= 10;
}
int a[10] = {0}, b[10] = {0};
while (n > 0) {
a[n % 10]++;
n /= 10;
}
while (sum > 0) {
b[sum % 10]++;
sum /= 10;
}
for (int i = 0; i < 10; i++) {
if (a[i] != b[i]) {
return false;
}
}
return true;
}
};🔗 題目連結
https://leetcode.com/contest/weekly-contest-490/problems/check-digitorial-permutation/