600. Non-negative Integers without Consecutive Ones

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: 5Output: 5Explanation: Here are the non-negative integers <= 5 with their corresponding binary representations:0 : 01 : 12 : 103 : 114 : 1005 : 101Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the

Note: 1 <= n <= 109

思路： 给一个数n，找出有多少个不大于n的正数，且这些正数的二进制表示中不包含两个连续的1。 int转2进制string的API

先用dp找出在k位二进制长度的数有多少满足条件的。a[i]表示以0为结尾的长度为i + 1的满足条件的数字个数，b[i]表示1为结尾的。

再找a[n - 1] + b[n - 1]里面overcount了多少，只有当连续两位为0时，b[i]是overcount的。11、01、10都能cover到a[i]和b[i]

class Solution public int findIntegers(int num) { StringBuilder sb = new StringBuilder(Integer.toBinaryString(num)).reverse(); int n = sb.length(); int[] a = new int[n]; int[] b = new int[n]; a[0] = 1; b[0] = 1; for (int i = 1; i < n; i++) { a[i] = a[i - 1] + b[i - 1]; b[i] = a[i - 1]; } int res = a[n - 1] + b[n - 1]; for (int i = n - 2; i >= 0; i--) { if (sb.charAt(i) == '0' && sb.charAt(i + 1) == '0') { res -= b[i]; } if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '1') { break; } } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。