[LeetCode] 每日一题 2269. 找到一个数字的 K 美丽值
题目链接
题目描述
一个整数 num
的 k 美丽值定义为 num
中符合以下条件的 子字符串 数目:
子字符串长度为
k
。子字符串能整除
num
。
给你整数 num
和 k
,请你返回 num
的 k 美丽值。
注意:
允许有 前缀 0 。
0
不能整除任何值。
一个 子字符串 是一个字符串里的连续一段字符序列。
示例输入
示例 1
输入:num = 240, k = 2
输出:2
解释:以下是 num 里长度为 k 的子字符串:
- "240" 中的 "24" :24 能整除 240 。
- "240" 中的 "40" :40 能整除 240 。
所以,k 美丽值为 2 。
示例 2
输入:num = 430043, k = 2
输出:2
解释:以下是 num 里长度为 k 的子字符串:
- "430043" 中的 "43" :43 能整除 430043 。
- "430043" 中的 "30" :30 不能整除 430043 。
- "430043" 中的 "00" :0 不能整除 430043 。
- "430043" 中的 "04" :4 不能整除 430043 。
- "430043" 中的 "43" :43 能整除 430043 。
所以,k 美丽值为 2 。
提示
1 <= num <= 10^9
1 <= k <= num.length
(将num
视为字符串)
解题思路
相比前几天的题目,今天这道题的难度要低很多。题目要求找到整数 num
中长度为 k
的所有子字符串,并统计其中能整除 num
的个数。由于子字符串是 连续的序列,且长度固定,因此可以采用 滑动窗口 的思想来遍历所有可能的子字符串。
不过,在这题中,num
是一个整数,而不是字符串,因此可以 直接使用取余和除法 来提取长度为 k
的子字符串,而不需要额外的字符串转换或复杂计算。我们通过 num % 10^k
取出最低 k
位数字,并在每次迭代时通过 / 10
去掉最低位,直到遍历完整个数字。
代码实现
class Solution {
public int divisorSubstrings(int num, int k) {
int m = (int)Math.pow(10, k);
int current = num;
int ans = 0;
while (current >= m / 10) {
int temp = current % m;
if (temp != 0 && num % temp == 0) {
ans++;
}
current /= 10;
}
return ans;
}
}
复杂度分析
时间复杂度:
O(log num)
,其中log num
代表num
的位数,我们每次将num
除以 10 进行遍历,总共执行log num
次操作空间复杂度:
O(1)
,只使用了常数个变量,没有额外的存储需求
总结
本题的关键点在于利用 数学运算代替字符串操作,通过 取余数 + 除法 来高效地获取长度为 k
的子字符串。相比转换为字符串再进行滑动窗口处理,这种方法更直观,且减少了不必要的空间开销。整体来说,这道题比前几天的题目简单很多
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。