谷歌跪经

619899442 发表于 2018-3-11 07:51
大概思路就是求最少多少次可以「保证」猜到，这是一种博弈问题，博弈双方（玩家/系统）都是完全理性的。 ...

明白了，谢谢！所以return min()即为所求，min的输入参数Set<Integer>是4位整数所有可能组合，作为起始状态。

heroic 发表于 2018-3-11 05:40
recursive的空间复杂度和递归树depth有关，含有n个元素的递归树，深度至少也是logn，不知道O(1)递归解法是 ...

面试官说递归函数栈应该不算空间的overhead

weindyu 发表于 2018-3-11 13:07
面试官说递归函数栈应该不算空间的overhead

也是醉了 那样recursive的dfs就是O(1)时间复杂度而用stack就是O(n)了。

给一个第四题的思路，只是一个recursion的解法，这里并没有考虑空间问题。

1. string pre2post(string pre) {
   
2.     if (pre.size() <= 1) return pre;
   
3.     if (!isalpha(pre[0])) {
   
4.         int operandCount = 0;
   
5.         int operatorCount = 0;
   
6.         size_t mid = 1;
   
7.         while (mid < pre.size() && operandCount - operatorCount != 1) {
   
8.             if (!isalpha(pre[mid])) operatorCount++;
   
9.             else operandCount++;
   
10.             mid++;
    
11.         }
    
12.         string a = pre2post(pre.substr(1, mid));
    
13.         string b = pre2post(pre.substr(mid));
    
14.         return a + b + pre[0];
    
15.     } else  {
    
16.         return pre.substr(0, 1);
    
17.     }
    
18. }
    

复制代码

补充内容 (2018-11-18 19:46):
稍微调整return和string的index的顺序应该也可以用于preorder，postorder和inorder之间的互转

楼主感谢内推，buffalo.edu邮箱，麻烦了

内推过来的 已发 usc邮箱

内推请求email已发， 感谢！