深圳做网站d,网页表格设计模板,一个人怎么开发自己的app,百度网站下拉排名本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.
Example 1:
Input: n 20
Output: 1
Explanation: The only positive number ( 20) with at least 1 repeated digit is 11.Example 2:
Input: n 100
Output: 10
Explanation: The positive numbers ( 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.Example 3:
Input: n 1000
Output: 262Constraints:
1 n 10^9
题意给定正整数 n返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。 解法 状压记忆化搜索数位DP
相似题目基本可用通用数位DP模板来解决但233和17.06可直接用计数原理解决更简单
233. 数字 1 的个数题解[[LeetCode 233. Number of Digit One【计数模拟】困难]]面试题 17.06. 2出现的次数题解[[LeetCode 面试题 17.06. 2出现的次数【数位DP计数原理】困难]]600. 不含连续1的非负整数902. 最大为 N 的数字组合1067. 范围内的数字计数1397. 找到所有好字符串有难度需要结合一个经典字符串算法更多题目见大佬[灵茶山艾府]模板库中的 dp.go。
用二进制表示集合二进制从低到高第 iii 位为 111 、表示 iii 在集合中为 000 表示 iii 不在集合中。 。设集合对应的二进制数为 xxx 两个位运算操作如下
判断元素 ddd 是否在集合中x d 1 可以取出 xxx 的第 ddd 个比特位如果是 111 就说明 ddd 在集合中。把元素 ddd 添加到集合中将 x 更新为 x | (1 d) 。
求至少有一个重复数位的数字个数有点难不如正难则反转换成求无重复数位数字的个数。答案等于 nnn 减去无重复数字的个数。将 nnn 转换成字符串 sss 定义 f(i,mask,isNum,isLimit)f(i,\textit{mask}, \textit{isNum},\textit{isLimit})f(i,mask,isNum,isLimit) 表示构造第 iii 位及其之后数位的合法方案数参数的含义为
iii 表示从第 iii 位开始填数字数位DP通用模板必备参数mask\textit{mask}mask 表示前面选过的数字集合换句话说第 iii 位要选的数字不能在 mask\textit{mask}mask 中这是为选出无重复数字做准备。isNum\textit{isNum}isNum 表示 iii 前面的数位是否填了数字。若为假表示前面没填数字则当前位可以不填数字或者要填入的数字至少为 111 若为真表示前面填了数字则必须要填入从 000 开始的数字。例如 n123n123n123 在 i0i0i0 时跳过不填相当于后面要构造的是一个 999999 以内的数字了如果 i1i1i1 不跳过那么相当于构造一个 101010 到 999999 的两位数如果 i1i1i1 跳过相当于构造的是一个 999 以内的数字。其实是统一的isNumisNumisNum 为假时当前位可填 000不填数字或 111 及以上填数字为真时必须填从 000 开始的数字。isNumisNumisNum 的真实用处在于递归结束时判断填成的数是否不为0全跳过或者说全填 000 就是 000 不能算有重复数位。isLimit\textit{isLimit}isLimit 表示当前是否受到了 nnn 的约束即要构造的数字不能超过 nnn**。若为真则第 iii 位填入的数字至多为 s[i]s[i]s[i] 否则可以是 999** 。数位DP通用模板必备参数如果在受到约束的情况下填了 s[i]s[i]s[i] 那么后续填入的数字仍会受到 nnn 的约束。例如 n123n123n123 那么 i0i0i0 填的是 111 的话i1i1i1 的这一位至多填 222 。
实现细节如下
递归入口 f(0, 0, true, false) 表示 从 s[0]s[0]s[0] 开始枚举一开始集合中没有数字一开始要受到 nnn 的约束否则就可以随意填了这肯定不行一开始没有填数字。 递归中 如果 isNum\textit{isNum}isNum 为假说明前面没有填数字那么当前也可以不填数字一旦从这里递归下去isLimit\textit{isLimit}isLimit 就可以置为 false 了因为前面的高位不填数字后面无论怎么填都比 nnn 小。如果 isNum\textit{isNum}isNum 为真那么当前必须填一个数字。枚举填入的数字要根据 isNum\textit{isNum}isNum 和 isLimit\textit{isLimit}isLimit 来决定填入数字的范围。填了数字后从这里递归下去isNumisNumisNum 置为真且看情况决定 isLimitisLimitisLimit 的值——如果现在的 isLimitisLimitisLimit 为假则递归下去也是假如果现在的 isLimitisLimitisLimit 为真但填的数字小于 s[i]s[i]s[i] 则要将 isLimitisLimitisLimit 置为假递归下去否则后面的 isLimitisLimitisLimit 仍为真。 递归终点当 iii 等于 sss 长度时如果 isNum\textit{isNum}isNum 为真则表示得到了一个合法数字因为不合法的不会继续递归下去返回 111 即一个方案否则返回 000 。
class Solution {
public:int numDupDigitsAtMostN(int n) {string s to_string(n);// f(i,mask,isNum,isLimit)表示计算第i位及以后的合法方案数// 这里先计算无重复数字的正整数的个数,因此用mask表示已经使用了哪些数字// isNum则表示前面是否是数字,即前面填了数字没有,填了前面就是数字为true,否则前面不是数字为false// isLimit表示是否受到了n的约束,为true表示受到n的约束,即第i位填的数s[i];为false表示不受到s[i]约束,最大能填9// isNum为true,前面填了数字,则这里必须填数字,从0开始,看是否受到限制来填数字// isNum为false,前面没填数字,则这里也可不填数字,此后isNum还是false,isLimit为false(因为前面必小于s[i]前面);或者从1填起来,看是否受到限制来填数字// 填数字后,isNum变为true,看情况决定isLimit是否为true(现在受到限制填的数字是否等于s[i])// 如果现在不受限制,以后也不受限制;如果现在受限制,但填的数小于s[i],则后面不受限制;否则后面要受到限制int m s.size(), dp[m][1 10][2][2];memset(dp, -1, sizeof(dp));functionint(int, int, bool, bool) f [](int i, int mask, bool isNum, bool isLimit) - int {if (i m) return isNum; // 为true表示是一个合法数字,否则不是if (dp[i][mask][isNum][isLimit] ! -1)return dp[i][mask][isNum][isLimit];int ans 0;if (!isNum) // 当前数位可以不填数字ans f(i 1, mask, false, false); // 后面不受限制了// 下面开始填数字int lower isNum ? 0 : 1, upper isLimit ? s[i] - 0 : 9;for (int d lower; d upper; d) // 枚举要填入的数字if ((mask d 1) 0) // i前面没有使用,这里可用ans f(i 1, mask | (1 d), true, isLimit d upper);// 当前位填数字和不填数字得到的合法方案数都考虑了return dp[i][mask][isNum][isLimit] ans;};return n - f(0, 0, false, true);}
};大佬的解答 问记忆化四个状态有点麻烦能不能只记忆化 (i,mask)(i,\textit{mask})(i,mask) 这两个状态 答是可以的。比如 n234n234n234 第一位填 222 第二位填 333 后面无论怎么递归都不会再次递归到第一位填 222 第二位填 333 的情况所以不需要记录。又比如第一位不填第二位也不填后面无论怎么递归也不会再次递归到这种情况所以也不需要记录。 根据这个例子我们可以只记录不受到 isLimit\textit{isLimit}isLimit 或 isNum\textit{isNum}isNum 约束时的状态 (i,mask)(i,\textit{mask})(i,mask) 。比如 n234n234n234 第一位最高位填的 111 那么继续递归后面就可以随便填所以状态 (1,2)(1,2)(1,2) 就表示前面填了一个 111对应的 mask\textit{mask}mask 从第二位往后随便填的方案数。 问isNum\textit{isNum}isNum 这个参数可以去掉吗 答对于本题是可以的。由于 mask\textit{mask}mask 中记录了数字可以通过判断 mask\textit{mask}mask 是否为 000 来判断前面是否填了数字所以 isNum\textit{isNum}isNum 可以省略。代码保留了 isNum\textit{isNum}isNum 主要是为了方便大家掌握这个模板。因为有些题目不需要 mask\textit{mask}mask 但需要 isNum\textit{isNum}isNum 。 问能不能只记忆化 iii 答这是不行的。想一想我们为什么要用记忆化如果递归到同一个状态时计算出的结果是一样的那么第二次递归到同一个状态就可以直接返回第一次计算的结果了。通过保存第一次计算的结果来优化时间复杂度。 由于前面选的数字会影响后面选的数字两次递归到相同的 iii 如果前面选的数字不一样计算出的结果就可能是不一样的。如果只记忆化 iii 就可能会算出错误的结果。 也可以这样理解记忆化搜索要求递归函数无副作用除了修改 dpdpdp 数组从而保证递归到同一个状态时计算出的结果是一样的。 class Solution {
public:int numDupDigitsAtMostN(int n) {string s to_string(n);int m s.size(), dp[m][1 10];memset(dp, -1, sizeof(dp));functionint(int, int, bool, bool) f [](int i, int mask, bool isNum, bool isLimit) - int {if (i m) return isNum; // 为true表示是一个合法数字,否则不是if (isNum !isLimit dp[i][mask] ! -1)return dp[i][mask];int ans 0;if (!isNum) // 当前数位可以不填数字ans f(i 1, mask, false, false); // 后面不受限制了// 下面开始填数字int lower isNum ? 0 : 1, upper isLimit ? s[i] - 0 : 9;for (int d lower; d upper; d) // 枚举要填入的数字if ((mask d 1) 0) // i前面没有使用,这里可用ans f(i 1, mask | (1 d), true, isLimit d upper);if (isNum !isLimit)dp[i][mask] ans;// 当前位填数字和不填数字得到的合法方案数都考虑了return ans;};return n - f(0, 0, false, true);}
};复杂度分析
时间复杂度O(mD2D)O(mD2^D)O(mD2D) 其中 mmm 为 sss 的长度即 O(logn)O(\log n)O(logn) D10D10D10 。由于每个状态只会计算一次因此动态规划的时间复杂度 状态个数 ×\times× 单个状态的计算时间。本题状态个数为 O(m2D)O(m2^D)O(m2D) 单个状态的计算时间为 O(D)O(D)O(D) 因此时间复杂度为 O(mD2D)O(mD2^D)O(mD2D) 。空间复杂度O(m2D)O(m2^D)O(m2D) 。
