資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究二進位制字串中零和一的最大差值 - (O(n) 時間複雜度) C++ 實現
給定任務是從給定的二進位制字串中找到一個子字串，然後找到零和一的數量之間的最大差值。
現在讓我們用一個例子來理解我們必須做什麼 -
輸入
str = “10010110”
輸出
2
解釋
在從位置 1 到 4 的子陣列（“0010”）中，零和一的差值 = 3 – 1 = 2，這是可以找到的最大值。
輸入
str = “00000”
輸出
5
下面程式中使用的方案如下
在 main() 函式中建立一個字串 str 來儲存二進位制字串。 同時宣告一個數組 int arr[str.length()+1];
使用 memset(arr,0,sizeof(arr)); 將 arr[] 的所有元素設定為 0。
迴圈從 j = 1 到 j<= str.length()
檢查 if(memset(arr,0,sizeof(arr)), 如果是，則將 arr[j] 設定為 max(arr[j-1]-1,-1);
否則將 arr[j] 設定為 max(arr[j-1]+1,1);
在迴圈外部，使用 *max_element(arr+1, arr+str.length()+1); 列印最大值。
示例
#include<bits/stdc++.h>
using namespace std;
int main(){
string str = "10010110";
int arr[str.length()+1];
memset(arr,0,sizeof(arr));
for(int j=1;j<=str.length();j++){
if(str[j-1]=='1')
arr[j]=max(arr[j-1]-1,-1);
else
arr[j]=max(arr[j-1]+1,1);
}
cout<<*max_element(arr+1,arr+str.length()+1);
return 0;
}輸出
2
更新於: 2020年8月4日
116 次瀏覽
廣告