题目：剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode）

题目的接口：

func numWays(n int) int {

}

解题思路：

这道题乍一看好像没什么思路，但是我们不妨把题目分析一下，跳 1，2，3 级台阶分别有多少种情况，然后再来探究规律，跳 1 级楼梯有一种方法，跳 2 级楼梯有两种方法（一步 2 级上去 + 一步 1 级上去），跳 3 级楼梯有三种方法，是哪三种？

如果第一步跳 1 级，就还剩下 2 级楼梯，跳 2 级楼梯有两种方法；如果第一步跳 2 级，就还剩下 1 级楼梯，跳 1 级楼梯有一种方法；2 + 1 = 3，所以跳 3 级楼梯有三种方法，发现没有，我们可以根据前面求出的两级楼梯的跳法来求出下一级的楼梯，

也就是我们可以用前面的状态推出后面的状态，这就可以用动态规划，在一刷剑指 Offer 的时候，我还是思考了蛮久这个问题的：【LeetCode】剑指 Offer（4）_戊子仲秋的博客-CSDN博客这里把我当时的思考写的很详细了，如果没有看懂可以去看看。代码如下

代码：

func numWays(n int) int {
    if n == 0 {return 1}
    if n <= 2 {return n}
    dp := make([]int, 101)
    dp[1] = 1
    dp[2] = 2
    for i := 3; i <= 100; i++ {
        dp[i] = (dp[i-1] + dp[i-2]) % (1e9 + 7)
    } 
    return dp[n]
}

过啦！！！

题目：剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode）

题目的接口：

func minArray(numbers []int) int {

}

解题思路：

这道题我能想到两种方法，题目给的复杂度都可以过，一个是暴力枚举，直接找出最小值，一个是用二分，也就是推荐的低复杂度解法，这里我就先暴力一手：

func minArray(numbers []int) int {
    maxVal := 5000
    for _, v := range numbers {
        maxVal = min(v, maxVal)
    }
    return maxVal
}

func min(a int, b int) int {
    if a > b {
        return b
    }
    return a
}

顺便吐槽一句，LeetCode 的 golang 编译器不是最新版，所以不支持 min 和 max 方法，必须吐槽两句，真是难受，搞得我写个暴力还得自己实现一个 min 方法来找最小值。

然后是二分查找，我个人认为二分查找的精髓在于两个，第一个是找到可以进行二分的单调性，这样我们可以确定这道题可以使用二分；第二个就是找到一个参照系来进行比对，而这道题我们可以选择左边，也可以选择右边作为参照，

就正常使用二分求解，唯一需要注意的点就是：比如：我选择右边作为参照对象，那使用右边元素进行比较的时候，如果出现相等的情况，我们就得让 right--，这样才能不陷入死循环。代码如下：

代码：

func minArray(numbers []int) int {
    left := 0
    right := len(numbers)-1
    for left < right {
        mid := left + (right - left) / 2
        if numbers[right] > numbers[mid] {
            right = mid
        } else if numbers[right] < numbers[mid] {
            left = mid + 1
        } else {
            right--
        }
    }
    return numbers[left]
}