题目

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 **连续的1 **的个数。

示例 1:

输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

说明: 1 <= n <= 109

思路

说实话没怎么懂，看 @宫水三叶 的讲解，抄了抄代码。
@宫水三叶的 讲解

这是一道典型的「数位 DP」题。

对于「数位 DP」题，都存在「询问 [ a , b ] [a, b] [a,b]（ a a a 和 b b b 均为正整数，且 a < b a < b a<b）区间内符合条件的数值个数为多少」的一般形式，通常我们需要实现一个查询 [ 0 , x ] [0, x] [0,x] 有多少合法数值的函数 int dp(int x)，然后应用「容斥原理」求解出 [ a , b ] [a, b] [a,b] 的个数： d p ( b ) − d p ( a − 1 ) dp(b) - dp(a - 1) dp(b)−dp(a−1)。
对于本题，虽然只需要求解 [ 0 , n ] [0, n] [0,n] 范围内数的个数，但其实拓展到求 [ a , b ] [a, b] [a,b] 区间个数的也不会增加难度。

具体的，对于「数位 DP」问题通常是「从高位到低位」的分情况讨论。

不失一般性的考虑数值 n n n 的某一位 c u r cur cur 是如何被处理的：

1. 如果当前位 c u r = 1 cur = 1 cur=1 的话，由于我们需要满足「小于等于 n n n」的要求，因此如果该位填 0 0 0 的话，后面的低位填什么都是满足要求的，因此我们期望能够查表得出「长度为 i + 1 i + 1 i+1，且二进制位置 i i i 数值为 0 0 0 时」有多少合法数值，将其累加到答案中；
   与此同时，我们需要确保当前位选 1 1 1 是合法的，即我们需要记录上一位 p r e v prev prev 是什么，确保 c u r cur cur 和 p r e v prev prev 不同时为 1 1 1。
2. 如果当前位 c u r = 0 cur = 0 cur=0 的话，我们只能选 0 0 0，并决策下一位。

当出现「当前位无法填入 c u r cur cur」或者「决策到最低位」时，则完成了所有合法答案的统计。

至于流程 1 1 1 中的查表操作，我们可以使用 static 预处理出 f 数组，定义 f [ i ] [ j ] f[i][j] f[i][j] 为考虑二进制长度为 i i i，且最高位为 j j j（ 0 0 0 or 1 1 1）时的合法数个数。

注意：为了防止重复计数问题，我们在不失一般性的计算 f [ i ] [ 0 ] f[i][0] f[i][0] 和 f [ i ] [ 1 ] f[i][1] f[i][1] 时，不能采用诸如 f [ i ] [ c u r ] + = f [ i − 1 ] [ p r e v ] f[i][cur] += f[i - 1][prev] f[i][cur]+=f[i−1][prev] 的 “后向查找依赖” 的方式进行转移，而要采用 f [ i + 1 ] [ c u r ] + = f [ i ] [ p r e v ] f[i + 1][cur] += f[i][prev] f[i+1][cur]+=f[i][prev] “前向主动更新” 的方式进行转移。

不失一般性的考虑 f [ i ] [ 0 ] f[i][0] f[i][0] 和 f [ i ] [ 1 ] f[i][1] f[i][1] 能够更新哪些状态：

• 如果期望当前位填 0 0 0 的话，需要统计所有满足 ( 0… ) 2 (0…)_2 (0…)2​ 形式的合法数值，当前位的低一位只能填 1 1 1（填 0 0 0 会出现重复计数，即需要忽略前导零的数值），此时有： f [ i + 1 ] [ 0 ] = f [ i ] [ 1 ] f[i + 1][0] = f[i][1] f[i+1][0]=f[i][1]；

• 如果期望当前位填 1 1 1 的话，需要统计所有满足 ( 1… ) 2 (1…)_2 (1…)2​ 和 ( 0… ) 2 (0…)_2 (0…)2​ 形式的合法数值：

• ( 1… ) 2 (1…)_2 (1…)2​ 时，当前位的低一位只能填 0 0 0；此时有： f [ i + 1 ] [ 1 ] + = f [ i ] [ 0 ] f[i + 1][1] += f[i][0] f[i+1][1]+=f[i][0]； * ( 0… ) 2 (0…)_2 (0…)2​ 时，当前位的低一位只能填 1 1 1；此时有： f [ i + 1 ] [ 1 ] + = f [ i ] [ 1 ] f[i + 1][1] += f[i][1] f[i+1][1]+=f[i][1]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int findIntegers(int n) {
        if(!n) return 1;
        int N = 32;
        int dp[N][2];
        memset(dp,0,sizeof(int)*N*2);
        dp[1][0] = 1;
        dp[1][1] = 2;
        for(int i=1;i<N-1;++i){
            dp[i+1][0] = dp[i][1];
            dp[i+1][1] = dp[i][0]+dp[i][1];
        }
        int pre = 0,ans=0,idx=31;
        for(;idx>=0;--idx){
            if(((n>>idx)&1)==1) break;
        }
        for(;idx>=0;--idx){
            int cur = (n>>idx)&1;
            if(cur==1) ans+=dp[idx+1][0];
            if(pre==1&&cur==1) break;
            pre=cur;
            if(idx==0) ans++;
        }
        return ans;
    }
};

题目

233. 数字 1 的个数 - 力扣（LeetCode） (leetcode-cn.com)

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

1
2

输入：n = 13
输出：6

示例 2：

1
2

输入：n = 0
输出：0

提示：

• 0 <= n <= 2 * 10^9

思路

是一个递推的问题。

方法一：直接递推

假设输入为 a*10^n^+b

中间情况：

只要递归：$$ f( a*10^n+b ) = f(b) + f ( a * 10^n-1 ) $$即可。

边界条件：

$$ f(x)=\left{ \begin {aligned} & 0,x<1\&1,1<=x<10 } \end {aligned} \right. $$

本方法会超时

方法二：避免重复计算

在
$$a*10^n+b$$
中，

• 如果a>2，在计算完b之后，需要计算a*10^n^-1。

  容易发现：

  当a>2 的时候，在2~a之间由于最高位都不是1，因此都是计算10^n-1^，可以合并为计算一次10^n-1^，之后乘上a-2 倍。

  当a==2的时候，计算2*10^n-1^，即计算与$$a*10^n+b$$ 相同位数，不过最高为是1时候的总的1的个数。

  计算a-2个b可以合并为计算一个b之后乘上a-2，之后在计算2*10^n-1^即可。

• 如果a==1：

  数字为$$10^n+b$$ ，首先有b+1个数字至少包含一个1，也就是不小于$$10^n$$的部分最高位包含1的个数，之后递归计算b，算出来不小于10^n^部分包含的所有的1，在计算10^n^-1内的1的个数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int countDigitOne(int n) {
        if(n<1) return 0;
        if(n<10) return 1;
        int a = n,e=1;
        while(a/10){
            a/=10;
            e*=10;
        }
        int b = n - a*e;
        if(a==1) return b+1+countDigitOne(b)+countDigitOne(e-1);
        return countDigitOne(b)+countDigitOne(2*e-1)+(a-2)*countDigitOne(e-1);
    }
};