這個(gè)題目有個(gè)巨坑，那就是當(dāng)字符串s中最長(zhǎng)連續(xù)數(shù)字串可能不只一串，例如： 
下面給出三種方法： 方法一只能用求出最后一串最長(zhǎng)連續(xù)數(shù)字子串 方法二用動(dòng)態(tài)規(guī)劃，方法三利用c++標(biāo)準(zhǔn)庫(kù)里的vector容器（相當(dāng)于java中的ArrayList）求解。這兩種方法可得到完美解
方法一：
#include<iostream>#include<cstdio>#include<cstring>#define MAX 100using namespace std;void input(char arr[]){ int i=0; char c; while((c=getchar()) != '#') *(arr+(i++)) = c; *(arr+i) = '/0';}int main(){ char s[MAX]; cout<<"請(qǐng)輸入字符串s: "; input(s); int i, len=0, max_len=0, temp=0, end=0; for(i=0; i<=strlen(s); ++i) { //當(dāng)i==strlen(s)時(shí)，s[i]里存的是'/0'執(zhí)行else里的代碼,此時(shí)考慮的是最長(zhǎng)數(shù)字串在整個(gè)字符串的末尾的情況 if(s[i]>='0' && s[i]<='9') { temp = i; ++len; }else{ if(len > max_len) { end = temp; max_len = len; } len = 0; } } int start = end-max_len+1; for(i=start; i<=end; ++i) cout<<s[i]; cout<<"開(kāi)始位置為："<<start+1<<endl; return 0;}方法二：
#include<iostream>#include<cstdio>#include<cstring>#define MAX 100using namespace std;void input(char arr[]){ int i=0; char c; while((c=getchar()) != '#') *(arr+(i++)) = c; *(arr+i) = '/0';}int main(){ char s[MAX]; cout<<"請(qǐng)輸入字符串s: "; input(s); int i,j, max_len=0, s_len=strlen(s); int dp[s_len]={0}; //初始化動(dòng)態(tài)規(guī)劃的初值 if(s[0]>='0' && s[0]<='9') dp[0]=1; for(i=1; i<s_len; ++i) { //狀態(tài)轉(zhuǎn)移方程，根據(jù)前面已有的解推出當(dāng)前解 if(s[i]>='0' && s[i]<='9') dp[i] = dp[i-1]+1; else dp[i] = 0; } for(i=0; i<s_len; ++i) { if(dp[i]>max_len) max_len = dp[i]; } for(i=0; i<s_len; ++i) { //最長(zhǎng)數(shù)字字串可能不只一串 if(dp[i] == max_len) { for(j=i-max_len+1; j<=i; ++j) cout<<s[j]; cout<<"開(kāi)始位置為："<<(i-max_len+2)<<endl; } } return 0;}方法三：
#include<iostream>#include<string>#include<vector>#define MAX 200using namespace std;int main(){ vector<string> arr;//放置最長(zhǎng)數(shù)字字串 vector<int> index;//放置最長(zhǎng)數(shù)字字串的開(kāi)始位置 string input="", temp=""; cin>>input; int i, max_len=0; for(i=0; i<=input.length(); ++i) { if(input[i]>='0' && input[i]<='9') { temp += input[i]; }else{ if(temp.length() == max_len) { arr.push_back(temp); index.push_back(i-temp.length()+1); }else if(temp.length() > max_len) { //清空已經(jīng)不是最長(zhǎng)字串的子串和開(kāi)始位置 arr.clear(); index.clear(); arr.push_back(temp); index.push_back(i-temp.length()+1); max_len = temp.length(); } temp=""; } } for(i=0; i<arr.size(); ++i) cout<<arr[i]<<" 開(kāi)始位置為："<<index[i]<<endl; return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
