leetcode
leetcode 1201 ~ 1250
找到一个数字的 K 美丽值

找到一个数字的 K 美丽值

难度:

标签:

题目描述

代码结果

运行时间: 19 ms, 内存: 16.0 MB


/*
 * Problem Statement:
 * Given an integer num and an integer k, return the k-beauty of num.
 * The k-beauty is defined as the number of substrings of num that have a length of k
 * and are divisible by num. Leading zeros are allowed in substrings.
 * However, a substring with value 0 is not considered as divisible.
 */
import java.util.stream.IntStream;
public class Solution {
    public int divisorSubstrings(int num, int k) {
        String numStr = String.valueOf(num);
        return (int) IntStream.range(0, numStr.length() - k + 1)
            .mapToObj(i -> numStr.substring(i, i + k))
            .mapToInt(Integer::parseInt)
            .filter(subNum -> subNum != 0 && num % subNum == 0)
            .count();
    }
}

解释

方法:

该题解采用滑动窗口的方法来查找所有长度为 k 的子字符串,并检查它们是否能整除 num。首先,将 num 转换为字符串 s。使用一个循环构建初始的长度为 k 的子字符串 s1,并检查它是否能整除 num。然后,滑动窗口遍历整个字符串 s,每次右移一位,更新 s1 以表示当前的长度为 k 的子字符串,并判断它是否为 num 的因子。特别地,更新 s1 时采用了数学运算来避免重新计算子字符串对应的整数值,利用先前的值进行快速更新。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在题解中,为什么需要使用pow(10, k)而不是直接乘以10?
在题解中,使用pow(10, k)是为了在滑动窗口中快速移除最左边的数字。由于窗口大小始终是k,所以最左边的数字的权重恰好是10的k次幂。例如,对于三位数123,要移除'1',我们需要从123中减去100,即1乘以10的2次幂。直接乘以10只适用于从一个数字左移一位,而pow(10, k)则是为了正确地在多位数中移除最左位数字。
🦆
题解中提到的'使用数学运算来避免重新计算子字符串对应的整数值'的具体实现是什么?如何从旧的子字符串值快速更新为新的子字符串值?
具体实现方法是,首先将子字符串s1左移一位(即乘以10),然后减去最左边的数字乘以10的k次幂,这样就移除了最左边的数字。接着,将当前新的右边的数字加到s1上。例如,如果子字符串是'123',右移后'234',则首先计算'1230'(123乘以10),然后减去'1000'(1乘以10的3次幂),最后加上'4',得到'234'。这样可以快速更新子字符串的整数值而无需每次都重新计算整个子字符串。
🦆
当子字符串的第一个数字是0时,如何处理这种情况,尤其是在计算s1时?
当子字符串的第一个数字是0时,在进行数学运算(移除最左边的数字)的过程中,它自然而然地被移除,因为0乘以任何数都是0。在新的子字符串中,这个0不会影响到最终的整数值,因为它在数值计算中的贡献是零。例如,如果子字符串是'023',在左移并添加新的数字后,'230'中的'0'不会对计算有任何影响,因为它在数值上的贡献是零。因此,这种情况下无需特殊处理。

相关问题