Google 电面

catinclay 发表于 2016-11-30 07:37
恩 先combination再permutation, 挺麻烦的 以为全部的button都要用到

补充内容 (2016-11-30 07:38):

我用backtracking求的combination，你的意思是？

jpeng7 发表于 2016-11-30 07:40
我用backtracking求的combination，你的意思是？

其实应该都差不多啦...
no more idea

第一题file那个不太明白是什么意思诶，，楼主能再详细说一下问题么？为什么是一行一行的存啊。。

zhangxi1994 发表于 2016-11-30 11:22
第一题file那个不太明白是什么意思诶，，楼主能再详细说一下问题么？为什么是一行一行的存啊。。

有一个input file，内容是
apple pen
pineapple pen
ang
penpineapple
apple pen
其中第一行跟最后一行是一样的，所以只需要输出第一行。不用care input file这个条件，可以只当是一个string数组

jpeng7 发表于 2016-11-30 12:13
有一个input file，内容是
apple pen
pineapple pen

谢谢楼主！想再问一下，一个map的size比较小那道题，是问怎么实现hashmap吗？

zhangxi1994 发表于 2016-12-1 05:26
谢谢楼主！想再问一下，一个map的size比较小那道题，是问怎么实现hashmap吗？

对的，紫薯紫薯紫薯

        第二题这样写不知道对不对

        public static  List<String>  buttonCombine(List<Integer> nums){
             List<String> re = new ArrayList<String>();
             boolean[] used = new boolean[nums.size()];
             help(re,0, new StringBuilder(), used, nums);
             return re;
        }
       
        public static void help( List<String> r,int level, StringBuilder sb, boolean[] used, List<Integer> nums){
            int size = nums.size();
            if(sb.length()!=0 && sb.charAt(sb.length()-1)!='-'){
                    StringBuilder newsb = new StringBuilder(sb);
                    r.add(newsb.toString());
            }
                if(level == size) return;
            for(int i=0; i<size; i++){
                        if(!used[i]){
                                used[i] = true;
                                sb.append(nums.get(i));
                                help(r,level+1, sb, used, nums);
                                sb.deleteCharAt(sb.length()-1);
                                if(level!=size-1){
                                        sb.append(nums.get(i)+"-");
                                        help(r,level+1, sb, used, nums);
                                        sb.delete(sb.length()-2, sb.length());
                                }
                                used[i] = false;
                        }
                }
        }

jpeng7 发表于 2016-11-30 15:13
对的，紫薯紫薯紫薯

hashmap的那个题楼主现在知道怎么做了吗？

按按钮，先组合，再全排，然后插 '-'

1. #include <iostream>
   
2. #include <string>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. void CombButtons(string& buttons, int l, int r, int len,
   
7.                  vector<string>& button_select, string path) {
   
8.   if (path.size() == len)
   
9.     button_select.push_back(path);
   
10.   else {
    
11.     for (int i = l; i <= r; i++) {
    
12.       path += buttons[i];
    
13.       CombButtons(buttons, i + 1, r, len, button_select, path);
    
14.       path.erase(path.end() - 1);
    
15.     }
    
16.   }
    
17. }
    
18. 
    
19. void PermButtons(string& buttons, int l, int r, vector<string>& button_seq) {
    
20.   if (l == r)
    
21.     button_seq.push_back(buttons);
    
22.   else {
    
23.     for (int i = l; i <= r; i++) {
    
24.       swap(buttons[i], buttons[l]);
    
25.       PermButtons(buttons, l + 1, r, button_seq);
    
26.       swap(buttons[i], buttons[l]);
    
27.     }
    
28.   }
    
29. }
    
30. 
    
31. void PressButtons(string buttons, int i, int n, vector<string>& res,
    
32.                   string path) {
    
33.   if (i == n)
    
34.     res.push_back(path);
    
35.   else {
    
36.     path += buttons[i];
    
37.     PressButtons(buttons, i + 1, n, res, path);
    
38.     if (i + 1 < n) PressButtons(buttons, i + 1, n, res, path + '-');
    
39.   }
    
40. }
    
41. 
    
42. int main(int argc, char const* argv[]) {
    
43.   string buttons = "123";
    
44.   int n = buttons.size();
    
45.   vector<string> res;
    
46.   vector<string> button_seq;
    
47.   vector<string> button_select;
    
48.   for (int len = 1; len <= n; len++)
    
49.     CombButtons(buttons, 0, n - 1, len, button_select, "");
    
50.   for (auto bs : button_select) PermButtons(bs, 0, bs.size() - 1, button_seq);
    
51.   for (auto pb : button_seq) PressButtons(pb, 0, pb.size(), res, "");
    
52.   for (auto r : res) cout << r << endl;
    
53.   return 0;
    
54. }
    

复制代码

sumomoshinqi 发表于 2016-12-2 10:27
按按钮，先组合，再全排，然后插 '-'

PermButtons写错了吧。。这样会少很多permutation的

补充内容 (2017-1-14 15:34):
看错了 看成i+1了