Java O(1) time O(1) space DP Solution


  • 4
    R

    Build a tree to consider all possible number.

    Let 1.and 0 for each bit be tree node

    compress to 4 possible result for each bit:

    1. all bit before cur is less than num and no continues 1 and cur bit is at one.
    2. all bit before cur is less than num and no continues 1 and cur bit is at zero.
    3. cur and prev bit is equal to num.
    4. larger than num or has contiunes '1'.

    then run through the tree.

    public class Solution {
        public int findIntegers(int num) {
            //one:all bit before cur is less than num and no continues 1 and cur bit is at one;
            //zero:all bit before cur is less than num and no continues 1 and cur bit is at zero;
            int one=0,zero=0,temp;
            boolean isNum=true;
            for(int i=31;i>=0;i--){
                temp=zero;
                zero+=one;
                one=temp;
                if(isNum&&((num>>i)&1)==1){
                    zero+=1;
                }
                if(((num>>i)&1)==1&&((num>>i+1)&1)==1){
                    isNum=false;
                }
                
            }
            return one+zero+(isNum?1:0);
        }
    }
    

  • 2

    li hai le wo de ge


  • 1
    T

    Bravo my borther


  • 0
    X

    superb !!!

    Here is a python version:

    class Solution(object):
        def findIntegers(self, num):
            """
            :type num: int
            :rtype: int
            """
            end0, end1 = 0, 0
            no_adj_1s = True
            prevbit = 0
            for i in reversed(range(num.bit_length())):
                end0, end1 = end0+end1, end0
                currbit = (num>>i) & 1
                if no_adj_1s and currbit:
                    end0 += 1
                if currbit and prevbit:
                    no_adj_1s = False
                prevbit = currbit
            return end0 + end1 + no_adj_1s        
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.