Easy

题目描述

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

  • 长度为 k
  • 是 num 的因数

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

注意：

  • 允许有前导零
  • 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 视为字符串）

解题思路

解题思路

这是一道典型的滑动窗口问题，需要我们枚举数字字符串中所有长度为 k 的子字符串，并检查它们是否为原数字的因数。

算法步骤：

  1. 字符串转换：将数字 num 转换为字符串，便于提取子字符串
  2. 滑动窗口遍历：使用长度为 k 的滑动窗口遍历字符串，获取所有可能的子字符串
  3. 因数判断：对于每个子字符串：
    • 将其转换为整数
    • 检查是否为 0（0 不是任何数的因数）
    • 检查是否能整除原数字 num
  4. 计数统计：统计满足条件的子字符串个数

关键点：

  • 需要注意 0 不是任何数的因数这个特殊情况
  • 子字符串可能有前导零，如 “04” 转换为整数 4
  • 使用滑动窗口可以高效地枚举所有长度为 k 的子字符串

时间复杂度主要取决于字符串长度，空间复杂度为常数级别。

代码实现

class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string s = to_string(num);
        int count = 0;
        
        for (int i = 0; i <= (int)s.length() - k; i++) {
            string substr = s.substr(i, k);
            int subnum = stoi(substr);
            
            if (subnum != 0 && num % subnum == 0) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        s = str(num)
        count = 0
        
        for i in range(len(s) - k + 1):
            substr = s[i:i+k]
            subnum = int(substr)
            
            if subnum != 0 and num % subnum == 0:
                count += 1
        
        return count

public class Solution {
    public int DivisorSubstrings(int num, int k) {
        string s = num.ToString();
        int count = 0;
        
        for (int i = 0; i <= s.Length - k; i++) {
            string substr = s.Substring(i, k);
            int subnum = int.Parse(substr);
            
            if (subnum != 0 && num % subnum == 0) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {number} num
 * @param {number} k
 * @return {number}
 */
var divisorSubstrings = function(num, k) {
    const str = num.toString();
    let count = 0;
    
    for (let i = 0; i <= str.length - k; i++) {
        const substring = str.slice(i, i + k);
        const subNum = parseInt(substring);
        
        if (subNum !== 0 && num % subNum === 0) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n-k+1) = O(n)，其中 n 是数字的位数，需要遍历所有长度为 k 的子字符串
空间复杂度O(n)，需要存储数字的字符串表示