2269. 找到一个数字的 K 美丽值

🟢   🔖  数学 字符串 滑动窗口  🔗 力扣 LeetCode

题目

The k-beauty of an integer num is defined as the number of substrings of num when it is read as a string that meet the following conditions:

• It has a length of k.
• It is a divisor of num.

Given integers num and k, return the k-beauty ofnum.

Note:

• Leading zeros are allowed.
• 0 is not a divisor of any value.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: num = 240, k = 2

Output: 2

Explanation: The following are the substrings of num of length k:

• "24" from "24 0": 24 is a divisor of 240.
• "40" from "2 40 ": 40 is a divisor of 240.

Therefore, the k-beauty is 2.

Example 2:

Input: num = 430043, k = 2

Output: 2

Explanation: The following are the substrings of num of length k:

• "43" from "43 0043": 43 is a divisor of 430043.
• "30" from "4 30 043": 30 is not a divisor of 430043.
• "00" from "43 00 43": 0 is not a divisor of 430043.
• "04" from "430 04 3": 4 is not a divisor of 430043.
• "43" from "4300 43 ": 43 is a divisor of 430043.

Therefore, the k-beauty is 2.

Constraints:

• 1 <= num <= 10^9
• 1 <= k <= num.length (taking num as a string)

题目大意

一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：

• 子字符串长度为 k 。
• 子字符串能整除 num 。

给你整数 num 和 k ，请你返回 num 的 k 美丽值。

注意：

• 允许有 前缀 0 。
• 0 不能整除任何值。

一个 子字符串 是一个字符串里的连续一段字符序列。

示例 1：

输入： num = 240, k = 2

输出： 2

解释： 以下是 num 里长度为 k 的子字符串：

• "24 0" 中的 "24" ：24 能整除 240 。
• "2 40 " 中的 "40" ：40 能整除 240 。

所以，k 美丽值为 2 。

示例 2：

输入： num = 430043, k = 2

输出： 2

解释： 以下是 num 里长度为 k 的子字符串：

• "43 0043" 中的 "43" ：43 能整除 430043 。
• "4 30 043" 中的 "30" ：30 不能整除 430043 。
• "43 00 43" 中的 "00" ：0 不能整除 430043 。
• "430 04 3" 中的 "04" ：4 不能整除 430043 。
• "4300 43 " 中的 "43" ：43 能整除 430043 。

所以，k 美丽值为 2 。

提示：

• 1 <= num <= 10^9
• 1 <= k <= num.length （将 num 视为字符串）

解题思路

1. 从整数中提取子字符串：

   • 将 num 逐位处理，构造长度为 k 的子整数。
   • 当子整数达到 k 位时，检查其是否能整除 num。

2. 滑动窗口技术：

   • 使用一个变量 cur 保存当前窗口的值。
   • 利用模运算和除法动态更新窗口值：
     • 添加低位的数字（通过模运算和乘法）。
     • 移除高位的数字（通过除法）。

3. 跳过特殊情况：

   • 如果当前子整数为 0，直接跳过（避免除以 0）。

复杂度分析

• 时间复杂度：O(d)，其中 d 是 num 的位数，遍历 num 的所有数字。
• 空间复杂度：O(1)，使用常量空间。

代码

/**
 * @param {number} num
 * @param {number} k
 * @return {number}
 */
var divisorSubstrings = function (num, k) {
	let res = 0; // 结果计数
	let cur = 0; // 当前窗口值
	let pow = 1; // 用于维护 k 位整数的权重（10 的次方）

	for (let n = num; n > 0; n = Math.floor(n / 10)) {
		// 添加低位数字
		cur += (n % 10) * pow;

		if (k-- > 1) {
			pow *= 10; // 增加权重
		} else {
			// 检查当前窗口是否符合条件
			if (cur !== 0 && num % cur === 0) {
				res++;
			}
			cur = Math.floor(cur / 10); // 移除高位数字
		}
	}
	return res;
};