数据结构
网络
关系数据库管理系统 (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 次浏览
广告