非死不可店面挂经

2月10号店面，今天收到消息悲剧了

上来没有自我介绍直接做题，
第一题一个四位数的密码锁，初始状态为0000， 输入解锁密码，返回最少多少个move可以解开。热身题，考虑几个异常输入即可。

第二题， 给一个map
{1，{‘A’,'B' , 'C'}},
{2,   { 'D' , 'E' , 'F' }}
。

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

面试官两次问我dp的helper返回的是什么，我就用1111一步一步用例子给他跑出来看。最后时间也没来得及写完。

网上找了一下也没找到类似的题， 求大神看看有什么更优的解法。

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

1. unordered_map<int, vector<char>> key_maps;
   
2. unordered_map<int, vector<string>> memo;
   
3. 
   
4. vector<string> helper(vector<int> nums, int i)
   
5. {
   
6.     if (memo.count(i))
   
7.         return memo[i];
   
8. 
   
9.     int n = nums.size();
   
10.     vector<string> result;
    
11. 
    
12.     //base case
    
13.     if (i == n) return {""};
    
14. 
    
15.     //recursive case
    
16.     int j = i;  
    
17.     while (j < n && (j == i || nums[j] == nums[j-1])) {
    
18.         vector<char> &keys = key_maps[nums[j]];
    
19.         int idx = (j - i) % keys.size();
    
20.         char c = keys[idx];
    
21. 
    
22.         vector<string> tmp = helper(nums, j+1);
    
23.         for (string &str : tmp)
    
24.             result.push_back(c + str);
    
25.         j++;
    
26.     }   
    
27. 
    
28.     memo[i] = result;
    
29. 
    
30.     return result;
    
31. }
    
32. 
    
33. vector<string> presskey(vector<pair<int, vector<char>>> &input, vector<int> &nums)
    
34. {
    
35.     for (auto &p : input)
    
36.         key_maps[p.first] = p.second;
    
37. 
    
38.     return helper(nums, 0);
    
39. }
    
40. 
    
41. int main()
    
42. {
    
43.     vector<pair<int, vector<char>>> input = {{1, {'A','B','C'}}, {2, {'D','E','F'}}, {0,{'X','Y','Z'}}};
    
44.     vector<int> nums = {1,1,1,2};
    
45.     vector<string> result = presskey(input, nums);
    
46.     for (string &str : result)
    
47.         cout << str << endl;
    
48.     return 0;
    

复制代码

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感觉就是手机键盘的变形，backtracking可解吧

找所有的方案，backtracking

第二题就是手机键盘...
面试官真的说说他们家不考DP么? 我看他们高频不少DP题..

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

painlet2 发表于 2021-2-17 09:58
第二题就是手机键盘...
面试官真的说说他们家不考DP么? 我看他们高频不少DP题..

请问手机键盘是哪道题？ 17吗？ 不像呀

DP咋给所有解？？问号脸

请问现在店面是不是都要开视频的？ 这样会不会很紧张？

小元宝 发表于 2021-2-17 13:06
请问现在店面是不是都要开视频的？ 这样会不会很紧张？

都要开视频吧，紧张倒不至于。只是写代码的时候没法看视频，不知道面试官实时反馈如何。