对于 LeetCode 3753 这道困难题核心解法是数位 DP配合前缀和技巧F(num2) - F(num1-1)。以下是基于该思路的 JavaScript 实现。javascript/*** param {number} num1* param {number} num2* return {number}*/var totalWaviness function(num1, num2) {const countUpTo (x) {if (x 100) return 0; // 少于3位数波动值为0const digits String(x).split().map(Number);const n digits.length;// 记忆化缓存key编码为字符串const memo new Map();// pos: 当前处理位置, prev2: 前两位数字(-1表示不存在), prev1: 前一位数字(-1表示不存在), tight: 是否受到上界限制, started: 是否已经开始构造有效数字const dfs (pos, prev2, prev1, tight, started) {if (pos n) {return { count: 1, sum: 0 };}const key ${pos},${prev2},${prev1},${tight},${started};if (memo.has(key)) return memo.get(key);const limit tight ? digits[pos] : 9;let totalCount 0;let totalSum 0;for (let d 0; d limit; d) {const nextTight tight (d limit);const nextStarted started || d ! 0;// 仍然是前导零的情况数字还未开始if (!nextStarted) {const res dfs(pos 1, -1, -1, nextTight, false);totalCount res.count;totalSum res.sum;continue;}// 构造当前数字的三元组prev2, prev1, dlet add 0;if (started prev2 ! -1 prev1 ! -1) {// 判断 prev1 是否为峰或谷if ((prev1 prev2 prev1 d) || (prev1 prev2 prev1 d)) {add 1;}}const nextPrev2 prev1;const nextPrev1 d;const res dfs(pos 1, nextPrev2, nextPrev1, nextTight, true);totalCount res.count;// 当前位对总和的贡献如果当前构成波动则后续每一种补全方式都贡献1totalSum res.sum add * res.count;}const result { count: totalCount, sum: totalSum };memo.set(key, result);return result;};// 返回 [0, x] 的总波动值return dfs(0, -1, -1, true, false).sum;};// 前缀和思想区间和 F(num2) - F(num1-1)return countUpTo(num2) - countUpTo(num1 - 1);};核心思路1. 数位 DP 容斥分别计算 [0, num2] 和 [0, num1-1] 的总波动值相减得到区间 [num1, num2] 的结果。2. 状态设计判断一个数字是否为峰/谷需要知道它的前两位数字 prev2 和 prev1因此将它们作为 DFS 的状态参数。此外还需· tight是否紧贴上界用于控制枚举上限。· started是否已经开始构造有效数字用于处理前导零。3. 贡献累加在 DFS 过程中每当我们确定一位数字 d 并发现它与 prev2、prev1 构成峰/谷时不仅累加自身的 1还要累加当前波动值 * 后续所有可能的补全方式数量从而一次性统计所有合法数字的贡献。复杂度· 时间复杂度O(log N * 10^2 * 2 * 2 * 10)即 O(400 * log N)其中 N 是 num2 的值。· 空间复杂度O(log N * 400)用于记忆化缓存。
对于 LeetCode 3753 这道困难题核心解法是数位 DP配合前缀和技巧F(num2) - F(num1-1)。以下是基于该思路的 JavaScript 实现。javascript/*** param {number} num1* param {number} num2* return {number}*/var totalWaviness function(num1, num2) {const countUpTo (x) {if (x 100) return 0; // 少于3位数波动值为0const digits String(x).split().map(Number);const n digits.length;// 记忆化缓存key编码为字符串const memo new Map();// pos: 当前处理位置, prev2: 前两位数字(-1表示不存在), prev1: 前一位数字(-1表示不存在), tight: 是否受到上界限制, started: 是否已经开始构造有效数字const dfs (pos, prev2, prev1, tight, started) {if (pos n) {return { count: 1, sum: 0 };}const key ${pos},${prev2},${prev1},${tight},${started};if (memo.has(key)) return memo.get(key);const limit tight ? digits[pos] : 9;let totalCount 0;let totalSum 0;for (let d 0; d limit; d) {const nextTight tight (d limit);const nextStarted started || d ! 0;// 仍然是前导零的情况数字还未开始if (!nextStarted) {const res dfs(pos 1, -1, -1, nextTight, false);totalCount res.count;totalSum res.sum;continue;}// 构造当前数字的三元组prev2, prev1, dlet add 0;if (started prev2 ! -1 prev1 ! -1) {// 判断 prev1 是否为峰或谷if ((prev1 prev2 prev1 d) || (prev1 prev2 prev1 d)) {add 1;}}const nextPrev2 prev1;const nextPrev1 d;const res dfs(pos 1, nextPrev2, nextPrev1, nextTight, true);totalCount res.count;// 当前位对总和的贡献如果当前构成波动则后续每一种补全方式都贡献1totalSum res.sum add * res.count;}const result { count: totalCount, sum: totalSum };memo.set(key, result);return result;};// 返回 [0, x] 的总波动值return dfs(0, -1, -1, true, false).sum;};// 前缀和思想区间和 F(num2) - F(num1-1)return countUpTo(num2) - countUpTo(num1 - 1);};核心思路1. 数位 DP 容斥分别计算 [0, num2] 和 [0, num1-1] 的总波动值相减得到区间 [num1, num2] 的结果。2. 状态设计判断一个数字是否为峰/谷需要知道它的前两位数字 prev2 和 prev1因此将它们作为 DFS 的状态参数。此外还需· tight是否紧贴上界用于控制枚举上限。· started是否已经开始构造有效数字用于处理前导零。3. 贡献累加在 DFS 过程中每当我们确定一位数字 d 并发现它与 prev2、prev1 构成峰/谷时不仅累加自身的 1还要累加当前波动值 * 后续所有可能的补全方式数量从而一次性统计所有合法数字的贡献。复杂度· 时间复杂度O(log N * 10^2 * 2 * 2 * 10)即 O(400 * log N)其中 N 是 num2 的值。· 空间复杂度O(log N * 400)用于记忆化缓存。
