[LeetCode]Non-negative Integers without Consecutive Ones

题目描述:

LeetCode 600. Non-negative Integers without Consecutive Ones

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.

Example 1:

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. 

Note: 1 <= n <= 109

题目大意:

给定正整数n,求小于等于n,并且二进制形式不包含连续1的数字的个数

注意:1 <= n <= 109

解题思路:

动态规划(Dynamic Programming)

参考:http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

首先构造斐波那契数列dp = [1, 2, 3, 5, 8, 13 ...]

记num的二进制串为bnum,其长度为size

令结果ans = dp[size]

从高位到低位遍历bnum,记当前下标为idx:

    若bnum[idx] == bnum[idx - 1] == '1':

        说明出现两个连续的1,退出循环
    
    若bnum[idx] == bnum[idx - 1] == '0':
    
        说明出现连个连续的0,ans 减去 dp[size - idx] - dp[size - idx - 1] (等于dp[size - idx - 2])

Python代码:

class Solution(object):
    def findIntegers(self, num):
        """
        :type num: int
        :rtype: int
        """
        dp = [1, 2]
        for x in range(2, 32):
            dp.append(dp[x - 1]+ dp[x - 2])
        bnum = bin(num)[2:]
        size = len(bnum)
        ans = dp[size]
        for idx in range(1, size):
            if bnum[idx] == bnum[idx - 1] == '1':
                break
            if bnum[idx] == bnum[idx - 1] == '0':
                ans -= dp[size - idx] - dp[size - idx - 1]
        return ans

 

本文链接:http://bookshadow.com/weblog/2017/05/28/leetcode-non-negative-integers-without-consecutive-ones/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论