[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':
    
        说明出现连个连续的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

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

查看所有标签

猜你喜欢:

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

高可用MySQL

高可用MySQL

)Charles Bell Mats Kindahl Lars Thalmann / 宁青、唐李洋 诸云萍 / 电子工业出版社 / 2011-10 / 98.00元

《高可用mysql:构建健壮的数据中心》是“mysql high availability”的中文翻译版,主要讲解真实环境下如何使用mysql 的复制、集群和监控特性,揭示mysql 可靠性和高可用性的方方面面。本书由mysql 开发团队亲自执笔,定位于解决mysql 数据库的常见应用瓶颈,在保持mysql 的持续可用性的前提下,挖潜各种提高性能的解决方案。本书分为三个部分。第一部分讲述mysql......一起来看看 《高可用MySQL》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

SHA 加密
SHA 加密

SHA 加密工具