邯郸建设网站制作,外贸卖货哪个平台好,网站前台设计软件,怎么建设网站啊目录1.题目2.思路3.代码实现#xff08;Java#xff09;1.题目
在 x 轴上有一个一维的花园。花园长度为 n#xff0c;从点 0 开始#xff0c;到点 n 结束。
花园里总共有 n 1 个水龙头#xff0c;分别位于 [0, 1, …, n] 。
给你一个整数 n 和一个长度为 n 1 的整数数…
目录1.题目2.思路3.代码实现Java1.题目
在 x 轴上有一个一维的花园。花园长度为 n从点 0 开始到点 n 结束。
花园里总共有 n 1 个水龙头分别位于 [0, 1, …, n] 。
给你一个整数 n 和一个长度为 n 1 的整数数组 ranges 其中 ranges[i] 下标从 0 开始表示如果打开点 i 处的水龙头可以灌溉的区域为 [i - ranges[i], i ranges[i]] 。
请你返回可以灌溉整个花园的最少水龙头数目。如果花园始终存在无法灌溉到的地方请你返回 -1 。
示例 1 输入n 5, ranges [3,4,1,1,0,0] 输出1 解释 点 0 处的水龙头可以灌溉区间 [-3,3] 点 1 处的水龙头可以灌溉区间 [-3,5] 点 2 处的水龙头可以灌溉区间 [1,3] 点 3 处的水龙头可以灌溉区间 [2,4] 点 4 处的水龙头可以灌溉区间 [4,4] 点 5 处的水龙头可以灌溉区间 [5,5] 只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。
示例 2 输入n 3, ranges [0,0,0,0] 输出-1 解释即使打开所有水龙头你也无法灌溉整个花园。
提示 1 n 104 ranges.length n 1 0 ranges[i] 100
来源力扣LeetCode 链接https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden
2.思路
1动态规划 思路参考本题官方题解。
3.代码实现Java
//思路1————动态规划
class Solution {public int minTaps(int n, int[] ranges) {int[][] intervals new int[n 1][];for (int i 0; i n; i) {int start Math.max(0, i - ranges[i]);int end Math.min(n, i ranges[i]);intervals[i] new int[]{start, end};}/*此时题目转换为从 [start0, end0]、[start1, end1]、...、[startn, endn] 中选出最少数目的区间使得它们可以覆盖 [0, n]*///将所有区间按照起点进行升序排序Arrays.sort(intervals, (a, b) - a[0] - b[0]);//设 dp[i] 表示覆盖区间 [0, i] 所需要的最少的区间数目int[] dp new int[n 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] 0;for (int[] interval : intervals) {int start interval[0];int end interval[1];if (dp[start] Integer.MAX_VALUE) {return -1;}for (int j start; j end; j) {dp[j] Math.min(dp[j], dp[start] 1);}}return dp[n];}
}
