略譯

原題目連結

給你 n 和 m
求 [n, m] 中有多少個整數，每一位數兩兩不相等

題解

按題目敘述暴力即可

每一位數兩兩不相等 之 取得每一位數

取出每一位數的方式可以用 % 來取餘數

由於我們只在意每一位數，不在意順序之類的，
對於一整數 i 我們可以一直對其 i%10 取得個位數，
再讓 i = i/10 消掉已經取得的個位數，
則原本的十位數會跑到個位數，故又可用 i%10 取得十位數，
直到 i 被除到 0 為止，此方法可以很方便的取得每一個位數

每一位數兩兩不相等 之 快速判斷兩兩不相等

每一位數的範圍只會有 0~9 共 10 種，
用一個長度 10 的陣列 tbl[k] 來存數字 k 是不是出現過，
可以避免每個位數兩兩比較

每一位數兩兩不相等 之 迴避 tbl 歸零

承上，tbl 需要在每個整數判斷時先行清空歸零；
但若我們不把 tbl 當成 bool 只存是與否，
而是存當前判斷中的整數 i

若 tbl[k] == i 代表 k 存在於整數 i 的某個位數

如此無須歸零，也可正確判斷

預建表

輸入範圍只到 5000，且每個數是否符合「每一位數兩兩不相等」，
不受輸入影響計算結果，故可以先行將結果建表，
便無須每次輸入重新計算

預加總

sum [a, b] = sum[0, b] - sum[0, a-1]

利用上述的建表結果，建立一張表 T
使得 T[i] = sum [0, i]

又，T[i-1] = sum[0, i-1]
設 A[i] 代表 i 是否每一位數兩兩不相等，是則 1，不是則 0
得到 T[i] = T[i-1] + A[i]

如此對於任一組詢問 [n, m]
都能透過 T[m] - T[n-1] 直接回答

實作提示

• 無