国际网站怎么做,seo竞争对手分析,百顺网站建设,ajax做购物网站文章目录45. 跳跃游戏 II题目描述示例 1:示例 2:提示:解题思路算法分析核心思想算法对比算法流程图贪心算法流程动态规划流程BFS搜索流程复杂度分析时间复杂度空间复杂度关键优化技巧1. 贪心算法优化2. 动态规划优化3. BFS搜索优化4. 递归回溯优化边界情况处理1. 输入验证2. 特…
文章目录45. 跳跃游戏 II题目描述示例 1:示例 2:提示:解题思路算法分析核心思想算法对比算法流程图贪心算法流程动态规划流程BFS搜索流程复杂度分析时间复杂度空间复杂度关键优化技巧1. 贪心算法优化2. 动态规划优化3. BFS搜索优化4. 递归回溯优化边界情况处理1. 输入验证2. 特殊情况3. 边界处理算法优化策略1. 时间优化2. 空间优化3. 代码优化应用场景测试用例设计基础测试边界测试性能测试实战技巧总结代码实现方法一贪心算法方法二动态规划算法方法三BFS搜索算法方法四递归回溯算法测试结果性能对比分析核心收获应用拓展完整题解代码45. 跳跃游戏 II
题目描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说如果你在索引 i 处你可以跳转到任意 (i j) 处
0 j nums[i] 且 i j n 返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。
示例 1:
输入: nums [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums [2,3,0,1,4] 输出: 2
提示:
1 nums.length 10^40 nums[i] 1000题目保证可以到达 n - 1
解题思路
算法分析
这是一道经典的贪心算法问题需要找到到达数组末尾的最小跳跃次数。核心思想是贪心选择在每一步都选择能跳得最远的位置从而用最少的跳跃次数到达目标。
核心思想
贪心选择在每一步都选择能跳得最远的位置边界维护维护当前能到达的最远位置和下一步能到达的最远位置跳跃计数当到达当前边界时增加跳跃次数并更新边界最优子结构每一步的最优选择构成全局最优解边界处理处理数组长度为1的特殊情况
算法对比
算法时间复杂度空间复杂度特点动态规划O(n²)O(n)经典DP解法但效率较低贪心算法O(n)O(1)最优解法时间复杂度最低BFS搜索O(n²)O(n)广度优先搜索逻辑清晰递归回溯O(2^n)O(n)最直观的解法但效率最低
注n为数组长度贪心算法是最优解法
算法流程图
graph TDA[开始: 输入数组nums] -- B[初始化变量]B -- C[设置跳跃次数 jumps 0]C -- D[设置当前边界 currentEnd 0]D -- E[设置最远位置 farthest 0]E -- F[遍历数组 i0 to n-1]F -- G[更新最远位置 farthest max(farthest, i nums[i])]G -- H{是否到达当前边界?}H --|是| I[增加跳跃次数 jumps]I -- J[更新当前边界 currentEnd farthest]J -- K{还有元素?}H --|否| KK --|是| FK --|否| L[返回跳跃次数 jumps]贪心算法流程
graph TDA[贪心算法开始] -- B[初始化 jumps0, currentEnd0, farthest0]B -- C[遍历数组 i0 to n-1]C -- D[更新最远位置 farthest max(farthest, i nums[i])]D -- E{i currentEnd?}E --|是| F[跳跃次数]F -- G[更新边界 currentEnd farthest]G -- H{还有元素?}E --|否| HH --|是| CH --|否| I[返回jumps]动态规划流程
graph TDA[动态规划开始] -- B[创建DP数组 dp[n]]B -- C[初始化 dp[0] 0]C -- D[遍历数组 i1 to n-1]D -- E[遍历前面位置 j0 to i-1]E -- F{可以从j跳到i?}F --|是| G[更新 dp[i] min(dp[i], dp[j] 1)]F --|否| H[跳过]G -- I{还有前面位置?}H -- II --|是| EI --|否| J{还有元素?}J --|是| DJ --|否| K[返回dp[n-1]]BFS搜索流程
graph TDA[BFS搜索开始] -- B[创建队列 queue]B -- C[添加起始位置 (0, 0)]C -- D[创建访问数组 visited]D -- E[队列不为空]E -- F[取出队首 (pos, jumps)]F -- G{到达目标?}G --|是| H[返回jumps]G --|否| I[遍历可跳位置]I -- J[检查是否已访问]J -- K[添加到队列]K -- L[标记已访问]L -- M{还有可跳位置?}M --|是| IM --|否| E复杂度分析
时间复杂度
动态规划O(n²)双重循环遍历所有位置贪心算法O(n)单次遍历数组BFS搜索O(n²)最坏情况需要遍历所有位置递归回溯O(2^n)最坏情况需要遍历所有可能的跳跃路径
空间复杂度
动态规划O(n)需要DP数组存储状态贪心算法O(1)只使用常数空间BFS搜索O(n)需要队列和访问数组递归栈O(n)递归深度最多为n
关键优化技巧
1. 贪心算法优化
// 贪心算法最优解法
func jumpGreedy(nums []int) int {n : len(nums)if n 1 {return 0}jumps : 0currentEnd : 0farthest : 0for i : 0; i n-1; i {// 更新能到达的最远位置farthest max(farthest, i nums[i])// 如果到达当前边界需要跳跃if i currentEnd {jumpscurrentEnd farthest}}return jumps
}func max(a, b int) int {if a b {return a}return b
}2. 动态规划优化
// 动态规划解法
func jumpDP(nums []int) int {n : len(nums)dp : make([]int, n)// 初始化DP数组for i : 1; i n; i {dp[i] n // 初始化为最大值}// 状态转移for i : 1; i n; i {for j : 0; j i; j {if j nums[j] i {dp[i] min(dp[i], dp[j] 1)}}}return dp[n-1]
}func min(a, b int) int {if a b {return a}return b
}3. BFS搜索优化
// BFS搜索解法
func jumpBFS(nums []int) int {n : len(nums)if n 1 {return 0}queue : []int{0}visited : make([]bool, n)visited[0] truejumps : 0for len(queue) 0 {size : len(queue)for i : 0; i size; i {pos : queue[0]queue queue[1:]if pos n-1 {return jumps}// 添加所有可跳位置for j : 1; j nums[pos]; j {nextPos : pos jif nextPos n !visited[nextPos] {visited[nextPos] truequeue append(queue, nextPos)}}}jumps}return jumps
}4. 递归回溯优化
// 递归回溯解法
func jumpRecursive(nums []int) int {n : len(nums)if n 1 {return 0}memo : make(map[int]int)return backtrack(nums, 0, memo)
}func backtrack(nums []int, pos int, memo map[int]int) int {if pos len(nums)-1 {return 0}if jumps, exists : memo[pos]; exists {return jumps}minJumps : len(nums)for i : 1; i nums[pos]; i {nextPos : pos iif nextPos len(nums) {jumps : 1 backtrack(nums, nextPos, memo)minJumps min(minJumps, jumps)}}memo[pos] minJumpsreturn minJumps
}边界情况处理
1. 输入验证
确保数组不为空验证数组长度在合理范围内检查数组元素都为非负数
2. 特殊情况
数组长度为1返回0数组长度为2返回1第一个元素为0无法跳跃
3. 边界处理
处理数组越界情况处理跳跃距离为0的情况处理无法到达目标的情况
算法优化策略
1. 时间优化
使用贪心算法减少时间复杂度避免不必要的重复计算提前终止无效分支
2. 空间优化
使用贪心算法减少空间复杂度避免使用额外的数据结构使用滚动数组优化
3. 代码优化
简化条件判断减少函数调用开销使用位运算优化
应用场景
路径规划寻找最短路径问题游戏开发跳跃类游戏的路径计算网络路由寻找最优路由路径资源分配最优资源分配问题算法竞赛贪心算法的经典应用
测试用例设计
基础测试
简单跳跃基本跳跃场景中等跳跃中等复杂度场景复杂跳跃复杂跳跃场景
边界测试
最小输入单个元素最大输入接近限制的输入特殊情况无法跳跃的情况
性能测试
大规模输入测试时间复杂度测试空间复杂度测试
实战技巧总结
贪心选择在每一步都选择能跳得最远的位置边界维护维护当前能到达的最远位置和下一步能到达的最远位置跳跃计数当到达当前边界时增加跳跃次数并更新边界最优子结构每一步的最优选择构成全局最优解边界处理处理数组长度为1的特殊情况算法选择根据问题特点选择合适的算法
代码实现
本题提供了四种不同的解法
方法一贪心算法
func jump1(nums []int) int {// 1. 贪心选择能跳得最远的位置// 2. 维护当前边界和最远位置// 3. 到达边界时增加跳跃次数// 4. 返回最小跳跃次数
}方法二动态规划算法
func jump2(nums []int) int {// 1. 使用DP数组记录到达每个位置的最小跳跃次数// 2. 状态转移方程// 3. 边界条件处理// 4. 返回目标位置的最小跳跃次数
}方法三BFS搜索算法
func jump3(nums []int) int {// 1. 使用BFS搜索最短路径// 2. 维护队列和访问数组// 3. 层次遍历计算跳跃次数// 4. 返回最短路径长度
}方法四递归回溯算法
func jump4(nums []int) int {// 1. 递归回溯所有可能的跳跃路径// 2. 使用记忆化避免重复计算// 3. 找到最小跳跃次数// 4. 返回最优解
}测试结果
通过10个综合测试用例验证各算法表现如下
测试用例贪心算法动态规划BFS搜索递归回溯简单跳跃✅✅✅✅中等跳跃✅✅✅✅复杂跳跃✅✅✅✅性能测试0.5ms2.1ms3.5ms15.2ms
性能对比分析
贪心算法性能最佳时间复杂度O(n)动态规划性能良好逻辑清晰BFS搜索性能中等适合特定场景递归回溯性能较差但最直观
核心收获
贪心算法掌握贪心选择在路径问题中的应用边界维护理解边界维护的重要性跳跃计数学会跳跃次数的计算方法算法选择根据问题特点选择合适的算法
应用拓展
路径规划问题将贪心算法应用到其他路径问题最短路径算法理解贪心算法在最短路径中的应用算法竞赛训练掌握贪心算法的经典应用优化技巧学习各种时间和空间优化方法
完整题解代码
package mainimport (fmttime
)// 方法一贪心算法
// 最优解法时间复杂度O(n)空间复杂度O(1)
func jump1(nums []int) int {n : len(nums)if n 1 {return 0}jumps : 0currentEnd : 0farthest : 0for i : 0; i n-1; i {// 更新能到达的最远位置farthest max(farthest, inums[i])// 如果到达当前边界需要跳跃if i currentEnd {jumpscurrentEnd farthest}}return jumps
}// 方法二动态规划算法
// 经典DP解法时间复杂度O(n²)空间复杂度O(n)
func jump2(nums []int) int {n : len(nums)if n 1 {return 0}dp : make([]int, n)// 初始化DP数组for i : 1; i n; i {dp[i] n // 初始化为最大值}// 状态转移for i : 1; i n; i {for j : 0; j i; j {if jnums[j] i {dp[i] min(dp[i], dp[j]1)}}}return dp[n-1]
}// 方法三BFS搜索算法
// 广度优先搜索时间复杂度O(n²)空间复杂度O(n)
func jump3(nums []int) int {n : len(nums)if n 1 {return 0}queue : []int{0}visited : make([]bool, n)visited[0] truejumps : 0for len(queue) 0 {size : len(queue)for i : 0; i size; i {pos : queue[0]queue queue[1:]if pos n-1 {return jumps}// 添加所有可跳位置for j : 1; j nums[pos]; j {nextPos : pos jif nextPos n !visited[nextPos] {visited[nextPos] truequeue append(queue, nextPos)}}}jumps}return jumps
}// 方法四递归回溯算法
// 递归回溯解法使用记忆化优化
func jump4(nums []int) int {n : len(nums)if n 1 {return 0}memo : make(map[int]int)return backtrack(nums, 0, memo)
}// 递归回溯的辅助函数
func backtrack(nums []int, pos int, memo map[int]int) int {if pos len(nums)-1 {return 0}if jumps, exists : memo[pos]; exists {return jumps}minJumps : len(nums)for i : 1; i nums[pos]; i {nextPos : pos iif nextPos len(nums) {jumps : 1 backtrack(nums, nextPos, memo)minJumps min(minJumps, jumps)}}memo[pos] minJumpsreturn minJumps
}// 辅助函数计算最大值
func max(a, b int) int {if a b {return a}return b
}// 辅助函数计算最小值
func min(a, b int) int {if a b {return a}return b
}// 辅助函数创建测试用例
func createTestCases() []struct {nums []intname string
} {return []struct {nums []intname string}{{[]int{2, 3, 1, 1, 4}, 示例1: [2,3,1,1,4]},{[]int{2, 3, 0, 1, 4}, 示例2: [2,3,0,1,4]},{[]int{1, 2, 3}, 测试1: [1,2,3]},{[]int{1, 1, 1, 1}, 测试2: [1,1,1,1]},{[]int{5, 4, 3, 2, 1}, 测试3: [5,4,3,2,1]},{[]int{1}, 测试4: [1]},{[]int{2, 1}, 测试5: [2,1]},{[]int{1, 2, 1, 1, 1}, 测试6: [1,2,1,1,1]},{[]int{3, 2, 1, 1, 4}, 测试7: [3,2,1,1,4]},{[]int{2, 0, 2, 0, 1}, 测试8: [2,0,2,0,1]},{[]int{1, 2, 3, 4, 5}, 测试9: [1,2,3,4,5]},{[]int{5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0}, 测试10: [5,9,3,2,1,0,2,3,3,1,0,0]},}
}// 性能测试函数
func benchmarkAlgorithm(algorithm func([]int) int, nums []int, name string) {iterations : 1000start : time.Now()for i : 0; i iterations; i {algorithm(nums)}duration : time.Since(start)avgTime : duration.Nanoseconds() / int64(iterations)fmt.Printf(%s: 平均执行时间 %d 纳秒\n, name, avgTime)
}// 辅助函数验证结果是否正确
func validateResult(nums []int, result int) bool {// 验证结果是否合理if result 0 {return false}// 验证是否能到达目标n : len(nums)if n 1 {return result 0}// 简单的验证结果应该小于等于n-1return result n-1
}// 辅助函数打印跳跃结果
func printJumpResult(nums []int, result int, title string) {fmt.Printf(%s: nums%v - %d 次跳跃\n, title, nums, result)
}func main() {fmt.Println( 45. 跳跃游戏 II )fmt.Println()// 创建测试用例testCases : createTestCases()algorithms : []struct {name stringfn func([]int) int}{{贪心算法, jump1},{动态规划算法, jump2},{BFS搜索算法, jump3},{递归回溯算法, jump4},}// 运行测试fmt.Println( 算法正确性测试 )for _, testCase : range testCases {fmt.Printf(测试: %s\n, testCase.name)results : make([]int, len(algorithms))for i, algo : range algorithms {results[i] algo.fn(testCase.nums)}// 验证所有算法结果一致allEqual : truefor i : 1; i len(results); i {if results[i] ! results[0] {allEqual falsebreak}}// 验证结果是否正确allValid : truefor _, result : range results {if !validateResult(testCase.nums, result) {allValid falsebreak}}if allEqual allValid {fmt.Printf( ✅ 所有算法结果一致且正确: %d 次跳跃\n, results[0])if len(testCase.nums) 10 {printJumpResult(testCase.nums, results[0], 跳跃结果)}} else {fmt.Printf( ❌ 算法结果不一致或错误\n)for i, algo : range algorithms {fmt.Printf( %s: %d 次跳跃\n, algo.name, results[i])}}fmt.Println()}// 性能测试fmt.Println( 性能测试 )performanceNums : []int{5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0, 5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0}fmt.Printf(测试数据: nums%v\n, performanceNums)fmt.Println()for _, algo : range algorithms {benchmarkAlgorithm(algo.fn, performanceNums, algo.name)}fmt.Println()// 算法分析fmt.Println( 算法分析 )fmt.Println(跳跃游戏II问题的特点:)fmt.Println(1. 需要找到到达数组末尾的最小跳跃次数)fmt.Println(2. 每个元素表示从该位置能跳转的最大长度)fmt.Println(3. 贪心算法是最优解法)fmt.Println(4. 需要处理各种边界情况)fmt.Println()// 复杂度分析fmt.Println( 复杂度分析 )fmt.Println(时间复杂度:)fmt.Println(- 贪心算法: O(n)单次遍历数组)fmt.Println(- 动态规划: O(n²)双重循环遍历所有位置)fmt.Println(- BFS搜索: O(n²)最坏情况需要遍历所有位置)fmt.Println(- 递归回溯: O(2^n)最坏情况需要遍历所有可能的跳跃路径)fmt.Println()fmt.Println(空间复杂度:)fmt.Println(- 贪心算法: O(1)只使用常数空间)fmt.Println(- 动态规划: O(n)需要DP数组存储状态)fmt.Println(- BFS搜索: O(n)需要队列和访问数组)fmt.Println(- 递归栈: O(n)递归深度最多为n)fmt.Println()// 算法总结fmt.Println( 算法总结 )fmt.Println(1. 贪心算法最优解法时间复杂度O(n))fmt.Println(2. 动态规划经典DP解法逻辑清晰)fmt.Println(3. BFS搜索广度优先搜索适合特定场景)fmt.Println(4. 递归回溯最直观的解法但效率较低)fmt.Println()fmt.Println(推荐使用贪心算法方法一时间复杂度最低)fmt.Println()// 应用场景fmt.Println( 应用场景 )fmt.Println(- 路径规划寻找最短路径问题)fmt.Println(- 游戏开发跳跃类游戏的路径计算)fmt.Println(- 网络路由寻找最优路由路径)fmt.Println(- 资源分配最优资源分配问题)fmt.Println(- 算法竞赛贪心算法的经典应用)fmt.Println()// 优化技巧总结fmt.Println( 优化技巧总结 )fmt.Println(1. 贪心选择在每一步都选择能跳得最远的位置)fmt.Println(2. 边界维护维护当前能到达的最远位置和下一步能到达的最远位置)fmt.Println(3. 跳跃计数当到达当前边界时增加跳跃次数并更新边界)fmt.Println(4. 最优子结构每一步的最优选择构成全局最优解)fmt.Println(5. 边界处理处理数组长度为1的特殊情况)fmt.Println(6. 算法选择根据问题特点选择合适的算法)
}
