题解：
考察点：贪心，动态规划，单调栈
常见错误：
如果除去输入只实现一个类的话，这是一个很经典的面试题目，很多同学在面试中都遇到过。但是因为这里的输入跟大家熟知的不太相同，很多同学拿着无从下手。其实面对这种没有给定个数的输入数据，有很多读入方法，其中最常见的就是当成字符串，以按照一行来读入，然后对字符串进行解析。但是最快的读入方法还是推荐使用
。
每次读入 1 byte 的数据，并将其转换为
类型的函数，且速度很快，可以用“读入字符——转换为整型”来代替缓慢的读入。同时在读入中修改
只对数字有效，而略过","，我们一般称这种方法为读入优化，有关于更多的知识，可以上OI-wiki去学习。
方法一：
使用一个数组记录给每个学生的糖果数。初始时，每个学生都分到
个糖果，对于当前的学生，如果评分比前一个学生大，但是
值却比前一个学生少，则把
值改为前一个学生的
值加
，同理对于后一个学生也是，如果评分比后一个学生大，
值却比后一个学生小，改为后一个学生的
值加
。同时设置一个变量
，检测
值是否满足要求，如果不满足进行新一轮的迭代，如果满足，则停止。因为对于每个元素，在极限状态下都可能被遍历
次，所以时间复杂度是
，空间复杂度是
#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
inline int read(){ //读入优化
int x=0,f=1;char ch=getchar();
if(!((ch>='0'&&ch<='9')||(ch==',')||(ch=='\n')||(ch=='\t'))) return INT_MIN;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,a[maxn],dp[maxn];
int main()
{
int x;
while(1){
x=read();
if(x==INT_MIN) break;
a[++n]=x;
}
for(int i=1;i<=n;i++) dp[i]=1;
bool flag=true;
while(flag){
flag=false;
for(int i=1;i<=n;i++){
if(i!=n&&a[i]>a[i+1]&&dp[i]<=dp[i+1]){
dp[i]=dp[i+1]+1;
flag=true;
}
if(i!=1&&a[i]>a[i-1]&&dp[i]<=dp[i-1]){
dp[i]=dp[i-1]+1;
flag=true;
}
}
}
int sum=0;
for(int i=1;i<=n;i++) sum+=dp[i];
printf("%d\n",sum);
return 0;
} 方法二：
基于上述方法做进一步优化，上述方法对于每个位置i同时考虑了左邻居和右邻居，但是其实可以将左邻居和右邻居分开来考虑。同样用数组记录给每个学生的糖果数。初始时，每个学生都分到1个糖果，接着从前往后遍历，找到分数比左邻居高且糖果数小于等于左邻居的学生，更新
。然后从后往前遍历，找到分数比右邻居高，且
值不大于右邻居的，更新
值为
。因为只需要扫
遍，时间复杂度为
，空间复杂度为
#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
inline int read(){ //读入优化
int x=0,f=1;char ch=getchar();
if(!((ch>='0'&&ch<='9')||(ch==',')||(ch=='\n')||(ch=='\t'))) return INT_MIN;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,a[maxn],dp[maxn];
int main()
{
int x;
while(1){
x=read();
if(x==INT_MIN) break;
a[++n]=x;
}
for(int i=1;i<=n;i++) dp[i]=1;
for(int i=2;i<=n;i++){
if(a[i]>a[i-1]) dp[i]=dp[i-1]+1;
}
for(int i=n-1;i>=1;i--){
if(a[i]>a[i+1]&&dp[i]<=dp[i+1]) dp[i]=dp[i+1]+1;
}
int sum=0;
for(int i=1;i<=n;i++) sum+=dp[i];
printf("%d\n",sum);
return 0;
} 题解：
考察点： 区间合并，双指针
方法一：暴力
一般来说，暴力都是解决问题最直观，也是最容易被同学们想到的方法。题中明确说明每个字母只能在一个子串中出现，因此必须保证子串内的每个字母在字符串中第一次出现的位置到最后一次出现的位置都位于区间中。设置两个指针和
，表示区间的开始位置和结束位置。当访问到字符串中位置
时，如果
不超过
，则比较在字符串中结束位置和
的大小，如果大于
，则把
修改为
的结束位置；如果
大于
，则记录区间
的长度。因为对于每个位置都需要向后找寻结束位置，一共有
个位置需要找寻，时间复杂度是
#include "bits/stdc++.h"
using namespace std;
string s;
int main()
{
cin>>s;
int len=s.length();
int Start=0,End=0;
for(int i=0;i<len;i++){
if(s[i]==s[0]) End=i;
}
vector<int>v;
for(int i=0;i<len;i++){
if(i<=End){
for(int j=i+1;j<len;j++){
if(s[i]==s[j]) End=max(End,j);
}
}else{
v.push_back(End-Start+1);
Start=i,End=i;
for(int j=i;j<len;j++){
if(s[j]==s[i]) End=j;
}
}
}
v.push_back(End-Start+1);
for(int i=0;i<v.size();i++){
if(i==v.size()-1) printf("%d\n",v[i]);
else printf("%d ",v[i]);
}
return 0;
} 方法二：区间合并
更进一步，可以对上述方法做出优化。设置两个数组和
，分别记录每个字母在字符串中的开始位置和结束位置。其余流程跟方法一相同，这样在维护每个字母的开始位置和结束位置时，不用对整个字符串做遍历，通过空间换时间的方法，将时间复杂度降到
#include "bits/stdc++.h"
using namespace std;
const int maxn=30;
int l[maxn],r[maxn];
string s;
int main()
{
memset(l,-1,sizeof(l));
memset(r,-1,sizeof(r));
cin>>s;
int len=s.length();
for(int i=0;i<len;i++){
int tmp=s[i]-'a';
if(l[tmp]==-1){
l[tmp]=i,r[tmp]=i;
}else{
r[tmp]=i;
}
}
int Start=l[s[0]-'a'],End=r[s[0]-'a'];
vector<int>v;
for(int i=0;i<len;i++){
int tmp=s[i]-'a';
if(i>End){
v.push_back(End-Start+1);
Start=i;
End=r[tmp];
}else{
End=max(End,r[tmp]);
}
}
v.push_back(End-Start+1);
for(int i=0;i<v.size();i++){
if(i==v.size()-1) printf("%d\n",v[i]);
else printf("%d ",v[i]);
}
return 0;
} 题解:
考察点：深度优先搜索，回溯，剪枝
易错点：
字符串中的字母有重复，直接使用全排列生成的字符串会有重复，需要通过剪枝或者等手段去重。
方法一：回溯+去重
回溯法是一种深度优先搜索中常用的一种手段，基本思想是首先按选设定条件进行深度搜索，当探索到某一步时，发现原先搜索的路径并不满足，就退回上一步重新选择。在全排列问题中，首先设置一个指针，代表当前生成的字符串中的元素个数，设置一个数组
表示每个位置是否被访问过，然后按照从前往后的顺寻，选择未被访问过的字母进入字符串，每次被选择的位置
把标记为已访问，在进行深度优先搜索之后再将标记释放，进行回溯。注意，因为字母有重复，因此生成的全排列也会有重复，需要进行去重。
#include "bits/stdc++.h"
using namespace std;
string s;
int vis[10];
void dfs(set<string>&res,string ans,vector<int> num,int pos){
if(pos==num.size()){
res.insert(ans);
}
for(int i=0;i<num.size();i++){
if(!vis[i]){
vis[i]=1;
ans.push_back(num[i]+'a');
dfs(res,ans,num,pos+1);
vis[i]=0;
ans.pop_back();
}
}
}
int main()
{
cin>>s;
vector<int>num;
for(int i=0;i<s.length();i++) num.push_back(s[i]-'a');
set<string>res;
string ans="";
dfs(res,ans,num,0);
int tmp=0;
int len=res.size();
for(auto s:res){
++tmp;
if(tmp==1){
cout<<"["<<s<<", ";
}else if(tmp==len){
cout<<s<<"]"<<endl;
}else{
cout<<s<<", ";
}
}
return 0;
} 方法二：回溯+剪枝
可以对上述方法进行改进，由于有重复字母存在，可以考虑生成答案的过程中对重复字母进行剪枝。对于两个重复元素，在全排列中交换其位置不会生成新的排列，基于这个思想，首先会对字母进行排序，这样确保重复元素相邻。那么假设当前位置为，在枚举排列的时候，保证当前位置的字母和之前的一样，并且之前的字母没有被标记，则可以把这种情况剪枝掉。
#include "bits/stdc++.h"
using namespace std;
string s;
int vis[10];
void dfs(vector<string>&res,string ans,vector<int> num,int pos){
if(pos==num.size()){
res.push_back(ans);
}
for(int i=0;i<num.size();i++){
if(!vis[i]){
if(i>0&&num[i]==num[i-1]&&!vis[i-1]) continue;
vis[i]=1;
ans.push_back(num[i]+'a');
dfs(res,ans,num,pos+1);
vis[i]=0;
ans.pop_back();
}
}
}
int main()
{
cin>>s;
vector<int>num;
for(int i=0;i<s.length();i++) num.push_back(s[i]-'a');
sort(num.begin(),num.end());
vector<string>res;
string ans="";
dfs(res,ans,num,0);
for(int i=0;i<res.size();i++){
if(i==0){
cout<<"["<<res[i]<<", ";
}else if(i==res.size()-1){
cout<<res[i]<<"]"<<endl;
}else{
cout<<res[i]<<", ";
}
}
return 0;
} 题解：
考察点： 深度优先搜索，动态规划
易错点：
方格的大小为，但是格点数却为
方法一：深度优先搜索
选用深度优先搜索是解决这类题目最直观的思路，因为格点只能往下走或者往右走，所以对于方格中位置，一定只能由它的上方位置和左边位置走过来。那么令
为走到位置
的方案数，则根据加法原理，它一定由左边位置的方案数加上上方位置的方案数。同时记得处理一下边界情况，也就是递归结束的条件，对于位置
，它的方案数一定为1，而对于越界的位置，方案数一定为0
#include "bits/stdc++.h"
using namespace std;
int n,m;
int dfs(int x,int y){
if(x==0||y==0||x==n+1||y==m+1) return 0;
if(x==1||y==1) return 1;
return dfs(x-1,y)+dfs(x,y-1);
}
int main()
{
scanf("%d%d",&n,&m);
++n,++m;
printf("%d\n",dfs(n,m));
return 0;
} 方法二：动态规划
方法一虽然很直观，但时间复杂度很高，是指数级的时间复杂度，原因是因为很多中间结果都要重新计算，如果能将中间结果存下来，而不需要每次使用的时候都要重新去计算，则可以大大降低复杂度。动态规划就是基于这样一种思想，令表示坐标
的方案数，则根据方法一的推理过程，
。经过空间换时间优化之后，时间复杂度降为
#include "bits/stdc++.h"
using namespace std;
const int maxn=12;
int dp[maxn][maxn];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
++n,++m;
dp[1][1]=1;
for(int i=2;i<=m;i++) dp[1][i]=1;
for(int i=2;i<=n;i++) dp[i][1]=1;
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
printf("%d\n",dp[n][m]);
return 0;
} 题解：
考察点： 深度优先搜索，字典树，剪枝
易错点：
本题的输入不是直接可用的，需要对输入进行字符串解析，同时由于输入带有空格，如果直接用
会无法读入，建议使用
按行进行读入。对于输入的解析，建议使用标记法，设置一个变量
，当处于有效区域时，把
标记为
，当处于无效区域时，把
标记为
。这样保证有效部分能够很好的被解析出来。
本题的输出结果是按照字典序从大到小降序输出的。
方法一：深度优先搜索+剪枝
这题最直观的想法就是，对于字符串
中每个位置
，如果其前缀在集合
中能找到，其可以以它为起点，往后找寻剩余部分是否在集合中，如果在集合中，则可以继续往后递归。这里加入一个剪枝，
表示从
到
是否满足条件，如果在进行
以后发现剩余部分并没有满足条件的字符串，则可以进行剪枝，说明枚举这个位置已经没有意义了
#include "bits/stdc++.h"
using namespace std;
const int maxn=1e3+10;
int vis[maxn];
void Input(string &str,vector<string>&dict){ //读入数据
string s,s1;
getline(cin,s1);
getline(cin,s);
int flag=0;
for(int i=0;i<s1.length();i++){
if(!flag){
if(s1[i]=='\"') flag=1;
continue;
}else{
if(s1[i]=='\"'){
flag=0;
}else{
str+=s1[i];
}
}
}
flag=0;
string res="";
for(int i=0;i<s.length();i++){
if(!flag){
if(s[i]=='\"') flag=1;
continue;
}else{
if(s[i]=='\"'){
flag=0;
dict.push_back(res);
res="";
}else{
res+=s[i];
}
}
}
}
void dfs(string str,vector<string>dict,vector<string>&res,int pos,string t){
if(pos==str.length()){
res.push_back(t.substr(0,t.size()-1));
}
for(int i=pos;i<str.length();i++){
string word=str.substr(pos,i-pos+1);
if(find(dict.begin(),dict.end(),word)!=dict.end()&&!vis[i+1]){
t.append(word).append(" ");
int h=res.size();
dfs(str,dict,res,i+1,t);
if(h==res.size()) vis[i+1]=1;
t.resize(t.size()-word.size()-1);
}
}
}
int main()
{
string str="";
vector<string>dict;
Input(str,dict);
memset(vis,0,sizeof(vis));
vector<string>res;
string t="";
dfs(str,dict,res,0,t);
sort(res.begin(),res.end());
if(res.size()==0){
cout<<"[]"<<endl;
}else if(res.size()==1){
cout<<"["<<res[0]<<"]"<<endl;
}else{
for(int i=res.size()-1;i>=0;i--){
if(i==res.size()-1){
cout<<"[";
cout<<res[i];
}else{
cout<<", "<<res[i];
if(i==0) cout<<"]"<<endl;
}
}
}
return 0;
} 方法二：字典树优化
在上述算法中，每次需要在集合中查询单词是否存在，如果集合很小还好，当集合非常大的时候，复杂度就会变得很高。可以引入字典树来进行优化。字典树由被称为前缀树，能在O(单词长度)的时间复杂度内查询单词是否存在与集合中，极大提升了查询的效率。关于字典树，网上资料很多，这里为同学们提供一份比较好用的模板
#include "bits/stdc++.h"
using namespace std;
const int maxn=1e3+10;
int vis[maxn];
int trie[maxn][26],tot;
bool End[maxn];
void insert(string str){
int len=str.length(),p=1;
for(int k=0;k<len;k++){
int ch=str[k]-'a';
if(trie[p][ch]==0) trie[p][ch]=++tot;
p=trie[p][ch];
}
End[p]=true;
}
bool search(string str){
int len=str.length(),p=1;
for(int k=0;k<len;k++){
p=trie[p][str[k]-'a'];
if(p==0) return false;
}
return End[p];
}
void Input(string &str){ //读入数据
string s,s1;
getline(cin,s1);
getline(cin,s);
int flag=0;
for(int i=0;i<s1.length();i++){
if(!flag){
if(s1[i]=='\"') flag=1;
continue;
}else{
if(s1[i]=='\"'){
flag=0;
}else{
str+=s1[i];
}
}
}
flag=0;
string res="";
for(int i=0;i<s.length();i++){
if(!flag){
if(s[i]=='\"') flag=1;
continue;
}else{
if(s[i]=='\"'){
flag=0;
insert(res);
res="";
}else{
res+=s[i];
}
}
}
}
void dfs(string str,vector<string>&res,int pos,string t){
if(pos==str.length()){
res.push_back(t.substr(0,t.size()-1));
}
for(int i=pos;i<str.length();i++){
string word=str.substr(pos,i-pos+1);
if(search(word)&&!vis[i+1]){
t.append(word).append(" ");
int h=res.size();
dfs(str,res,i+1,t);
if(h==res.size()) vis[i+1]=1;
t.resize(t.size()-word.size()-1);
}
}
}
int main()
{
string str="";
Input(str);
memset(vis,0,sizeof(vis));
vector<string>res;
string t="";
dfs(str,res,0,t);
sort(res.begin(),res.end());
if(res.size()==0){
cout<<"[]"<<endl;
}else if(res.size()==1){
cout<<"["<<res[0]<<"]"<<endl;
}else{
for(int i=res.size()-1;i>=0;i--){
if(i==res.size()-1){
cout<<"[";
cout<<res[i];
}else{
cout<<", "<<res[i];
if(i==0) cout<<"]"<<endl;
}
}
}
return 0;
} 题解：
考察点： 暴力
易错点：
从位置
开始，长度为
的字符串为
的大小可能为0
解法：
由于每次选取长度为n的字符串输出，同时结合易错点中所述，需要枚举
的值为
，建议使用
中
类里面的
函数输出结果比较方便，该函数第一个参数为子串开始位置，第二个参数为子串长度。注意当
的值大于
或者小于
时不合理
#include "bits/stdc++.h"
using namespace std;
string s;
int n;
int main()
{
cin>>s>>n;
int len=s.length();
if(n>len||n<1){
cout<<"-1"<<endl;
}else{
for(int i=0;i+n<=len;i++){
cout<<s.substr(i,n)<<" ";
}
cout<<endl;
}
return 0;
} 题解：
考察点： 链表，迭代，递归
易错点：
题目只给定链表，并不确定链表中元素的个数。很多同学不会读入。因为输入由整数和空格构成，建议当成字符串读入，使用
按行读入，因为
无法处理空格。同时推荐使用
类对输入进行解析
很多同学不会写链表，其实链表的表示非常简单，可以定义为由值
和指向下一个结点指针
构成的结构体，同时C++ 中最好使用构造函数为
和
赋上初值
方法一：迭代
当链表和
均不为空时，分别设置两个指针指向
和
，当
中元素较小时，选取
中的元素，并把
的指针后移；当
中元素较小时，选取
中元素，并把指针后移。此时，如果
还有剩余，将排序好的链表直接指向
；如果
还有剩余，则将排序好的链表指向
#include "bits/stdc++.h"
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x): val(x),next(NULL){}
};
ListNode* merge(ListNode *l1,ListNode *l2){
if(l1==NULL) return l2;
if(l2==NULL) return l1;
ListNode *q=new ListNode(0);
ListNode *p=q;
while(l1&&l2){
if(l1->val<l2->val){
p->next=l1;
l1=l1->next;
}else{
p->next=l2;
l2=l2->next;
}
p=p->next;
}
if(l1){
p->next=l1;
}
if(l2){
p->next=l2;
}
return q->next;
}
int main()
{
ListNode *l=new ListNode(0);
ListNode *l1=l;
int x,n=0;
string s;
getline(cin,s);
stringstream ss1(s);
while(ss1>>x){
l1->next=new ListNode(x);
l1=l1->next;
++n;
}
s="";
getline(cin, s);
stringstream ss2(s);
ListNode *r=new ListNode(-1);
ListNode *l2=r;
while(ss2>>x){
l2->next=new ListNode(x);
l2=l2->next;
++n;
}
ListNode *res=merge(l->next,r->next);
for(int i=0;i<n;i++){
if(i==n-1){
printf("%d\n",res->val);
}else{
printf("%d ",res->val);
}
res=res->next;
}
return 0;
} 方法二：递归
当和
为空时，是递归的终止条件，因为此时只需要返回另一个链表即可。否则需要判断
和
哪一个头元素更小，然后递归地将更小那个视为下一个添加到结果里的值。
#include "bits/stdc++.h"
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x): val(x),next(NULL){}
};
ListNode* merge(ListNode *l1,ListNode *l2){
if(l1==NULL) return l2;
if(l2==NULL) return l1;
if(l1->val<l2->val){
l1->next=merge(l1->next,l2);
return l1;
}else{
l2->next=merge(l1,l2->next);
return l2;
}
}
int main()
{
ListNode *l=new ListNode(0);
ListNode *l1=l;
int x,n=0;
string s;
getline(cin,s);
stringstream ss1(s);
while(ss1>>x){
l1->next=new ListNode(x);
l1=l1->next;
++n;
}
s="";
getline(cin, s);
stringstream ss2(s);
ListNode *r=new ListNode(-1);
ListNode *l2=r;
while(ss2>>x){
l2->next=new ListNode(x);
l2=l2->next;
++n;
}
ListNode *res=merge(l->next,r->next);
for(int i=0;i<n;i++){
if(i==n-1){
printf("%d\n",res->val);
}else{
printf("%d ",res->val);
}
res=res->next;
}
return 0;
} 
京公网安备 11010502036488号