leetcode逐日一题：统计强盛整数的数量

标题

2999. 统计强盛整数的数量
给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。
如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强盛的 。
请你返回区间 [start..finish] 内强盛整数的 总数量 。
如果一个字符串 x 是 y 中某个下标开始（包罗 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。

示例 1：

1. 输入：start = 1, finish = 6000, limit = 4, s = "124"
2. 输出：5
3. 解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。
4. 这个区间内总共只有这 5 个强大整数。

复制代码

示例 2：

1. 输入：start = 15, finish = 215, limit = 6, s = "10"
2. 输出：2
3. 解释：区间 [15..215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。
4. 这个区间总共只有这 2 个强大整数。

复制代码

示例 3：

1. 输入：start = 1000, finish = 2000, limit = 4, s = "3000"
2. 输出：0
3. 解释：区间 [1000..2000] 内的整数都小于 3000 ，所以 "3000" 不可能是这个区间内任何整数的后缀。

复制代码

提示：

• 1 <= start <= finish <= 1015
  
• 1 <= limit <= 9
  
• 1 <= s.length <= floor(log10(finish)) + 1
  
• s 数位中每个数字都小于即是 limit 。
  
• s 不包含任何前导 0 。
  

思路

        标题要求在[start, finish]范围内符合条件的数字的数量，对于这类区间的问题，一开始想到的思路就是前缀和。如果我们有1个函数f(x)表示在[0, x]范围内符合条件的数字的数量，那么标题所求就是f(finish) - f(start-1)。
        如许，我们就把标题转换成了如何求出f(x)。由于s是符合条件数字的后缀，我们分别记lenX为x的长度，lenS为s的长度，先分成3种基本情况：

• lenX < lenS，那么范围内任何数字都小于后缀，f(x) = 0
  
• lenX = lenS，那么范围内最多只有1个数字符合条件，就看是否满足 s < x
  
• lenX > lenS，那么可能有多个数字符合条件，我们接下来重点讨论这种情况
  

        finish除去后缀s的位数后，我们记前缀有preLen位。按照次序从前往后遍历，遍历到第i位时，我们记当前位的数字是current，这时会有2种情况：

• current > limit，当前位和背面所有位（仅包含前缀的范围），每1位都可以取[0, limit]，不必再向后遍历
  
• current <= limit，当前位的取值又可以分成2种：
  

        当前位取[0, current-1]时，背面所有位（仅包含前缀的范围）可以取[0, limit]
        当前位取current时，背面的位数在下一次循环中决策怎么取
代码

1. public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
2.    return cnt(finish, limit, s) - cnt(start - 1, limit, s);
3. }
4. ​
5. /**
6. * 获取在[0,finish]区间内有多少个数符合
7. */
8. private long cnt(long finish, int limit, String s) {
9.    String finishStr = String.valueOf(finish);
10.    // 数字长度小于后缀，那么范围内所有的数字都无法满足
11.    if (finishStr.length() < s.length()) {
12.        return 0L;
13.    }
14.    // 如果长度相同，只需判断finish是否大于后缀s
15.    if (finishStr.length() == s.length()) {
16.        return finishStr.compareTo(s) >= 0 ? 1L : 0L;
17.    }
18.    long ans = 0;
19.    int preLen = finishStr.length() - s.length();
20.    for (int i = 0; i < preLen; i++) {
21.        int current = finishStr.charAt(i) - '0';
22.        // 当前位和后面所有位（仅包含前缀的范围），每1位都可以取[0, limit]
23.        if (current > limit) {
24.            ans += (long) Math.pow(limit + 1, preLen - i);
25.            return ans;
26.        } else {
27.            // 否则，当前位取[0, current-1]时，后面所有位（仅包含前缀的范围）可以取[0, limit]
28.            ans += (long) (current * Math.pow(limit + 1, preLen - 1 - i));
29.            // 当前位取current时，后面的位数在下一次循环中决策怎么取
30.        }
31.    }
32.    String suffix = finishStr.substring(preLen);
33.    if (suffix.compareTo(s) >= 0) {
34.        ans += 1;
35.    }
36.    return ans;
37. }

复制代码

耗时

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。