這道題要求統(tǒng)計(jì)區(qū)間 [l, r] 內(nèi)所有相鄰數(shù)位絕對(duì)差不超過(guò) k 的整數(shù)個(gè)數(shù)。由于 r 最大可達(dá) 10^15暴力枚舉不可行需要用數(shù)位 DP (Digit DP) 來(lái)解決。核心思路數(shù)位 DP 的核心是“按位構(gòu)造”數(shù)字。我們定義一個(gè)遞歸函數(shù) dfs(i, prev, tightLow, tightHigh)· i當(dāng)前處理到第幾位?！?prev上一位的數(shù)字用 -1 表示還沒(méi)有有效前一位以處理前導(dǎo)零?！?tightLow / tightHigh表示前綴是否分別緊貼著下界 l 或上界 r。狀態(tài)轉(zhuǎn)移1. 遞歸出口處理完所有位數(shù)返回 1 表示找到一個(gè)好數(shù)。2. 確定當(dāng)前位的可選范圍· 下界tightLow ? low[i] : 0· 上界tightHigh ? high[i] : 93. 枚舉并遞歸· 若當(dāng)前仍處于前導(dǎo)零狀態(tài) (prev -1) 且選擇 0則繼續(xù)視為無(wú)前導(dǎo)零?！?否則檢查當(dāng)前位與 prev 的絕對(duì)差是否 k。TypeScript 實(shí)現(xiàn)typescriptfunction goodIntegers(l: number, r: number, k: number): number {// 將上下界補(bǔ)零對(duì)齊到相同長(zhǎng)度方便數(shù)位DP處理const maxLen: number String(r).length;const lowStr: string String(l).padStart(maxLen, 0);const highStr: string String(r).padStart(maxLen, 0);const low: number[] lowStr.split().map(Number);const high: number[] highStr.split().map(Number);// 記憶化數(shù)組dp[i][prev1][tightLow][tightHigh]// prev 范圍 -1 ~ 9加1偏移映射到 0 ~ 10const memo: Mapstring, number new Map();function dfs(i: number, prev: number, tightLow: boolean, tightHigh: boolean): number {if (i maxLen) {return 1; // 成功構(gòu)造出一個(gè)好數(shù)}const key: string ${i},${prev 1},${tightLow},${tightHigh};if (memo.has(key)) {return memo.get(key)!;}// 確定當(dāng)前位的可選范圍const lo: number tightLow ? low[i] : 0;const hi: number tightHigh ? high[i] : 9;let ans: number 0;for (let digit lo; digit hi; digit) {const nextTightLow: boolean tightLow (digit lo);const nextTightHigh: boolean tightHigh (digit hi);// 處理前導(dǎo)零如果之前沒(méi)有有效數(shù)字且當(dāng)前填0則prev仍為-1if (prev -1 digit 0) {ans dfs(i 1, -1, nextTightLow, nextTightHigh);} else if (prev -1 || Math.abs(digit - prev) k) {// 第一個(gè)有效數(shù)字或差值滿(mǎn)足條件ans dfs(i 1, digit, nextTightLow, nextTightHigh);}}memo.set(key, ans);return ans;}return dfs(0, -1, true, true);}復(fù)雜度分析· 時(shí)間復(fù)雜度O(maxLen * 10 * 2 * 2 * 10)即 O(log r * 10^2)對(duì)于 10^15 的量級(jí)綽綽有余?！?空間復(fù)雜度O(log r * 10 * 2 * 2)。