1function countDigitOne(n) {
2 const digits = String(n).split('').map(Number);
3 const memo = new Map();
4 function dfs(pos, cnt, limit) {
5 if (pos === digits.length) return cnt;
6 const key = pos + ',' + cnt + ',' + limit;
7 if (!limit && memo.has(key)) return memo.get(key);
8 const up = limit ? digits[pos] : 9;
9 let res = 0;
10 for (let d = 0; d <= up; d++)
11 res += dfs(pos + 1, cnt + (d === 1 ? 1 : 0), limit && d === up);
12 if (!limit) memo.set(key, res);
13 return res;
14 }
15 return dfs(0, 0, true);
16}