建设网站费用如何入账,网站的二级目录是什么,响应式网站模板xd,wordpress仿百度首页灌溉花园的最少水龙头数目
题目描述
在 x 轴上有一个一维的花园。花园长度为 n#xff0c;从点 0 开始#xff0c;到点 n 结束。
花园里总共有 n 1 个水龙头#xff0c;分别位于 [0, 1, …, n] 。
给你一个整数 n 和一个长度为 n 1 的整数数组 ranges #xff0c;其中…灌溉花园的最少水龙头数目
题目描述
在 x 轴上有一个一维的花园。花园长度为 n从点 0 开始到点 n 结束。
花园里总共有 n 1 个水龙头分别位于 [0, 1, …, n] 。
给你一个整数 n 和一个长度为 n 1 的整数数组 ranges 其中 ranges[i] 下标从 0 开始表示如果打开点 i 处的水龙头可以灌溉的区域为 [i - ranges[i], i ranges[i]] 。
请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方请你返回 -1 。
样例
样例输入 n 5, ranges [3,4,1,1,0,0] n 3, ranges [0,0,0,0] 样例输出 1 解释 点 0 处的水龙头可以灌溉区间 [-3,3] 点 1 处的水龙头可以灌溉区间 [-3,5] 点 2 处的水龙头可以灌溉区间 [1,3] 点 3 处的水龙头可以灌溉区间 [2,4] 点 4 处的水龙头可以灌溉区间 [4,4] 点 5 处的水龙头可以灌溉区间 [5,5] 只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。 -1 解释即使打开所有水龙头你也无法灌溉整个花园。 提示
1n1041 n 10^41n104ranges.lengthn1ranges.length n 1ranges.lengthn10ranges[i]100 ranges[i] 100ranges[i]10
思路
大的总问题可以化为相同类型的子问题可以使用动态规划。且不仅仅可以使用动态规划还可以使用贪心思想因为在相同类型的子问题中可以取其最优解。
代码实现
动态规划
class Solution {public int minTaps(int n, int[] ranges) {int[][] arr new int[n1][2];for(int i 0; i n; i){arr[i][0] Math.max(0, i - ranges[i]);arr[i][1] Math.min(n, i ranges[i]);}Arrays.sort(arr, (a, b) - a[0] - b[0]);int[] dp new int[n1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] 0;for(int[] a : arr){if(dp[a[0]] Integer.MAX_VALUE) return -1;for(int i a[0]; i a[1]; i) dp[i] Math.min(dp[i], dp[a[0]] 1);}return dp[n];}
}贪心思想
class Solution {public int minTaps(int n, int[] ranges) {int[] right new int[n1];for(int i 0; i n; i) right[i] i;for(int i 0; i ranges.length; i){int start Math.max(0, i - ranges[i]);int end Math.min(n, i ranges[i]);right[start] Math.max(right[start], end);}int last 0, res 0, pre 0;for(int i 0; i n; i){last Math.max(last, right[i]);if(i last) return -1;if(i pre){res;pre last;}}return res;}
}
