有了空间怎么做网站,网站开发技术论文,洞泾做网站,wordpress 添加留言板题目描述
给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到#xff1a;
i x #xff0c;其中 i x arr.length 且 0 x d 。i - x #xff0c;其中 i - x 0 且 0 x d 。
除此以外#xff0c;你从下标 i 跳到下标 j 需要满…题目描述
给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到
i x 其中 i x arr.length 且 0 x d 。i - x 其中 i - x 0 且 0 x d 。
除此以外你从下标 i 跳到下标 j 需要满足arr[i] arr[j] 且 arr[i] arr[k] 其中下标 k 是所有 i 到 j 之间的数字更正式的min(i, j) k max(i, j)。
你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。
请注意任何时刻你都不能跳到数组的外面。 示例 1 输入arr [6,4,14,6,8,13,9,7,10,6,12], d 2
输出4
解释你可以从下标 10 出发然后如上图依次经过 10 -- 8 -- 6 -- 7 。
注意如果你从下标 6 开始你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 9 。你也不能跳到下标 4 处因为下标 5 在下标 4 和 6 之间且 13 9 。
类似的你不能从下标 3 处跳到下标 2 或者下标 1 处。
示例 2
输入arr [3,3,3,3,3], d 3
输出1
解释你可以从任意下标处开始且你永远无法跳到任何其他坐标。
示例 3
输入arr [7,6,5,4,3,2,1], d 1
输出7
解释从下标 0 处开始你可以按照数值从大到小访问所有的下标。
示例 4
输入arr [7,1,7,1,7,1], d 2
输出2
示例 5
输入arr [66], d 1
输出1 提示
1 arr.length 10001 arr[i] 10^51 d arr.length 问题分析
这道题是跳跃游戏系列的第五题有以下特点
跳跃规则 可以向左或向右跳跃跳跃距离范围是 [1, d]只能从高处往低处跳arr[i] arr[j]跳跃路径上的所有点都必须比起点低arr[i] arr[k]对于所有 i 到 j 之间的 k 目标找出从任意起点出发最多可以访问多少个下标。关键点 可以从任意下标开始需要计算的是最大访问点数而不是是否能到达某个特定目标
这个问题适合使用动态规划来解决因为跳跃决策具有重叠子问题的性质。同时由于跳跃的方向性只能从高处跳到低处我们可以按高度排序来确定解决问题的顺序。 解题思路
动态规划 记忆化搜索
我们可以定义 dp[i] 表示从下标 i 开始跳跃最多可以访问的下标数量包括起点自身。
递推关系如下
对于每个下标 i我们尝试向左或向右跳跃距离 x其中 1 x d如果可以跳到下标 j那么 dp[i] max(dp[i], 1 dp[j])
由于跳跃方向是从高到低我们需要确保先计算出较低位置的 dp 值再计算较高位置的 dp 值。一种方法是使用记忆化搜索也称为自顶向下的动态规划。
算法步骤
创建一个 dp 数组dp[i] 表示从下标 i 开始最多可以访问的下标数量将所有 dp[i] 初始化为 1至少可以访问自身使用记忆化搜索对每个下标 i 尝试向左或向右跳跃距离 x1 x d检查跳跃条件目标位置在数组范围内且路径上所有点都比起点低如果可以跳到下标 j则 dp[i] max(dp[i], 1 dp[j]) 返回所有 dp[i] 中的最大值 算法过程
以示例1为例arr [6,4,14,6,8,13,9,7,10,6,12], d 2
让我们跟踪从下标10开始的DFS过程这是最优起点
初始化 dp[10] 1至少可以访问自身当前下标10对应值12
尝试向左跳 检查下标10-19arr[10] arr[9] (12 6) ✓ 递归计算 dp[9]dp[9] 1至少可以访问自身由于没有可跳的地方dp[9] 1 检查下标10-28arr[10] arr[8] (12 10) ✓ 递归计算 dp[8]dp[8] 1检查下标8-17arr[8] arr[7] (10 7) ✓ 递归计算 dp[7]dp[7] 1检查下标7-16arr[7] arr[6] (7 9) ✗ 不能跳检查下标7-25超出范围(d2) 所以 dp[7] 1更新 dp[8] 1 dp[7] 2检查下标8-26arr[8] arr[6] (10 9) ✓ 已计算 dp[6] 1没有可跳的地方 更新 dp[8] max(2, 11) 2更新 dp[10] max(1, 1dp[8]) 12 3
最终路径 下标10 - 下标8 - 下标7 - 可能的终点无法继续跳跃或者 下标10 - 下标8 - 下标6 - 可能的终点最多访问4个下标包括起点10
事实上完整的最优路径是10 - 8 - 6 - 7总共访问4个下标。 详细代码实现
Java 实现
class Solution {private int[] dp;private int[] arr;private int d;public int maxJumps(int[] arr, int d) {int n arr.length;this.arr arr;this.d d;this.dp new int[n];// 初始化dp数组每个位置至少可以访问自身Arrays.fill(dp, -1);int maxVisited 0;for (int i 0; i n; i) {maxVisited Math.max(maxVisited, dfs(i));}return maxVisited;}private int dfs(int i) {// 如果已经计算过直接返回if (dp[i] ! -1) {return dp[i];}// 至少可以访问自身dp[i] 1;// 尝试向右跳for (int j i 1; j Math.min(i d, arr.length - 1); j) {// 检查跳跃条件if (arr[i] arr[j]) {break;}// 检查路径上的所有点boolean canJump true;for (int k i 1; k j; k) {if (arr[k] arr[i]) {canJump false;break;}}if (canJump) {dp[i] Math.max(dp[i], 1 dfs(j));}}// 尝试向左跳for (int j i - 1; j Math.max(i - d, 0); j--) {// 检查跳跃条件if (arr[i] arr[j]) {break;}// 检查路径上的所有点boolean canJump true;for (int k i - 1; k j; k--) {if (arr[k] arr[i]) {canJump false;break;}}if (canJump) {dp[i] Math.max(dp[i], 1 dfs(j));}}return dp[i];}
}
C# 实现
public class Solution {private int[] dp;private int[] arr;private int d;public int MaxJumps(int[] arr, int d) {int n arr.Length;this.arr arr;this.d d;this.dp new int[n];// 初始化dp数组for (int i 0; i n; i) {dp[i] -1;}int maxVisited 0;for (int i 0; i n; i) {maxVisited Math.Max(maxVisited, Dfs(i));}return maxVisited;}private int Dfs(int i) {// 如果已经计算过直接返回if (dp[i] ! -1) {return dp[i];}// 至少可以访问自身dp[i] 1;// 尝试向右跳for (int j i 1; j Math.Min(i d, arr.Length - 1); j) {// 检查跳跃条件if (arr[i] arr[j]) {break;}// 检查路径上的所有点bool canJump true;for (int k i 1; k j; k) {if (arr[k] arr[i]) {canJump false;break;}}if (canJump) {dp[i] Math.Max(dp[i], 1 Dfs(j));}}// 尝试向左跳for (int j i - 1; j Math.Max(i - d, 0); j--) {// 检查跳跃条件if (arr[i] arr[j]) {break;}// 检查路径上的所有点bool canJump true;for (int k i - 1; k j; k--) {if (arr[k] arr[i]) {canJump false;break;}}if (canJump) {dp[i] Math.Max(dp[i], 1 Dfs(j));}}return dp[i];}
} 复杂度分析
时间复杂度O(n²)其中n是数组的长度。在最坏情况下对于每个位置我们需要检查最多2d个可能的跳跃目标总时间复杂度为O(n * d)。由于d最大可达n所以最坏情况下时间复杂度是O(n²)。
空间复杂度O(n)主要用于存储dp数组和递归调用栈。 优化单调栈方法
上面的实现中检查路径上的所有点是否都比起点低的时间复杂度是 O(d)我们可以使用单调栈来优化这一过程降低时间复杂度。
Java 实现
class Solution {public int maxJumps(int[] arr, int d) {int n arr.length;int[] dp new int[n];Arrays.fill(dp, -1);// 将下标按照高度排序从低到高处理Integer[] indices new Integer[n];for (int i 0; i n; i) {indices[i] i;}Arrays.sort(indices, (a, b) - arr[a] - arr[b]);int maxVisited 0;for (int idx : indices) {maxVisited Math.max(maxVisited, dfs(arr, d, idx, dp));}return maxVisited;}private int dfs(int[] arr, int d, int i, int[] dp) {if (dp[i] ! -1) {return dp[i];}dp[i] 1; // 至少可以访问自身// 向右跳for (int j i 1; j Math.min(i d, arr.length - 1); j) {if (arr[i] arr[j]) {dp[i] Math.max(dp[i], 1 dfs(arr, d, j, dp));}// 如果遇到更高或相等的点则无法继续向右if (arr[j] arr[i]) {break;}}// 向左跳for (int j i - 1; j Math.max(i - d, 0); j--) {if (arr[i] arr[j]) {dp[i] Math.max(dp[i], 1 dfs(arr, d, j, dp));}// 如果遇到更高或相等的点则无法继续向左if (arr[j] arr[i]) {break;}}return dp[i];}
}
C#实现
public class Solution {public int MaxJumps(int[] arr, int d) {int n arr.Length;int[] dp new int[n];// 初始化dp数组所有值设为-1表示未计算for (int i 0; i n; i) {dp[i] -1;}// 将下标按照高度排序从低到高处理int[] indices new int[n];for (int i 0; i n; i) {indices[i] i;}Array.Sort(indices, (a, b) arr[a] - arr[b]);int maxVisited 0;foreach (int idx in indices) {maxVisited Math.Max(maxVisited, Dfs(arr, d, idx, dp));}return maxVisited;}private int Dfs(int[] arr, int d, int i, int[] dp) {// 如果已经计算过直接返回if (dp[i] ! -1) {return dp[i];}// 至少可以访问自身dp[i] 1;// 向右跳for (int j i 1; j Math.Min(i d, arr.Length - 1); j) {if (arr[i] arr[j]) {dp[i] Math.Max(dp[i], 1 Dfs(arr, d, j, dp));}// 如果遇到更高或相等的点则无法继续向右if (arr[j] arr[i]) {break;}}// 向左跳for (int j i - 1; j Math.Max(i - d, 0); j--) {if (arr[i] arr[j]) {dp[i] Math.Max(dp[i], 1 Dfs(arr, d, j, dp));}// 如果遇到更高或相等的点则无法继续向左if (arr[j] arr[i]) {break;}}return dp[i];}
} 复杂度分析
时间复杂度O(n log n n * d) 排序下标需要O(n log n)时间对于每个位置我们最多检查2d个可能的跳跃目标总共n个位置所以是O(n * d)综合起来就是O(n log n n * d)
空间复杂度O(n) 主要用于存储dp数组、排序后的下标数组和递归调用栈 优化与技巧
按高度排序处理先计算高度较低的点的dp值再计算高度较高的点的dp值可以减少重复计算。提前终止如果遇到高度大于等于当前点的位置可以提前终止搜索因为无法跳过这个位置。记忆化搜索使用dp数组存储已计算的结果避免重复计算。边界检查确保跳跃不会超出数组范围。利用问题特性由于只能从高处跳到低处整个跳跃路径形成了一个有向无环图(DAG)这使得动态规划可以正确解决此问题。
