[LeetCode]Non-negative Integers without Consecutive Ones

栏目: 编程工具 · 发布时间: 8年前

内容简介:[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 <= 10 9

题目大意:

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

注意:1 <= n <= 10 9

解题思路:

动态规划(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':
    
        说明出现连个连续的0ans 减去 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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

流量的秘密

流量的秘密

(英)Brian Clifton / 钟镭 / 人民邮电出版社 / 2010-2 / 45.00元

你对自己的网站有足够的了解吗?你知道自己网站的真实影响力和竞争力吗?你在想尽办法留住你的访客吗?《流量的秘密:Google Analytics网站分析与优化技巧》将运用最新的网络计量学方法,教你获取真正有价值的信息。 哪种市场营销活动最有成效?如何量化这些效果?应该从哪些衡量指标进行追踪?《流量的秘密:Google Analytics网站分析与优化技巧》介绍的Google Analytics......一起来看看 《流量的秘密》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

在线进制转换器
在线进制转换器

各进制数互转换器