骨骼 OV 挂经 求米安抚

旧未来 发表于 2020-7-31 07:25
感谢lz面筋 有几个问题想问题一下
1. ”验证这轮的string有没有可能性成为上一轮原string“这个问题是什么 ...

1.  我也是被他给问懵了一开始，然后花了2-3分钟去问他具体什么意思。后来才发现他的意思是
   第一部分，如果target是abcd, 猜测是accc，这个时候return 1完全匹配1位置匹配。那到第二部分，我们已经知道输入accc，得到1完全匹配1位置匹配，那我们再输入一个cccc，我们就知道这个肯定不可能是target，因为我们accc和cccc无法得到1完全匹配1位置匹配。

5. 不行。不能落单。

密码 发表于 2020-7-31 10:17
是L4么?楼主方便透露是哪方面feedback不好么? 如果都写的不错还被挂,我感觉我也不用去面了最近

最后一轮，写得方法复杂度太高，写得有点慢。其他都是说很好的，让我保持，特别是沟通和the way to appoach problem。是l4。

YZPYAN 发表于 2020-7-31 10:24
已加米！想问下112这个情况胡么？虽然有11 但是2落单了。谢谢

不行。这样打麻将是不胡牌的。lol

匿名者 发表于 2020-7-31 10:57
1.  我也是被他给问懵了一开始，然后花了2-3分钟去问他具体什么意思。后来才发现他的意思是
   第一部分 ...

给的数字都是作为1-9来看待吗？就是都是single-digit的用来判断

最后一问dfs/bfs加memorization或者dp，复杂度应该是O（n）吧？这还能怎么优化啊

这问参考leetcode wordbreak，这问相当于dictionary里的word length都是2或者3，所以wordbreak是square，这问应该是linear

匿名者 发表于 2020-7-31 06:40
可能是我没有表达清楚。input随便，
还有
例子1：22334455也是胡牌，你可以自己组和成234 234 55。

第五题应该可以用greedy来做

mylarryshell 发表于 2020-7-31 12:01
第五题应该可以用greedy来做

求问greedy具体怎么实现啊

尝试了一下感觉greedy似乎可以：主要就是每次都选一个数作为pair的那个数，然后只要确保剩下的数可以构成ABC或者AAA的pattern，这个结果就是valid的

1. bool isABCOrAAAPattern(const vector<int>& v) {
   
2.     vector<int> newArr(v);
   
3.    
   
4.     for (int i = 0; i < newArr.size() - 2; i++) {
   
5.         while (newArr[i] > 0 && newArr[i] != 3) {   
   
6.             newArr[i] -= 1;
   
7.             if (newArr[i + 1] <= 0) {
   
8.                 return false;
   
9.             } else {
   
10.                 newArr[i + 1] -= 1;
    
11.             }
    
12.             
    
13.             if (newArr[i + 2] <= 0) {
    
14.                 return false;
    
15.             } else {
    
16.                 newArr[i + 2] -= 1;
    
17.             }
    
18.         }
    
19.     }
    
20.          
    
21.     for (int i=0; i<newArr.size(); i++) {
    
22.         if (newArr[i] != 0 && newArr[i] != 3) {
    
23.             return false;
    
24.         }
    
25.     }
    
26.    
    
27.     return true;
    
28. 
    
29. }
    
30. 
    
31. bool isOK(){
    
32.     vector<int> cards{1,1,2,2,2,3,3,3,3,3,4};
    
33.     vector<int> nums(10);
    
34.     for (int i = 0; i < cards.size(); i++)
    
35.         nums[cards[i]]++;
    
36.     for (int i = 1; i <= 9; i++){
    
37.         if (nums[i] < 2)
    
38.             continue;
    
39.         
    
40.         // try i
    
41.         nums[i] -= 2;
    
42.         if (isABCOrAAAPattern(nums))
    
43.             return true;
    
44.         
    
45.         nums[i] += 2;
    
46.     }
    
47.    
    
48.     return false;
    
49. }
    
50. 
    
51. // To execute C++, please define "int main()"
    
52. int main() {
    
53.     cout << isOK();   
    
54. }
    

复制代码

[/i][/i][/i][/i][/i][/i][/i][/i][/i]

zvzv1919 发表于 2020-07-30 20:58:34
最后一问dfs/bfs加memorization或者dp，复杂度应该是O（n）吧？这还能怎么优化啊

lol，第五题怎么可能O(n)，你写个我看看。