内容简介:[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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
The Art of Computer Programming, Volume 2
Knuth, Donald E. / Addison-Wesley Professional / 1997-11-04 / USD 79.99
Finally, after a wait of more than thirty-five years, the first part of Volume 4 is at last ready for publication. Check out the boxed set that brings together Volumes 1 - 4A in one elegant case, and ......一起来看看 《The Art of Computer Programming, Volume 2》 这本书的介绍吧!