600. Non-negative Integers without Consecutive Ones
Đề Bài
Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.
Example 1:
Input: n = 5 Output: 5 Explanation: Here are the non-negative integers <= 5 with their corresponding binary representations: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.
Example 2:
Input: n = 1 Output: 2
Example 3:
Input: n = 2 Output: 3
Constraints:
1 <= n <= 109
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
C++
0600-non-negative-integers-without-consecutive-ones.cpp
int memo[32][2][2];
string tmp;
class Solution {
private:
string s;
int sz;
public:
int dp(int i, int state, int is_one) {
if (i == sz) {
// cout << tmp << '\n';
return 1;
}
if (memo[i][state][is_one] != -1) {
return memo[i][state][is_one];
}
int ans = 0;
int limit_number = state ? (s[i] - '0') : 1;
for (int d = 0; d <= limit_number; ++d) {
if (is_one && d == 1) {
continue;
}
// tmp += (d + '0');
ans += dp(i + 1, state && (d == limit_number), d == 1);
// tmp.pop_back();
}
return memo[i][state][is_one] = ans;
}
int findIntegers(int n) {
// dp(i_current, state, is_one)
while (n) {
s += (n & 1) + '0';
n >>= 1;
}
reverse(s.begin(), s.end());
sz = s.size();
memset(memo, -1, sizeof(memo));
// cout << s << '\n';
return dp(0, 1, 0);
}
};
Python
0600-non-negative-integers-without-consecutive-ones.py
class Solution:
def findIntegers(self, n: int) -> int:
nums = []
while n > 0:
nums.append(n % 2)
n //= 2
if len(nums) == 0:
nums.append(0)
nums = nums[::-1]
sz = len(nums)
@cache
def dp(i, tight, prev):
if i == sz:
return 1
limit = nums[i] if tight else 1
limit += 1
ans = 0
for d in range(limit):
if d == 1 and prev == 1:
continue
newTight = tight and d == nums[i]
ans += dp(i + 1, newTight, d)
return ans
return dp(0, True, 0)