-
Notifications
You must be signed in to change notification settings - Fork 25
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
LeetCode困难题赏 - 600.不含连续1的非负整数 #21
Comments
var findIntegers = function(num) {
let dp = new Array()
let sum = 0
let binary = Number(num).toString(2)
let N = binary.length
dp[0] = 1
dp[1] = 2
for (let i = 2; i < 32; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
for (let i = 0, k = N; i < N; i++, k--) {
if (binary[i] == '1') {
sum += dp[k-1]
if(i>0 && binary[i-1]=='1'){
return sum
}
}
}
sum++
return sum
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
题目
给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续的1的个数,其中$1\leq n \leq 10^9$。
示例:
来源:600. 不含连续1的非负整数
解析
对于这种涉及到二进制字符串的题目,一般都会采用动态规划的思想来解决,观察本题所规定的二进制字符串,发现可以由以下文法$[1]$给出:
那么根据该文法,我们自然而然地想到构造一个基于字符串长度的状态表$dp$,其中$dp[k]$表示长度为$k$的不含连续1的二进制字符串的个数,然后根据文法写出状态表的初始值:
然后根据文法语句$S\rightarrow 10S | 0S$可知,任何长度为$k$的符合条件的字符串,都是由以下两种规则得到的:
从而得到状态表的递推式:
dp[k] = dp[k - 1] + dp[k - 2]
,可以发现,该递推式就是斐波那契的生成式。到此为止,我们只能得到指定长度的二进制字符串的个数,题目中还有个限定条件是$\leq n$,我们分析一个十进制转化为二进制字符串后的构成:
$$5 \rightarrow 101, 16 \rightarrow 1000$$
即首个字符肯定为1,也就是文法$[1]$中给出的形如$10S$的字符串,我们直接把十进制上界$n$转化为二进制后,可能会得到两种形式的字符串:
对于第二种形式的正整数$n$,我们只需要计算小于$n$的形如$10S$的字符串对应的解即可,设求解程序为$f(S)$,则有如下的分解方式:
$$f(S)=dp[L(g(S))]+f(g(S)_{suffix})$$
其中$g(S)$表示不大于$S$的形如$10S$的字符串,$L(S)$表示字符串$S$的长度。
代码
[TODO]
The text was updated successfully, but these errors were encountered: