【题目】
给定一个数组,数组中只包含0和1。请找到一个最长的子序列,其中0和1的数量是相同的。
例1:10101010 结果就是其本身。
例2:1101000 结果是110100
【解析】
这个题目,看起来比较简单,一些同学可能认为题目的描述符合动态规划的特征,然后就开始用动态规划解,努力找状态转移方程。这些同学的感觉,是很正确的。
但找状态转移方程,我们要对原来的数组进行变换一下。原来是0和1的串,我们将0都换为-1。
这样题目目标就变成,找到一个最长的子串,子串数字和是0。设原数组为A, DP[i]表示从0开始到i的子数组和。DP遍历一遍数组即可。
例1中的数组产生的DP为:
这个例子,最后一个值是0,并且长度是偶数位。直接满足了结果。
再看例子2:
5的位置为0,最长子串从0开始到5,长度为6。
上面这两个例子,所求的子串都是从头开始,如果不是从头开始,会是什么样的呢?看这个例子:1101100
通过观察上面的表格,我们可以得到,DP[0]==DP[6]==DP[2],DP[1]==DP[3]. 根据DP的定义,如果DP[i]==DP[j],i 一种方法,
我们用map保存DP的值到位置的映射,如下表:
我们最终的算法,要综合考虑最常穿是否从头开始的。 上面的这个思路,时间复杂度是O(n),空间复杂度也是O(n).
还有其他的思路,例如DP保存的是[0,i]的1的个数,那么DP[j] - DP[i] * 2 == j - i则表明A[i+1]...A[j]是一个满足条件的串,
找到j-i最大的,就是最终的结果,这个思路的时间复杂度为O(n^2),空间复杂度为O(n).
【代码】
#include <iostream>
#include <string.h>
#include <map>
using namespace std;
//最长的01字串
string MaxSubStr(string str){
int len = str.length();
int* dp = new int[len+1];
//dp下标从1开始
dp[1] = (str[0] - '0') == 1?1:-1;
for(int i = 2;i <= len;i++){
dp[i] = (str[i-1] - '0') == 1?1:-1;
dp[i] += dp[i-1];
}
//统计最大01字串
int start = 0,end = 0,max = 0,begin;
map<int,int> m;
for(int i = 1;i <= len;i++){
// 不同dp值原始起点
begin = m[dp[i]];
if(begin == 0 && dp[i] != 0){
m[dp[i]] = i;
}
else{
//更新最大子串
if(i - begin > max){
max = i - begin;
start = begin;
end = i;
}//if
}//if
}//for
return str.substr(start,max);
}
int main(){
string str("01101100001");
cout<<"Max:"<<MaxSubStr(str)<<endl;
return 0;
}
分享到:
相关推荐
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的非空字符串。 输出格式: 在...
java面试 java面试_leetcode面试java编程题解之第5题最长回文子串_java题解
最长公共子串的快速搜索算法 最长公共子串的快速搜索算法 最长公共子串的快速搜索算法
在随意给出的2个字符串中,找出它们共同的最长的子串。 【输入】 输入文件的第一行为一个整数2,接下来有2行,每行为一个字符串,每个字符串的长度均小于255。 【输出】 输出只有一行,即:共同的最长子串,若有多个...
最长回文子串
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和xyyxyyx。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应该...
c++ c++_c++编程基础之leetcode题解第5题最长回文子串
最长公共子串求解,有需要的可以下来参考……
查找两个字符串a,b中的最长的公共子串,并将结果输出
最长回文子串,算法还算可以,能运行通过,运行时间也不长
大整数计算器最长公共子串数据结构课设,沈阳工程学院
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
用定长顺序存储结构表示串: (1) 建立两个文本文件,分别存储串str1“hellohisgoodl”和串str“hellogdygoodl” (2) 输出两个串的最长公共子串“hello”和“goodl”; (3) 分析算法时间复杂度。
求两个字符数组的最长公共子串的问题,使用动态规划法,java语言实现。
输入一个字符串,将输出该字符串最长对称子串及其长度,很精巧的算法
自己编的,望大家指点!这是西工大期末考试的题目,做了好久才做出来
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
【华为OD机试真题2023JAVA】寻找符合要求的最长子串.html
leetcode刷题宝典