网站文章质检,服务器一年多少钱,中铁建设集团有限公司,公司网站设x轴上的花园范围为[0,n], 0~n这个n1个离散点上有水龙头#xff0c;第 i 个水龙头能浇水的范围为[i-ranges[i], iranges[i]]. 求能浇整个花园的最小水龙头个数。
思路#xff1a;
方法一#xff1a; greedy
先把每个水龙头能浇的区间准备好#xff0c; 用一个数组保存所有…
x轴上的花园范围为[0,n], 0~n这个n1个离散点上有水龙头第 i 个水龙头能浇水的范围为[i-ranges[i], iranges[i]]. 求能浇整个花园的最小水龙头个数。
思路
方法一 greedy
先把每个水龙头能浇的区间准备好 用一个数组保存所有区间数组下标为区间起点数组内容为区间终点。
然后从左到右遍历这个数组到这里就和55题Jump Game类似了。 用一个变量canReach表示到目前的水龙头为止能浇到的最远距离。preEnd表示前一个水龙头的区间终点。
如果当前位置 preEnd说明需要开一个新的水龙头 但是如果这时canReach preEnd前一水龙头处能浇到的最远距离也无法到达当前位置后面有说明说明无法到达返回-1. 更新preEnd到canReach (canReach这时还没有更新即preEnd更新到前一个水龙头为止的最远范围). 水龙头个数1. 把canReach更新到和当前区间终点相比的较大值。
有一个特殊情况要注意下就是Example2中ranges[i]0的情况。 注意能浇水到整个花园说明不止是离散点i , i1, …能浇到i 到 i1之间的连续点部分也必须在区间中。 而ranges[i] 0 表示只能浇到离散点 i 本身。比如12点能浇到但它们之间的1.1, 1.2, …都不在浇灌范围。 所以在处理区间时canReach必须能到达当前点才算满足条件。 public int minTaps(int n, int[] ranges) {int preEnd 0;int canReach 0;int[] startEnd new int[n1];int cnt 0;for(int i 0; i n; i) {if(ranges[i] 0) continue;int start (i - ranges[i] 0 ? 0 : i - ranges[i]);int end (i ranges[i] n ? n : i ranges[i]);startEnd[start] end;}for(int i 0; i n; i) {if(i preEnd) {if(canReach preEnd) return -1;cnt ;preEnd canReach;}if(startEnd[i] canReach) canReach startEnd[i];}//cnt是前一区间满足条件时在当前区间加的最后一个区间没有下一区间去处理所以要在最后处理一下//如果preEnd能到达最后位置就不需要cnt1,如果到不了需要再cnt,preEnd更新到canReachreturn cnt (preEnd n ? 1 : 0);}方法二
DP dp[i ] 表示浇到 i 位置所需的水龙头个数。 开始的时候除了dp[0]其他全部初始化为无穷大。
还是像上面一样从左到右计算每个水龙头的浇水区间。 区间内每个点处所需的最少水龙头个数dp[ i ] min(dp[i], dp[区间的起点]1). 这是什么意义呢 因为dp[0]0, 当更新水龙头0的区间时都会以dp[0]1为准把0处的水龙头能浇到的范围内每个点处所需水龙头个数更新为1. 假设第一个区间为[0,2]更新如下 1 1 1 Inf Inf Inf 这时假如进入下一区间[2,4]那么在2的位置仍然可以保持dp[2]min(dp[2], dp[2]1)1. 到了位置3时dp[3]min(Inf,dp[2]1)就变成需要2个水龙头。 同样的如果前一范围覆盖不到后面的区间就会出现min(inf, inf1)的情况。 最后返回dp[n], 如果dp[n]为Inf, 说明无法浇到整个花园返回-1. public int minTaps(int n, int[] ranges) {final int INF 100000;int[] dp new int[n1];Arrays.fill(dp, INF);dp[0] 0;for(int i 0; i n; i) {int start (i-ranges[i] 0 ? 0 : i-ranges[i]);int end (i ranges[i] n ? n : iranges[i]);for(int j start; j end; j){dp[j] Math.min(dp[j], dp[start]1);}}return dp[n] INF ? -1 : dp[n];}
