資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告