技巧篇｜算法小白如何快速且高效的刷力扣题？
算法萌新在刷力扣时，虽然已有一些算法基础但仍然出现一题都做不出来的现象，经常有以下困惑：
1.代码写了又删、删了又写，写到一半才发现逻辑走不通，没有整体思路。
2.不能分析出题目需要用到什么算法。
那么想要高效地刷题首先要知道每道题目应该怎么做。
力扣上的 Easy 题分两种，一种是不需要算法逻辑，只要按照题目描述将代码敲出来即可。另一种是不拐弯抹角，只需要一种标准算法即可。
题目描述很清晰，看完题目我们可以先想出代码的流程：
fun twoCitySchedCost(costs: Array<IntArray>): Int {// 先让所有人都选择距离最近的城市// 判断到A城市的人数和到B城市的人数相差的数量// 计算从当前人数多的城市移动到另一座城市的最小差值// 将差值排序，让差值小的人移动到另一座城市}
将流程写出来后，再逐步补全代码：
class Solution {var result = 0var countA = 0var countB = 0val distance = mutableListOf<Int>()fun twoCitySchedCost(costs: Array<IntArray>): Int {// 先让所有人都选择距离最近的城市chooseShortestCity(costs)// 判断到A城市的人数和到B城市的人数相差的数量if (countA == countB) return result// 计算从当前人数多的城市移动到另一座城市的最小差值calculateMoveDistance(costs)// 将差值排序，让差值小的人移动到另一座城市shortDistanceMoveToAnother()return result}private fun chooseShortestCity(costs: Array<IntArray>) {costs.forEach {if (it[0] < it[1]) {result += it[0]countA++} else {result += it[1]countB++}}}private fun calculateMoveDistance(costs: Array<IntArray>) {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()}}
同样的，我们先根据题目描述写出代码流程：
fun allCellsDistOrder(R: Int, C: Int, r0: Int, c0: Int): Array<IntArray> {// 计算每个点到(r0,c0)的距离，保存在map中（距离 -> 坐标列表）// 由于R和C的范围都是0~100，所以map的key范围是0~200，从0到200输出map即可}
然后逐步补全代码
class Solution {val distanceMap = HashMap<Int, MutableList<IntArray>>()val result = mutableListOf<IntArray>()fun allCellsDistOrder(R: Int, C: Int, r0: Int, c0: Int): Array<IntArray> {// 计算每个点到(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()) breakif (!distanceMap.containsKey(i)) continueresult.addAll(distanceMap[i]!!)}}}
伪代码可以帮助我们明确自己需要做什么，这一点和”测试驱动开发“（TDD）的思想是一致的。我们在做的时候就会知道：“只要我完成了这些步骤，就可以实现我要的效果。” 而不是盲目的写了又删、删了又写。
判断条件
新手在阅读算法题目时，经常会分析不出题目需要用哪一种算法来解决。主要的原因在于阅读的题目太少，对每一类算法适用的场景不熟悉。
这个问题很好解决，力扣对每个题目都设置有相应的 tag，我们可以按照力扣对题型的分类，先看同一类题目。对这类算法题目的描述就会有个比较清晰的认识。如同学习英语一样，看多了倒装句，一眼就能看出倒装句的结构；看多了感叹句，一眼就能看出感叹句的结构。这也是一个熟能生巧的过程，需要花时间去了解、总结每类算法的特点，量变引起质变。
例如，我们点击“二分查找”标签，显示如下：
这道题就属于上文所说的只需要一种标准算法的 Easy 题。没有任何的拐弯抹角，一道典型的二分题目。题目场景有以下特点：
数组是有序的
答案是有界的，在 [0, nums.size] 之间
目标值越大，答案越大，这里有一个单调递增的关系
二分法有标准的套路 (本例使用的 Kotlin 语言，不过算法跟编程语言关系不大)：
// 二分法套路fun dichotomy(){...// 左边界var left// 右边界var right// 记录答案var answhile (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 = 0var right = nums.sizewhile (left < right) {val middle = (left + right) / 2if (nums[middle] == target) return middleif (nums[middle] < target) {left = middle + 1} else {right = middle}}return left}}
分析题目，可知：
数组旋转之前是有序的
答案是有界的，在 [0, nums.size] 之间
目标值越大，答案越大，这里有一个单调递增的关系
与标准的二分题目相比，只多了一个条件：有序数组被旋转了。只要先将数组旋转回来，再用二分法求出结果，再根据旋转的位置调整下标即可。其实中等题目很多都是在典型的算法题上面拐一个弯，困难题目一般是糅合两种算法，万变不离其宗。此题解决方案如下：
class Solution {fun search(nums: IntArray, target: Int): Int {val rotateIndex = getRotateIndex(nums)val orderedNums = getOrderedNums(nums, rotateIndex)var left = 0var right = orderedNums.sizewhile (left < right) {val middle = (left + right) / 2when {orderedNums[middle] > target -> right--orderedNums[middle] < target -> left++// 找到了答案，根据旋转下标调整结果else -> return when {rotateIndex == 0 -> middleorderedNums.size - rotateIndex <= middle -> middle - orderedNums.size + rotateIndexelse -> middle + rotateIndex}}}return -1}/*** 获取旋转前排好序的数组*/private fun getOrderedNums(nums: IntArray, rotateIndex: Int): MutableList<Int> {val orderedNums = mutableListOf<Int>()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}}
通过以上两个题，相信你对二分法已经有了一个基本认识，他们都有一个共同点：答案是有界且单调的。事实上，只要是满足此条件的题目都可以使用二分法解决。所以我们分析题目时，可以通过检查这一条件来判断是否是二分算法的题目。
接下来我们再来分析一下动态规划题目的特点，选择“动态规划”标签：
粗略浏览，可以发现，题目中很多带有“最大/最小”、“最长/最短”、“不同”字样。上文已经说到，简单的题目往往更典型，我们以一道简单题目为例：
这是一道典型的动态规划题目。
分析题目：假如我们要到达第 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 1if (n == 2) return 2return 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] = 12 -> f[i] = 2else -> 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 = 1repeat(n) {lastOne += lastTwolastTwo = lastOne - lastTwo}return lastOne}}
写在最后
刚开始刷题时，如果厌倦了从 Easy 入手的话，就按照开头所讲的先写伪代码，再逐步补全的方式编程，可以让你少走很多弯路。此外，还可以去力扣题解区看看别的小伙伴的解题思路，开拓解题思维。
做算法题时循序渐进，不要上来就做困难题目，Easy 题反而更加典型，不掺杂其他算法在其中，更有助于萌新理解此类算法。每个题目多刷几遍，不断地优化代码，直到脑中对此题有一个清晰的认识，切忌“萌混过关”。
学习算法要渐次进行，先掌握一类算法，钻研透了再去掌握另一类。建议先定一个能达到的小目标，比方说我先掌握一个算法。
BY /
本文作者：力扣
编辑&版式：Janson
声明：本文归“力扣”版权所有，如需转载请联系。
点个在看，少个 bug
微信扫码关注该文公众号作者