网站建设公司行业描述,衣服网站模板,小程序开发平台哪家产品好,网页制作模板的网站element文章目录 题目思路Java 记忆化搜索的数位 DP 模板 特判第 1 步#xff1a;第 2 步#xff1a;第 3 步#xff1a; 复杂度Code 题目
Problem: 100163. 统计强大整数的数目给你三个整数 start #xff0c;finish 和 limit 。同时给你一个下标从 0 开始的字符串 s #xf… 文章目录 题目思路Java 记忆化搜索的数位 DP 模板 特判第 1 步第 2 步第 3 步 复杂度Code 题目
Problem: 100163. 统计强大整数的数目给你三个整数 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 start finish 10 ^ 151 limit 91 s.length floor(log10(finish)) 1s 数位中每个数字都小于等于 limit 。s 不包含任何前导 0 。
思路
Java 记忆化搜索的数位 DP 模板 特判
第 1 步
根据题意可以想到记忆化搜素的数位 DP 模板
第 2 步
计算 [0, finish] - [0, start-1]将其置为 maxNum将 maxNum 中超过 s 的前面位 sChar 取出来其可以直接套用记忆化搜索的数位 DP 模板注意套用模板时每一位的上限为 limit它可能小于 sChar[curIndex]如果这样后面也是随便
第 3 步
最后结果加上 0s 的可能性判断是否 DP 中是否取了不能取的 sChars是则减去
复杂度
时间复杂度: 时间复杂度 O ( l i m i t ∗ l o g 10 ( f i n i s h ) ) O(limit * log10(finish)) O(limit∗log10(finish)) 空间复杂度: 空间复杂度 O ( l o g 10 ( f i n i s h ) ) O(log10(finish)) O(log10(finish)) Code
class Solution {/*** Java 记忆化搜索的数位 DP 模板 特判* 第 1 步* 根据题意可以想到记忆化搜素的数位 DP 模板* ** 第 2 步* 计算 [0, finish] - [0, start-1]将其置为 maxNum* 将 maxNum 中超过 s 的前面位 sChar 取出来其可以直接套用记忆化搜素的数位 DP 模板* 注意套用模板时每一位的上限为 limit它可能小于 sChar[curIndex]如果这样后面也是随便* * 第 3 步* 最后结果加上 0s 的可能性* 判断是否 DP 中是否取了不能取的 sChars是则减去* 时间复杂度Olimit * log10(finish)空间复杂度Olog10(finish)*/public long numberOfPowerfulInt(long start, long finish, int limit, String s) {// 转化为 [0, finish] - [0, start-1]return doNumberOfPowerfulInt(finish, limit, Long.parseLong(s), s)- doNumberOfPowerfulInt(start - 1, limit, Long.parseLong(s), s);}/*** 求出 [0, maxNum] 的结果*/private long doNumberOfPowerfulInt(long maxNum, int limit, long sLong, String s) {if (sLong maxNum) {return 0;}// 将 maxNum 中超过 s 的前面位 sChar 取出来其可以直接套用记忆化搜素的数位 DP 模板sChar (maxNum ).substring(0, (maxNum ).length() - s.length()).toCharArray();int m sChar.length;// 记忆化搜索超过 s 的前面位memo new long[m];// 初始化-1 表示没有计算过Arrays.fill(memo, -1);// 记忆化搜素的数位 DP 模板注意 0s 可能可以long res recursionDigitDP(0, limit, true, false) 1;// s 大于 maxNum 对应的位置sChar 均不大于 limit此时 DP 中取了不能取的 sCharsif (checkNotEquals(maxNum, limit, sLong, s)) {res--;}System.out.println(res: res);return res;}private boolean checkNotEquals(long maxNum, int limit, long sLong, String s) {String maxNumStr maxNum ;long sLenMaxNum Long.parseLong(maxNumStr.substring(maxNumStr.length() - s.length()));// s 大于 maxNum 对应的位置if (sLong sLenMaxNum) {for (int i 0; i maxNumStr.length() - s.length(); i) {if (maxNumStr.charAt(i) - 0 limit) {return false;}}// sChar 均不大于 limitreturn true;}return false;}private char sChar[];private long memo[];/*** 数位 DP 模板记忆化搜索获取合法数字的个数* param curIndex 从 i 位开始填数字* param isLimit 前面填写的数字是否与 sChar 对应上如果为 true 当前最大为 int(sChar[i])否则当前最大为 limit* param isNum 前面是否填写过数字即处理前导零用如果为 true 当前可以从 0 开始否则可以 跳过 或 从 1 开始* return 返回合法数字的个数*/private long recursionDigitDP(int curIndex, int limit, boolean isLimit, boolean isNum) {/*** 仅有此位置最终定义是否合法* isNum 为 true 表示得到了一个合法数字*/if (curIndex sChar.length) {return isNum ? 1 : 0;}// isLimit 为 true前面与 sChar 一样以及 isNum 为 false前面全没有填仅有一种情况不需要记忆化if (!isLimit isNum memo[curIndex] ! -1) {return memo[curIndex];}long res 0;// isNum前面是否填写过数字即处理前导零用可以跳过当前数位if (!isNum) {res recursionDigitDP(curIndex 1, limit, false, false);}/*** 判断最大值* isLimit前面填写的数字是否与 sChar 对应上如果为 true 当前最大为 int(sChar[i])否则当前最大为 limit否则就超过 n 啦*/int up isLimit ? Math.min(sChar[curIndex] - 0, limit) : limit;// 枚举要填入的数字 disNum如果为 true 当前可以从 0 开始否则可以 跳过 或 从 1 开始for (int d isNum ? 0 : 1; d up; d) {// 由于最大值可能小于 sChar[curIndex]如果这样后面也是随便选因此返回 falseres recursionDigitDP(curIndex 1, limit, isLimit d up up sChar[curIndex] - 0, true);}// 记忆化入数组if (!isLimit isNum) {memo[curIndex] res;}return res;}
}
