[LeetCode] 每日一题 2269. 找到一个数字的 K 美丽值

题目链接

https://leetcode.cn/problems/find-the-k-beauty-of-a-number

题目描述

一个整数 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 的子字符串。相比转换为字符串再进行滑动窗口处理，这种方法更直观，且减少了不必要的空间开销。整体来说，这道题比前几天的题目简单很多

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。