非死不可店面挂经

huali0415

这是一个明显的backtracking题，dp可能没必要

匿名用户-K6AJR *2021-2-17 14:02:40* · 2021-2-17 14:02:40

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

glad2mu

感觉就是建一个map，里面是1->A, 11->B, 111->C, 2->D...以此类推，然后backtracking。

匿名用户-K6AJR *2021-2-17 14:30:31* · 2021-2-17 14:30:31

glad2mu 发表于 2021-2-17 14:23
感觉就是建一个map，里面是1->A, 11->B, 111->C, 2->D...以此类推，然后backtracking。

但是还有1111->A， 11111->B的情况怎么建表呢？

glad2mu

匿名者发表于 2021-2-17 14:30
但是还有1111->A， 11111->B的情况怎么建表呢？

长度超过了可以取mod呀~~zszs

Jennifer1986

请问楼主那个热身的密码锁题能说详细一点，谢谢

匿名用户-K6AJR *2021-2-20 06:01:52* · 2021-2-20 06:01:52

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

whiteboard

第二题写一个，是要用memo记录下来已经解决的子问题

unordered_map<int, vector<char>> key_maps;
unordered_map<int, vector<string>> memo;
vector<string> helper(vector<int> nums, int i)
{
if (memo.count(i))
return memo[i];
int n = nums.size();
vector<string> result;
//base case
if (i == n) return {""};
//recursive case
int j = i;
while (j < n && (j == i || nums[j] == nums[j-1])) {
vector<char> &keys = key_maps[nums[j]];
int idx = (j - i) % keys.size();
char c = keys[idx];
vector<string> tmp = helper(nums, j+1);
for (string &str : tmp)
result.push_back(c + str);
j++;
}
memo[i] = result;
return result;
}
vector<string> presskey(vector<pair<int, vector<char>>> &input, vector<int> &nums)
{
for (auto &p : input)
key_maps[p.first] = p.second;
return helper(nums, 0);
}
int main()
{
vector<pair<int, vector<char>>> input = {{1, {'A','B','C'}}, {2, {'D','E','F'}}, {0,{'X','Y','Z'}}};
vector<int> nums = {1,1,1,2};
vector<string> result = presskey(input, nums);
for (string &str : result)
cout << str << endl;
return 0;

复制代码

mzhou21

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Falldawn

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式