深圳市住房和建设局网站,php带数据库的网站,有没有免费看的视频,重庆市建设工程信息网文件打不开很多朋友害怕算法#xff0c;其实大可不必#xff0c;算法题无非就那几个套路#xff0c;一旦掌握#xff0c;就会觉得算法实在是太朴实无华且枯燥了#xff01;本文选自硬核算法教程《labuladong的算法小抄》#xff0c;带你学习套路#xff0c;把握各类算法问题的共性…很多朋友害怕算法其实大可不必算法题无非就那几个套路一旦掌握就会觉得算法实在是太朴实无华且枯燥了本文选自硬核算法教程《labuladong的算法小抄》带你学习套路把握各类算法问题的共性数据结构是工具算法是通过合适的工具解决特定问题的方法。对于任何数据结构其基本操作无非遍历 访问再具体一点就是增、删、查、改。那么该如何在力扣刷题呢很多文章都会告诉你“按标签刷”“坚持下去”等。不说这些不痛不痒的话直接给具体的建议。先刷二叉树先刷二叉树先刷二叉树这是我刷题一年的亲身体会下图是 2019 年 10 月的提交截图据我观察大部分人对与数据结构相关的算法文章不感兴趣而是更关心动态规划、回溯、分治等技巧。这是不对的这些常考算法技巧在《labuladong的算法小抄》中都会有所涉及到时候你就会发现它们看起来高大上但本质上就是一个多叉树遍历的问题配合算法框架并没有多难。为什么要先刷二叉树呢因为二叉树是最容易培养框架思维的而且大部分常考算法本质上都是树的遍历问题。刷二叉树时看到题目没思路其实大家不是没思路只是没有理解“框架”是什么。不要小看下面这几行代码几乎所有二叉树的题目一套用这个框架就都出来了。1void traverse(TreeNode root) {2 // 前序遍历3 traverse(root.left);4 // 中序遍历5 traverse(root.right);6 // 后序遍历7}比如随便拿几道题的解法代码出来这里不用管具体的代码逻辑只看看框架在其中是如何发挥作用的。 LeetCode 124 题 难度为 Hard求二叉树中最大路径和主要代码如下 1int ans INT_MIN; 2int oneSideMax(TreeNode* root) { 3 if (root nullptr) return 0; 4 5 int left max(0, oneSideMax(root-left)); 6 int right max(0, oneSideMax(root-right)); 7 8 /**** 后序遍历 ****/ 9 ans max(ans, left right root-val);10 return max(left, right) root-val;11 /****************/12}你看这不就是后序遍历嘛。那为什么是后序呢题目要求最大路径和对于一个二叉树节点是不是先计算左子树和右子树的最大路径和然后加上自己的值这样就得出新的最大路径和了所以说这里就要使用后续遍历框架。 LeetCode 105 题 难度为 Medi um要求根据前序遍历和中序遍历的结果还原一棵二叉树这是很经典的问题主要代码如下 1TreeNode buildTree(int[] preorder, int preStart, int preEnd, 2 int[] inorder, int inStart, int inEnd, Map inMap) { 3 4 if(preStart preEnd || inStart inEnd) return null; 5 6 /**** 前序遍历 ****/ 7 TreeNode root new TreeNode(preorder[preStart]); 8 int inRoot inMap.get(root.val); 9 int numsLeft inRoot - inStart;10 /****************/1112 root.left buildTree(preorder, preStart 1, preStart numsLeft, 13 inorder, inStart, inRoot - 1, inMap);14 root.right buildTree(preorder, preStart numsLeft 1, preEnd, 15 inorder, inRoot 1, inEnd, inMap);16 return root;17}不要看这个函数的参数很多它们只是为了控制数组索引而已本质上该算法就是一个前序遍历算法。 LeetCode 99 题 难度为 Hard要求恢复一棵 BST(完全二叉树)主要代码如下 1void traverse(TreeNode* node) { 2 if (!node) return; 3 4 traverse(node-left); 5 6 /****中序遍历 ****/ 7 if (node-val val) { 8 s (s NULL) ? prev : s; 9 t node;10 }11 prev node;12 /****************/1314 traverse(node-right);15}这不就是中序遍历嘛对于一棵 BST中序遍历意味着什么应该不需要解释了吧。你看Hard 难度的题目不过如此而且还这么有规律可循只要把框架写出来然后往相应的位置加内容就行了这不就是思路嘛对于一个理解二叉树的人来说刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理不妨从二叉树下手前 10 道也许有点难受结合框架再做 20 道题也许你就有点自己的理解了刷完整个专题再去做什么回溯、动态规化、分治专题你就会发现只要涉及递归的问题基本上都是树的问题。▽▽▽再举些例子吧。在《labuladong的算法小抄》“动态规划解题套路框架”章节中会讲到凑零钱问题暴力解法就是遍历一棵 N 叉树 1def coinChange(coins: List[int], amount: int): 2 3 def dp(n): 4 if n 0: return 0 5 if n 这么多代码看不懂怎么办直接提取框架这样就能看出核心思路了这就是刚才说到的遍历 N 叉树的框架1def dp(n):2 for coin in coins:3 dp(n - coin)其实很多动态规划问题就是在遍历一棵树你如果对树的遍历操作烂熟于心那么起码知道怎么把思路转化成代码也知道如何提取别人解法的核心思路。再看看回溯算法在《labuladong的算法小抄》“回溯算法解题套路框架”中会直接告诉你回溯算法就是一个 N 叉树的前序 后序遍历问题没有例外。比如排列组合问题、经典的回溯问题主要代码如下 1void backtrack(int[] nums, LinkedList track) { 2 if (track.size() nums.length) { 3 res.add(new LinkedList(track)); 4 return; 5 } 6 7 for (int i 0; i track) {18 for (int i 0; i N 叉树的遍历框架找出来了吧。你说树这种结构重不重要综上所述对于畏惧算法或者刷题很多但依然感觉不得要领的朋友来说可以先刷树的相关题目试着从框架看问题而不要纠结于细节。所谓纠结细节就比如纠结 i 到底应该加到 n 还是加到 n - 1 这个数组的大小到底应该开成 n 还是 n 1 从框架看问题就是像我们这样基于框架进行抽取和扩展既可以在看别人解法时快速理解核心逻辑也有助于我们找到自己写解法时的思路方向。当然如果细节出错你将得不到正确的答案但是只要有框架再错也错不到哪去因为你的方向是对的。但是你要是心中没有框架那么根本无法解题给你答案也不能意识到这就是树的遍历问题。框架思维是很重要的有时候按照流程写出解法说实话我自己都不知道为啥是对的反正它就是对了……这就是框架的力量能够保证你在思路不那么清晰的时候依然写出正确的程序。—— ——最后我们总结一下刷算法题建议从“树”分类开始刷结合框架思维把几十道题刷完对于树结构的理解应该就到位了。这时候去看回溯、动态规划、分治等算法专题对思路的理解可能会更加深刻一些。在思考问题的过程中少纠结细节不要热衷于炫技希望读者多从框架看问题多学习套路把握各类算法问题的共性《labuladong的算法小抄》将会为你提供这方面的帮助。图书推荐▊《labuladong的算法小抄》付东来(labuladong) 著GitHub 68.8k star的硬核算法教程labuladong带你挑战力扣算法题挑战BAT等大厂Offer本书专攻算法刷题训练算法思维应对算法笔试。注重用套路和框架思维解决问题以不变应万变。
