问题
小王的保险箱密码是一个升序排列的数字串,小王对密码进行加密。流程如下:
1.数字用英文单词代替
2.加密算法会按照某种规则改变原字符串中字符的排列顺序,同时还会改变某些字符的大小写。
该加密算法存在漏洞,即使不知道具体实现细节,也可还原出原始密码。写一段程序来破解小王的密码。
输入格式
一段英文非空字符串,且字符串可完美还原成数字
输出格式
输出原始密码
输入样例
TonwotreeeH
输出样例
123
思路
华为2019实习校园招聘的笔试题,还是挺考察编程思维的一道题。从每个单词的字符出发,先确定特殊。待特殊情况确定后,与之冲突的单词也可确定下来。即:0/2/4/6/8可以用字母z/w/u/x/g确定出来,然后用字母o/t/f/s/n确定出1/3/5/7/9。
先将子串都转为大写,然后根据前面提到的思路,依次判断每一个数字。每确定一个数字,就将其从字符串中删除。最后排序即可
含有相同字符的所有冲突的数字对,例如0和1,均需要,判断是否删除成功。否则下一个重复的0,会被当做1处理。
代码
知识积累
修改原字符串,参数定义为引用:void deletNum(string &str, string num)
。string tmp = str;
备份,后续修改无tmp无关
string的find,指定位置开始查找,返回开始位置,查找失败返回string::npos(-1)
字符:`size_t find (const string& str, size_t pos = 0) const;`
字符串:`size_t find (char c, size_t pos = 0) const;`
string的erase
序列:`string& erase (size_t pos = 0, size_t len = npos);`
返回被删除字符/区间的下一个字符的迭代器,否则返回string::npos
区间:`iterator erase (iterator first, iterator last);`
字符:`iterator erase (iterator p);`
string大小写的转换
transform(str.begin(), str.end(), str.begin(), ::toupper);
transform(str.begin(), str.end(), str.begin(), ::tolower);
数字转字符:ans += '0' + v[i];
调试过程
1.由于数字8和9,均含字符g,故需要特殊处理下。
2.00,第二个0,会按照1去处理。类似含有相同字符的所有冲突的数字对,均需要,判断是否删除成功。
#include <iostream>
#include <string>
uisng namespace std;
bool suc = true;
void deletNum(string &str, string num)
{
int pos;
suc = true;
string tmp = str;
for (int i = 0; i < num.length(); i++)
{
pos = str.find(num[i]);
if (pos == -1) break;
str.erase(str.begin()+pos);
}
if (pos == -1)
{
suc = false;
str = tmp;
}
}
string getPassWord(string str)
{
string ans;
vector<int> v;
transform(str.begin(), str.end(), str.begin(), ::toupper);
while(str.size() != 0)
{
if(str.find('Z') != -1)
{
deletNum(str, "ZERO");
if (suc) v.push_back(0);
}
if(str.find('W') != -1)
{
deletNum(str, "TWO");
if (suc) v.push_back(2);
}
if(str.find('U') != -1)
{
deletNum(str, "FOUR");
if (suc) v.push_back(4);
}
if(str.find('X') != -1)
{
deletNum(str, "SIX");
if (suc) v.push_back(6);
}
if(str.find('G') != -1)
{
deletNum(str, "EIGHT");
if (suc) v.push_back(8);
}
if(str.find('O') != -1)
{
deletNum(str, "ONE");
if (suc) v.push_back(1);
}
if(str.find('T') != -1)
{
deletNum(str, "THREE");
if (suc) v.push_back(3);
}
if(str.find('F') != -1)
{
deletNum(str, "FIVE");
if (suc) v.push_back(5);
}
if(str.find('S') != -1)
{
deletNum(str, "SEVEN");
if (suc) v.push_back(7);
}
if(str.find('N') != -1)
{
deletNum(str, "NIGH");
if (suc) v.push_back(9);
}
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++)
{
ans += '0' + v[i];
}
return ans;
}
int main()
{
string str = "ftoigurzfivesIxszErotowthrexerehighTonoighevienenonwesone";
cout << getPassWord(str) << endl;
}