asp语言的网站建设,凡科网站能在百度做推广吗,高端网站开发怎么选,生鲜网站开发背景灌溉花园的最少水龙头数目【LC1326】 在 x 轴上有一个一维的花园。花园长度为 n#xff0c;从点 0 开始#xff0c;到点 n 结束。 花园里总共有 n 1 个水龙头#xff0c;分别位于 [0, 1, ..., n] 。 给你一个整数 n 和一个长度为 n 1 的整数数组 ranges #xff0c;其中 …灌溉花园的最少水龙头数目【LC1326】 在 x 轴上有一个一维的花园。花园长度为 n从点 0 开始到点 n 结束。 花园里总共有 n 1 个水龙头分别位于 [0, 1, ..., n] 。 给你一个整数 n 和一个长度为 n 1 的整数数组 ranges 其中 ranges[i] 下标从 0 开始表示如果打开点 i 处的水龙头可以灌溉的区域为 [i - ranges[i], i ranges[i]] 。 请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方请你返回 -1 。 过了的那一刻很是震惊 也许是昨天周赛刚看的01背包也许不大恰当但是我做出来了
01背包 思路每个水龙头有选或者不选两种可能因此转化为01背包问题 物品为每个水龙头的灌溉范围背包容量为灌溉范围表示背包能灌溉0−j0-j0−j范围内的花园。定义状态dp[j]dp[j]dp[j]表示 灌溉范围为0−j0-j0−j时所需要的最少水龙头数目。dp[n]dp[n]dp[n]即为最终结果如果位置iii的水龙头的灌溉范围为[l,r][i−ranges[i],iranges[i]][l,r][i-ranges[i],iranges[i]][l,r][i−ranges[i],iranges[i]]枚举每一个灌溉范围小于rrr的背包更新需要的水龙头数目。 一维动态规划 确定dp数组dp table以及下标的含义 dp[j]dp[j]dp[j]表示 灌溉范围为0−j0-j0−j时所需要的最少水龙头数目。 确定递推公式 对于每一个位置的水龙头更新其能灌溉的右范围 位置i不放水龙头dp[j]dp[j]dp[j] dp[j]dp[j]dp[j] 位置i放水龙头该水龙头的灌溉范围记为[l,r][l,r][l,r] 如果l≤0l\le 0l≤0那么dp[j]1dp[j]1dp[j]1 如果l0l\gt 0l0那么能否灌溉[0,j][0,j][0,j]与[0,l][0,l][0,l]所需要的水龙头数目相关 dp[j]dp[l]1dp[j]dp[l]1 dp[j]dp[l]1 dp数组如何初始化 当位置0的灌溉范围一定大于等于0那么灌溉原点需要的最少水龙头数目为1 初始情况时其他的范围均灌溉不到因此初始化为任意不可能的数值我选择初始化为n2n2n2当最终结果dp[n]n2dp[n]n2dp[n]n2时就表示可以灌溉整个花园 dp[0] 1;
dp[1,n] n 1;确定遍历顺序 一维dp 先遍历物品再从后往前遍历背包重量将物品i放进能放进的背包j中 举例推导dp数组 class Solution {public int minTaps(int n, int[] ranges) {int[] dp new int[n 1];Arrays.fill(dp, n 2);dp[0] 1;for (int i 0; i n; i){int l i - ranges[i], r i ranges[i];for (int j Math.min(r, n); j 0; j--){if (l 0){dp[j] 1;}else{dp[j] Math.min(dp[l] 1, dp[j]);}}}return dp[n] n 2 ? dp[n] : -1;}
}复杂度 时间复杂度O(n2)O(n^2)O(n2),n为数组长度空间复杂度O(n)O(n)O(n)dp数组的额外空间
贪心 思路 首先对于所有能覆盖某个左端点的水龙头选择能覆盖最远右端点的那个水龙头是最优的。【贪心】那么可以先预处理rangesrangesranges数组求出所有能覆盖左端点lll的水龙头中右端点最大的那个位置记录在数组 rightMost[i]中。那么从原点出发记录当前所达到的右端点cur和下一个可以达到的位置next 当next与cur相等时无法进行移动返回-1否则移动到next步骤1 class Solution {public int minTaps(int n, int[] ranges) {int[] rightMost new int[n 1];for (int i 0; i n; i) {int r ranges[i];// 这样写可以在 ir 时少写一个 max// 凭借这个优化恭喜你超越了 100% 的用户// 说「超越」是因为原来的最快是 2ms现在优化后是 1msif (i r) rightMost[i - r] i r; // 对于 i-r 来说ir 必然是它目前的最大值else rightMost[0] Math.max(rightMost[0], i r);}int ans 0;int curRight 0; // 已建造的桥的右端点int nextRight 0; // 下一座桥的右端点的最大值for (int i 0; i n; i) { // 注意这里没有遍历到 n因为它已经是终点了nextRight Math.max(nextRight, rightMost[i]);if (i curRight) { // 到达已建造的桥的右端点if (i nextRight) return -1; // 无论怎么造桥都无法从 i 到 i1curRight nextRight; // 造一座桥ans;}}return ans;}
}作者灵茶山艾府
链接https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/solutions/2123855/yi-zhang-tu-miao-dong-pythonjavacgo-by-e-wqry/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。复杂度 时间复杂度O(n)O(n)O(n),n为数组长度 空间复杂度O(n)O(n)O(n)rightMost数组的额外空间
