LeetCode - 600 不含连续1的非负整数

心已赠人 2023-09-23 17:20 53阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[600. 不含连续1的非负整数 - 力扣（LeetCode）  
][600. _1_ - _LeetCode_]

### 题目描述 ###

给定一个正整数 `n` ，请你统计在 `[0, n]` 范围的非负整数中，有多少个整数的二进制表示中不存在 **连续的 1** 。

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:90px;">输入</td> 
   <td style="width:408px;">n = 5</td> 
  </tr> 
  <tr> 
   <td style="width:90px;">输出</td> 
   <td style="width:408px;">5</td> 
  </tr> 
  <tr> 
   <td style="width:90px;">说明</td> 
   <td style="width:408px;">下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示： 
    <ul> 
     <li>0 : 0</li> 
     <li>1 : 1</li> 
     <li>2 : 10</li> 
     <li>3 : 11</li> 
     <li>4 : 100</li> 
     <li>5 : 101</li> 
    </ul> 其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

*  `1 <= n <= 109`

### 题目解析 ###

本题可以通过数位DP求解，具体分析请先参考

[数位DP - 带3的数\_伏城之外的博客-CSDN博客][DP - _3_-CSDN]

再参考

[数位DP - 带49的数\_伏城之外的博客-CSDN博客][DP - _49_-CSDN]

### 算法源码 ###

/**
     * @param {number} n
     * @return {number}
     */
    var findIntegers = function(n) {
        const arr = Number(n).toString(2).split('').map(Number);
        const f = new Array(arr.length).fill(0).map(() => new Array(2));
    
        return dfs(0, true, f, arr, 0)
    };
    
    function dfs(pos, limit, f, arr, pre) {
        if(pos === arr.length) return 1;
    
        if(!limit && f[pos][pre]) return f[pos][pre];
    
        const max = limit ? arr[pos] : 1;
        let count = 0;
    
        for(let i=0; i<=max; i++) {
            if(i === 1 && pre === 1) continue;
            count += dfs(pos+1, limit && i === max, f, arr, i)
        }
    
        if(!limit) f[pos][pre] = count;
        return count;
    }

![75ce584d0a2f4599b3bcdfbe845fc145.png][]

[600. _1_ - _LeetCode_]: https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/
[DP - _3_-CSDN]: https://blog.csdn.net/qfc_128220/article/details/128128007
[DP - _49_-CSDN]: https://blog.csdn.net/qfc_128220/article/details/128139171?spm=1001.2014.3001.5501
[75ce584d0a2f4599b3bcdfbe845fc145.png]: https://img-blog.csdnimg.cn/75ce584d0a2f4599b3bcdfbe845fc145.png