600. Non-negative Integers without Consecutive Ones

 1 class Solution {
 2     public int findIntegers(int num) {
 3         StringBuilder sb = new StringBuilder(Integer.toBinaryString(num)).reverse();
 4         int n = sb.length();
 5         
 6         int a[] = new int[n];//以0结尾的二进制长度为n的没有连续1的数字个数
 7         int b[] = new int[n];//以1结尾............................个数
 8         a[0] = b[0] = 1;
 9         for (int i = 1; i < n; i++) {
10             a[i] = a[i - 1] + b[i - 1];
11             b[i] = a[i - 1]; //为什么是这样的计算公式? 需要思考一下,长度为1 以0结尾的有"0",以1结尾的有"1"; 所以长度为2的,以0结尾的"10,0",以1结尾的"1"
12         }
13         
14         int result = a[n - 1] + b[n - 1];//这里计算的是n-1长度结尾为0的数字个数;总长度为n
15         for (int i = n - 2; i >= 0; i--) {
16             if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '1') break;//遇到连续的11就结束, 因为上面计算的是n-1长度,所以即使这里11连续,也不影响
17             if (sb.charAt(i) == '0' && sb.charAt(i + 1) == '0') result -= b[i];//连续的00,意味着无法出现以1结尾的数字,必须减掉b[i]
18         }
19         
20         return result;
21     }
22 }

这题可是hard....

开始的思路想到了如何计算没有连续1的数字个数,但是卡在了如何保证数字 <n. 最终还是去看了答案..