两个问题
来源：6-5 BFS和图的最短路径 Perfect Squares
讲武德的年轻人
2022-07-11
bobo老师，最近遇到两个coding题目，不确定自己思路是否正确和最优，想请教您。
第一题目这样：给定一个long型整数，范围[1, 10^15]，把它的二进制表示成一个string或者数组。目标是：通过一定规则把这个string或数组变成全为0的string或数组，返回使用的最少步数。只能使用两个规则:
规则1：对于第i位数字，如果第(i+1)位数字是1，而且从第(i+2)位数字开始，之后的数字都是0，则可以变化第i位数字。
规则2： 可以变化最后一位数字。
举例：n = 4， 则其二进制表示为"100"。可以通过100 -> 101(规则2) -> 111 (规则1) -> 110(规则2) -> 010 (规则1) -> 011(规则2) -> 001(规则1) -> 000 (规则2)。所以返回7。
我的理解：可以用BFS。因为只有两个规则，所以对于任意一个二进制表示的字符串，最多只有两种变化可能。所以可以通过BFS来求得最少步数。而且，因为整数可能非常大，可以考虑用双向BFS进行优化。因为我刚刚开始看您的动态规划视频，不知道这道题最优解是否是DP呢？感觉BFS的开销会有些大。
2. 第二个题目是我看到别人发的。题目是这样：给定一个int[]闭区间，比如[80, 120]。求这个区间内没有重复字符的整数数量，比如[80, 120]一共有41个数字，其中27个数字没有重复字符 ，而14个数字有重复字符。比如，88, 99, 101, 110这种还有两个8，两个9，两个1都是还有重复字符的数字。
我的理解：直观上的暴力解法是访问每个数字，然后放进hash set中看有无重复数字，但是貌似这种方法会超时。我能想到一个优化方向，利用数学上的性质。比如两位数的整数，只有11, 22, 33, ..., 99这9种可能，而三位数的整数可以用排列组合的性质： 如果有两个字符相同，有9 * (8 + 9 + 9) = 26*9种可能，再加上三个字符相同有9种可能，所以三位整数有重复字符的情形一共有27 * 9种。其余高位数字以此类推。当然，结果还要考虑给定的区间上限。不知道您觉得这种优化是否可行？
谢谢老师指点！
1回答
-
这两个问题都是竞赛水平的问题了。
第一个问题，BFS 应该是不可以的。因为每一个数字都是一个节点，那么节点数最多达到 10^15 这个级别。妥妥超时。
如果我没有理解错，这个规则完全是格雷码的变换规则，求的就是给定数字的二进制作为格雷码对应的次序，可以搜索一下格雷码和二进制码的转换。
==========
第二个问题，你没有给出数据范围，但通常暴力也是超时的。（不然没啥意义。）
首先，求 [a, b] 之间满足某个条件的数字个数，这个模式的问题的套路是，设 f(x) 为 [0, x] 满足某个条件的数字个数。只要能设计出 f，最终的结果就是 f(b) - f(a - 1)。而通常求解 [0, x] 之间满足某个条件的数字个数会更容易。
其次，这个问题是一个标准的数字 dp。什么是数字 dp，解释起来有些复杂。面试近乎一定不会考，在竞赛中属于一类不能说非常常见，但是很标准，合格的选手都一定了解的 dp 类问题。
力扣中有一些数位 dp 的问题。我搜了一下，力扣的这个问题基本上就是你的这个问题的“反面”（n - 这个问题的解就是你的问题的解），你可以研究一下这个问题：https://leetcode.cn/problems/numbers-with-repeated-digits/
==========
整体，如果你是准备面试的话，在我看来，这两个问题都不用管。如果是准备竞赛的话，你需要先进一步学习很多竞赛中才会涉及的技术点。不然基本方法没有掌握，肯定大多数问题是没有思路的。
这里是一个很好的竞赛相关知识点的总结：https://oi-wiki.org/
如果习惯看英文的话，看这里：https://cp-algorithms.com/
但再强调一下，这些竞赛中的技术点，在面试中意义不大的。
继续加油！：）
012022-07-11
相似问题