不含连续1的非负整数

Category Difficulty Likes Dislikes
algorithms Hard (48.52%) 293 -
Tags

dynamic-programming

Companies

Unknown

给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。

示例 1:

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

示例 2:

1
2
输入: n = 1
输出: 2

示例 3:

1
2
输入: n = 2
输出: 3

提示:

  • 1 <= n <= 109

动态规划

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem600.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=600 lang=cpp
 *
 * [600] 不含连续1的非负整数
 */

/** 
 * 7
 * 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 
 * 
 * f[i] = f[i - 1] + C(num)
 * 00 01 10 11 
 * 10
 * 
 * 101
 * 
 */

// @lc code=start
class Solution {
public:
    int findIntegers(int n) {
        // vector<int> f(n + 1, 0);
        // f[0] = 1;
        // for (int i = 1; i <= n; ++i) {
        //     int tmp = i;
        //     bool bl = true;
        //     while (tmp > 0) {
        //         if ((tmp & 0x01) == 1 && (tmp & 0x02) == 2) {
        //             bl = false;
        //             break;
        //         }
        //         tmp >>= 1;
        //     }
        //     f[i] = f[i - 1] + bl;
        // }
        // return f[n];
        vector<int> f(32);
        f[0] = f[1] = 1;
        for (int i = 2; i < 31; ++i) {
            f[i] = f[i - 1] + f[i - 2];
        }
        int pre = 0, res = 0;
        for (int i = 29; i >= 0; --i) {
            int val = 1 << i;
            if ((val & n) != 0) {
                res += f[i + 1];
                if (pre == 1) {
                    break;
                }
                pre = 1;
            } else {
                pre = 0;
            }
            if (i == 0) {
                ++res;
            }
        }
        return res;
    }
};
// @lc code=end