動機

這題會不會太過分

Problem

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 = 5Output: 5Explanation:Here are the non-negative integers <= 5 with their corresponding binary representations:0 : 01 : 12 : 103 : 114 : 1005 : 101Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

Example 2:

Input: n = 1Output: 2

Example 3:

Input: n = 2Output: 3

 

Constraints:

  • 1 <= n <= 109

Sol

原本是給一個dp，用奇偶去刷出後面違法的數字，但要alloc很大的mem，大概到10^8就很慢，10^9直接死亡

class Solution {
public:
    int findIntegers(int n) {
        int ret = 1;
        bool* dp = new bool[n+1];
        memset(dp,0,sizeof(bool)*(n+1));
        for(auto i=1;i<=n;i++) {
            if(dp[i]) {
                for (auto now = (i << 1);now <= n;now <<= 1)
                    dp[now] = dp[now+1 < n+1 ? now+1 : now] = 1;
            } else {
                if (i%2 == 1){
                    for (auto now = (i << 1)|1;now <= n;now = ((now<<1)|1))
                        dp[now] = 1;
                }
                ret++;
            }
        }
        return ret;
    }
};

假設f(n)是n位數的所有沒有連續1的總數

如果n是5，11111 ~ 00000 就會是

  • 10 111 ~ 10 000
    • f(3)
  • 0 1111 ~ 0 0000
    • f(4)

這兩種組合，11 111 ~ 11 000就會出事就不用考慮，01 111 ~ 01 000會被0 1111 ~ 0 0000包含

而這就是fib的遞迴模式

所以要做的是，從最高位往下加所有組合，同時看有沒有11出現，有就後面不用算了 順利走完代表數字本身是ok的，故回傳之前要加1

class Solution:
    def findIntegers(self, n: int) -> int:
        @cache
        def fib(n):
            if n == 0:
                return 1
            elif n == 1:
                return 2
            else:
                return fib(n-1)+fib(n-2)
        
        ret, pre0 = 0, False
        for k in reversed(range(32)):
            if (n & (1 << k)): # k+1 == 目前最高位長度
                ret += fib(k) 
                if pre0:
                    return ret
                else:
                    pre0 = True
            else:
                pre0 = False
        return ret+1 # 能跑出loop就是沒有Consecutive Ones