乐趣区

关于golang:golangleetcode中级跳跃游戏不同路径

jiezi

第一题 跳跃游戏

题目

贪婪解法

对于每个下标而言，元素规定了它能够达到的最大间隔

因而这部分间隔范畴内的下标都是能够到达的
.

例如示例 1：nums = [2,3,1,1,4]
.

对于下标 0 而言，它能够抉择下标 1 或者下标 2

抉择下标 1. 能够达到下标 4

抉择下标 2，能够达到下标 3

.

因为本题返回值为布尔类型，无需存储跳跃门路

咱们只需记住跳跃能达到的最远下标即可，

对于最远下标以内，咱们总能找到一条能够到达的门路

因而咱们能够失去公式

maxIndex=max(maxIndex,i+nums[i])

直到最远下标到达最初一个下标

if maxIndex>=n-1 {return true}

核心思想为 贪婪算法，即优先思考可取得的最佳的解法

对于每个下标，咱们都将其最优解退出思考范畴

具体代码 

func canJump(nums []int) bool {n:=len(nums)
    var maxIndex int
    for i:=0;i<n;i++{if i>maxIndex{return false}
        maxIndex=max(maxIndex,i+nums[i])
        if maxIndex>=n-1 {return true}
    }
    return false
}

func max(x int,y int)int {
    if x<y{return y}else {return x}
}

官解

动静布局解法

在用动静布局求解之前，让咱们在强调一下动静布局的几个步骤


具体学习能够参考
https://labuladong.gitee.io/a…

https://houbb.github.io/2020/…

而对于本题而言

代码 

func canJump(nums []int) bool {n:=len(nums)
    a:=nums[0]  // a=dp[i-1]
    for i:=1;i<n;i++ {if a==0  {return false}
        a=max(a-1,nums[i])    // a=dp[i]
    }
    return true
}

func max(x int,y int)int {
    if x<y{return y}else {return x}
}

复杂度剖析

工夫复杂度：O(n)，其中 n 为数组的大小。只须要拜访 nums 数组一遍，共 n 个地位。

空间复杂度：O(1)，常数级的空间开销。

第二题 不同门路

题目

思路

dp

这是组合数学中经典的格路模型，它的计算与杨辉三角是等价的

都是

f(i,j)=f(i−1,j)+f(i,j−1)

代码 

func uniquePaths(m int, n int) int {
    // 初始化
    arr := make([][]int, m)
    for i := range arr {arr[i] = make([]int, n)
        arr[i][0]=1
    }
    for i:=range arr[0]{arr[0][i]=1
    }
    if m==1||n==1 {return 1}

    for i:=1;i<m;i++{
        for j:=1;j<n;j++{arr[i][j]=arr[i-1][j]+arr[i][j-1]
        }
    }
    return arr[m-1][n-1]
}

复杂度剖析

工夫复杂度：O（mn），计算了 m * n 矩阵个数值，最终失去第 m 行第 n 列的答案

空间复杂度：O（mn），借助二维数组失去最终答案

同时

组合数学

go 语言中提供了计算排列组合数的办法

因而咱们也能够间接调用该办法获取答案

办法具体参数为

第 m，n 项的组合数为

故代码为 

func uniquePaths(m, n int) int {return int(new(big.Int).Binomial(int64(m+n-2), int64(n-1)).Int64())
}
退出移动版