基础算法题——估值一亿的AI核心代码（细节拉满）

雨点打透心脏的1/2处 2022-11-21 09:42 156阅读 0赞

#### [估值一亿的AI核心代码][AI]![AI][AI 1] ####

以上图片来自新浪微博。

本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是：

1、无论用户说什么，首先把对方说的话在一行中原样打印出来；  
2、消除原文中多余空格：把相邻单词间的多个空格换成 1 个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉；  
3、把原文中所有大写英文字母变成小写，除了 I；  
4、把原文中所有独立的 can you、could you 对应地换成 I can、I could—— 这里“独立”是指被空格或标点符号分隔开的单词；  
5、把原文中所有独立的 I 和 me 换成 you；  
6、把原文中所有的问号 ? 换成惊叹号 !；  
7、在一行中输出替换后的句子作为 AI 的回答。  
输入格式：  
输入首先在第一行给出不超过 10 的正整数 N，随后 N 行，每行给出一句不超过 1000 个字符的、以回车结尾的用户的对话，对话为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。

输出格式：  
按题面要求输出，每个 AI 的回答前要加上 AI: 和一个空格。

输入样例：  
6  
Hello ?  
Good to chat with you  
can you speak Chinese?  
Really?  
Could you show me 5  
What Is this prime? I,don 't know  
输出样例：  
Hello ?  
AI: hello!  
Good to chat with you  
AI: good to chat with you  
can you speak Chinese?  
AI: I can speak chinese!  
Really?  
AI: really!  
Could you show me 5  
AI: I could show you 5  
What Is this prime? I,don 't know  
AI: what Is this prime! you,don’t know

--------------------

这题说真的恶心，要考虑的情况较多，疯狂特判的感觉  
（菜是原罪…，请让我慢慢诉说其中细节吧）

#### 解题思路 ####

**用题目要求将原文转换为 AI 回答**  
①、题目要求消除原文中多余空格，把相邻单词间的多个空格换成 1 个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉。

**策略**：为了方便删除空格，这里我利用 stringstream 流对字符串以空格进行截取，得到每一个非空格的“单词”（包括一些奇怪的符号，但一定要是有效字符，这里也是一个坑）。

while(getline(ss, tmp, ' ')){ 
    		if(tmp[0]>32)	//保证dc中一定是有效字符
    			dc[x++]=tmp;
    	}

②、题目要求把原文中所有大写英文字母变成小写，除了 I。

**策略**：直接扫描字符串，将全部字母字符串转换为小写，当然这里要除了 ‘I’ 以及所有的问号 ? 换成惊叹号 !。（记住一定要转换了，再去判断有没有独立 me或者 you can 或者 you could，我之前就是卡死在这里）

for(int i=0; i<x; i++){ 
    			for(int j=0; j<dc[i].size(); j++){ 
    				if(dc[i][j]>='A'&&dc[i][j]<='Z'
    					&&dc[i][j]!='I')
    					dc[i][j] = dc[i][j]+32;
    				if(dc[i][j]=='?')
    					dc[i][j] = '!';
    			}
    		}

③、题目要求把原文中所有独立的 **can you**、**could you** 对应地换成 **I can**、**I could**—— 这里“独立”是指被空格或标点符号分隔开的单词。（记住一定要先转换字母小写了，再判断有没有独立 me或者 you can 或者 you could，我之前就是卡死在这里）

**策略**：还是扫描每个单词的字符，若符合条件 can you 或 could you 被空格或标点符号分隔开，则替换为 I can 或 I could 。这里也有个坑，就是 you 后面是否存在的有效字符，若存在那就直接替换，否则就要跳过一个单词，避免出现**重复替换**。  
(重复替换，例如原文：can you you you 替换后 I I I can，这样是错误的，我们需要避免这种情况）

if(dc[i][j]=='c'){ 
    //单独的 can you 
    	if(dc[i].substr(j)=="can"
    		&&dc[i+1].substr(0,3)=="you")
    		if((dc[i+1].size()>3&&dc[i+1][3]<=47)
    			||dc[i+1].size()==3){ 
    			int flag=0;
    			//避免重复替换
    			if(dc[i+1].size()==3) flag=1;
    			dc[i] = dc[i].substr(0,j)+"I";
    			dc[i+1] = "can"+dc[i+1].substr(3);
    			i += flag;
    			break;
    		}
    	//单独的 could you 
    	if(dc[i].substr(j)=="could"
    		&&dc[i+1].substr(0,3)=="you")
    		if((dc[i+1].size()>3&&dc[i+1][3]<=47)
    			||dc[i+1].size()==3){ 
    			int flag=0;
    			//避免重复替换
    			if(dc[i+1].size()==3) flag=1;
    			dc[i] = dc[i].substr(0,j)+"I";
    			dc[i+1] = "could"+dc[i+1].substr(3);
    			i += flag;
    			break;
    		}
    }

④、题目要求把原文中所有独立的 I 和 me 换成 you。

**策略**：直接扫描，符合条件直接替换即可。（记住一定要先转换字母小写了，再判断有没有独立 me或者 you can 或者 you could，我之前就是卡死在这里，重要的事说三遍！）

//单独的 I
    if(dc[i].substr(j, 1)=="I"&&
    	((j+1<dc[i].size()&&dc[i][j+1]<=64)||
    	j==dc[i].size()-1)&&((j>0&&dc[i][j-1]<=64)||j==0))
    	dc[i] = dc[i].substr(0,j)+"you"+dc[i].substr(j+1);
    
    //单独的 me
    if(dc[i].substr(j, 2)=="me"&&
    	((j+2<dc[i].size()&&dc[i][j+2]<=64)||
    	j+1==dc[i].size()-1)&&((j>0&&dc[i][j-1]<=64)||j==0))
    	dc[i] = dc[i].substr(0,j)+"you"+dc[i].substr(j+2);
    }

⑤、输出 AI 的回答，注意只要 dc\[i\] 的开头不是标点符号同时 i > 0，即可输出空格。

--------------------

整合代码

#include<bits/stdc++.h>
    using namespace std;
    string s, tmp, dc[1010];
    int main(){ 
    	int n;
    // freopen("data.txt", "r", stdin);
    	cin>>n;
    	getchar();
    	while(n--){ 
    		int x=0;
    		getline(cin, s);
    		stringstream ss(s);
    		cout<<s<<endl<<"AI: ";
    		while(getline(ss, tmp, ' ')){ 
    			if(tmp[0]>32)
    				dc[x++]=tmp;
    		}
    		
    		for(int i=0; i<x; i++){ 
    			for(int j=0; j<dc[i].size(); j++){ 
    				if(dc[i][j]>='A'&&dc[i][j]<='Z'&&dc[i][j]!='I')
    					dc[i][j] = dc[i][j]+32;
    				if(dc[i][j]=='?')
    					dc[i][j] = '!';
    			}
    		}
    		for(int i=0; i<x; i++){ 
    			for(int j=0; j<dc[i].size(); j++){ 
    				if(dc[i][j]=='c'){ 
    					//单独的 can you 
    					if(dc[i].substr(j)=="can"&&dc[i+1].substr(0,3)=="you")
    					if((dc[i+1].size()>3&&dc[i+1][3]<=64)||dc[i+1].size()==3){ 
    						int flag=0;
    						if(dc[i+1].size()==3) flag=1;
    						dc[i] = dc[i].substr(0,j)+"I";
    						dc[i+1] = "can"+dc[i+1].substr(3);
    						i += flag;
    						break;
    					}
    					//单独的 could you 
    					if(dc[i].substr(j)=="could"
    						&&dc[i+1].substr(0,3)=="you")
    					if((dc[i+1].size()>3&&dc[i+1][3]<=64)
    						||dc[i+1].size()==3){ 
    						int flag=0;
    						if(dc[i+1].size()==3) flag=1;
    						dc[i] = dc[i].substr(0,j)+"I";
    						dc[i+1] = "could"+dc[i+1].substr(3);
    						i += flag;
    						break;
    					}
    				}
    				
    				//单独的 I
    				if(dc[i].substr(j, 1)=="I"&&
    					((j+1<dc[i].size()&&
    						dc[i][j+1]<=64)||
    						j==dc[i].size()-1)&&
    					((j>0&&dc[i][j-1]<=64)||j==0))
    					dc[i] = dc[i].substr(0,j)+"you"+dc[i].substr(j+1);
    				
    				//单独的 me
    				if(dc[i].substr(j, 2)=="me"&&
    					((j+2<dc[i].size()&&dc[i][j+2]<=64)||
    					j+1==dc[i].size()-1)&&
    					((j>0&&dc[i][j-1]<=64)||j==0))
    					dc[i] = dc[i].substr(0,j)+"you"+dc[i].substr(j+2);
    			}
    		}
    		for(int i=0; i<x; i++){ 
    			cout<<dc[i];
    			if(i!=x-1&&dc[i+1][0]>47) 
    				cout<<" ";
    		}
    		cout<<endl;
    	}
    	
    	return 0;
    }

如果开头的代码有一亿，那我这个起码得有两个亿对吧…

[AI]: https://pintia.cn/problem-sets/994805046380707840/problems/1111914599412858885
[AI 1]: /images/20221120/ed80c79766b5431d94401540337b3961.png