雅布设计,站长之家的seo综合查询工具,怎样打小广告最有效,个人租车网站源码1. 题目
给你一个整数数组 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 需要满足…1. 题目
给你一个整数数组 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 1000
1 arr[i] 10^5
1 d arr.length来源力扣LeetCode 链接https://leetcode-cn.com/problems/jump-game-v 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. DP解题
相关题目 LeetCode 55. 跳跃游戏贪心 LeetCode 45. 跳跃游戏 II贪心/BFS难 LeetCode 1306. 跳跃游戏 III广度优先搜索BFS LeetCode 1345. 跳跃游戏 IVBFS LeetCode LCP 09. 最小跳跃次数
首先根据题意只能往低了跳且中间不能遇到比我高的用 dp[i] 表示从 i 开始跳最多可以跳的台阶数那么 dp 需要从低的开始往高的计算所以要先排序状态转移方程 dp[i]max(dp[i],1dp[j])dp[i] max(dp[i], 1dp[j])dp[i]max(dp[i],1dp[j]), 从 i 跳到所有可能的 j
class Solution {
public:int maxJumps(vectorint arr, int d) {int i, j, n arr.size(), idx;vectorint dp(n, 0);//dp数组multimapint, int m;for (i 0; i n; i)m.insert(make_pair(arr[i],i));//map有序默认升序按数值排序了for(auto it : m){ //从低到高开始dpidx it.second;//下标dp[idx] 1;//至少为1自己本身for(j idx-1; j idx-d j0 arr[idx] arr[j]; j--){ //往左边跳遇到比我高的停止dp[idx] max(dp[idx], 1dp[j]);}for(j idx1; j idxd jn arr[idx] arr[j]; j){ //往右边跳遇到比我高的停止dp[idx] max(dp[idx], 1dp[j]);}}return *max_element(dp.begin(),dp.end());//取最大值}
};
