資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中二進位制字串中0和1的最大差值
給定的任務是從給定的二進位制字串中找到一個子字串，然後找到0和1數量之間的最大差值。
讓我們用一個例子來理解我們必須做什麼：
輸入
str = “100100110”
輸出
2
解釋
在從位置1到5的子陣列（“00100”）中，0和1之間的差值 = 4 – 1 = 3，這是可以找到的最大值。
輸入
str = “00000”
輸出
5
下面程式中使用的演算法如下：
在main()函式中，建立一個字串**str**來儲存二進位制字串。還初始化一個變數int size來儲存字串的**大小**，並將兩者都傳遞給Max()函式。
在Max()函式中，首先透過呼叫One()函式檢查所有元素是否都是1。
建立一個bool型別的One()函式，並在其中建立一個變數int O = 0。
迴圈從i = 0到i< str.size()，如果str[i] == 1，則將1新增到變數O中。
在迴圈外部，檢查if(O == size)。如果是，則返回true。
回到Max()函式，如果One()函式返回true，則返回-1作為答案。
否則繼續查詢長度。初始化一個數組int a[100] = {0}。
迴圈從i = 0到i< size，並設定a[i] = (str[i] == '0' ? 1 : -1)，以此方式檢查str的每個元素。
在迴圈外部，初始化另一個數組int arr[100][3]，並使用memset(arr, -1, sizeof arr)將其所有元素替換為-1，最後呼叫Length(a, str, size, 0, 0, arr)
在Length()函式中，首先檢查if (i >= size)，如果是，則表示字串結束，返回0。
然後檢查if (arr[i][s] != -1)。如果是，則表示狀態已計算，返回arr[i][s]。
然後檢查if(s == 0)。如果是，則返回arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), Length(a, str, size, i + 1, 0, arr));
否則返回arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), 0);
示例
#include <bits/stdc++.h>
using namespace std;
bool One(string str, int size){
int O = 0;
for (int i = 0; i < str.size(); i++)
O += (str[i] == '1');
return (O == size);
}
int Length(int a[], string str, int size,
int i, int s, int arr[][3]){
// If string is over.
if (i >= size)
return 0;
// If the already calculated.
if (arr[i][s] != -1)
return arr[i][s];
if (s == 0)
return arr[i][s] = max(a[i] +
Length(a, str, size, i + 1, 1, arr),
Length(a, str, size, i + 1, 0, arr));
else
return arr[i][s] = max(a[i] +
Length(a, str, size, i + 1, 1, arr), 0);
}
int Max(string str, int size){
// Checking if all elements are 1
if (One(str, size))
return -1;
// Finding length
int a[100] = { 0 };
for (int i = 0; i < size; i++)
a[i] = (str[i] == '0' ? 1 : -1);
int arr[100][3];
memset(arr, -1, sizeof arr);
return Length(a, str, size, 0, 0, arr);
}
// main function
int main(){
string str = "100100110";
int size = 9;
cout << Max(str, size);
return 0;
}輸出
3
257 次瀏覽
