新鲜狗狗店面，感觉是跪了啊。。。

第二题一般都是binary search， 还算靠谱

mazytes 发表于 2016-9-1 13:38
OA是面经的意思吗？

OA = Online Assessment.
现在大公司似乎越来越有一个趋势是用这个方法在人工筛选简历之前做在线测试，减少人工成本。也可能OA也指电话面试的一种吧，我不是很肯定。

感觉和lc410题很像

我定义供暖站覆盖范围m是指覆盖m个连续整数[left, left+m-1]。若是指单位区间个数的话类似，不影响算法实现。
第一个问给定m，求最小的n。这个应该用greedy。对于给定的每个station的覆盖范围[left, left+m-1] (m给定)，首先找最左边还没有覆盖的第一个房子，用station的左边缘覆盖（这样还可以同时覆盖右边其它的房子），然后看还有没有未被覆盖的房子。若没有的话算法就完成，否则继续。最差情况时间复杂度O(N) (N为房子个数)，当房子间距比起station覆盖范围来说非常稀疏时。
第二问给定n，求最小的m。利用第一问已有的方法对station覆盖范围做binary search. 下限当然=1，上限=最两边的房子间距+1. 因为房子给定是在1D array上，所以最大间距范围不过int范围，这样外层binary search 时间O(log(int range))我觉得可以按常数对待吧，内部每次搜索调用第一题的O(N)算法，最终时间复杂度也为O(N)。

1. // assume houses is a sorted array
   
2. // a station covers [left, left+m-1]
   
3. int minStation(vector<int>& houses, int m) {
   
4.   if (m <= 0) return INT_MAX; // cannot cover
   
5.   int n = 0; // number of stations needed
   
6.   int left = INT_MIN; // left boundary of current coverage
   
7.   auto pos = houses.begin(); // position of first uncovered house
   
8.   while ((pos = upper_bound(pos, houses.end(), left+m-1)) != houses.end()) {
   
9.      n++;
   
10.      left = *pos; // left boundary of next coverage
    
11.   }
    
12.   return n;
    
13. }
    
14. 
    
15. int minCoverage(vector<int>& houses, int n) {
    
16.   int nHouses = houses.size();
    
17.   if (nHouses <= n) return 1; // if we have sufficiently many stations
    
18.   int minCover = 1, maxCover = houses[nHouses-1] - houses[0];
    
19.   while (minCover < maxCover) {
    
20.     int mid = (minCover+maxCover)/2;
    
21.     if (minStation(houses, mid) <= n) maxCover = mid;
    
22.     else minCover = mid + 1;
    
23.   }
    
24.   return minCover;
    
25. }

复制代码

补充内容 (2016-10-28 09:59):
C++ API: ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)是在范围[first, last)中寻找第一个大于val的元素并返回iterator. 若找不到就返回last.

huai10 发表于 2016-10-26 14:16
第二题一般都是binary search， 还算靠谱

请问第二题用binary search的话怎么判断当前猜的m是大是小呢？难道每次都要再把array of house再扫一遍吗

syjohnson 发表于 2016-10-30 12:23
请问第二题用binary search的话怎么判断当前猜的m是大是小呢？难道每次都要再把array of house再扫一遍吗

应该是再扫一遍，因为对于不同的m来说，这个覆盖的格局可能会彻底改变。利用第一问已有的方法对station覆盖范围做binary search. 下限当然=1，上限=最两边的房子间距+1. 因为房子给定是在1D array上，所以最大间距范围不过int范围，这样外层binary search 时间O(log(int range))我觉得可以按常数对待吧，内部每次搜索调用第一题的O(N)算法，最终时间复杂度也为O(N)。我自己写了一下在24层。

zzgzzm 发表于 2016-10-30 12:48
应该是再扫一遍，因为对于不同的m来说，这个覆盖的格局可能会彻底改变。利用第一问已有的方法对station覆 ...

多谢回答！

第二问应该是dp吧
一个维度是供电站的个数i:0->n
一个维度是前j个供电站所需要的覆盖的范围m

dp[i][j]= max(dp[i-1][j] ,(A[A.size()-1]- A[j])/2)

wangyiduo999 发表于 2016-10-31 02:39
第二问应该是dp吧
一个维度是供电站的个数i:0->n
一个维度是前j个供电站所需要的覆盖的范围m

不是很明白这个DP的意思。dp[i][j]本身的定义是什么？是指是用i个站来供应前j个房子的每个站的最小m吗？
每个供暖站的覆盖范围m都是一样的。我觉得这个题不好用i-1的结果来推算i的结果。例如若只有2个房子A[0]<A[1]，若要求只用一个供暖站的话，那么就得覆盖半径(A[1]-A[0])/2. 但如果可以用2个站的话，每个站只覆盖A[i]一个孤立点就可以了，覆盖半径=0，和房子间距无关了。

电面时候可以用纸笔自己画一画吗？还是只能在屏幕上打code？