https://www.cnblogs.com/grandyang/p/6959585.html
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
X. DP
https://www.jiuzhang.com/solution/non-negative-integers-without-consecutive-ones/
- 数字n转化为01字符串,从前向后遍历，f[i]表示当前i为'1'时，i位其右侧01串排列的合法方案。
- f[i] = f[i - 1] + f[i - 2]，此处求出i位的右侧的01串排列的合法方案，可以由i - 1时尾部加上一个'0'转移到i，可以由i - 2时尾部加上'01'转移到i。
- 从高位向低位遍历，每次遇到为'1'的位时，加上f[i]即可，遇到连续两个'1'时，返回即可
public int findIntegers(int num) {
if (num < 2) {
return num + 1;
}
StringBuilder str = new StringBuilder(Integer.toBinaryString(num)).reverse();
int k = str.length();
int[] f = new int[k];
f[0] = 1;
f[1] = 2;
for (int i = 2; i < k; i++) { //f[i]表示当前i为'1'时，i位其右侧01串排列的合法方案。
f[i] = f[i - 1] + f[i - 2]; //f[i] = f[i - 1] + f[i - 2]，此处求出i位的右侧的01串排列的合法方案，可以由i - 1时尾部加上一个'0'转移到i，可以由i - 2时尾部加上'01'转移到i。
}
int ans = 0;
for (int i = k - 1; i >= 0; i--) {
if (str.charAt(i) == '1') {
ans += f[i]; //每次遇到为'1'的位时，加上f[i]即可
if (i < k - 1 && str.charAt(i + 1) == '1') {
return ans;
}
}
}
ans++; //加上自身数字
return ans;
}
This problem can be solved using Dynamic Programming. Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0. Similarly, let b[i] be the number of such strings which end in 1. We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:
a[i] = a[i - 1] + b[i - 1] b[i] = a[i - 1]
The base cases of above recurrence are a[1] = b[1] = 1. The total number of strings of length i is just a[i] + b[i].
Following is the implementation of above solution. In the following implementation, indexes start from 0. So a[i] represents the number of binary strings for input length i+1. Similarly, b[i] represents binary strings for input length i+1.
static int countStrings(int n) { int a[] = new int [n]; int b[] = new int [n]; a[0] = b[0] = 1; for (int i = 1; i < n; i++) { a[i] = a[i-1] + b[i-1]; b[i] = a[i-1]; } return a[n-1] + b[n-1]; }
- let one[i] be the number of non-consecutive-1 solutions with the i-th significant bit being 1;
- let zero[i] be the number of non-consecutive-1 solutions with the i-th significant bit being 0;
the most tricky part is how to count the solutions smaller than
We first calculate number of all n-bits solutions:
then we subtract the solutions which is larger than
num.We first calculate number of all n-bits solutions:
res = one[n - 1] + zero[n - 1].then we subtract the solutions which is larger than
num, we iterate from the MSB to LSB of num:- if bit[i] == 1
- if bit[i + 1] == 0, there's no solutions in
resthat is larger thannum, we go further into smaller bit and subtract. - if bit[i + 1] == 1, we know in those
ressolutions it won't have any consecutive ones. when bit[i + 1] == 1, in one[i + 1], the i-th bit in valid solutions must be 0, which are all smaller than 'num', we don't need to check smaller bits and subtract, so we break form the loop.
- if bit[i + 1] == 0, there's no solutions in
- if bit[i] == 0
- if bit[i + 1] == 1, there's no solutions in
resthat is larger thannum, we go further into smaller bit and subtract. - if bit[i + 1] == 0, we know zero[i + 1] includes solutions of i-th == 0 (
00***) and i-th bit == 1 (01***), we know the i-th bit ofnumis 0, so we need to subtract all the01***solutions because it is larger thannum. Therefore, one[i] is subtracted fromres.
- if bit[i + 1] == 1, there's no solutions in
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] = b[0] = 1;
for (int i = 1; i < n; i++) {
a[i] = a[i - 1] + b[i - 1];
b[i] = a[i - 1];
}
int result = a[n - 1] + b[n - 1];
for (int i = n - 2; i >= 0; i--) {
if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '1') break;
if (sb.charAt(i) == '0' && sb.charAt(i + 1) == '0') result -= b[i];
}
return result;
}
X. Memoized DP
public int findIntegers(int num) {
return findIntegers(num, new HashMap<>());
}
public int findIntegers(int num, Map<Integer, Integer> memo) {
if (num <= 2) return num + 1; // base case
if (memo.containsKey(num)) return memo.get(num); // check if this result has already been computed
int msb = 31 - Integer.numberOfLeadingZeros(num); // retrieve index of most significant bit
int subNum = (1 << msb) - 1, subNum2 = ~(1 << msb) & num;
if (subNum2 >= 1 << msb - 1) subNum2 = subNum >> 1;
int result = findIntegers(subNum, memo) + findIntegers(subNum2, memo);
memo.put(num, result); // add result to memo
return result;
}
X.
https://www.acwing.com/solution/LeetCode/content/467/
- 按照数位统计的一般思路，从二进制的高位向底位，每次保证作为答案的数字不能超过 n。
- 首先预处理出长度为 i 的二进制串中，以 0 作为最高位且符合条件的二进制串的个数。这里从低位开始往高位递推，递推方程为 ，其中，。 无具体含义。
- 从高到底遍历 n 的二进制位，设计布尔变量 last_one，表示 n 的二进制位中上一位是否为 1，初始为 false。
- 若第 i 位为 1，累计答案 ，然后考察 last_one，若 last_one 为 true，则此时统计工作已经结束，直接返回 ans；否则，设置 last_one = true。
- 若第 i 位为 0，设置 last_one = false。
- 最终返回 ans + 1，这里的加 1 加的是 n 本身作为合法的答案。
下面以例子
10101100 为例分析：- 第 7 位是 1，则答案累计 f(8)，这里累计的是
00000000 - 01111111的答案个数；此时 last_one = false，然后设置 last_one = true。 - 第 6 位是 0，设置 last_one = false。
- 第 5 位是 1，则答案累计 f(6)，这里累计的是
10000000 - 10011111的答案个数；此时 last_one = false，然后设置 last_one = true - 第 4 位是 0，设置 last_one = false。
- 第 3 位是 1，则答案累计 f(4)，这里累计的是
10100000 - 10100111的答案个数。此时 last_one = false，然后设置 last_one = true。 - 第 2 位是 1，则答案累计 f(3)，这里累计的是
10101000 - 10101011的答案个数。此时 last_one = true，无需再进行之后的统计，因为第 2 位不能放置 1，所以返回答案为 f(3) + f(4) + f(6) + f(8) = 55。
时间复杂度
- 只涉及到对二进制位的操作，故时间复杂度为 。
确实是一道比较难的题目，参考了网上的解法。该解法基于如下两个观察：
1）在由'0'和'1'构成的长度为k的字符串中，不含连续'1'的字符串的个数为菲波那切数列f(k)。我觉得这个可以严格证明，但是为了简便，这里仅举例说明一下。例如我们假设k = 5，那么字符串的的范围为00000 - 11111。我们可以将该范围分为两个部分：[00000, 01111) U [10000, 10111)。 而任何大于等于110000的数字都不符合条件，因为其必定含有两个连续的1。[00000, 01111)其实就对应了f(4)，而[10000, 10111)其实就对应了f(3)，所以f(5) = f(4) + f(3)。
2）如果对字符串从左往右扫描，每次遇到一个1的时候，如果它的左边是0并且右面还有k位，那么就可以给结果加上f(k)，这是因为我们可以将该位置为0，并且在之后的k位上添加任意合法的长度为k的字符串，其大小都不会超过该字符串并且符合条件。但是如果其左边是1并且后面还有k位，那么添加f(k)之后就应该立即返回，这是因为任何之后添加f(i) (i < k)所对应的结果都不符合条件，原因是当前已经出现了两个连续的1了。如果程序在循环中没有提前返回，那么说明n本身也是符合条件的，所以最后返回ans + 1。
该算法的时间复杂度是O(1)，空间复杂度也是O(1)，这是因为对于int而言k <= 32，实在是好的不能再好的算法了。当然如果不限制是int，而是任意大小的正整数，那么其时间复杂度和空间复杂度都是O(log(num))，也是非常好的算法了。
public int findIntegers(int num) { int[] f = new int[32]; f[0] = 1; f[1] = 2; for (int i = 2; i < f.length; i++) f[i] = f[i - 1] + f[i - 2]; int i = 30, sum = 0, prev_bit = 0; while (i >= 0) { if ((num & (1 << i)) != 0) { sum += f[i]; if (prev_bit == 1) { sum--; break; } prev_bit = 1; } else prev_bit = 0; i--; } return sum + 1; }
Build a tree to consider all possible number.
Let 1.and 0 for each bit be tree node
compress to 4 possible result for each bit:
- all bit before cur is less than num and no continues 1 and cur bit is at one.
- all bit before cur is less than num and no continues 1 and cur bit is at zero.
- cur and prev bit is equal to num.
- larger than num or has contiunes '1'.
then run through the tree.
public int findIntegers(int num) {
//one:all bit before cur is less than num and no continues 1 and cur bit is at one;
//zero:all bit before cur is less than num and no continues 1 and cur bit is at zero;
int one=0,zero=0,temp;
boolean isNum=true;
for(int i=31;i>=0;i--){
temp=zero;
zero+=one;
one=temp;
if(isNum&&((num>>i)&1)==1){
zero+=1;
}
if(((num>>i)&1)==1&&((num>>i+1)&1)==1){
isNum=false;
}
}
return one+zero+(isNum?1:0);
}
这道题给了我们一个数字，让我们求不大于这个数字的所有数字中，其二进制的表示形式中没有连续1的个数。根据题目中的例子也不难理解题意。我们首先来考虑二进制的情况，对于1来说，有0和1两种，对于11来说，有00，01，10，三种情况，那么有没有规律可寻呢，其实是有的，我们可以参见这个帖子，这样我们就可以通过DP的方法求出长度为k的二进制数的无连续1的数字个数。由于题目给我们的并不是一个二进制数的长度，而是一个二进制数，比如100，如果我们按长度为3的情况计算无连续1点个数个数，就会多计算101这种情况。所以我们的目标是要将大于num的情况去掉。下面从头来分析代码，首先我们要把十进制数转为二进制数，将二进制数存在一个字符串中，并统计字符串的长度。然后我们利用这个帖子中的方法，计算该字符串长度的二进制数所有无连续1的数字个数，然后我们从倒数第二个字符开始往前遍历这个二进制数字符串，如果当前字符和后面一个位置的字符均为1，说明我们并没有多计算任何情况，不明白的可以带例子来看。如果当前字符和后面一个位置的字符均为0，说明我们有多计算一些情况，就像之前举的100这个例子，我们就多算了101这种情况。我们怎么确定多了多少种情况呢，假如给我们的数字是8，二进制为1000，我们首先按长度为4算出所有情况，共8种。仔细观察我们十进制转为二进制字符串的写法，发现转换结果跟真实的二进制数翻转了一下，所以我们的t为"0001"，那么我们从倒数第二位开始往前遍历，到i=1时，发现有两个连续的0出现，那么i=1这个位置上能出现1的次数，就到one数组中去找，那么我们减去1，减去的就是0101这种情况，再往前遍历，i=0时，又发现两个连续0，那么i=0这个位置上能出1的次数也到one数组中去找，我们再减去1，减去的是1001这种情况
int findIntegers(int num) { int cnt = 0, n = num; string t = ""; while (n > 0) { ++cnt; t += (n & 1) ? "1" : "0"; n >>= 1; } vector<int> zero(cnt), one(cnt); zero[0] = 1; one[0] = 1; for (int i = 1; i < cnt; ++i) { zero[i] = zero[i - 1] + one[i - 1]; one[i] = zero[i - 1]; } int res = zero[cnt - 1] + one[cnt - 1]; for (int i = cnt - 2; i >= 0; --i) { if (t[i] == '1' && t[i + 1] == '1') break; if (t[i] == '0' && t[i + 1] == '0') res -= one[i]; } return res; }
下面这种解法其实蛮有意思的，其实长度为k的二进制数字符串没有连续的1的个数是一个斐波那契数列f(k)。比如当k=5时，二进制数的范围是00000-11111，我们可以将其分为两个部分，00000-01111和10000-10111，因为任何大于11000的数字都是不成立的，因为有开头已经有了两个连续1。而我们发现其实00000-01111就是f(4)，而10000-10111就是f(3)，所以f(5) = f(4) + f(3)，这就是一个斐波那契数列啦。那么我们要做的首先就是建立一个这个数组，方便之后直接查值。我们从给定数字的最高位开始遍历，如果某一位是1，后面有k位，就加上f(k)，因为如果我们把当前位变成0，那么后面k位就可以直接从斐波那契数列中取值了。然后标记pre为1，再往下遍历，如果遇到0位，则pre标记为0。如果当前位是1，pre也是1，那么直接返回结果。最后循环退出后我们要加上数字本身这种情况
int findIntegers(int num) { int res = 0, k = 31, pre = 0; vector<int> f(32, 0); f[0] = 1; f[1] = 2; for (int i = 2; i < 31; ++i) { f[i] = f[i - 2] + f[i - 1]; } while (k >= 0) { if (num & (1 << k)) { res += f[k]; if (pre) return res; pre = 1; } else pre = 0; --k; } return res + 1; }
Numbers WIthout Consecutive 1s in binary representation
