垫面没做出来

判断覆盖网络需要的最少点数给一个数组每个位置代表当前位置放路由器

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

覆盖.
没做出来 只想到了暴力解

将a转化为覆盖区间clips=[[-1,1], [0,2], [0,4], [2,4], [3,5]]，然就问题就变为如何选最少的区间来覆盖[0,4]. 和LC1024相同。
My solution

1.         int videoStitching(vector<vector<int>>& clips, int T)
   
2.     {
   
3.       sort(clips.begin(), clips.end()); // sort clips by start
   
4.       
   
5.       int i = 0; // clips index
   
6.       int maxReach = 0; // max time reachable by clips
   
7.       int cnt = 0; // number of clips needed
   
8.       
   
9.       while (maxReach < T) {
   
10.         int currentMaxReach = 0;
    
11.         while (i < clips.size() && clips[i][0] <= maxReach)
    
12.           currentMaxReach = max(currentMaxReach, clips[i++][1]);
    
13.         
    
14.         if (currentMaxReach <= maxReach) return -1; // can't reach further
    
15.         maxReach = currentMaxReach;
    
16.         cnt++; // need an additional clip to reach new maxReach        
    
17.       }
    
18.       
    
19.       return cnt;
    
20.     }

复制代码

[/i]

henry_ma 发表于 2020/02/08 16:08:08
啊，谢谢大佬的讲解，我原本以为要用贪心法来做哩

不是大佬...不客气哈哈哈哈，既然你懂了，还请你帮忙给我加个米呀～新人想多求点米看面经...

woyaoshuati 发表于 2020-2-8 08:15
和lc易散尔溜很像

不是很像，就是

[1,1,2,1,1]  转换成 [4, 0, 2, 1, 0] 变成jump game O(n)

lyronly 发表于 2020/02/08 07:26:37
[1,1,2,1,1]  转换成 [4, 0, 2, 1, 0] 变成jump game O(n)

不太明白中间是怎么转换的，层主能稍微详细讲讲么？

似乎是二维dp

dp[i][j] = min (dp[i-1][j]  + A[i,..j]里的路由器能覆盖A[i-1] ? 0 : 1, dp[i][j+1] + A[i,..j]里路由器能覆盖A[j] ? 0 : 1])

假设路由器至少能覆盖自己(A[i] >= 1 for all i)

best O(n^2)

和lc易散尔溜很像

谷歌又开始面全职了吗？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

thorax 发表于 2020/02/08 08:06:15
似乎是二维dp

dp[j] = min (dp[i-1][j]  + A[i,..j]里的路由器能覆盖A[i-1]...

应该不是二维dp，二维dp的时间复杂度没比brute force好。这个可以巧妙地转为一维dp，可以看我下面给别人的回复。

请问这是哪家的店面？