【刷题篇】LeetCode Jump Game 1-7详解（附Kotlin代码）

最近刷题看到LeetCode这个Jump Game系列已经出了七道题了，之前对这个题型很有兴趣，在面试中也遇到过。所以就顺着把它们一一解决了，看看他们的区别和相似之处。在这里附上思路和代码，供大家参考。

Jump Game I

难易度：Medium

解法：遍历数组，更新最远位置

复杂度：时间O(n) 空间O(1)

因为只需要返回boolean表示是否能到达最后一个位置，所以遍历数组检查一遍，然后判断就可以了。

    fun canJump(nums: IntArray): Boolean {
        var current = 0     // 当前位置
        var maxReach = 0    // 最远可到达位置
        while (current <= maxReach) {
            // 检查是否到达数组最后一个位置
            if (current == nums.size - 1) {
                return true
            }

            // 更新能到达的最远位置，并向前走一步
            maxReach = maxOf(maxReach, current + nums[current])
            current += 1
        }

        // 到达maxReach，但不是数组最后一位，返回false
        return false
    }
复制代码

Jump Game II

难易度：Medium

解法：Greedy，每次选择能到达的最远位置来跳下一步

复杂度：时间O(n) 空间O(1)

这道题的关键思路在于：选择下一步位置时，要选择能跳得最远的位置。因为题目的条件是：如果当前位置i的步数为k，那么跳到(i+1, i+k)之间的任意位置都可以，所以当然可以选择最远的位置来跳。换句话说，跳到最远位置的情况可以包含跳到中间位置的情况，而且用的步数会更少。所以我们只需要用一个while循环查找最远位置并计算步数，返回结果即可。

    fun jump(nums: IntArray): Int {
        var current = 0     // 当前位置
        var stepCount = 0   // 步数计数器
        while (current < nums.size - 1) {
            var maxReach = current + nums[current]
            var nextPosition = current

            // 更新步数计数，找到当前位置所能到达的最远位置，作为下一步
            stepCount += 1
            for (i in current..current + nums[current]) {

                // 如果下一步直接能到数组最后一位，直接返回结果，否则更新下一步位置
                if (i >= nums.size - 1) {
                    return stepCount
                } else if (i + nums[i] > maxReach) {
                    maxReach = i + nums[i]
                    nextPosition = i
                }
            }
            current = nextPosition
        }
        return stepCount
    }
复制代码

Jump Game III

难易度：Medium

解法：DFS，从起始开始向左右分别进行DFS搜索，注意判断是否重复到达某一位置

复杂度：时间O(n) 空间O(n)

这道题就是一个简单的DFS情景，关于DFS其实主要关注三点：

1. base case：在什么情况下DFS触底，此时可以停止DFS并返回结果；
2. branching：如何在当前状态下对多个分支进行搜索，常见情况例如向上下左右四个方向搜索，向树的子节点搜索等；
3. cut edges：对于一些情况可以通过增加判断条件进行剪枝，比如这里的isVisited数组，可以大幅度减少运行时间。

    private var canReach = false
    fun canReach(arr: IntArray, start: Int): Boolean {
        if (arr[start] == 0) return true

        // 创建boolean数组来记录是否到达过当前位置
        val isVisited = BooleanArray(arr.size)
        jumpGameIIIHelper(arr, isVisited, start)
        isVisited[start] = true
        return canReach
    }

    private fun jumpGameIIIHelper(arr: IntArray, isVisited: BooleanArray, current: Int) {
        if (arr[current] == 0) {
            canReach = true
            return
        }

        // 向当前位置的左右分别进行DFS搜索
        if (current - arr[current] >= 0 && !isVisited[current - arr[current]]) {
            isVisited[current - arr[current]] = true
            jumpGameIIIHelper(arr, isVisited, current - arr[current])
            isVisited[current - arr[current]] = false
        }
        if (current + arr[current] < arr.size && !isVisited[current + arr[current]]) {
            isVisited[current + arr[current]] = true
            jumpGameIIIHelper(arr, isVisited, current + arr[current])
            isVisited[current + arr[current]] = false
        }
    }
复制代码

Jump Game IV

难易度：Hard

解法：BFS 建立一个Queue来保存每一步可以到达的所有位置

复杂度：时间O(n+k)，k为图的边数，也就是包含相同值的位置的pair数，最差情况O(n^2) 空间O(n)

至此进入Hard难度，这道题的主要解法分为两个部分：

1. 如何建图：因为这道题允许在值相同的任意位置间进行跳跃，所以建图时我们应该用数组的值来作为HashMap的key而不是index索引，这样在极端情况例如[7,7,7…7]无数相同数字的数组时更加节省空间；
2. 如何进行BFS：在进行搜索时有三种走法：向前，向后以及相同值跳跃。因为是BFS，所以我们同同时需要维护一个isVisited数组来检查是否已经走到，并用一个Queue按顺序记录当前步数的到达位置，这部分属于比较正常的BFS。

    fun minJumps(arr: IntArray): Int {
        var answer = 0

        // 用HashMap建立graph
        val graph = HashMap<Int, LinkedList<Int>>()
        for (index in arr.indices) {
            graph.computeIfAbsent(
                arr[index]
            ) { LinkedList<Int>() }.add(index)
        }

        // 用queue来进行BFS，每一步建立一个新queue
        val visited = BooleanArray(arr.size)
        var queue = LinkedList<Int>()
        queue.add(0)
        while (queue.isNotEmpty()) {
            val newQueue = LinkedList<Int>()
            for (current in queue) {
                if (current == arr.size - 1) {
                    return answer
                }

                // 搜索相同值的其他位置进行跳跃
                for (next in graph.getOrDefault(arr[current], LinkedList())) {
                    if (!visited[next]) {
                        visited[next] = true
                        newQueue.add(next)
                    }
                }
                graph[arr[current]]?.clear()

                // 向后走一格进行跳跃
                if (current - 1 >= 0 && !visited[current - 1]) {
                    visited[current - 1] = true
                    newQueue.add(current - 1)
                }

                // 向前走一格进行跳跃
                if (current + 1 < arr.size && !visited[current + 1]) {
                    visited[current + 1] = true
                    newQueue.add(current + 1)
                }
            }
            answer += 1
            queue = newQueue
        }
        return -1
    }
复制代码

Jump Game V

难易度：Hard

解法：DFS + Memoization

复杂度：时间O(n+k)，k为DFS图的边数，也就是向左右可跳跃的位置的pair数，最坏情况为O(n^2) 空间O(n)

同样是一道Hard题，根据题目要求可以发现：只能向左右比当前位置低的地方跳，并且中间不能有比当前位置高的阻挡。可以看出这里使用DFS更好，而如果只是单纯的DFS这道题会报TLE，而其实我们在判断当前位置时，对于之前已经计算过最大跳跃步数的位置，它们的结果是一样的。所以这里可以用空间来补时间，也就是通过Memoization来维护一个List，记录已经计算过的位置，可以大幅减少计算时间。

    fun maxJumps(arr: IntArray, d: Int): Int {

        // 用mutableList存储已经DFS过并算出结果的位置，避免重复
        val maxJumpResults = MutableList(arr.size) { 0 }
        var result = 0
        for (i in arr.indices) {
            result = max(result, maxJumpsHelper(arr, d, i, maxJumpResults))
        }
        return result
    }

    private fun maxJumpsHelper(
        arr: IntArray,
        range: Int,
        current: Int,
        maxJumpResults: MutableList<Int>
    ): Int {

        // 已经查过有结果的位置直接取结果
        if (maxJumpResults[current] != 0) return maxJumpResults[current]

        var max = 1 // 自身位置算一步，至少为1

        // range内向右遍历，一旦有超过arr[current]立刻停止遍历
        for (i in 1..range) {
            val nextRight = current + i
            if (nextRight < arr.size && arr[nextRight] < arr[current]) {
                max = max(max, maxJumpsHelper(arr, range, nextRight, maxJumpResults) + 1)
            } else {
                break
            }
        }

        // range内向左遍历，一旦有超过arr[current]立刻停止遍历
        for (i in 1..range) {
            val nextLeft = current - i
            if (nextLeft >= 0 && arr[nextLeft] < arr[current]) {
                max = max(max, maxJumpsHelper(arr, range, nextLeft, maxJumpResults) + 1)
            } else {
                break
            }
        }
        maxJumpResults[current] = max
        return max
    }
复制代码

Jump Game VI

难易度：Medium

解法：动态规划 + Sliding Window，状态转移方程：dp[i] = max(dp[i - k], dp[i - k + 1],...,dp[i - 1]) + nums[i]

复杂度：时间O(nlgn) 空间O(n)

这道题的难点在于：1. 动态规划的状态转移方程；2.快速获得(dp[i – k],…, dp[i – 1])范围内的最大值。对于第二点要注意：如果只是单纯遍历来找滑动窗口的最大值的话，会出现超时TLE报错。所以我们需要用PriorityQueue来维护这个区间的所有值，这样才能以O(lgn)时间来进行查询，更新和删除的操作。

    fun maxResult(nums: IntArray, k: Int): Int {
        val dp = MutableList(nums.size) { 0 }
        dp[0] = nums[0]

        // 用PriorityQueue来维护（dp[i-k],...dp[i-1]）的所有值
        val pq = PriorityQueue(Comparator<Int> { o1, o2 -> o2 - o1 })
        pq.add(dp[0])
        for (i in 1 until nums.size) {
            dp[i] = pq.peek() + nums[i]

            // 更新sliding window的范围和值
            pq.add(dp[i])
            if (i - k >= 0) {
                pq.remove(dp[i - k])
            }
        }
        return dp[nums.size - 1]
    }
复制代码

Jump Game VII

难易度：Medium

解法：动态规划 + Sliding Window，状态转移方程：dp[i] = (dp[i - maxJump] || dp[i - maxJump + 1] || ... dp[i - minJump]) && (s[i] == '0')

复杂度：时间O(n) 空间O(n)

这道题和上面的Jump Game VI可太像了，唯一的区别在于这次不用在sliding window里找最大值，而是找是否存在一个位置的值是true。所以用MultipleSet来记录所有dp[i] = true的位置，然后判断set.isNotEmpty()即可。时间复杂度比Jump Game VI更低，因为只需要用O(1)判断一下set是否为空即可。

    fun canReach(s: String, minJump: Int, maxJump: Int): Boolean {
        val dp = MutableList(s.length) { false }
        dp[0] = true

        // 用MutableSet来记录（dp[i-maxJump],...dp[i-minJump]）中所有可到达的位置的坐标
        val slidingWindow = mutableSetOf<Int>()
        if (minJump == 1) slidingWindow.add(0)      // base case，需要单独判断
        for (i in 1 until s.length) {
            if (s[i] == '0') {
                dp[i] = slidingWindow.isNotEmpty()  // 这里只要sliding window不为空即可
            }

            // 更新sliding window，加入i - minJump + 1，移除i - maxJump(if any)
            val newAdded = i - minJump + 1
            if (newAdded >= 0 && dp[newAdded]) slidingWindow.add(newAdded)
            slidingWindow.remove(i - maxJump)
        }
        return dp[s.length - 1]
    }
复制代码