Algorithm

[LeetCode 600] Non-negative Integers without Consecutive Ones [Java]

顿搜

2017-09-14

0 评论

604 阅读

正在检测是否收录...

09/14

1. Description

Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

2. Runtime Distribution

3. Submission Details

4. Example

Input: 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

5. Code

public int findIntegers(int num) {

    int bitCount = 0;
    int[] numInBit = new int[32];

    for (int i = num; i > 0; i >>= 1) {
        numInBit[bitCount++] = (i & 1);
    }

    int[] dp = new int[bitCount + 1];
    dp[0] = 1;
    dp[1] = 2;
    for (int i = 2; i <= bitCount; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    int result = 0;
    for (int i = bitCount - 1; i >= 0; i--) {
        if (numInBit[i] == 0) {
            continue;
        }
        result += dp[i];

        if (numInBit[i + 1] == 1) {
            return result;
        }
    }

    return result + 1;

}

6.Test

public class LeetCode0600 {

    public int findIntegers(int num) {

        int bitCount = 0;
        int[] numInBit = new int[32];

        for (int i = num; i > 0; i >>= 1) {
            numInBit[bitCount++] = (i & 1);
        }

        int[] dp = new int[bitCount + 1];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i <= bitCount; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        int result = 0;
        for (int i = bitCount - 1; i >= 0; i--) {
            if (numInBit[i] == 0) {
                continue;
            }
            result += dp[i];

            if (numInBit[i + 1] == 1) {
                return result;
            }
        }

        return result + 1;

    }

    public static void main(String[] args) {
        System.out.println(new LeetCode0600().findIntegers(5));
    }

}

BIT

朗读