谷歌google跪经

zzgzzm 发表于 2016-11-21 14:28
第一题：这个题应该可以DP: 假设delta[]是相邻加油站的间距，并且是sorted（这个题与顺序无关，所以若不是s ...

能否看一下我在4楼的贴子？我感觉我只需要O(lgk * n)
k = 初始的间距数量
n = 插入的加油站数

补充内容 (2016-11-21 14:59):
包含一開始的建立heap應該是O(k + lgk * n)

zzgzzm 发表于 2016-11-21 14:56
第一题贪心算法是不行的，比如两个间距1，9。要求再加2个点。最优结果应该是3，但贪心算法结果为4。因为 ...

谢谢反例~想太简单了

catinclay 发表于 2016-11-21 14:57
能否看一下我在4楼的贴子？我感觉我只需要O(lgk * n)
k = 初始的间距数量
n = 插入的加油站数

说真的，我很佩服你的max heap设计！不算初始化heap，你是时间复杂度的确只有O(n*logk)，而我的DP不算初始化排序时间O(n*k*logn)太慢了。

你的这个max heap真的很巧妙，我把你的描述用数学严格证明一下：（纯娱乐了。。。）因为我刚看到这个题的时候就感觉是个数学问题。

给定正数列{d_j} (1<=j<=N)和整数C>=0，求非负整数列k = {k_j}最优解使得目标函数F_c(k)最小化：
F_c(k) := Max_j(d_j/(k_j+1)), 其中k = {k_j}的元素总和为C.
对于C=0, 显然每个k_j = 0 (1<=j<=N)为最优解。
若对于C的最优解为{k_j}, 那么对于C+1的最优解如下构造：
存在指标j’(1<=j’<=N)使得d_j’/(k_j’+1) = F_c(k), 那么将{k_j}中的k_j’换为1+k_j’，其它不变，一定是对于C+1的最优解(最小化F_{c+1})。
证明：证明k_1, k_2, …, 1+k_j’,…,k_N是F_{c+1}的最优解，就是等价于对任意解{g_j}（总和为C+1），证明：
对任意j!=j’有d_j/(k_j+1) <= F_{c+1}(g) 以及d_j’/(k_j’+2) <= F_{c+1}(g)。（*）
分两种情况：
1. 若g_j’ = 0，那么d_j/(k_j+1) <= d_j’/(k_j’+1)<=d_j’<=F_{c+1}(g)，并且d_j’/(k_j’+2)<= d_j’<=F_{c+1}(g).
2. 若g_j’>0，那么g_1, g_2, …, g_j’-1,…,g_N是F_c的一个解，但我们已假设F_c的最优解为{k_j}，所以d_j’/(k_j’+1) = F_c(k)<= max(d_j*/(g_j*+1), d_j’/g_j’)对于某个j* != j’。
若 d_j*/(g_j*+1)>= d_j’/g_j’，那么d_j/(k_j+1)<= d_j’/(k_j’+1)<=d_j*/(g_j*+1)<=F_{c+1}(g)，并且d_j’/(k_j’+2)< d_j’/(k_j’+1)<= d_j*/(g_j*+1)<=F_{c+1}(g)，所以结论(*)得证。
否则d_j*/(g_j*+1) < d_j’/g_j’，那么d_j’/(k_j’+1)< d_j’/g_j’，所以k_j’+1>g_j’，即k_j’>=g_j’。  那么d_j’/(k_j’+2)< d_j’/(g_j’+1)<=F_{c+1}(g)，并且d_j/(k_j+1)<= d_j’/(k_j’+1)<= d_j’/(g_j’+1)<=F_{c+1}(g)，所以结论(*)得证。

补充内容 (2016-11-22 02:46):
我是对于坐标为一般的double类型分析的，若是int类型的话应该也不影响实现。

第四题：这个题貌似很喜欢考

1. string getCountryByWeight(vector<pair<string, double>>& cw) {
   
2.   vector<double> pdf = {0.0}; double sum = 0.0;
   
3.   for (auto& x:cw) { // create probability distribution function (pdf)
   
4.     pdf.push_back(pdf.back()+x.second);
   
5.     sum += x.second;
   
6.   }
   
7.   for (auto& p:pdf) p /= sum;
   
8.   int i = lower_bound(pdf.begin(), pdf.end(), rand()/RAND_MAX) - pdf.begin();
   
9.   return cw[i-1].first;
   
10. }

复制代码

zzgzzm 发表于 2016-11-22 01:23
说真的，我很佩服你的max heap设计！不算初始化heap，你是时间复杂度的确只有O(n*logk)，而我的DP不算初 ...

我比较佩服你能用dp解...我是刚好灵光乍现想到的..

...竟然当场写Word squares II，有点狠啊

感觉第一题有点像lc410?

第二题candy crash: 这个好像就是随机的一行一行从左向右生在board上成均匀随机数{1, 2, 3, 4}。在位置(i,j)时，同时检查若纵向(i-1,j)与(i-2,j)的candy相同，那么(i,j)不能放这种candy；同理对横向(i,j-1), (i,j-2)同样处理。将不允许放的candy从{1, 2, 3, 4}去除然后再均匀分布生成。

1. // candy at cell[i][j] could be 1, 2, 3 or 4
   
2. vector<vector<int>> getRandCandyBoard(int n) {
   
3.   vector<vector<int>> board(n, vector<int>(n));
   
4.   // options[i][i]: candy options if candy i and j not allowed: O(1) time/space
   
5.   vector<vector<vector<int>>> options(n, vector<vector<int>>(n));
   
6.   for (int i = 0; i <= 4; ++i)
   
7.   for (int j = 0; j <= 4; ++j) {
   
8.     for (int k = 1; k <= 4; ++k) if (k != i && k != j) options[i][j].push_back(k);
   
9.   }  
   
10.   
    
11.   // O(n^2) time
    
12.   for (int i = 0; i < n; ++i)
    
13.   for (int j = 0; j < n; ++j) {
    
14.     int vert = 0, hor = 0; // not allowed candy
    
15.     if (i > 1 && board[i-1][j] == board[i-2][j]) vert = board[i-1][j];
    
16.     if (j > 1 && board[i][j-1] == board[i][j-2]) hor  = board[i][j-1];
    
17.     board[i][j] = options[vert][hor][rand()%options[vert][hor].size()];
    
18.   }
    
19.   return board;
    
20. }

复制代码

补充内容 (2016-11-24 07:12):
我的方法也未必是等概率的。用3X1的棋盘验证即可，若4种candy的话共有60种棋盘，但我的方法给出12种以概率1/48出现，48种以概率1/64出现。不是每个1/60的等概率。

catinclay 发表于 2016-11-22 03:10
我比较佩服你能用dp解...我是刚好灵光乍现想到的..

DP基本相当于暴力解了,correctness比较显然但效率低。
Max Heap在每次加入点后及时优化自动调出当前的max subinterval（max heap）, 高效率。就是correctness要证明还真不容易。

zzgzzm 发表于 2016-11-22 01:23
说真的，我很佩服你的max heap设计！不算初始化heap，你是时间复杂度的确只有O(n*logk)，而我的DP不算初 ...

这个heap的复杂度是O(k*logn)吧，虽然应该也没什么差别
证明的话induction可以更清晰一些，可以直接比较最后答案得到结论，不过应该都差不多
DP的话不单调优化确实比较好想，我觉得两种算法都很不错，当然从复杂度考虑确实heap更巧妙一些