关于数据结构与算法:来和大家聊聊我是如何刷题的第三弹

前两篇的地址在这里，没有看过的同学倡议先看下。

• 来和大家聊聊我是如何刷题的（第一弹）
• 来和大家聊聊我是如何刷题的（第二弹）

本章或者是这个系列的最终章。这次给大家聊一点硬核的，聊一些简直所有算法题都能用得上的超实用思维。

上一节给大家抛出了两个问题，别离是：

• 如何锁定应用哪种算法？比方我看到了这道题，我怎么晓得该用什么解法呢？二分？动静布局？
• 一看就会，一写就废，如何克服？

明天，我就来圆一个当初吹下的牛逼。话不多说，间接上干货。如果你感觉有用，请三连反对我一下，让我可能坚持下去，给大家带来更多的干货。

<!– more –>

如何锁定应用哪种算法？

为什么很多人刚看了一眼题目就晓得怎么解？

• 一种可能是 ta 之前做过同样或者相似的题目，造成了外在的记忆，间接提取了之前的记忆。
• 另一种可能是题目给出了明确的提示信息，他们依据这些信息”蒙“的，这种蒙就是 题感。
• 最初一种是刚开始也没思路，尝试暴力解，发现某些步骤能够优化，缓缓剥茧抽丝，推导出最终答案。

接下来，咱们来聊下第二种和第三种。至于第一种则不是一篇文章能解决的，这须要大家多做题，并且做题的时候要多总结多交换。

关键字

关键字能够对解题起到提醒作用。这很好了解，假如题目没有限度信息等关键字，那就是耍流氓，毫无算法可言了。比方”在一个数组中找 target“，这道题就很无聊，失常不会有这种算法题。可能的出题模式是 加上有序两个字，变成有序数组。那有序就是关键字了。

其余的例子有很多，接下来咱们来看下常见的关键字以及对应的可能解法有哪些。

• 如果题目是求极值，计数，很有可能是动静布局，堆等。
• 如果题目是有序的，则可能是双指针。比方二分法。
• 如果题目要求间断，则可能是滑动窗口。
• 如果题目要求所有可能，须要门路信息，则可能是回溯。

如上的这些只是看到关键词你应该第一工夫想到的 可能解法，到底正确与否，以及复杂度是否达标须要在脑子里二次加工。

对于复杂度是否达标这一点，前面给大家介绍。

限度条件

很多题目都会给一些数据范畴的提醒，大家肯定要留神看。比方 1681. 最小不兼容性，题目形容就不看了，咱们不打算在这里讲具体怎么解。这道题的函数签名如下：

def minimumIncompatibility(self, nums: List[int], k: int) -> int:

这道题的提醒是这样的:

1 <= k <= nums.length <= 16
nums.length 能被 k 整除。1 <= nums[i] <= nums.length

看到了这个你有什么想法么？

留神到 nums 的长度和值都很小，这道题很可能是暴力回溯 + 状态压缩。对于回溯和状态压缩技巧能够翻翻我的历史文章。

这里再给大家一个超实用小技巧。

• 如果 n 是 10 左右，那么算法通常是 n! 的工夫复杂度。
• 如果 n 是 20 左右，那么算法通常是 2^n 的工夫复杂度

因而 1681. 最小不兼容性 这道题的复杂度很可能就是指数级别。

那为什么 10 左右就是 n!，20 是 2^n? 这里给大家介绍一个你可能不晓得的技巧。请大家记住一个数字 1000 万。

下面之所以是 10 左右，20 左右就是因为你把 n 带进去差不多都是 1000 万。再比方一道题是 n 是 $10^7$，那很可能是 $O(N)$ 复杂度，因为 $10 ^7$ 就是 1000 万。

再比方，我之前写的一篇文章《穿上衣服我就不意识你了？来聊聊最长回升子序列》，下面所有的题工夫复杂度都是 $N^2$，根本都能够通过所有的测试用例。为什么？因为题目数据范畴差不多是 2500，那 2500 的平方是多少？是 600 多万，因而数据范畴是 3000 以内，平方差不多都可解，当然我说的只是大多数状况，并且须要留神 越靠近临界值越可能超时。

再比方1631. 最小膂力耗费门路。题目形容：

你筹备加入一场远足流动。给你一个二维 rows x columns 的地图 heights，其中 heights[row][col] 示意格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0)，且你心愿去最右下角的格子 (rows-1, columns-1)（留神下标从 0 开始编号）。你每次能够往 上，下，左，右 四个方向之一挪动，你想要找到消耗 膂力 最小的一条门路。一条门路消耗的 体力值 是门路上相邻格子之间 高度差绝对值 的 最大值 决定的。请你返回从左上角走到右下角的最小 膂力耗费值。。

示例 1：

输出：heights = [[1,2,2],[3,8,2],[5,3,5]]
输入：2
解释：门路 [1,3,5,3,5] 间断格子的差值绝对值最大为 2。这条门路比门路 [1,2,2,2,5] 更优，因为另一条门路差值最大值为 3。

这道题的函数签名如下：

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:

这道题的提醒是这样的:

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

首先，咱们至多须要从左上走到右下，那么工夫复杂度就曾经是 $O(rows * columns)$ 了。题目说了这两个数字都不大于 100，因而最大就是 $10^4$。而对于路线上的高度差绝对值的数据范畴也不超过 $10^6$。

暴力法就是一个个试，复杂度是二者间接相乘，也就是 $10^10$，大于后面给大家讲的 $10^7$，因而这个复杂度通常是不能 AC 的。

而下面说了 $O(rows * columns)$ 是不可能省的，因为你至多要走一次。但如果 $10^6$ 不是线性去试，而是指数的话呢？而指数复杂度首先想到二分。

此题的伪代码：

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        def test(mid, x, y):
            # dosomething
        l, r = 0, 10**6
        # 最左满足条件的值的二分模板。大家能够去 leetcode-cheatsheet 插件获取更多算法模板
        while l <= r:
            mid = (l + r) // 2
            # 测试有没有一条门路从 (0,0) 登程达到(rows-1,cols-1)，且门路上的高度绝对值差不大于 mid
            if test(mid, 0, 0):
                r = mid - 1
            else:
                l = mid + 1
        return l

你说 1000 万这个数字重要不重要？1000 万不仅是我的人生目标，更是做题时刻铭刻的一个数字！^\_^

暴力优化

最初给大家介绍的”辨认题目可能的解法“的技巧是暴力优化。

一句话概括就是 先暴力解，而后思考性能瓶颈，再尝试应用数据结构和算法对瓶颈进行优化。

比方 316. 去除反复字母，我就是先暴力求进去。发现每次都直接判断是否在是否在栈上须要 $O(N)$ 的工夫，太慢了。因为我就用了哈希表进行优化。而应用哈希表这点，相对不是我一开始就想到的，而是先暴力求解，求解的过程发现算法的性能瓶颈才意识到该用哈希表的。对于这道题的具体的解法就不再这里讲了，大家点进去看我的题解就行。或者间接去力扣搜题，排名第一的非官方题解应该就是我。

总结一下就是，大家肯定不要小看暴力法。暴力法解进去剪剪枝说不定就过了。如果不过，思考下瓶颈在哪，用适合的数据结构和算法优化一下说不定也就过了。这可不是随便说说。比方上面要讲的硬币找零问题，就是暴力解发现瓶颈，加个记忆化去除重复子问题就是动静布局了

一看就会，一写就废，如何克服？

针对这个问题，之前我给大家的倡议是 多温习 ， 多入手写。

起初我和几个敌人聊了一下，发现自己有点 幸存者偏差 。我发现很多人 在没有算法思维的状况下就开始学习算法了，这很不可取。

不过算法思维这货色你让我在这一篇文章给你整的明明白白的，这也不事实。明天我给大家分享一个我认为最最重要的一个算法思维 – 分治。

分治思维

“一看就会，一写就废，如何克服？”，有一个可能是你没有分治思维。咱们的大脑天生适宜 解决一些简略 的货色，而不适宜解决看起来就很简单的货色。因而面对一个很简单的货色，第一件事件应该是思考 是否能够将其合成，而后一一击破。

举个例子给大家，如下是一道力扣的 hard 题《2 呈现的次数》，题目形容如下：

编写一个办法，计算从 0 到 n (含 n) 中数字 2 呈现的次数。示例:

输出: 25
输入: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(留神 22 应该算作两次)
提醒：n <= 10^9

很多人一看到题就蒙了，这要多少种状况啊? 总不可能一个数字一个数字试过来吧？

其实看一眼数据范畴中 n 下限是 10^9，大于 1000 万，就晓得不能这样暴力。

于是轻轻关上题解，不仅感叹“原来是这样啊！”，“这怎么想到的？这什么脑子啊！”

来让我通知你，你缺啥。你缺的不是一个好使的脑子，而是一个 懂得将简单问题变成若干个简略问题的意识和能力。

以这道题来说，我能够将其合成为几个子问题。

• 从 0 到 n (含 n) 中 个位 数字 2 呈现的次数
• 从 0 到 n (含 n) 中 十位 数字 2 呈现的次数
• 。。。

最终的答案就是以上几个 子问题的和。

通过这样的思路，大家一下子就能关上思路。剩下的工作就简略了。因为每次固定一位之后，就将数字分为了左右两局部，那么该位是 2 的次数就是左右所有可能的笛卡尔积，即 a \* b。

比方 n 是 135。

百位上不可能是 2，因为 2xx 肯定超过 135 了。

那十位有多少个 2 呢？依照下面的思路：

• 右边就是百位，百位可能是 0 或者 1，共 2 种可能。
• 左边就是个位，个位可能是 [0 – 9] 共 10 种可能。

那么十位是 2 的次数就是 2 \* 10 = 20。

那个位有多少个 2 呢？依照下面的思路：

• 右边就是十位和百位，其可能是 [0-13]，共 14 种可能。
• 左边啥都没有，1 种可能。

那么个位是 2 的次数就是 14 种。

因而不超过 135 的数字中 2 的呈现次数就是 20 + 14 = 34 种。

当然，这外面还有一些细节，比方如果某一位比 2 小或者正好是 2 怎么办？我就不在这里讲了。这里间接贴下代码，大家本人持续实现好了。

class Solution:
    def numberOf2sInRange(self, n: int) -> int:
        ans = 0
        m = 1
        while m <= n:
            cur = n // m % 10
            if cur > 2: ans += (n // m // 10 + 1) * m
            else:
                if cur == 2: ans += n % m + 1
                ans += (n // m // 10) * m
            m *= 10
        return ans

把 2 换成其余数字 x，那就能够计算不超过 n 的 x 的呈现次数。

举这个例子就想通知大家为啥一些题目你压根就没有思路的起因：

• 要么就是这种题没见过，那没方法，多做题呗。
• 要么就是你算法思维还不够。比方我下面讲的分治的算法思维。

一看就会又阐明 这种题你是答复过的 ，因而 一看就会，一写就废，个别都是没有养成良好的算法思维，而分治就是一种十分重要的算法思维。当算法思维有了，剩下的细节就缓缓练习就好了，这没有捷径。然而算法思维是有捷径的，大家在刷题之前要特地重视算法思维的学习。

我再举几个例子给大家，帮忙大家加深了解。

三个题目带你了解分治思维

1. 在一个数组 nums 中找值为 target 的元素，并返回数组下标，题目保障 nums 中有且仅有一个数等于 target。
2. 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算能够凑成总金额所需的起码的硬币个数。如果没有任何一种硬币组合能组成总金额，返回  -1。你能够认为每种硬币的数量是有限的。（322. 零钱兑换）
3. n 皇后问题钻研的是如何将 n 个皇后搁置在 n×n 的棋盘上，并且使皇后彼此之间不能互相攻打。（51. N 皇后）

这几道题笼罩了简略中等和艰难三种难度。接下来，咱们来看下这几个题。

第一题

对于第一题，答案无非就是 [0, n – 1]。因而咱们能够将问题合成为以下几个子问题：

• 是 0 么？no
• 是 1 么？no
• 是 2 么？no
• 。。。

最终的答案就是子问题中答复为“yes”的索引。严格意义上来说，这里只有分，没有治，而且这个分和后面的分有奥妙的差别。后面的分完之后前面还要用，这个分是间接给扔掉了。相似的有二分法，二分法就是一种只有分没有治的“分治法”。

第二题

coins 是个变量，amount 也是变量，它们关系感觉好多的样子？我该怎么理清呢？

咱们从非凡动手，比方 coins = [1, 2, 5], amount = 11。为了不便形容，原问题我用 f([1,2,5], 11) 示意 coins 为 [1,2,5]，amount 为 11 的起码须要多少硬币凑齐。

我也不晓得最终的 起码硬币计划 是怎么选的。那我就所有状况都走一遍呗，比拟一下哪种计划用硬币起码就用哪个不就行了么？

最终的算法还真就是基于这个浮夸的想法来的。

选第一枚硬币的时候，一共只有三种状况：抉择 1，抉择 2，抉择 5。

• 如果咱们先选了 1，那么再凑出 10 就行了。那怎么凑出 10 呢？不就是 f([1, 2, 5], 10) 么？
• 如果咱们先选了 2，那么再凑出 9 就行了。那怎么凑出 9 呢？不就是 f([1, 2, 5], 9) 么？
• 如果咱们先选了 5，那么再凑出 6 就行了。那怎么凑出 6 呢？不就是 f([1, 2, 5], 6) 么？

下面是选取一个硬币的状况，因为没有凑到 amount，咱们持续反复，直到凑到 amount。

于是你能够画出相似如下的逻辑树结构，因为节点太多我没有画全。

有没有发现你的大脑间接解决大问题没有思路，但将其合成为小问题就简略了许多？分 完了，咱们还要 治。

这就如同你是主管，向上面安排了作业，安排完了你还要收作业将他们汇总起来搞个 ppt 啥的。

不过这也不难。因为问题是起码硬币，那么治就取起码呗。

1 + min(f([1,2,5], 10),f([1,2,5], 9),f([1,2,5], 6))

总结一下：

这道题的分咱们能够从几个特例动手就能够关上思维。下面的 分的伎俩用伪代码形容就是：

for (int coin : coins) {f(coins, amount - coin)
}

分完了就是解决边界和 治了。

残缺的分治代码就是：

public int f(coins, amount) {if (amount < 0) {
        // 非法解，用正无穷示意
        return Float.POSITIVE_INFINITY
    }
    // 叶子节点
    if (amount == 0) {
        // 找到一个解，是不是最小的”治“阶段解决。return 0
    }
    int ans = Float.POSITIVE_INFINITY
    for (int coin : coins) {ans = Math.min(ans, 1 + f(coins, amount - coins))
    }
    return ans
}

为了突出我的算法主框架，略去了一些细节。比方原题在无解的时候须要返回 – 1，而我返回的是正无穷。

如果之前做过这道题的敌人应该晓得这是一个典型的背包问题。如果当初让我做，我可能也间接自底向上 dp table 解决了（不过 dp table 和记忆化递归没有实质的思维差异）。然而算法是如何想进去的这一点，是如何一步一步优化的，大家肯定 钻到底，这样刷题效率才高。

第三题

不懂题目意思的能够去看下力扣原题 51. N 皇后。这道题就是典型的回溯题目，什么是回溯？一言以蔽之，那就是一个一个试，不行了就返回上一步持续试。

这么多格子我该放哪呢？每个格子还有制约关系！好乱，没有思路。

别急，持续应用分治的思维。这道题是让咱们将 N 个皇后放到 N X N 的棋盘上。那不就是：

• 第一行的皇后应该放到第几列？
• 第二行的皇后应该放到第几列？
• 第三行的皇后应该放到第几列？
• 。。。

改成”第 x 列的皇后应该放到第几行？”这种子问题划分模式也是能够的。

伪代码：

public int placeRow(i) {// 决定应该放到第几列}

for (int i=0;i<n;i++) {placeRow(i)
}

如果下面的子问题都解决了，那整个问题不就解决了么？

然而下面的子问题，还是无奈间接解决。比方“第一行的皇后应该放到第几列？”我也不晓得啊。没关系，咱们持续对“第一行的皇后应该放到第几列？”这个问题进行合成。

• 第一行的皇后放到第 1 列么？
• 第一行的皇后放到第 2 列么？
• 第一行的皇后放到第 3 列么？
• 。。。

持续欠缺下面的 placeRow 代码即可。这里给出伪代码：

public  boolean canPlaceQueue(i, j) {// 依据目前的棋局（放了是否能不互相攻打），剖析 i 和 j 这个地位是否放女王。}
public int placeRow(i) {for (int j=0;j<n;j++) {if (canPlaceQueue(i, j)) {// 将女王放到 (i,j)，更新以后棋局
            placeQueue(i, j)
        }
    }
}

当初的问题就只剩下实现 canPlaceQueue(i, j) 和 placeQueue(i, j) 了，这两个函数依据题目要求模仿实现即可。

须要留神的是咱们做了一个 placeQueue(i, j) 的操作，这 可能 是一个 mutable 的操作。因而如果一条路行不通须要回溯，那么 mutable 的数据须要撤销批改。当然如果你的数据是 immutable 就无所谓了。不过 immutable 则有可能内存移除或者超时的危险。

因为这里只是讲思维的，不是讲题目自身的，因而还是点到为止，前面的算法细节我就不讲了，心愿读者能本人将代码欠缺一下。

更多

相似的例子切实太多了，基本举不过去，我随口给大家说几个。

• 如果让你求一个数组的间断子数组总个数，你会如何求？其中间断指的是数组的索引间断。比方 [1,3,4]，其间断子数组有：[1], [3], [4], [1,3], [3,4] , [1,3,4]，你须要返回 6。分治就好了，间断子数组个数等于：以索引为 0 结尾的子数组个数 + 以索引为 1 结尾的子数组个数 + … + 以索引为 n – 1 结尾的子数组个数
• 70. 爬楼梯 让你求爬到最初一级台阶有多少种办法。这太多了，我数不过去。然而我能够将其分解成两个子问题。如果我用 f(n) 示意爬到第 n 级的办法数，那么 f(n) = f(n – 1) + f(n – 2)。然而 n – 1 我也不会啊，没关系，咱们持续合成。这和下面的硬币问题有多大差异么？对于这道题，分就是拆成两个子问题，治就是求和。

这就是最简略的无抉择的 递推 动静布局

• 746. 应用最小破费爬楼梯 换了个皮又来了？
• 220 场周赛 – 跳跃游戏 VI 这不还是下面爬楼梯换皮么？这次变成了一次能爬 k 级台阶罢了。

这道题数组长度是 $10^5$，如果不做优化复杂度会是 $N^2$，算起来就是 $10^10$ 过不了，大于下面给大家讲的 1000 万。如何优化有点跑题了，就不在这里讲了。

• 62. 不同门路 穿个二维的衣服就看不出你是爬楼梯了？

相干换皮题目太多，大家能够去我的插件里看。

总结

本次给大家分享了一个很重要的算法思维 分治，很多题都能够用到这个思维。能使用分治思维的专题有“动静布局”,”分治“，“回溯”等，大家在平时做题的时候能够参考我的这种思考形式。

如果你碰到一个简单的问题，能够尝试以下几个办法。

• 无妨先尝试将其拆解，看是否将其拆解成几个小问题。
• 在草稿上画画图，从非凡状况动手，看是否发现什么蛛丝马迹
• 暴力模仿。看是否通过剪枝和增加失当的数据结构来优化算法，使之通过。

如果你有更好的干货技巧，十分心愿你能和我交换，万分期待！

除了算法思维，我还和大家分享两个超实用的技巧，别离是：

• 看关键字。关键字很多时候起到了提醒作用，甭管对不对，咱要想到。想到之后迅速脑子中过一下能不能 AC。
• 看限度条件。记住一个数字就行了，1000 万。

最初和大家说了一个小心得 –”不要小看暴力法“。暴力法不仅能帮忙你关上思路，有时候甚至暴力 + 剪枝（或数据结构优化）就过了。鼎力出奇观，欧耶！\(^o^)/

爱心三连击

1. 看到这里了就点个在看反对下吧，你的 在看 是我创作的能源。

2. 关注公众号 力扣加加 ，带你啃下算法这块硬骨头！ 加个星标，不错过每一条成长的机会。

3. 如果你感觉本文的内容对你有帮忙，就帮我 转发 一下吧。