一【题目类别】

• 滑动窗口

二【题目难度】

• 简单

三【题目编号】

• 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视为字符串）$

七【解题思路】

• 利用滑动窗口的思想
• 此窗口固定大小为题目给定的k，从左到右滑动，如果此窗口内的数字不为0，并且可以整除给定数字，那么就记录到结果中
• 需要注意不要越界，思路不难，如果不用库函数，那么具体实现稍复杂一些，具体可见下面的代码，写的很详细
• 最后返回结果即可

八【时间频度】

• 时间复杂度：$O(n)$，$n$为传入数字的长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

class Solution {
    public int divisorSubstrings(int num, int k) {
        int res = 0;
        int[] temp_num = new int[10];
        int i,count,temp;
        for(i = 0,temp = num;temp > 0;temp /= 10,i++){
            temp_num[i] = temp % 10;
        }
        count = i - k + 1;
        for(i = 0;i < count;i++){
            int sum = 0;
            for(int j = 0;j<k;j++){
                sum *= 10;
                sum += temp_num[i + k - j - 1];
            }
            if(sum != 0 && num % sum == 0){
                res++;
            }
        }
        return res;
    }
}

2. C语言版

int divisorSubstrings(int num, int k)
{
    int res = 0;
    int* temp_num = (int*)malloc(sizeof(int) * 10);
    int i,count,temp;
    for(i = 0,temp = num;temp > 0;temp /= 10,i++)
    {
        temp_num[i] = temp % 10;
    }
    count = i - k + 1;
    for(i = 0;i < count;i++)
    {
        int sum = 0;
        for(int j = 0;j < k;j++)
        {
            sum *= 10;
            sum += temp_num[i + k - j - 1];
        }
        if(sum != 0 && num % sum == 0)
        {
            res++;
        }
    }
    return res;
}

3. Python语言版

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        res = 0
        num = str(num)
        for i in range(0,len(num) - k + 1):
            temp = int(num[i:i+k])
            if temp == 0:
                continue
            if int(num) % temp == 0:
                res += 1
        return res;

4. C++语言版

class Solution {
public:
    int divisorSubstrings(int num, int k) {
        int res = 0;
        int i,count,temp;
        int* temp_count = (int*)malloc(sizeof(int) * 10);
        for(i = 0,temp = num;temp > 0;temp /= 10,i++){
            temp_count[i] = temp % 10;          
        }
        count = i - k + 1;
        for(i = 0;i < count;i++){
            int sum = 0;
            for(int j = 0;j < k;j++){
                sum *= 10;
                sum += temp_count[i + k - j - 1];
            }
            if(sum != 0 && num % sum == 0){
                res++;
            }
        }
        return res;
    }
};

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版