数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中无连续1的非负整数
假设我们有一个正整数n。我们必须找到小于或等于n的非负整数。约束条件是二进制表示中不包含连续的1。因此，如果输入为7，则答案为5，因为5的二进制表示为101。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数convert()，它将接收n，
- ret := 空字符串
- 当n不为零时，执行：
- ret := ret + (n mod 2)
- n := n右移1位
- 返回ret
- 从主方法中执行以下操作：
- bits := 调用函数convert(num)
- n := bits的长度
- 定义一个大小为n的数组ones，定义一个大小为n的数组zeroes
- ones[0] := 1, zeroes[0] := 1
- for i := 1 to n-1
- zeroes[i] := zeroes[i - 1] + ones[i - 1]
- ones[i] := zeroes[i - 1]
- ret := ones[n - 1] + zeroes[n - 1]
- for i := n - 2 to 0
- if bits[i] == '0' and bits[i + 1] == '0', then
- ret := ret - ones[i]
- else if bits[i] == '1' and bits[i + 1] == '1', then
- 退出循环
- if bits[i] == '0' and bits[i + 1] == '0', then
- 返回ret
让我们来看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string convert(int n){
string ret = "";
while(n){
ret += (n % 2) + '0';
n >>= 1;
}
return ret;
}
int findIntegers(int num) {
string bits = convert(num);
int n = bits.size();
vector <int> ones(n);
vector <int> zeroes(n);
ones[0] = zeroes[0] = 1;
for(int i = 1; i < n; i++){
zeroes[i] = zeroes[i - 1] + ones[i - 1];
ones[i] = zeroes[i - 1];
}
int ret = ones[n - 1] + zeroes[n - 1];
for(int i = n - 2; i >= 0; i--){
if(bits[i] == '0' && bits[i + 1] == '0') ret -= ones[i];
else if(bits[i] == '1' && bits[i + 1]== '1') break;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findIntegers(7));
}输入
7
输出
5
更新于：2020年6月1日
279 次浏览
广告