[编程题]字符串中找出连续最长的数字串

链接：https://www.nowcoder.com/questionTerminal/bd891093881d4ddf9e56e7cc8416562d?orderByHotValue=0&page=1&onlyReference=false 来源：牛客网

读入一个字符串str，输出字符串str中的连续最长的数字串

输入描述:

个测试输入包含1个测试用例，一个字符串str，长度不超过255。

输出描述:

在一行内输出str中里连续最长的数字串。

示例1

输入

abcd12345ed125ss123456789

输出

123456789

思路1： 利用常规手段，从起始位置开始寻找，找到数字串之后存下来，和保存的最长数字串长度进行比较，保留最大的，直到超过字符串的size。代码较为简单，就不贴出来了。

思路2：利用动态规划实现

开辟二维数组进行存放当前字符串中最长数字串的个数，找到最长的数字串之后将其截取出来。

代码及注释如下：

#include <iostream> #include <vector> using namespace std; int main() { string s; while (getline(cin,s)) { int len = s.size(); vector<vector<int>> vv; vv.resize(len); for (int i = 0; i<len; i++) { vv[i].resize(len); } //第一个字符是数字就将其标记为1，否则是0 if (isdigit(s[0])) vv[0][0] = 1; else vv[0][0] = 0; int max = vv[0][0]; int index = 0; //只走对角线 for (int i = 1; i<vv.size(); i++) { for (int j = i; j<i + 1; j++) { if (isdigit(s[i]))//当前字符是数字，那么截止当前位置的数字串长度就是1+前面的长度 vv[i][j] = vv[i - 1][j - 1] + 1; else//当前不是数字直接将该位置置0 vv[i][j] = 0; if (vv[i][j] > max)//每次看是否需要更新max { max = vv[i][j]; index = i - max + 1;//记录当前数字串的起始下标 } } } //截取最长的字符串 string ret = s.substr(index, max); cout << ret << endl; } return 0; }