力扣每日打卡 1922. 统计好数字的数目 (中等)

---

前言

这是刷算法题的第十一天，用到的语言是JS
题目：力扣 1922. 统计好数字的数目 (中等)

---

一、题目内容

我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。

比方说，“2582” 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 “3245” 不是 好数字，因为 3 在偶数下标处但不是偶数。

给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。

一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

示例 1：
输入：n = 1
输出：5
解释：长度为 1 的好数字包括 “0”，“2”，“4”，“6”，“8” 。

示例 2：
输入：n = 4
输出：400

示例 3：
输入：n = 50
输出：564908303

提示：
1 <= n <= 10¹⁵

二、解题方法

1. 暴力解法（会超时，此法不通）

1. 遍历所有长度为n的数字字符串，判断是否为好数字
2. 好数字的偶数下标处的数字为偶数且奇数下标处的数字为质数
3. 时间复杂度为O(n)，空间复杂度为O(1)
4. 由于n的范围较大，暴力解法会超时，所以需要优化

代码如下（实例）：

*** @param {number} n* @return {number}*/
var countGoodNumbers = function (n) {// 暴力解法let count = 0for(let i = 0; i.toString().length <= n; i++) {if (i.toString().length === n) {const si = i.toString() // 将数字转换为字符串if (si.length > n) returnfor (let j = 0; j < si.length; j++) {let access = false  // 如果每一位数字都通过，则数量+1if (j % 2 === 0 && si[j] % 2 === 0) access = trueelse breakif( j > 10 ) {if (j % 2 && (si[j] % 2 === 2 || si[j] % 2 === 3 || si[j] % 2 === 5 || si[j] % 2 === 7)) access = trueelse break}if (access) count++}}}return count % (10 ** 9 + 7)
}// console.log(countGoodNumbers(1)) // 5 正确，也会打印，但也仅此而已
// console.log(countGoodNumbers(8)) // 40000000 正确，也会打印，但也仅此而已
// console.log(countGoodNumbers(9)) // 400000000正确，但是不会打印，可能直接超时了，或者打印时间非常慢

2. 快速幂运算

涉及到JS的 大数运算（关于大数运算的补充在下面有）

代码如下（示例）：（使用了JS的 大数运算 ）

/*** @param {number} n* @return {number}*/
var countGoodNumbers = function (n) {// 此题无法使用暴力算法const MOD = BigInt(10 ** 9 + 7)// ai得到的逻辑思维：// 一个长度为n的字符串，偶数位置可以有02468五种选择，奇数位置可以有2357四种选择// 因此对其进行排列组合，可以得到好数字的个数一共是 (符合偶数位置的数字的个数 * 符合奇数位置的数字的个数)// 即 (5^evenFuhe) * (4^oddFuhe)const evenCount = BigInt(Math.ceil(n / 2)) // 偶数下标的数量const oddCount = BigInt(Math.floor(n / 2)) // 奇数下标的数量const count = (Fuhe(5n, evenCount, MOD) * Fuhe(4n, oddCount, MOD)) % MODreturn Number(count)
}// 快速幂运算的函数实现
const Fuhe = ( a, b, mod ) => {let ans = 1na = a % modwhile(b) {if( b & 1n) ans = (a * ans) % moda = (a * a) % modb >>= 1n}return ans
}

---

代码：（下面的代码没有使用JS的 大数运算，会出现精准度问题）

/*** @param {number} n* @return {number}*/
var countGoodNumbers2 = function (n) {// 此题无法使用暴力算法const MOD = 10 ** 9 + 7// ai得到的逻辑思维：// 一个长度为n的字符串，偶数位置可以有02468五种选择，奇数位置可以有2357四种选择// 因此对其进行排列组合，可以得到好数字的个数一共是 (符合偶数位置的数字的个数 * 符合奇数位置的数字的个数)// 即 (5^evenFuhe) * (4^oddFuhe)const evenCount = Math.ceil(n / 2) // 偶数下标的数量const oddCount = Math.floor(n / 2) // 奇数下标的数量const count = (Fuhe(5, evenCount, MOD) * Fuhe(4, oddCount, MOD)) % MODreturn count
}
const Fuhe = ( a, b, mod ) => {let ans = 1a = a % modwhile(b) {if( b & 1) ans = (a * ans) % moda = (a * a) % modb >>= 1// b = Math.floor(b / 2) }return ans
}
console.log(countGoodNumbers2(50)) // 应该是564908303，而非564908313，但是打印的是564908313

3. 组合计数的思维

理解这个问题的数学思维需要我们从组合计数的角度出发，分析如何在特定的约束下选择数字字符串。以下是分析的详解：

逻辑分析

1. 字符串结构:

   • 我们需要生成的字符串长度为 ( n )。
   • 字符串的下标为 ( 0 ) 到 ( n-1 )。

2. 下标分类：

   • 偶数下标（如 0, 2, 4, …）和奇数下标（如 1, 3, 5, …）之间有不同的限制条件。
   • 偶数下标位置的数字必须是偶数。
   • 奇数下标位置的数字必须是质数。

3. 可能的选项：

   • 偶数的选择: 偶数下标的位置可以选择的数字有 0, 2, 4, 6, 8，共 5 种选择。
   • 质数的选择: 奇数下标的位置可以选择的质数有 2, 3, 5, 7，共 4 种选择。

组合计数的推导

1. 偶数下标的数量:

   • 在一个长度为 ( n ) 的字符串中，偶数下标的数量可以通过 evenCount = ⌈n / 2⌉计算得出。
     • 这表示当 ( n ) 为奇数时，偶数下标数量会比奇数下标数量多 1。

2. 奇数下标的数量:

   • 奇数下标的数量可以通过 oddCount = ⌊ n / 2 ⌋计算得出。
     • 这表示当 ( n ) 为偶数时，偶数下标和奇数下标数量相等。

3. 总组合数的计算:

   • 对于每一个偶数下标，我们有 5 种选择（偶数）。
   • 对于每一个奇数下标，我们有 4 种选择（质数）。
   • 最终的好数字字符串数量可以通过将偶数下标的选择和奇数下标的选择相乘得到：
     goodNumbers = 5^evenCount × 4^oddCount

例子分析

假设 ( n = 4 )：

• 字符串有长度 4，下标为 0, 1, 2, 3。
• 偶数下标（0 和 2）: 2 个位置，每个位置可以选择【0, 2, 4, 6, 8】中的任意一个，即 5 种选择。
• 奇数下标（1 和 3）: 2 个位置，每个位置可以选择【2, 3, 5, 7】中的任意一个，即 4 种选择。

因此，字符串的组合数是：
goodNumbers = 5² × 4² = 25 × 16 = 400

思维小结论

通过这样的数学推理，我们能够清楚地理解在给定的条件下，为什么能够将问题转换为计算选项的排列组合。在面对其他类似的问题时，这种分解和组合的思维方式可以帮助我们有效解决复杂问题。

---

4.官方题解

4.1 方法一：快速幂

思路与算法：
对于偶数下标处的数字，它可以为 0,2,4,6,8 共计 5 种，而长度为 n 的数字字符串有 ⌊ n+1 / 2 ⌋ 个偶数下标，其中 ⌊x⌋ 表示对 x 向下取整。

对于奇数下标处的数字，它可以为 2,3,5,7 共计 4 种，而长度为 n 的数字字符串有 ⌊ n / 2 ⌋ 个奇数下标。

因此长度为 n 的数字字符串中，好数字的总数即为：
5^⌊ n+1 / 2 ⌋^ ⋅ 4^⌊ n / 2 ⌋^
在本题中，由于 n 的取值最大可以到 10¹⁵，如果通过普通的乘法运算直接求出上式中的幂，会超出时间限制，因此我们需要使用快速幂算法对幂的求值进行优化。

快速幂算法可以参考「50. Pow(x, n)」的官方题解。

代码如下（示例）：

var countGoodNumbers = function(n) {const mod = 1000000007n;// 快速幂求出 x^y % modfunction quickmul(x, y) {let ret = 1n;let mul = x;while (y > 0) {if (y % 2n === 1n) {ret = (ret * mul) % mod;}mul = (mul * mul) % mod;y = y / 2n;}return ret;}return Number(quickmul(5n, BigInt(n + 1) / 2n) * quickmul(4n, BigInt(n) / 2n) % mod);
};作者：力扣官方题解
链接：https://leetcode.cn/problems/count-good-numbers/solutions/857968/tong-ji-hao-shu-zi-de-shu-mu-by-leetcode-53jj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析：

时间复杂度：O(log n)。

空间复杂度：O(1)。

链接：力扣本题官方题解
来源：力扣（LeetCode）

三、快速幂运算

快速幂运算（Exponentiation by Squaring）

快速幂运算是一种高效计算 ( b^e ) 的算法，其中 ( b ) 是基数，( e ) 是指数。传统的逐步乘法方法的时间复杂度为 ( O(e) )，而快速幂运算的时间复杂度为 ( O(\log e) )，因此在处理大数时特别有效。

基本思想

快速幂运算的基本思想是利用平方和乘法来减少乘法的次数。其主要依据是：

• 如果指数 ( e ) 为偶数，则 ( b^e = (b^{e/2})2 )
• 如果指数 ( e ) 为奇数，则 ( b^e = b \times b^{e-1} )

通过这种方式，可以在每次迭代中将指数减半，从而显著降低计算时间。

算法实现（②③为非递归）

以下是使用 JavaScript 实现的快速幂运算的代码：

① 递归运算

/**  不带模数* 快速幂运算* @param {number} base - 基数* @param {number} exp - 指数* @returns {number} */
function quickPow(base, exp) {if (exp === 0) {return 1; // 任何数的零次方为 1}if (exp % 2 === 0) {const half = quickPow(base, exp / 2);return half * half;} else {return base * quickPow(base, exp - 1);}
}

② 普通 除模运算（不带 模数 与 带 模数）

/** 不带模数* 快速幂运算* @param {number} a- 基数* @param {number} b- 指数* @returns {number} 计算结果 (a ^ b)*/
function quick (a, b) {let ans = 1while(b) { // 当指数存在的时候// 如果指数是奇数，则要先拉出来一个底数乘到最终结果上，其余步骤和偶数一样操作// 如果指数是偶数，则要底数平方，指数除以2（如果是使用按位与运算，则使用 "b >>= 1"）b/2if(b % 2 === 1) ans *= aa *= ab = Math.floor(b / 2) // 注意一定要使用Math.floor()，否则会出现小数点，导致结束循环}return ans
}
console.log(quick(2, 7)) // 128/**  带模数* 快速幂运算* @param {number} base - 基数* @param {number} exp - 指数* @param {number} mod - 模数* @returns {number} 计算结果 (base^exp) % mod*/
const modExp = (base, exp, mod) => {let result = 1; // 初始化结果为 1base = base % mod; // 将基数在模数下取值while (exp > 0) {// 如果 exp 为奇数，将当前的 base 乘入结果if (exp % 2 === 1)  result = (result * base) % mod;// 将 base 平方base = (base * base) % mod;// exp 右移，相当于整除 2exp = Math.floor(exp / 2);}return result; // 返回最终结果
}

③ 按位与运算

/** 不带模数* 快速幂运算* @param {number} a- 基数* @param {number} b- 指数* @returns {number} 计算结果 (a ^ b)*
function quick2 (a, b) {let ans = 1while(b) { // 当指数存在的时候// 如果指数是奇数，则要先拉出来一个底数乘到最终结果上，其余步骤和偶数一样操作// 如果指数是偶数，则要底数平方，指数除以2（如果是使用按位与运算，则使用 "b >>= 1"）b/2if(b & 1) ans *= aa *= ab >>= 1 // b右移一位}return ans
}
console.log(quick2(2, 8)) // 256

使用示例

快速幂运算可以用于很多应用场景，包括计算大数的幂、加密算法、以及任何需要快速计算大数时。

示例代码

const MOD = 10 ** 9 + 7; // 定义模数console.log(modExp(2, 10, MOD)); // 输出: 1024
console.log(modExp(5, 3, MOD));  // 输出: 125
console.log(modExp(3, 7, MOD));  // 输出: 2187
console.log(modExp(10, 9, MOD)); // 输出: 1000000000

复杂度分析

• 时间复杂度: ( O(log e) ) — 每次操作将指数减半。
• 空间复杂度: ( O(1) ) — 仅使用常量级额外空间。

小结论

快速幂运算是一个非常实用且高效的算法，广泛应用于计算大数的幂以及各种算法中。了解并实现该算法可以显著提高程序运行效率，特别是在处理与模数运算相关的问题时。

---

四、JS的大数运算

JavaScript 在处理数字时，其默认的数值类型是基于 IEEE 754 标准的双精度浮点数。这个数值类型有一些限制，特别是在进行大数运算时。以下是 JavaScript 中大数运算的简单介绍：

1. 数字精度限制

• 安全整数: JavaScript 支持的安全整数范围是 (-2^{53} + 1) 到 (2^{53} - 1)（即 Number.MAX_SAFE_INTEGER 的值为 9007199254740991）。超出这个范围的整数计算可能会出现精度丢失（例如， 9007199254740992 会变成 9007199254740992）。

• 浮点数问题: 由于浮点数的表示方式，某些小数（如 0.1 和 0.2 的和）可能无法精确表示。

2. 大数解决方案

由于上述限制，处理大数运算时，可以考虑以下几种方案：

2.1. 使用 BigInt

从 ES2020 开始，JavaScript 引入了 BigInt 类型，用于表示任意大小的整数。你可以通过在数字后添加 “n” 来创建 BigInt：

const bigInt1 = BigInt(9007199254740992)
const bigInt2 = 12345678901234567890n // 后缀 "n" 表示 BigInt
const sum = bigInt1 + bigInt2         // 可以进行大数运算
console.log(sum)                       // 输出: 12345678901234567892nconsole.log(Number(sum))  // 输出: 12345678901234567892

2.2. 使用第三方库

如果你需要支持比 BigInt 更广泛的数值（比如更复杂的数学操作、浮点数等），可以使用大数运算库，例如：

• Decimal.js: 支持任意精度的十进制运算，适合处理小数。
• Big.js: 提供了对大浮点数的高精度运算支持。
• bignumber.js: 可以处理比较大的数值以及高精度的浮点数运算。

使用示例（以 decimal.js 为例）：

const Decimal = require('decimal.js');const a = new Decimal(0.1);
const b = new Decimal(0.2);
const sum = a.plus(b); // 精确计算
console.log(sum.toString()); // 输出: "0.3"

2.3. 总结

在 JavaScript 中，大数运算可以通过 BigInt 来实现任意大小的整数计算，或使用第三方库来处理更复杂的场景（如浮点数和高精度计算）。在处理大数运算时，需要注意原生数值类型的限制，以确保计算的准确性。

2.4 补充：本题使用大数运算的例子

代码如下：

/*** @param {number} n* @return {number}*/
var countGoodNumbers = function (n) {// 此题无法使用暴力算法const MOD = BigInt(10 ** 9 + 7)// ai得到的逻辑思维：// 一个长度为n的字符串，偶数位置可以有02468五种选择，奇数位置可以有2357四种选择// 因此对其进行排列组合，可以得到好数字的个数一共是 (符合偶数位置的数字的个数 * 符合奇数位置的数字的个数)// 即 (5^evenFuhe) * (4^oddFuhe)const evenCount = BigInt(Math.ceil(n / 2)) // 偶数下标的数量const oddCount = BigInt(Math.floor(n / 2)) // 奇数下标的数量const count = (Fuhe(5n, evenCount, MOD) * Fuhe(4n, oddCount, MOD)) % MODreturn Number(count)
}// 快速幂运算的函数实现
const Fuhe = ( a, b, mod ) => {let ans = 1na = a % modwhile(b) {if( b & 1n) ans = (a * ans) % moda = (a * a) % modb >>= 1n}return ans
}