算法学习——华为机考题库10（HJ64 - HJ70）
HJ64 MP3光标位置
描述
MP3 Player因为屏幕较小，显示歌曲列表的时候每屏只能显示几首歌曲，用户要通过上下键才能浏览所有的歌曲。为了简化处理，假设每屏只能显示4首歌曲，光标初始的位置为第1首歌。
现在要实现通过上下键控制光标移动来浏览歌曲列表，控制逻辑如下：
歌曲总数<=4的时候，不需要翻页，只是挪动光标位置。
光标在第一首歌曲上时，按Up键光标挪到最后一首歌曲；光标在最后一首歌曲时，按Down键光标挪到第一首歌曲。
输入说明：
1 输入歌曲数量
2 输入命令 U或者D
输出说明
1 输出当前列表
2 输出当前选中歌曲
示例
代码解析
#include <iostream>
using namespace std;
int main() {
int num;
string str;
cin>>num;
cin>>str;
int cur = 0;
int left = 0,right;
if(num >3) right = 3;
else right = num-1;
for(auto it:str)
{
// cout<<cur<<" "<<left<<' '<<right<<endl;
if(it == 'U')
{
cur--;
cur = cur%num;
if(cur < 0) cur += num;
if(num > 4)
{
if(cur >= left && cur <= right ) {}
else if( cur == num-1 ) { left = num - 1 - 3; right = num - 1; }
else { left-- ; right--; }
}
}
else if(it == 'D')
{
cur++;
cur = cur%num;
if(cur < 0) cur += num;
if(num > 4)
{
if(cur >= left && cur <= right ) {}
else if( cur == 0 ) { left = 0; right = 3; }
else { left++ ; right++; }
}
}
}
for(int i=left ; i<=right ; i++)
{
cout<<i+1<<' ';
}
cout<<endl;
cout<<cur+1;
}
// 64 位输出请用 printf("%lld")
HJ65 查找两个字符串a,b中的最长公共子串
描述
查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！
数据范围：字符串长度 1≤length≤300
进阶：时间复杂度：O(n 3) ，空间复杂度：O(n)
输入描述：
输入两个字符串
输出描述：
返回重复出现的字符
示例
代码解析
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
string str1,str2;
cin>>str1>>str2;
if(str1.size() > str2.size())
{
string tmp = str1;
str1 = str2;
str2 = tmp;
}
int m = str1.size() , n = str2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
int indnx , lenght = 0;
for(int i=1 ; i<=m ;i++)
{
for(int j=1 ; j<=n ;j++)
{
if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i][j] > lenght)
{
lenght = dp[i][j];
indnx = i;
}
}
}
// for(int i=0 ; i<=m ;i++)
// {
// for(int j=0 ; j<=n ;j++)
// {
// cout<<dp[i][j]<<' ';
// }
// cout<<endl;
// }
string result(str1.begin()+indnx-lenght , str1.begin() + indnx);
cout<<result;
}
// 64 位输出请用 printf("%lld")
HJ66 配置文件恢复
描述
有6条配置命令，它们执行的结果分别是：
注意：he he不是命令。
为了简化输入，方便用户，以“最短唯一匹配原则”匹配（注：需从首字母开始进行匹配）：
1、若只输入一字串，则只匹配一个关键字的命令行。例如输入：r，根据该规则，匹配命令reset，执行结果为：reset what；输入：res，根据该规则，匹配命令reset，执行结果为：reset what；
2、若只输入一字串，但匹配命令有两个关键字，则匹配失败。例如输入：reb，可以找到命令reboot backpalne，但是该命令有两个关键词，所有匹配失败，执行结果为：unknown command
3、若输入两字串，则先匹配第一关键字，如果有匹配，继续匹配第二关键字，如果仍不唯一，匹配失败。
例如输入：r b，找到匹配命令reset board 和 reboot backplane，执行结果为：unknown command。
例如输入：b a，无法确定是命令board add还是backplane abort，匹配失败。
4、若输入两字串，则先匹配第一关键字，如果有匹配，继续匹配第二关键字，如果唯一，匹配成功。例如输入：bo a，确定是命令board add，匹配成功。
5、若输入两字串，第一关键字匹配成功，则匹配第二关键字，若无匹配，失败。例如输入：b addr，无法匹配到相应的命令，所以执行结果为：unknow command。
6、若匹配失败，打印“unknown command”
注意：有多组输入。
数据范围：数据组数：1≤t≤800 ，字符串长度1≤s≤20
进阶：时间复杂度：O(n) ，空间复杂度：O(n)
输入描述：
多行字符串，每行字符串一条命令
输出描述：
执行结果，每条命令输出一行
示例
代码解析
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
vector<pair<string, string>> instr = { {"reset",""},
{"reset","board"},
{"board","add"},
{"board","delete"},
{"reboot","backplane"},
{"backplane","abort"}}; //存放每一对关键字
vector<string> outstr = { "reset what","board fault","where to add",
"no board at all","impossible","install first"}; //存放每条命令对应执行结果
int main() {
string str;
while ( getline(cin,str) ) { // 注意 while 处理多个 case
stringstream ss(str);
string key;
vector<string> date;
while( getline(ss, key, ' ') )
{
date.push_back(key);
}
int count = 0;
string result;
for(int i=0 ; i<instr.size() ; i++)
{
int i1 = instr[i].first.find(date[0]);
int i2;
if(date.size() == 2 )
{
i2 = instr[i].second.find(date[1]);
}else if( date.size() == 1 && instr[i].second.empty() == 1)
{
i2 = 0;
}else i2 = -1;
if( i1 == 0 && i2 == 0 )
{
count++;
result = outstr[ i ];
}
}
if(count == 1) cout<<result<<endl;
else cout<<"unknown command"<<endl;
str.clear();
date.clear();
}
}
// 64 位输出请用 printf("%lld")
HJ67 24点游戏算法
描述
给出4个1-10的数字，通过加减乘除运算，得到数字为24就算胜利,除法指实数除法运算,运算符仅允许出现在两个数字之间,本题对数字选取顺序无要求，但每个数字仅允许使用一次，且需考虑括号运算
此题允许数字重复，如3 3 4 4为合法输入，此输入一共有两个3，但是每个数字只允许使用一次，则运算过程中两个3都被选取并进行对应的计算操作。
输入描述：
读入4个[1,10]的整数，数字允许重复，测试用例保证无异常数字。
输出描述：
对于每组案例，输出一行表示能否得到24点，能输出true，不能输出false
示例
代码示例
#include <iostream>
#include <vector>
using namespace std;
bool flag = false;
void track(vector<double> &date ,vector<bool> &path , int indnx , double result)
{
if( indnx > 4 || flag == true ) return;
//cout<<indnx<<' '<<result<<endl;
if( result == 24 )
{
flag = true;
return;
}
for(int i=0 ; i<date.size() ;i++)
{
if(path[i] == false)
{
path[i] = true;
track(date, path, indnx + 1 , result + date[i]);
track(date, path, indnx + 1 , result - date[i]);
track(date, path, indnx + 1 , result * date[i]);
track(date, path, indnx + 1 , result / date[i]);
path[i] = false;
}
}
}
int main() {
int tmp;
vector<double> date;
while (cin >> tmp) { // 注意 while 处理多个 case
date.push_back(tmp);
}
vector<bool> path(date.size(),false);
track(date,path,0,0);
if(flag == true) cout<<"true"<<endl;
else cout<<"false"<<endl;
}
// 64 位输出请用 printf("%lld")
