链接：600. 不含连续1的非负整数

题目描述

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

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

题解

2的n次方对应二进制数的特点：

2~10 4~100 8~1000 16~10000

二进制数在两个2的n次方数当中变化的特点： 观察在8到16当中:

1000 - 1100 //含连续'11'的数的个数等于00到100含连续'11'的数的个数；
1100 - 10000 //全部含连续'11'

其中1000 - 1100中含连续'11'的数的个数为4含连续'11'的数的个数；1100 - 10000中含连续'11'的数的个数就是为4。

dp[i][0]表示2的i+1次方
dp[i][1]表示小于或等于dp[i][0]的数中含有连续'11'的个数
i: 0 1 2 3；
dp[i][0]: 2 4 8 16；
dp[i][1]: 0 1 3 8；
dp[i][0] = 2^(i+1)；
dp[i][1] = dp[i-1][1] + dp[i-2][1] + dp[i-2][0]；

最后想办法求出所有含连续'11'的数的个数，用总数减去该数即可

class Solution {
    public int findIntegers(int n) {
        //1~7的数自行处理
    	if(n<3) {
    		return n+1;
    	}else if(n<6) {
    		return n;
    	}else if(n==6) {
    		return n-1;
    	}else if(n<8) {
    		return n-2;
    	}
    	//初始化数据
    	List<int[]> dp = new ArrayList<int[]>();
    	int[] indexOne = {2,0};
    	int[] indexTwo = {4,1};
    	dp.add(indexOne);dp.add(indexTwo);
    	int index = 4;int i = 1;
    	//找小于n到最大2的i次方,多找一次：	dp.get(i-1)才是小于n到最大2的i次方
    	while(index<=n) {
    		i+=1;
    		index *= 2;
    		int[] temp = new int[2];
    		int value = dp.get(i-1)[1] + dp.get(i-2)[1] + dp.get(i-2)[0];
    		temp[0] = index;temp[1] = value;
    		dp.add(temp);    		
    	}    	
    	int m = 0;	//含连续'11'的数的个数
    	int remainer = n;	//剩余的数
    	while(i>2) {
    		if(remainer>=dp.get(i-1)[0]) {	//匹配：1****
    			m += dp.get(i-1)[1];	//把100...0中含有含连续'11'的数加进去
    			//特殊情况：	n刚好落在全选的那个区间
        		if(dp.get(i)[0]-remainer<=dp.get(i-2)[0]) {        		
            		m += (dp.get(i)[1]- dp.get(i-1)[1]) - (dp.get(i)[0] - remainer) +1;	//加上剩余含连续'11'的数(n不要减：+1)
            		return n-m+1;	//limit到n有n-limit个数，减去含11的数即可
            	}
        		//其他情况	：因为首位为1，第二位为0，于是可以直接从第三位开始看，把前两位去掉    		
        		if(remainer>=dp.get(i-1)[0]) {
        			remainer = remainer-dp.get(i-1)[0];	//剪掉前面的'10'
        			i-=2;	//往前移动两位
        		}
    		}else {
    			i-=1;	//往前移动一位 
    		}   		  		    		    		   		
    	}
    	//此时的n只有余下 0-7的情况
    	if(remainer<3) {
    		return n-m+1;
    	}else if(remainer<6) {
    		return n-m;
    	}else if(remainer==6) {
    		return n-m-1;
    	}else {
    		return n-m-2;
    	}   	
    }
}

评论