给定一个正整数 n
,请你统计在 [0, n]
范围的非负整数中,有多少个整数的二进制表示中不存在 连续的 1 。
示例 1:
输入: n = 5
输出: 5
解释: 下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 其中,只有整数 3 违反规则(有两个连续的 1 ),其他 5 个满足规则。
示例 2:
输入: n = 1
输出: 2
示例 3:
输入: n = 2
输出: 3
class Solution { public int findIntegers(int n) { int m = Integer.SIZE - Integer.numberOfLeadingZeros(n); int[][] memo = new int[m][2]; for (int[] row : memo) { Arrays.fill(row, -1); // -1 表示没有计算过 } return dfs(m - 1, 0, true, n, memo); // 从高位到低位 } // pre 表示前一个比特位填的数 private int dfs(int i, int pre, boolean isLimit, int n, int[][] memo) { if (i < 0) { return 1; } if (!isLimit && memo[i][pre] >= 0) { // 之前计算过 return memo[i][pre]; } int up = isLimit ? n >> i & 1 : 1; int res = dfs(i - 1, 0, isLimit && up == 0, n, memo); // 填 0 if (pre == 0 && up == 1) { // 可以填 1 res += dfs(i - 1, 1, isLimit, n, memo); // 填 1 } if (!isLimit) { memo[i][pre] = res; // 记忆化 } return res; } }
Comments NOTHING