leetcode600. 不含连续1的非负整数

柔情只为你懂 2022-09-11 06:22 51阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_7_color_FFFFFF_t_70_g_se_x_16]  
思路

1.  暴力，每次后移一位与当前值&如果为0，则当前值符合条件
2.  `dp[i][1] = dp[i-1][0],dp[i][0] = dp[i-1][1]+dp[i-1][0]`得出第i位的值是0或者1时的有效数量。`1[......]--->0[.....], 0[......]->0[.....]+1[.....]`
3.  我们只把第i个有效位1换为0，这个1后面怎么放数字，都会比n小，`res = dp[i-1][0]+d[i-1][1]`，如果有连续的1，那么就返回`res`  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_12_color_FFFFFF_t_70_g_se_x_16]

代码

int dp[32][2];
    void getdp(){ 
        int i;
        dp[0][0] = 1;
        dp[1][1] = 1;
        dp[1][0] = 1;
        for(i=2;i<32;i++){ 
            dp[i][0] = dp[i-1][0]+dp[i-1][1];
            dp[i][1] = dp[i-1][0];
        }
    }
    
    int findIntegers(int n) { 
        getdp();
        int k = 30;
        int res = 0;
        int pre = 0;
        while (k>=0) { 
            if(n&(1<<k)){ 
                res = res + dp[k][0]+dp[k][1];
                if(pre){ 
                    return res;
                }
                pre = 1;
            }
            else pre = 0;
            k--;
        }
        return res+1;//未出现连续的1，那么其本身也是一个合法的数
        
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a33b634175714fd08c4c5d6d3dc6a7a6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f9bb56a8c98f487c8f9cacb865267d23.png