LeetCode 600. Non-negative Integers without Consecutive Ones    原题链接    困难

作者： 作者的头像   wzc1995 ,  2018-07-31 22:47:51 ,  所有人可见 ,  阅读 1809

3


1

题目描述

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含连续的 1 的个数。

样例

输入: 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

注意

  • $1 \le n \le 10^9$

算法

(数位统计) $O(\log n)$
  1. 按照数位统计的一般思路，从二进制的高位向底位，每次保证作为答案的数字不能超过 n。
  2. 首先预处理出长度为 i 的二进制串中，以 0 作为最高位且符合条件的二进制串的个数。这里从低位开始往高位递推，递推方程为 $f(i) = f(i - 1) + f(i - 2)$，其中，$f(0) = f(1) = 1$。$f(0)$ 无具体含义。
  3. 从高到底遍历 n 的二进制位，设计布尔变量 last_one，表示 n 的二进制位中上一位是否为 1，初始为 false。
  4. 若第 i 位为 1，累计答案 $f(i + 1)$，然后考察 last_one，若 last_one 为 true，则此时统计工作已经结束，直接返回 ans；否则，设置 last_one = true。
  5. 若第 i 位为 0，设置 last_one = false。
  6. 最终返回 ans + 1，这里的加 1 加的是 n 本身作为合法的答案。

下面以例子 10101100 为例分析：

  1. 第 7 位是 1，则答案累计 f(8)，这里累计的是 00000000 - 01111111的答案个数；此时 last_one = false，然后设置 last_one = true。
  2. 第 6 位是 0，设置 last_one = false。
  3. 第 5 位是 1，则答案累计 f(6)，这里累计的是 10000000 - 10011111的答案个数；此时 last_one = false，然后设置 last_one = true
  4. 第 4 位是 0，设置 last_one = false。
  5. 第 3 位是 1，则答案累计 f(4)，这里累计的是 10100000 - 10100111的答案个数。此时 last_one = false，然后设置 last_one = true。
  6. 第 2 位是 1，则答案累计 f(3)，这里累计的是 10101000 - 10101011的答案个数。此时 last_one = true，无需再进行之后的统计，因为第 2 位不能放置 1，所以返回答案为 f(3) + f(4) + f(6) + f(8) = 55。

时间复杂度

  • 只涉及到对二进制位的操作，故时间复杂度为 $O(\log n)$。

C++ 代码

class Solution {
public:
    int findIntegers(int num) {
        vector<int> f(31);
        f[0] = f[1] = 1;
        for (int i = 2; i < 31; i++)
            f[i] = f[i - 1] + f[i - 2];

        bool last_one = false;
        int ans = 0;
        for (int i = 29; i >= 0; i--) {
            if (num & (1 << i)) {
                ans += f[i + 1];
                if (last_one)
                    return ans;
                last_one = true;
            }
            else
                last_one = false;
        }
        return ans + 1;
    }
};

1 评论

用户头像
JasonSun   2019-12-16 11:10         踩      回复

相似的想法， 但是用递归实现的。

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };


class Solution {
 public:
  int findIntegers(int num) {

    const vector<int> binary = [&](vector<int> self = {}) {
      string s = (std::bitset<32>(num)).to_string();
      std::transform(begin(s), end(s), std::back_inserter(self), [&](auto &x) { return x - '0'; });
      std::reverse(begin(self), end(self));
      while(self.back() == 0) self.pop_back();
      return self;
    }();

    auto f = rec([&, memo = array<optional<int>, 32> {}](auto &&f, int i) mutable -> int {
      if (memo[i]) return *memo[i];
      return *(memo[i] = [&]{
        if (i == 0)      return 2;
        else if (i == 1) return 3;
        else return f(i - 1) + (i - 2 >= 0 ? f(i - 2) : 0);
      }());
    });

    auto g = rec([&, memo = array<optional<int>, 32> {}](auto&& g, int i) mutable -> int {
      if (memo[i]) return *memo[i];
      return *(memo[i] = [&]{
        if (i == 0)
          return binary[i] == 0 ? 1 : 2;
        else {
          if (binary[i] == 1 and binary[i - 1] == 0)
            return f(i - 1) + (i - 2 >= 0 ? g(i - 2) : 1);
          else if (binary[i] == 1 and binary[i - 1] == 1)
            return f(i - 1) + (i - 2 >= 0 ? f(i - 2) : 1);
          else if (binary[i] == 0)
            return g(i - 1);
          else throw std::domain_error("unmatched case");
          }
      }());
    });

    return g(size(binary) - 1);
  }
};