文章

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

题目链接

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

题目描述

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

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

License:  CC BY 4.0