Home LeetCode-600 Non-negative Integers without Consecutive Ones
Post
Cancel

LeetCode-600 Non-negative Integers without Consecutive Ones

Description

给出\(n\),返回区间\([0,n]\)内不含连续二进制1的数位的数字个数

Constraints

\(1 \le n \le 10^9\)

Solution

数位DP直接解

Code

class Solution {
public:
    int findIntegers(int n) {
        // i: length of digits
        // j: last 1
        int dp[35][2];
        memset(dp, -1, sizeof dp);
        bool a[35]; a[0] = 0;
        int length = 0;
        for(auto m{n}; m;) {
            a[length++] = m & 1;
            m >>= 1;
        }

        auto solve = [&](auto &&func, int cur, bool limit, bool last1) -> int {
            if(cur == -1) return 1;
            if(!limit && ~dp[cur][last1]) return dp[cur][last1];
            int up = limit ? a[cur] : 1;
            int ans = 0;
            for(int i = 0; i <= up; ++i) {
                if(i == 1 && last1) continue;
                ans += func(func, cur-1, limit && a[cur]==i, i==1);
            }
            return limit ? ans : dp[cur][last1] = ans;
        };

        return solve(solve, length-1, true, false);
    }
};

LeetCode-600 Non-negative Integers without Consecutive Ones

This post is licensed under CC BY 4.0 by the author.
Contents