技巧篇｜算法小白如何快速且高效的刷力扣题？

算法萌新在刷力扣时，虽然已有一些算法基础但仍然出现一题都做不出来的现象，经常有以下困惑：

1.代码写了又删、删了又写，写到一半才发现逻辑走不通，没有整体思路。

2.不能分析出题目需要用到什么算法。

那么想要高效地刷题首先要知道每道题目应该怎么做。

刷题小技巧

力扣上的 Easy 题分两种，一种是不需要算法逻辑，只要按照题目描述将代码敲出来即可。另一种是不拐弯抹角，只需要一种标准算法即可。

对于第一类 Easy 题，我们可以先根据题意将逻辑理顺，写出伪代码，然后逐步补全小段的代码。

例如：1029. 两地调度

题目描述很清晰，看完题目我们可以先想出代码的流程：

fun twoCitySchedCost(costs: Array): Int {
        // 先让所有人都选择距离最近的城市
        
        // 判断到A城市的人数和到B城市的人数相差的数量
        
        // 计算从当前人数多的城市移动到另一座城市的最小差值
        
        // 将差值排序，让差值小的人移动到另一座城市
        
}

将流程写出来后，再逐步补全代码：

class Solution {


    var result = 0
    var countA = 0
    var countB = 0
    val distance = mutableListOf()


    fun twoCitySchedCost(costs: Array): Int {
        // 先让所有人都选择距离最近的城市
        chooseShortestCity(costs)
        // 判断到A城市的人数和到B城市的人数相差的数量
        if (countA == countB) return result
        // 计算从当前人数多的城市移动到另一座城市的最小差值
        calculateMoveDistance(costs)
        // 将差值排序，让差值小的人移动到另一座城市
        shortDistanceMoveToAnother()
        return result
    }


    private fun chooseShortestCity(costs: Array) {
        costs.forEach {
            if (it[0] < it[1]) {
                result += it[0]
                countA++
            } else {
                result += it[1]
                countB++
            }
        }
    }


    private fun calculateMoveDistance(costs: Array) {
        costs.forEach {
            if (countA > countB) {
                if (it[0] < it[1]) {
                    // 这是现在往A城市走的人，记录他们往B城市走的距离
                    distance.add(it[1] - it[0])
                }
            } else {
                if (it[0] >= it[1]) {
                    // 这是现在往B城市走的人，记录他们往A城市走的距离
                    distance.add(it[0] - it[1])
                }
            }
        }
    }


    private fun shortDistanceMoveToAnother() {
        distance.sort()
        result += distance.take(Math.abs(countA - countB) / 2).sum()
    }
}

这就好比先规划好目的地，再一小段一小段的达成目标。开发者要写一个功能单一的函数是比较简单的，这就像一个小步快跑的过程。

再比如：1030. 距离顺序排列矩阵单元格

同样的，我们先根据题目描述写出代码流程：

fun allCellsDistOrder(R: Int, C: Int, r0: Int, c0: Int): Array {
    // 计算每个点到(r0,c0)的距离，保存在map中（距离 -> 坐标列表）
    
    // 由于R和C的范围都是0~100，所以map的key范围是0~200，从0到200输出map即可
    
}

然后逐步补全代码

class Solution {
    
    val distanceMap = HashMap>()
    val result = mutableListOf()


    fun allCellsDistOrder(R: Int, C: Int, r0: Int, c0: Int): Array {
        // 计算每个点到(r0,c0)的距离，保存在map中（距离 -> 坐标列表）
        calculateDistance(R, C, r0, c0)
        // 由于R和C的范围都是0~100，所以map的key范围是0~200，从0到200输出map即可
        recordResult()
        return result.toTypedArray()
    }


    private fun calculateDistance(R: Int, C: Int, r0: Int, c0: Int) {
        for (x in 0 until R) {
            for (y in 0 until C) {
                val distance = Math.abs(x - r0) + Math.abs(y - c0)
                distanceMap[distance] ?: let {
                    distanceMap[distance] = mutableListOf()
                }
                distanceMap[distance]!!.add(intArrayOf(x, y))
            }
        }
    }


    private fun recordResult() {
        for (i in 0..200) {
            if (distanceMap.isEmpty()) break
            if (!distanceMap.containsKey(i)) continue
            result.addAll(distanceMap[i]!!)
        }
    }
}

伪代码可以帮助我们明确自己需要做什么，这一点和”测试驱动开发“（TDD）的思想是一致的。我们在做的时候就会知道：“只要我完成了这些步骤，就可以实现我要的效果。” 而不是盲目的写了又删、删了又写。

判断条件

新手在阅读算法题目时，经常会分析不出题目需要用哪一种算法来解决。主要的原因在于阅读的题目太少，对每一类算法适用的场景不熟悉。

这个问题很好解决，力扣对每个题目都设置有相应的 tag，我们可以按照力扣对题型的分类，先看同一类题目。对这类算法题目的描述就会有个比较清晰的认识。如同学习英语一样，看多了倒装句，一眼就能看出倒装句的结构；看多了感叹句，一眼就能看出感叹句的结构。这也是一个熟能生巧的过程，需要花时间去了解、总结每类算法的特点，量变引起质变。

例如，我们点击“二分查找”标签，显示如下：

粗略浏览，可以发现，二分查找的题目中很多都带有“有序“、”排序“字样。接下来我们进一步分析题目，先从简单题开始：

35. 搜索插入位置

这道题就属于上文所说的只需要一种标准算法的 Easy 题。没有任何的拐弯抹角，一道典型的二分题目。题目场景有以下特点：

数组是有序的

答案是有界的，在 [0, nums.size] 之间

目标值越大，答案越大，这里有一个单调递增的关系

二分法有标准的套路 (本例使用的 Kotlin 语言，不过算法跟编程语言关系不大)：

// 二分法套路
fun dichotomy(){
    ...
    // 左边界
    var left
    // 右边界
    var right
    // 记录答案
    var ans
    while (left <= right) {
        // 中间值
        val middle = (left + right) / 2
        // 猜测是否满足条件
        if (guess(middle, ... )) {
            // 如果满足条件，记录答案
            ans = middle
            // 缩小搜索范围，在更小的值中搜索
            right = middle - 1
        } else {
            // 不满足条件，缩小搜索范围，在更大的值中搜索
            left = middle + 1
        }
    }
    return ans
}


// 猜测是否满足条件
fun guess(middle, ... ){
    ...
}

如果你熟悉这个套路的话，我们可以很快写出答案：

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size
        while (left < right) {
            val middle = (left + right) / 2
            if (nums[middle] == target) return middle
            if (nums[middle] < target) {
                left = middle + 1
            } else {
                right = middle
            }
        }
        return left
    }
}

再来一道中等题目练练手：

33. 搜索旋转排序数组

分析题目，可知：

数组旋转之前是有序的

答案是有界的，在 [0, nums.size] 之间

目标值越大，答案越大，这里有一个单调递增的关系

与标准的二分题目相比，只多了一个条件：有序数组被旋转了。只要先将数组旋转回来，再用二分法求出结果，再根据旋转的位置调整下标即可。其实中等题目很多都是在典型的算法题上面拐一个弯，困难题目一般是糅合两种算法，万变不离其宗。此题解决方案如下：

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        val rotateIndex = getRotateIndex(nums)
        val orderedNums = getOrderedNums(nums, rotateIndex)
        var left = 0
        var right = orderedNums.size
        while (left < right) {
            val middle = (left + right) / 2
            when {
                orderedNums[middle] > target -> right--
                orderedNums[middle] < target -> left++
                // 找到了答案，根据旋转下标调整结果
                else -> return when {
                    rotateIndex == 0 -> middle
                    orderedNums.size - rotateIndex <= middle -> middle - orderedNums.size + rotateIndex
                    else -> middle + rotateIndex
                }
            }
        }
        return -1
    }


    /**
     * 获取旋转前排好序的数组
     */
    private fun getOrderedNums(nums: IntArray, rotateIndex: Int): MutableList {
        val orderedNums = mutableListOf()
        orderedNums.addAll(nums.drop(rotateIndex))
        orderedNums.addAll(nums.take(rotateIndex))
        return orderedNums
    }


    /**
     * 获取旋转位置的下标
     */
    private fun getRotateIndex(nums: IntArray): Int {
        for ((index, value) in nums.dropLast(1).withIndex()) {
            if (value > nums[index + 1]) {
                return index + 1
            }
        }
        return 0
    }
}

通过以上两个题，相信你对二分法已经有了一个基本认识，他们都有一个共同点：答案是有界且单调的。事实上，只要是满足此条件的题目都可以使用二分法解决。所以我们分析题目时，可以通过检查这一条件来判断是否是二分算法的题目。

接下来我们再来分析一下动态规划题目的特点，选择“动态规划”标签：

粗略浏览，可以发现，题目中很多带有“最大/最小”、“最长/最短”、“不同”字样。上文已经说到，简单的题目往往更典型，我们以一道简单题目为例：

70. 爬楼梯

这是一道典型的动态规划题目。

分析题目：假如我们要到达第 100 步台阶。我们不可能一步登天，直接飞上去。我们只能从第 98 步走两步到达，或者从 99 步走一步到达。

同样，我们也不可能直接飞到 98 步，我们只能从 96 步走两步到达，或者从 97 步走一步到达。

如果用 f(n) 表示到达第 n 步的走法，根据我们的分析，以下方程成立：

f(n) = f(n-2) + f(n-1)

边界条件如下：

f(1) = 1 f(2) = 2

所以我们可以写出以下算法：

class Solution {
    fun climbStairs(n: Int): Int {
        if (n == 1) return 1
        if (n == 2) return 2
        return climbStairs(n - 2) + climbStairs(n - 1)
    }
}

然而这样是不能通过的，因为递归会带来大量的重复计算，所以我们将其修改为迭代：

class Solution {
    fun climbStairs(n: Int): Int {
        val f = IntArray(n + 1)
        for (i in 1..n) {
            when (i) {
                1 -> f[i] = 1
                2 -> f[i] = 2
                else -> f[i] = f[i - 1] + f[i - 2]
            }
        }
        return f[n]
    }
}

这样写这道题目就 AC 了。这道题很好的体现了动态规划算法题目的特点：问题能够以大化小，化到最小时有边界条件。

对于动态规划题目，我们只需要处理以大化小的过程和边界条件即可。这个以大化小的过程，专业术语叫”状态转移“。状态转移的条件被称作“状态转移方程”，本题中，状态转移方程就是：f(n) = f(n-2) + f(n-1)。只要找出了”状态转移方程”，就可以很轻松的解决动态规划问题，这就是动态规划算法的套路。

此题还可以再次优化，仔细分析题目可知，我们并不需要记录 f(i) 的每一个值，只需要记录前两个值即可。也就是只记录到达前一步阶梯的方法总数和到达前两步阶梯的方法总数，进一步优化的算法如下：

class Solution {
    fun climbStairs(n: Int): Int {
        // 前面第二个数
        var lastTwo = 0
        // 前一个数
        var lastOne = 1
        repeat(n) {
            lastOne += lastTwo
            lastTwo = lastOne - lastTwo
        }
        return lastOne
    }
}

对于每一个题目，不要仅仅满足于通过。最好是不断地优化代码，使得其时间复杂度和空间复杂度最低。养成这个好习惯，以后一出手就是最优方案，有助于我们的编程水平进一步提升。

写在最后

刚开始刷题时，如果厌倦了从 Easy 入手的话，就按照开头所讲的先写伪代码，再逐步补全的方式编程，可以让你少走很多弯路。此外，还可以去力扣题解区看看别的小伙伴的解题思路，开拓解题思维。

做算法题时循序渐进，不要上来就做困难题目，Easy 题反而更加典型，不掺杂其他算法在其中，更有助于萌新理解此类算法。每个题目多刷几遍，不断地优化代码，直到脑中对此题有一个清晰的认识，切忌“萌混过关”。

学习算法要渐次进行，先掌握一类算法，钻研透了再去掌握另一类。建议先定一个能达到的小目标，比方说我先掌握一个算法。

BY /

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。