如何利用力扣学习算法和数据结构

这篇内容基本来源于力扣官方在知乎给萌新学习力扣的建议。

在开始刷题前，只需要你至少掌握一门编程语言，即使你从未刷过算法题。

算法和数据结构的知识考点

算法和数据结构的关系。如果把算法比作建筑工程的图纸，数据结构就像是建造大楼的工具。数据结构设计的初衷就是方便程序员使用，虽然看似种类较多，但实际上每一种都不难，可以结合算法一起学习。

Pasted image 20230307150405.png|650

探索卡片

对于零基础的同学来说，不建议一开始就从题库页开始按顺序刷题。在力扣的 探索页面 有十分丰富的算法和数据结构主题卡片，从探索卡片开始学习能帮助你快速入门。每个卡片都覆盖了详细的知识点介绍，概念讲解，结构特点，代码实现，例题及答题套路。按照正确的顺序来刷探索卡片，由浅入深，逐层打好算法根基。

Pasted image 20230307150630.png|400

进阶

接着上面的探索卡片学习；有了一定的算法和数据结构基础以后，这时你就可以选择刷面试题、或者题库了。要准备面试的话，多写写面试题。面试题可以选最近时期的「名企高频面试题」、「剑指 Offer」等。如果已经在准备面试冲刺的阶段，这时候不妨多刷两遍「剑指 Offer」题库。当然也可以养生刷刷题库；根据题库页的标签进行专项刷题也是一个非常不错的选择。

Pasted image 20230307151612.png|250

刷题技巧

当我们开始刷一类算法题前，如果对此算法的概念还不太熟悉，花费 5 分钟左右的时间了解其概念是很有必要的。在力扣题库页的 标签分类 中，点击对应的标签即可查看算法概念。

在足够多的准备工作后，我们就可以开始找一道简单～中等的题目小试牛刀了。有的同学会想：直接从困难题目开始练习，练会了困难题目，再去看简单题和中等题岂不是轻而易举？事实上我们不建议初学者直接练习困难题目。因为困难题目往往不够典型，困难题总是糅合了多种算法，难点在于对多种算法的综合应用，不适合在学习阶段用来专攻某一类算法。

下面举一个具体的例子，比如我们计划本周刷深度优先搜索的题目。先点击题库页「深度优先搜索」标签，查看其概念：

Pasted image 20230307151936.png|500

从概念中我们知道，深度优先搜索，简称 DFS，主要用于遍历或搜索树或图。核心是沿着树的深度遍历树的节点，以深度优先的方式来遍历一棵树，直到找到需要搜索的节点或是遍历结束。这不难理解，了解完概念，我们的脑中就对此算法有了一个粗略地认识：

想象我们正站在一棵大树前，我们想要浏览这棵树的整个结构。
于是我们选择从大树的根出发，往树枝处浏览；
遇到树木分叉的地方，就随机选择一个树枝开始浏览；
浏览完后，回到上一个分叉的地方，选择另一个树枝继续浏览，直到所有的树枝都浏览完成。

事实上，深度优先搜索和树形结构经常成双成对出现，二者总是密不可分。有了一个粗略的认识后，我们应该立即选择一道简单的题目开始练习：

Pasted image 20230307152046.png|500

看到题目，我们的第一想法可能是以根节点为中心，左边的最长路径加上右边的最长路径应该就是答案。如题目示例中的树：

Pasted image 20230307152116.png|80

根节点左边的最长路径为 2，右边的最长路径为 1，所以和为 3。

看起来没有错，我们再考虑一些特殊情况，有没有可能最长路径不经过根节点呢？不妨画个草图看一下：

Pasted image 20230307152134.png|80

对于这样一棵树，根节点没有右子树，所以根节点右边的最长路径为 0，而左边的最长路径是 3，所以这样算起来直径为 3。但我们发现以2做为根节点的子树直径为 4，大于我们当前算法算出的直径！显然我们之前的思路是错误的，根节点其实不一定经过根节点，子节点可能存在更长的直径。我们不得不选择另一种思路。

如果此时冥思苦想，仍然没有思路的话，我们可以点开题解区抄一下别人的解题思路。先依着葫芦画瓢，等学会了再自己创造。

我们看到本题题解区有力扣官方发布的题解：

Pasted image 20230307152149.png|600

看完题解我们已经有了具体的解题思路。此时切记不要眼高手低，不要觉得看懂了就是会了，一定要亲自将代码敲一遍，有过刷题经验的人都知道，看别人解题和自己亲自上手是完全不一样的感觉。经常是脑子和眼睛在说：我会了。而手在说：不，你不会！

仿照着官方题解，我们写出本题的 kotlin 解法：

class Solution {
var ans = 0
fun diameterOfBinaryTree(root: TreeNode?): Int {
        ans = 1
        depth(root)
return ans - 1
    }
 
 
fun depth(node: TreeNode?): Int {
if (node == null) return 0 // 访问到空节点了，返回0
val L = depth(node.left) // 左儿子为根的子树的深度
val R = depth(node.right) // 右儿子为根的子树的深度
        ans = Math.max(ans, L + R + 1) // 计算d_node即L+R+1 并更新ans
        return Math.max(L, R) + 1 // 返回该节点为根的子树的深度
    }
}

这是一道非常典型的 DFS 算法题，刷完之后我们应该反复思索，做出总结：DFS 的核心是依次尝试，运用的主要手段是递归函数。

然后我们马上再找一道近似的题，继续练习本类算法，比如：

Pasted image 20230307152248.png|500

这道题与上道题非常类似，它也是非常典型的 DFS 题，因为它没有掺杂多类算法，实际难度算不上困难。这一次我们争取不查看题解，先将上题的模板拷贝过来，加以修改写出解法：

class Solution {
var max = Int.MIN_VALUE
 
 
fun maxPathSum(root: TreeNode?): Int {
        maxDeep(root)
        return max
    }
 
 
fun maxDeep(node: TreeNode?): Int {
if (node == null) return 0
val L = Math.max(maxDeep(node.left), 0)
val R = Math.max(maxDeep(node.right), 0)
        max = Math.max(max, node.`val` + L + R)
        return node.`val` + Math.max(L, R)
    }
}

如果此时仍然不能手打出一道完整的典型 DFS 题目，就继续反复练习，坚持这个过程，直至自己完全掌握此类题目。

总而言之，算法学习技巧可总结为四个步骤：一看二抄三改四写。