Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

600. Non-negative integers without consecutive 1’s

Given a positive integer n, find the number of non-negative integers less than or equal to n whose binary representation does not contain consecutive 1s.

Example 1: Input: 5 Output: 5 Description: The following are non-negative integers with the corresponding binary representation <= 5:0:0 1:1 2:10 3:11 4:100 5:101 Where only the integer 3 (with two consecutive 1s) violates the rule, and the other five comply with the rule.Copy the code

Their thinking

  1. Dp [I] represents the number of consecutive ones when the ith bit is 0.
  2. When the ith bit of n is 1, then two things happen. That is, when this bit is 0 and when this bit is 1, when this bit is 0, we can directly use dp[I] to figure out how many binary numbers without consecutive ones can be generated when this bit is 0. If this bit is 1, we need to check whether the previous bit is 1. If the previous bit is 0, it means that the bit can take 1 and continue traversing down in the same way, otherwise it cannot be traversed down.

code

class Solution {
    public int findIntegers(int n) {

        int[] dp=new int[31];
        dp[0] =1;
        dp[1] =1;
        for(int i=2; i<31; i++) dp[i]=dp[i-1]+dp[i-2];
        int pre=0,res=0;
        for(int i=29; i>=0; i--) {int cur=(1<<i);
            if((n&cur)! =0)
            {
                res+=dp[i+1];
                if(pre==1)
                    break;
                pre=1;
            }else pre=0;
            if(i==0)
                res++;
        }
        
        returnres; }}Copy the code
  • Time complexity: O(C), C is fixed at 31, time complexity of pretreatment.
  • Space complexity: O(C), C is fixed at 31, the space occupied by DP