資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中0和1片段的最大長度
問題陳述
給定一個由1和0組成的字串。任務是找到字串片段的最大長度，使得每個片段中1的個數大於0。
示例
如果輸入字串是“10111000001011”，答案將是12，如下所示：
- 第一個片段長度為7 10111000001011
- 第二個片段長度為5 10111000001011
- 總長度是（片段1 + 片段2）的長度 = (7 + 5) = 12
演算法
- 如果 start == n，則返回 0。
- 從 start 到 n 迴圈，計算到 n 的每個子陣列。
- 如果字元是 1，則遞增 1 的計數，否則遞增 0 的計數。
- 如果 1 的計數大於 0，則遞迴呼叫索引 (k+1)（即下一個索引）的函式，並新增剩餘長度，即 k-start+1。
- 否則，只遞迴呼叫下一個索引 k+1 的函式。
- 返回 dp[start]。
示例
#include <bits/stdc++.h>
using namespace std;
int getSegmentWithMaxLength(int start, string str, int n, int dp[]) {
if (start == n) {
return 0;
}
if (dp[start] != -1) {
return dp[start];
}
dp[start] = 0;
int one = 0;
int zero = 0;
int k;
for (k = start; k < n; ++k) {
if (str[k] == '1') {
++one;
} else {
++zero;
} if (one > zero) {
dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp) + k - start + 1);
} else {
dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp));
}
}
return dp[start];
}
int main() {
string str = "10111000001011";
int n = str.size();
int dp[n + 1];
memset(dp, -1, sizeof(dp));
cout << "Maximum length of segment = " << getSegmentWithMaxLength(0, str, n, dp) << endl;
return 0;
}輸出
編譯並執行上述程式時，會生成以下輸出：
Maximum length of segment = 12
更新於：2020年1月10日
179 次瀏覽
廣告