滴滴新锐计划2017研发工程师B卷在线笔试题总结

——笔试题总结

Posted by Samuel on May 8, 2017

目录

岛屿

0是陆地,1是海洋,输入一个字符串格式的二维数组,判断岛屿个数。

输入样例:
4 5
11000
11000
00100
00011
输出:
3

图的广度优先搜索

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

struct q{
	int x,y;
	q(int a,int b):x(a),y(b){}
};
int n,m;

int moves[4][2]={ {0,1},{0,-1},{-1,0},{1,0} }; //上下左右四个方向

bool bound(int x,int y, vector<vector<int>> map){ //判断是否越界
	if(x<0||y<0||x>=n||y>=m||map[x][y]==0)
		return true;
	return false;
}
int main(){
	cin>>n>>m; //n行m列
	vector<vector<int>> map(n,vector<int>(m,0)); //标记地图
	vector<vector<int>> book(n,vector<int>(m,0)); //标记访问

	char ch;
	for(int i=0;i<n;i++){ //读入岛屿图
		for(int j=0;j<m;j++){
			cin>>ch;
			map[i][j]= ch-'0';
		}
	}

	int count=0; //统计岛屿个数
	for(int i=0;i<n;i++){ //遍历n行m列
		for(int j=0;j<m;j++){
			queue<q> que; //如果是深度优先搜索用stack
			if(!bound(i,j,map)&&book[i][j]==0){ //未越界也未被访问
				count++;
				q temp(i,j);
				que.push(temp);
				book[i][j]=count; //标记访问
			}
			else
				continue;
			while(que.size()){
				q temp=que.front();
				que.pop();
				book[temp.x][temp.y]=count; //标记访问
				for(int k=0;k<4;k++){ //上下左右判断
					int px=temp.x+moves[k][0];
					int py=temp.y+moves[k][1];
					if(bound(px,py,map)||book[px][py]!=0) //越界且被访问过
						continue;
					else{
						que.push(q(px,py));
						book[px][py]=count;
					}
				}
			}
		}
	}
	cout<<count<<endl;
	return 0;
}

T9键盘

根据T9键盘的数字和英文对应关系,输入对应的三个数字,求出最相似的单词。

{'2':"abc",
'3':"def",
'4':"ghi",
'5':"jkl",
'6':"mno",
'7':"pqrs",
'8':"tuv",
'9':"wxyz"
}
输入描述:
输入的第一行为字典,里面包含若干备选单词。
第二行为输入的数字。

输出描述:
根据T9键盘的对应关系,求出字典的最相似单词。

输入例子:
Produces a printable string representation of a dictionary
784

输出例子:
string
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

//单词转数字序列
string StringToNum(string str){
	string res;
	for(int i=0;i<str.size();i++){
		if((str[i]>='a'&&str[i]<='c')||(str[i]>='A'&&str[i]<='C'))
			res.push_back('2');
		else if((str[i]>='d'&&str[i]<='f')||(str[i]>='D'&&str[i]<='F'))
			res.push_back('3');
		else if((str[i]>='g'&&str[i]<='i')||(str[i]>='G'&&str[i]<='I'))
			res.push_back('4');
		else if((str[i]>='j'&&str[i]<='l')||(str[i]>='J'&&str[i]<='L'))
			res.push_back('5');
		else if((str[i]>='m'&&str[i]<='o')||(str[i]>='M'&&str[i]<='O'))
			res.push_back('6');
		else if((str[i]>='p'&&str[i]<='s')||(str[i]>='P'&&str[i]<='S'))
			res.push_back('7');
		else if((str[i]>='t'&&str[i]<='v')||(str[i]>='T'&&str[i]<='V'))
			res.push_back('8');
		else if((str[i]>='w'&&str[i]<='z')||(str[i]>='W'&&str[i]<='Z'))
			res.push_back('9');
	}
	return res;
}
//最长子序列长度
int lcs(string str1,string str2){
	int len1 = str1.length();
	int len2 = str2.length();
	vector<vector<int>> c(len1+1,vector<int>(len2+1,0));
	for (int i = 0; i <= len1; i++) {
		for( int j = 0; j <= len2; j++) {
			if(i == 0 || j == 0) 
				c[i][j] = 0;
			else if (str1[i-1] == str2[j-1]) 
				c[i][j] = c[i-1][j-1] + 1;
			else 
				c[i][j] = max(c[i - 1][j], c[i][j - 1]);
		}
	}
	return c[len1][len2];
}
int main(){
	string str,num;
	//getline(cin,str);
	str="Produces a printable string representation of a dictionary";
	cin>>num;

	//字典抽取单词
	vector<string> dictionary;
	stringstream ss;
	ss<<str;
	while(!ss.eof()){
		string temp;
		ss>>temp;
		dictionary.push_back(temp);
	}
	int max=0,curIndex=0;
	for(int i=0;i<dictionary.size();i++){
		string numStr=StringToNum(dictionary[i]);
		int length=lcs(numStr,num);
		if(max<length)
			max=length,curIndex=i;
		else if(length!=0&&max==length)
			curIndex=(dictionary[curIndex].size()<dictionary[i].size())?curIndex:i;
	}
	if(curIndex!=0)
		cout<<dictionary[curIndex]<<endl;
	return 0;
}