华为上机题汇总（十二）
注：编译环境为Visual Studio 2012，答案仅供参考。
目录
第五十六题
56.在中国，形容夫妻恩爱的词汇中，大家用的比较多的就是“夫妻相”。所谓“夫妻相”，就是两个人看上去比较般配，长相、身材等某些方面有一定的相似度。本题则另辟蹊径，从人的姓名维度，以字母重复个数来寻找最具“夫妻相”的人。
题目中预先给定一组女士的姓名拼音。输入男士的姓名拼音（拼音中间可以有空格,字母全部小写），依预先给定姓名拼音的先后遍历所有姓名，输出字母重复数最多的女士姓名。
规则：如果字母重复数最多的女士有多位相同，则以最先匹配的女士做为最具“夫妻相”的人选。
规则：人名中的相同字母，按重复一次处理。例如：li ling 与li lei 重复的字符个数为2,而不是4。
预置女士名单(先后循序必须保证):
“wang fei”,
“zhang man yu”,
“zhang zhi yi”,
“li li”,
“li xiao man”,
“li yu cun”,
“yang ni”,
“xiao tong”,
“li lei”,
“zhang san”
运行时间限制: 无限制
内存限制: 无限制
输入: 输入一个男士姓名，字符串
输出: 输出最具“夫妻相”的女士姓名
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s[] = {"wang fei","zhang man yu","zhang zhi yi","li li","li xiao man","li yu cun","yang ni","xiao tong","li lei","zhang san"};
string dealStr(const string &str){
string result;
bool chars[26];
for (int i = 0; i < 26; i++)
{
chars[i] = false;
}
for (unsigned i = 0; i < str.size(); i++)
{
if (str[i] >= 'a' && str[i] <= 'z' && !chars[str[i] - 'a'])
{
chars[str[i] - 'a'] = true;
result.push_back(str[i]);
}
}
sort(result.begin(),result.end());
return result;
}
int countSum(const string &s1, const string &s2){
auto b1 = s1.begin(), b2 = s2.begin();
int sum = 0;
while (b1!= s1.end() && b2 != s2.end())
{
if (*b1 == *b2)
{
b1++;
b2++;
sum++;
}
else if (*b1 < *b2)
{
b1++;
}
else
{
b2++;
}
}
return sum;
}
string match(const string &male){
string female = s[0], maleStr = dealStr(male);
int max = countSum(maleStr,dealStr(female));
for (int i = 1; i < 10; i++)
{
int sum = countSum(maleStr,dealStr(s[i]));
if (sum > max)
{
female = s[i];
max = sum;
}
}
return female;
}
int main()
{
string s;
cout << "请输入待测男士的拼音:";
getline(cin,s);
cout << match(s) << endl;
return 0;
}第五十七题
57.CandyBrush游戏
描述: CandyBrush一款流行的消除游戏，在一个方阵中布满各种糖果，任意交换两个糖果，如果交换后出现横向或者竖向有连续三个相同的情况，则可以消除糖果并得分。
输入个字符组成的字符串（编号为到），表示×的方阵，每个字符表示不同类型的糖果（区分大小写），判断是否有解，即交换某两个糖果后能够消除糖果。
举例，下面的方阵无解
T M T M O
X R U C q
A B C X R
U R M T O
T Q C R A
下面的方阵交换(0, 2)和(1, 2)两个糖果后，能消除M
T M T M O
X R M C q
A B C X R
U R M T O
T Q C R A
如果有解，则输出YES，同时输出所有交换方案中，被交换糖果最小编号（到），比如：上面的方阵中，被交换的糖果，编号最小的为糖果“T”，编号为。
如果无解，则输出NO。
运行时间限制: 无限制
内存限制: 无限制
输入:
输入个字符组成的字符串，不含空格，表示×的方阵
输出:
如果有解，则输出YES，同时输出所有交换方案中，被交换糖果最小编号，以空格隔开。如果无解，则输出NO。
样例输入:
TMTMOXRMCqABCXRURMTOTQCRA
样例输出:
YES 3
答案提示:
输出最小糖果编号的意思，就是从左至右，从上到下遍历糖果，找到第一个跟其他交换后能消除的糖果即可。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool canAdd(int index, const vector<int> &answers){
for (unsigned i = 0; i < answers.size(); i++)
{
if (index == answers[i])
{
return false;
}
}
return true;
}
bool hasThreeSame(int row, int col, int n ,const vector<string> &v){
for (int i = row-2; i <= row; i++)
{
if (i < 0) continue;
if (i >= n - 2) break;
if (v[i][col] == v[i+1][col] && v[i][col] == v[i+2][col])
{
return true;
}
}
for (int i = col-2; i <= col; i++)
{
if (i < 0) continue;
if (i >= n - 2) break;
if (v[row][i] == v[row][i+1] && v[row][i] == v[row][i+2])
{
return true;
}
}
return false;
}
void canMove(int row, int col, int n, const vector<string> &v, vector<int> &answers){
if (row > 0)
{
vector<string> tmpV = v;
char tmp = tmpV[row][col];
tmpV[row][col] = tmpV[row-1][col];
tmpV[row-1][col] = tmp;
if (hasThreeSame(row,col,n,tmpV)){
int index = (row-1)*n+col;
if (canAdd(index,answers))
{
answers.push_back(index);
}
}
}
if (row < n-1)
{
vector<string> tmpV = v;
char tmp = tmpV[row][col];
tmpV[row][col] = tmpV[row+1][col];
tmpV[row+1][col] = tmp;
if (hasThreeSame(row,col,n,tmpV)){
int index = row*n+col;
if (canAdd(index,answers))
{
answers.push_back(index);
}
}
}
if (col > 0)
{
vector<string> tmpV = v;
char tmp = tmpV[row][col];
tmpV[row][col] = tmpV[row][col-1];
tmpV[row][col-1] = tmp;
if (hasThreeSame(row,col,n,tmpV)){
int index = row*n+col-1;
if (canAdd(index,answers))
{
answers.push_back(index);
}
}
}
if (col < n-1)
{
vector<string> tmpV = v;
char tmp = tmpV[row][col];
tmpV[row][col] = tmpV[row][col+1];
tmpV[row][col+1] = tmp;
if (hasThreeSame(row,col,n,tmpV)){
int index = row*n+col;
if (canAdd(index,answers))
{
answers.push_back(index);
}
}
}
}
bool game(int n, const vector<string> &v, vector<int> &answers){
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
canMove(i,j,n,v,answers);
}
}
return answers.size();
}
int main()
{
vector<int> answers;
vector<string> v;
string s;
cin >> s;
int n = sqrt((double)s.size());
for (int i = 0; i < n; i++)
{
v.push_back(string(s.begin()+i*n,s.begin()+i*n+n));
}
if (game(n,v,answers))
{
cout << "YES ";
for (unsigned i = 0; i < answers.size(); i++)
{
cout << answers[i]+1 << " ";
}
}
else
{
cout << "NO";
}
cout << endl;
return 0;
}第五十八题
58.问题描述：
把一个字符串中的除大写字母、小写字母和数字字符之外的其他字符都去掉，输出新字符串。
#include <iostream>
#include <string>
using namespace std;
bool isChar(char c){
if (c >= 'a' && c <= 'z')
{
return true;
}
if (c >= 'A' && c <= 'Z')
{
return true;
}
if (c >= '0' && c <= '9')
{
return true;
}
return false;
}
void filt(const string &s1, string &s2){
for (unsigned i = 0; i < s1.size(); i++)
{
if (isChar(s1[i]))
{
s2.push_back(s1[i]);
}
}
}
int main()
{
string s, output;
getline(cin,s);
filt(s,output);
cout << output << endl;
return 0;
}第五十九题
59.正数减法
问题描述：
两个任意长度的正数相减，这两个正数可以带小数点，也可以是整数，请输出结果。 输入的字符串中，不会出现除了数字与小数点以外的其它字符，不会出现多个小数点以及小数点在第一个字符的位置等非法情况，所以考生的程序中无须考虑输入的数值字符串非法的情况。
详细要求以及约束：
1.输入均为正数，但输出可能为负数；
2.输入输出均为字符串形式；
3.如果输出是正数则不需要带符号，如果为负数，则输出的结果字符串需要带负号
例如：2.2-1.1 直接输出为“1.1”，1.1-2.2 则需要输出为“-1.1”
4.输出的结果字符串需要过滤掉整数位前以及小数位后无效的0，小数位为全0的，直接输出整数位
例如相减结果为11.345，此数值前后均不可以带0，“011.345”或者“0011.34500”等等前后带无效0的均视为错误 输出。例如1.1-1.1结果为0.0，则直接输出0。
要求实现函数：
void Decrease(char *input1, char*input2, char *output)
【输入】 char *iinput1 被减数
char*nput2 减数
【输出】 char *output 减法结果
【返回】 无
示例
输入：char *input1=”2.2”
char *input2=”1.1”
输出：char*output=”1.1”
输入：char *input1=”1.1”
char *input2=”2.2”
输出：char *output=”-1.1”
#include <iostream>
#include <string>
using namespace std;
void divive(const string &s, string &si, string &sf){
int pos = s.find('.');
if (pos >= 0)
{
si = string(s.begin(),s.begin()+pos);
sf = string(s.begin()+pos+1,s.end());
}
else
{
si = s;
sf = "0";
}
}
int compute(const string &s1, const string &s2, int overFlow, string &result){
auto b1 = s1.rbegin(), b2 = s2.rbegin();
while (b1 != s1.rend() && b2 != s2.rend())
{
int value = (*b1++ - '0') - (*b2++ - '0') - overFlow;
if (value < 0)
{
overFlow = 1;
result.push_back(value+10+ '0');
}
else
{
overFlow = 0;
result.push_back(value + '0');
}
}
return overFlow;
}
void Decrease(char *input1, char*input2, char *output){
string s1(input1,strlen(input1)), s2(input2,strlen(input2)),s3;
string si1,si2,sf1,sf2;
divive(s1,si1,sf1);
divive(s2,si2,sf2);
int byte1 = si1.size() - si2.size();
int byte2 = sf1.size() - sf2.size();
if (byte1 < 0)
{
si1.insert(si1.begin(),-byte1,'0');
}
else if (byte1 > 0)
{
si2.insert(si2.begin(),byte1,'0');
}
if (byte2 < 0)
{
sf1.insert(sf1.end(),-byte2,'0');
}
else if (byte2 > 0)
{
sf2.insert(sf2.end(),byte2,'0');
}
string iresult,fresult;
bool flag;
if (si1 == si2 && sf1 == sf2)
{
*output++ = '0';
*output = '\0';
return;
}
else if (si1 > si2 || (si1 == si2 && sf1 > sf2))
{
flag = 0;
int overFlow = compute(sf1,sf2,0,fresult);
compute(si1,si2,overFlow,iresult);
}
else
{
flag = 1;
int overFlow = compute(sf2,sf1,0,fresult);
compute(si2,si1,overFlow,iresult);
}
int pos = iresult.find_last_not_of('0');
if (pos < 0)
{
iresult = flag ? "-0" :"0";
}
else
{
iresult.erase(iresult.begin()+pos+1,iresult.end());
reverse(iresult.begin(),iresult.end());
if (flag)
{
iresult.insert(iresult.begin(),'-');
}
}
reverse(fresult.begin(),fresult.end());
pos = fresult.find_last_not_of('0');
if (pos < 0)
{
s3 = iresult;
}
else
{
fresult.erase(fresult.begin()+pos+1,fresult.end());
s3 = iresult + "." + fresult;
}
for (unsigned i = 0; i < s3.size(); i++)
{
*output++ = s3[i];
}
*output = '\0';
}
int main()
{
char s1[100],s2[100],output[100];
cin.getline(s1,100);
cin.getline(s2,100);
Decrease(s1,s2,output);
cout << output << endl;
return 0;
}第六十题
60.判断比整数N小的数里，有多少个与7相关的数。与7相关指：7的倍数或者带有7的数（比如7、14、17、27）。只需要给出总的个数，不需要输出
它们(N小于30000)
#include <iostream>
using namespace std;
bool isRight(int n){
if (n % 7 == 0)
{
return true;
}
while (n != 0)
{
if (n % 10 == 7)
{
return true;
}
n /= 10;
}
return false;
}
int count7(int n){
if (n < 0 || n >= 30000)
{
return -1;
}
int count = 0;
for (int i = 0; i < n; i++)
{
if (isRight(i))
{
count++;
}
}
return count;
}
int main()
{
int n;
cin >> n;
cout << count7(n) << endl;
return 0;
}