写点什么

数据结构和算法学习指南

用户头像
Android架构
关注
发布于: 5 小时前

}


void traverse(ListNode head) {


for (ListNode p = head; p != null; p = p.next) {


// 迭代访问 p.val


}


}


void traverse(ListNode head) {


// 递归访问 head.val


traverse(head.next)


}


二叉树遍历框架,典型的非线性递归遍历结构:


/* 基本的二叉树节点 */


class TreeNode {


int val;


TreeNode left, right;


}


void traverse(TreeNode root) {


traverse(root.left)


traverse(root.right)


}


你看二叉树的递归遍历方式和链表的递归遍历方式,相似不?再看看二叉树结构和单链表结构,相似不?如果再多几条叉,N 叉树你会不会遍历?


二叉树框架可以扩展为 N 叉树的遍历框架:


/* 基本的 N 叉树节点 */


class TreeNode {


int val;


TreeNode[] children;


}


void traverse(TreeNode root) {


for (TreeNode child : root.children)


traverse(child)


}


N 叉树的遍历又可以扩展为图的遍历,因为图就是好几 N 叉棵树的结合体。你说图是可能出现环的?这个很好办,用个布尔数组 visited 做标记就行了,这里就不写代码了。


所谓框架,就是套路。


不管增删查改,这些代码都是永远无法脱离的结构,你可以把这个结构作为大纲,根据具体问题在框架上添加代码就行了,下面会具体举例


3、算法刷题指南


========


首先要明确的是,数据结构是工具,算法是通过合适的工具解决特定问题的方法。也就是说,学习算法之前,最起码得了解那些常用的数据结构,了解它们的特性和缺陷。


那么该如何在 LeetCode 刷题呢?之前的文章?算法学习之路?写过一些,什么按标签刷,坚持下去云云。


现在距那篇文章已经过去将近一年了,我不想说那些不痛不痒的话了,直接说具体的建议:


先刷二叉树,先刷二叉树,先刷二叉树


先刷二叉树,先刷二叉树,先刷二叉树


先刷二叉树,先刷二叉树,先刷二叉树



这是我这刷题的亲身体会,下图是我从 2018/10 到 2019/10 这一年的心路历程:



公众号文章的阅读数据显示,大部分人对数据结构相关的算法文章不感兴趣,而是更关心动规回溯分治等等技巧。


为什么要先刷二叉树呢?


因为二叉树是最容易培养框架思维的,而且大部分算法技巧,本质上都是树的遍历问题


刷二叉树看到题目没思路?


根据很多读者的问题,其实大家不是没思路,只是没有理解我们说的「框架」是什么。


不要小看这几行破代码,几乎所有二叉树的题目都是一套这个框架就出来了


void traverse(TreeNode root) {


// 前序遍历


traverse(root.left)


// 中序遍历


traverse(root.right)


// 后序遍历


}


补充学习:?一组动画彻底理解二叉树遍历


比如说我随便拿几道题的解法出来,不用管具体的代码逻辑,只要看看框架在其中是如何发挥作用的就行。


LeetCode 124 题,难度 Hard,让你求二叉树中最大路径和,主要代码如下:



看出来了吗,这就是个后序遍历嘛。


LeetCode 105 题,难度 Medium,让你根据前序遍历和中序遍历的结果还原一棵二叉树,很经典的问题吧,主要代码如下:



不要看这个函数的参数很多,只是为了控制数组索引而已,本质上该算法也就是一个前序遍历。


LeetCode 99 题,难度 Hard,恢复一棵 BST,主要代码如下:



这不就是个中序遍历嘛,对于一棵 BST 中序遍历意味着什么,应该不需要解释了吧。


你看,Hard 难度的题目不过如此,而且还这么有规律可循,只要把框架写出来,然后往相应的位置加东西就行了,这不就是思路吗。


刚开始刷二叉树的题目,前 10 道也许有点难受;结合框架再做 20 道,也许你就有点自己的理解了;刷完整个专题,再去做什么回溯动规分治专题,你就会发现只要涉及递****归的问题,都是树的问题


直接举例吧,说几道我们之前文章写过的问题。


动态规划详解?说过凑零钱问题,暴力解法就是遍历一棵 N 叉树:


def coinChange(coins: List[int], amount: int):


def dp(n):


if n == 0: return 0


if n < 0: return -1


res = float('INF')


for coin in coins:


subproblem = dp(n - coin)

子问题无解,跳过

if subproblem == -1: continue


res = min(res, 1 + subproblem)


return res if res != float('INF') else -1


return dp(amount)


这么多代码看不懂咋办?直接提取出框架,就能看出核心思路了:

不过是一个 N 叉树的遍历问题而已

def dp(n):


for coin in coins:


dp(n - coin)



其实很多动态规划问题就是在遍历一棵树,你如果对树的遍历操作烂熟于心,起码知道怎么把思路转化成代码,也知道如何提取别人解法的核心思路。


再看看回溯算法,前文?回溯算法详解?干脆直接说了,回溯算法就是个 N 叉树的前后序遍历问题,没有例外。


比如 N 皇后问题吧,主要代码如下:


void backtrack(int[] nums, LinkedList<Integer> track) {


if (track.size() == nums.length) {


res.add(new LinkedList(track));


return;


}


for (int i = 0; i < nums.length; i++) {


if (track.contains(nums[i]))


continue;


track.add(nums[i]);


// 进入下一层决策树


backtrack(nums, track);


track.removeLast();


}


/* 提取出 N 叉树遍历框架 */


void backtrack(int[] nums, LinkedList<Integer> track) {


for (int i = 0; i < nums.length; i++) {


backtrack(nums, track);


}


N 叉树的遍历框架,找出来了吧。你说,树这种结构重不重要?


综上,对于算法无从下手的朋友来说,可以先刷树的相关题目,试着从框架上看问题,而不要纠结于细节问题


纠结细节问题,就比如纠结 i 到底应该加到 n 还是加到 n - 1,这个数组的大小到底应该开 n 还是 n + 1 ?


从框架上看问题,就是像我们这样基于框架进行抽取和扩展,既可以在看别人解法时快速理解核心逻辑,也有助于找到我们自己写解法时的思路方向。


当然,如果细节出错,你得不到正确的答案,但是只要有框架,你再错也错不到哪去,因为你的方向是对的。


但是,你要是心中没有框架,那么你根本无法解题,给了你答案,你也不会发现这就是个树的遍历问题。


这种思维是很重要的,动态规划详解?中总结的找状态转移方程的几步流程,有时候按照流程写出解法,说实话我自己都不知道为啥是对的,反正它就是对了。。。


**这就是框架的力量,能够保证你在快睡着的时候,依然能写出正确的程序;**就算你啥都不会,都能比别人高一个级别。


4、最后总结


======


数据结构的基本存储方式就是链式和顺序两种,基本操作就是增删查改,遍历方式无非迭代递归

用户头像

Android架构

关注

还未添加个人签名 2021.10.31 加入

还未添加个人简介

评论

发布
暂无评论
数据结构和算法学习指南