Java实现 LeetCode 600 不含连续1的非负整数（有些题为了避免使用位运算可以换成动态规划）

刺骨的言语ヽ痛彻心扉 2023-07-19 10:37 10阅读 0赞

## 600. 不含连续1的非负整数 ##

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

示例 1:

输入: 5  
输出: 5  
解释:  
下面是带有相应二进制表示的非负整数<= 5：  
0 : 0  
1 : 1  
2 : 10  
3 : 11  
4 : 100  
5 : 101  
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。  
说明: 1 <= n <= 109  
PS：  
动态规划

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] = 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;
                //如果出现00，则一定会出现11，减去当前位置的b
                if (sb.charAt(i) == '0' && sb.charAt(i + 1) == '0') result -= b[i];
            }
            
            return result;
        }
     
     
    }

PS：  
看不懂的大佬的位运算

class Solution { 
         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;
        }
     
     
     
    }