字母组合
一.题目
二.歧义
这题目文字描述和样例没有讲清楚：
1.是否要做输入的数字校验，因为有可能输入超过10的数字
2.输入的字符和数字之间一定用空格分隔，还是可以不分割。
三.解题思路
这道题剔除一些无关简要的代码，可以采用暴力排列组合，也可以采用动态规划。由于此题难度其实不大， 也不涉及背包问题，就采用了暴力的排列组合。
四.代码
1.先上主函数 。
- 先初始化加载关联字母。
- 输入cin
- 因为题目没有讲清楚输入是否一定采用空格分隔，这里做了切分和内部转换为数字
- 通过用户输入的数字获取哪些字母集合要进行排列
- 进行排列
- 剔除屏蔽的字符
- 输出结果
void main()
{
InitDictionary();
std::string numString;
std::string ingnoreString;
std::getline(std::cin ,numString);
std::getline(std::cin, ingnoreString);
std::cout << std::endl;
std::string space = " ";
//分割字符串
std::vector<int> nums = SplitStringToDigit(numString, space);
bool isContainSameDigit = IsContainSameDigit(nums);
if (isContainSameDigit)
return;
std::vector<char> ignore = SplitString(ingnoreString, space);
//做完校验，获取到用户输入的信息之后 就可以开始 排列组合 剔除掉受影响的组合即可。 这里可以用排列组合,也可以用动态规划的思维来解决问题
std::vector<std::vector<char>> sources = GetDictionary(nums);
std::vector<std::vector<char>> result=GetPermutation(sources, ignore);
for (auto& vect : result)
{
std::string str;
for (char c : vect)
{
str += c;
}
std::cout << str << std::endl;
}
}
2.初始化关联字母
std::unordered_map<int, std::vector<char>> dictionary;
void InitDictionary()
{
std::vector<char> v0 = { 'a','b','c' };
std::vector<char> v1 = { 'd','e','f' };
std::vector<char> v2 = { 'g','h','i' };
std::vector<char> v3 = { 'j','k','l' };
std::vector<char> v4 = { 'm','n','o' };
std::vector<char> v5 = { 'p','q','r' };
std::vector<char> v6 = { 's','t' };
std::vector<char> v7 = { 'u','v' };
std::vector<char> v8 = { 'w','x' };
std::vector<char> v9 = { 'y','z' };
dictionary.insert(std::make_pair(0, v0));
dictionary.insert(std::make_pair(1, v1));
dictionary.insert(std::make_pair(2, v2));
dictionary.insert(std::make_pair(3, v3));
dictionary.insert(std::make_pair(4, v4));
dictionary.insert(std::make_pair(5, v5));
dictionary.insert(std::make_pair(6, v6));
dictionary.insert(std::make_pair(7, v7));
dictionary.insert(std::make_pair(8, v8));
dictionary.insert(std::make_pair(9, v9));
}
3.切分
//如果字符串包含指定字符，则分割之后转换为数字。 不包含则按位切分
std::vector<int> SplitStringToDigit(std::string str, const std::string& reg)
{
std::vector<int> result;
if (str.find(reg) == std::string::npos)
{
for (char c : str)
{
result.push_back(c - '0');
}
return result;
}
else
{
std::string::size_type posLast = 0;
std::string::size_type posCurrent = str.find(reg);
while (posCurrent != std::string::npos)
{
result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0] - '0');
posLast = posCurrent + reg.size();
posCurrent = str.find(reg, posLast);
}
if (posLast < str.length())
{
result.push_back(str.substr(posLast).c_str()[0] - '0');
}
}
return result;
}
//题目也没有说输入的字符是否以空格排列， 此处考虑空格间隔情况
std::vector<char> SplitString(std::string str, const std::string& reg)
{
std::vector<char> result;
if (str.find(reg) == std::string::npos)
{
for (char c : str)
{
result.push_back(c);
}
return result;
}
else
{
std::string::size_type posLast = 0;
std::string::size_type posCurrent = str.find(reg);
while (posCurrent != std::string::npos)
{
result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0]);
posLast = posCurrent + reg.size();
posCurrent = str.find(reg, posLast);
}
if (posLast < str.length())
{
result.push_back(str.substr(posLast).c_str()[0]);
}
}
return result;
}
4.排列
//std::vector<std::vector<char>> 为一个动态的二维数组，一维指的是用户输入的数字， 二维指的是输入的数字所关联的字符
// i这里表示的是一维索引位置。 j表示的是二维索引位置
void GetPermuatations(int i,int j,std::vector<std::vector<char>>& sources, std::vector<std::vector<char>>& pers)
{
//如果超过了限定，就退出，避免递归死循环
if (i >= sources.size()) return;
if (i == 0 && j == 0)
{
for (int k = 0; k < sources[i].size(); k++)
{
std::vector<char> vs;
vs.push_back(sources[i][k]);
pers.push_back(vs);
}
}
else
{
//在上一轮的排列结果至上 继续进行新的元素的排列
std::vector<std::vector<char>> newPers;
for (auto& vect : pers)
{
for (int k = 0; k < sources[i].size(); k++)
{
std::vector<char> vs(vect);
vs.push_back(sources[i][k]);
newPers.push_back(vs);
}
}
pers.clear();
pers = newPers;
}
GetPermuatations(++i, ++j, sources, pers);
}
//字符集合 是否连续存在被忽略的字符信息
bool IsIgnore(const std::vector<char>& chrs, std::vector<char>& ignore)
{
std::sort(ignore.begin(), ignore.end());
if (chrs.size() < ignore.size())
return false;
char first = *ignore.begin();
auto iter=std::find(chrs.begin(), chrs.end(), first);
if (iter == chrs.end())
return false;
int start = std::distance(chrs.begin(), iter);
for (int i = start; i < ignore.size(); i++)
{
if (chrs[i] != ignore[i - start])
return false;
}
return true;
}
//字母组合的核心函数
std::vector<std::vector<char>> GetPermutation(std::vector<std::vector<char>>& sources, std::vector<char>& ignore)
{
std::vector<std::vector<char>> pers;
GetPermuatations(0,0, sources, pers);
std::vector<std::vector<char>> result;
//剔除掉被忽略的场景
for (auto& vect : pers)
{
if (!IsIgnore(vect, ignore))
{
result.push_back(vect);
}
}
return result;
}
完整代码
#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>
#pragma region 11
//如果字符串包含指定字符，则分割之后转换为数字。 不包含则按位切分
std::vector<int> SplitStringToDigit(std::string str, const std::string& reg)
{
std::vector<int> result;
if (str.find(reg) == std::string::npos)
{
for (char c : str)
{
result.push_back(c - '0');
}
return result;
}
else
{
std::string::size_type posLast = 0;
std::string::size_type posCurrent = str.find(reg);
while (posCurrent != std::string::npos)
{
result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0] - '0');
posLast = posCurrent + reg.size();
posCurrent = str.find(reg, posLast);
}
if (posLast < str.length())
{
result.push_back(str.substr(posLast).c_str()[0] - '0');
}
}
return result;
}
#pragma endregion
//题目也没有说输入的字符是否以空格排列， 此处考虑空格间隔情况
std::vector<char> SplitString(std::string str, const std::string& reg)
{
std::vector<char> result;
if (str.find(reg) == std::string::npos)
{
for (char c : str)
{
result.push_back(c);
}
return result;
}
else
{
std::string::size_type posLast = 0;
std::string::size_type posCurrent = str.find(reg);
while (posCurrent != std::string::npos)
{
result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0]);
posLast = posCurrent + reg.size();
posCurrent = str.find(reg, posLast);
}
if (posLast < str.length())
{
result.push_back(str.substr(posLast).c_str()[0]);
}
}
return result;
}
//集合中是否包含相同的元素 true:包含相同的元素
bool IsContainSameDigit(const std::vector<int>& nums)
{
std::set<int> se;
for (int i : nums)
{
se.insert(i);
}
if (se.size() != nums.size())
return true;
else
return false;
}
//std::vector<std::vector<char>> 为一个动态的二维数组，一维指的是用户输入的数字， 二维指的是输入的数字所关联的字符
// i这里表示的是一维索引位置。 j表示的是二维索引位置
void GetPermuatations(int i,int j,std::vector<std::vector<char>>& sources, std::vector<std::vector<char>>& pers)
{
//如果超过了限定，就退出，避免递归死循环
if (i >= sources.size()) return;
if (i == 0 && j == 0)
{
for (int k = 0; k < sources[i].size(); k++)
{
std::vector<char> vs;
vs.push_back(sources[i][k]);
pers.push_back(vs);
}
}
else
{
//在上一轮的排列结果至上 继续进行新的元素的排列
std::vector<std::vector<char>> newPers;
for (auto& vect : pers)
{
for (int k = 0; k < sources[i].size(); k++)
{
std::vector<char> vs(vect);
vs.push_back(sources[i][k]);
newPers.push_back(vs);
}
}
pers.clear();
pers = newPers;
}
GetPermuatations(++i, ++j, sources, pers);
}
//字符集合 是否连续存在被忽略的字符信息
bool IsIgnore(const std::vector<char>& chrs, std::vector<char>& ignore)
{
std::sort(ignore.begin(), ignore.end());
if (chrs.size() < ignore.size())
return false;
char first = *ignore.begin();
auto iter=std::find(chrs.begin(), chrs.end(), first);
if (iter == chrs.end())
return false;
int start = std::distance(chrs.begin(), iter);
for (int i = start; i < ignore.size(); i++)
{
if (chrs[i] != ignore[i - start])
return false;
}
return true;
}
//字母组合的核心函数
std::vector<std::vector<char>> GetPermutation(std::vector<std::vector<char>>& sources, std::vector<char>& ignore)
{
std::vector<std::vector<char>> pers;
GetPermuatations(0,0, sources, pers);
std::vector<std::vector<char>> result;
//剔除掉被忽略的场景
for (auto& vect : pers)
{
if (!IsIgnore(vect, ignore))
{
result.push_back(vect);
}
}
return result;
}
std::unordered_map<int, std::vector<char>> dictionary;
void InitDictionary()
{
std::vector<char> v0 = { 'a','b','c' };
std::vector<char> v1 = { 'd','e','f' };
std::vector<char> v2 = { 'g','h','i' };
std::vector<char> v3 = { 'j','k','l' };
std::vector<char> v4 = { 'm','n','o' };
std::vector<char> v5 = { 'p','q','r' };
std::vector<char> v6 = { 's','t' };
std::vector<char> v7 = { 'u','v' };
std::vector<char> v8 = { 'w','x' };
std::vector<char> v9 = { 'y','z' };
dictionary.insert(std::make_pair(0, v0));
dictionary.insert(std::make_pair(1, v1));
dictionary.insert(std::make_pair(2, v2));
dictionary.insert(std::make_pair(3, v3));
dictionary.insert(std::make_pair(4, v4));
dictionary.insert(std::make_pair(5, v5));
dictionary.insert(std::make_pair(6, v6));
dictionary.insert(std::make_pair(7, v7));
dictionary.insert(std::make_pair(8, v8));
dictionary.insert(std::make_pair(9, v9));
}
std::vector<std::vector<char>> GetDictionary(const std::vector<int>& nums)
{
std::vector<std::vector<char>> result;
for (int i : nums)
{
result.push_back(dictionary[i]);
}
return result;
}
void main()
{
InitDictionary();
std::string numString;
std::string ingnoreString;
std::getline(std::cin ,numString);
std::getline(std::cin, ingnoreString);
std::cout << std::endl;
std::string space = " ";
//分割字符串
std::vector<int> nums = SplitStringToDigit(numString, space);
bool isContainSameDigit = IsContainSameDigit(nums);
if (isContainSameDigit)
return;
std::vector<char> ignore = SplitString(ingnoreString, space);
//做完校验，获取到用户输入的信息之后 就可以开始 排列组合 剔除掉受影响的组合即可。 这里可以用排列组合,也可以用动态规划的思维来解决问题
std::vector<std::vector<char>> sources = GetDictionary(nums);
std::vector<std::vector<char>> result=GetPermutation(sources, ignore);
for (auto& vect : result)
{
std::string str;
for (char c : vect)
{
str += c;
}
std::cout << str << std::endl;
}
}
华为OD2024 E 文章被收录于专栏
实时更新华为2024 E卷答案
