概念类似高中学过的集合的概念，一个元素对应唯一的集合；并查集通常包含两种操作，寻找元素的唯一集合和合并两个不相交集。 123456789101112131415161718CONNECTED-COMPONENT(G) for each vertex v in G.V MAKE-SET(v) for each edge(u,v) i...

概念拓扑排序(Topological Sort)是有向图中所有结点的一种线性次序，即最终的排序结果一定要符合图中的先后方向。也就是说拓扑排序是存在多解或者无解的可能，显然有向环不存在拓扑排序。详细概念这篇文章还是讲得挺细致的，包括全序/偏序概念。其实现有Kahn算法(类似BFS)和DFS算法，分别如下图所示。 Kahn算法DFS算法 LeetCo...

概念如上图所示，对于每次搜索而言尽可能往深度前进，直到结点v的所有出发边都被找到然后回溯。通常用递归实现，遍历结果依赖每次选择遍历子结点的顺序。 LeetCode之深度优先搜索 332.Reconstruct Itinerary重建飞行旅程，给定n段起点终点旅程，输出飞行目的地的先后顺序，从”JFK”为最初起点，可以返回飞行，若有多个答案，输出字典小序的那个...

上篇中介绍了二叉树的基本概念和操作。本篇着重于实际问题。 545.Boundary of Binary Tree定义树的左边界为根节点到最左节点的路径，右边界为根节点到最右节点的路径。最左节点为从根节点能到达的最左叶子节点，若没有左子树存在右子树，能在右子树中找最左节点，对于根而言若不存在左子树则根为最左节点；同理最右节点。要求逆时针输出：左边界+叶子节点...

概念 有一个根节点 每一个节点有左右子节点 n层二叉树最多2^n-1个节点（满二叉树） 完全二叉树前n-1层位满二叉树，最后一层左节点必须先于右节点存在 完全二叉树节点数量2^(n-1)~2^n-1 节点类型1234function TreeNode(val) { this.val = val; this.left = this.right...

概念贪心算法相比动态规划，是在子问题中每次做出局部最优选择，以得到全局最优解。贪心算法不一定总能得到最优解，但对某些问题很有效。与动态规划不同之处在于，动态规划每次做出的选择依赖于子问题的解，通常需要从较小子问题向较大子问题自底向上求解。而贪心算法不依赖于将来的选择或者子问题的解，而是做出看起来最佳的选择，通常是自顶向下的。贪心算法的关键是找出最优子结构里的...

概念堆是一种有效的优先队列，对于二叉堆而言，有最大堆与最小堆。最大堆的性质是所有节点满足A[Parent[i]]>=A[i]，最小堆相反。 《算法导论》里给出了最大堆的几种操作： Max-Heapify 当有节点不满足大于子节点特性时，进行下沉，时间复杂度O(lgn)，是维护最大堆性质的重要过程。 Build-Max-Heap 建堆过程，具...

概念栈和队列都是简单的基础数据结构，栈(stack)实现的是后进先出(LIFO)策略，队列则是先进先出(FIFO)策略。话不多说，我们看看LeetCode上tag为栈的几道题目。 LeetCode之栈 255.Verify Preorder Sequence in Binary Search Tree给定数组，判断其是否是二叉搜索树(BST)的先序遍历，假定...

按标签刷Leetcode也有一段时间了，本周轮到回溯算法，因此作一个适时的输出。 概念回溯法，顾名思义，在找解的过程中需要掉回头重新找的。与之对应的是贪心算法或动态规划，贪心算法与动态规划都需要在子结构中找到最优解以进行下一步求解。通常求解问题脑子第一想法也是用穷举来暴力求解，若不满足题目约束条件，换一条路重新穷举。换路的过程就是回溯了，概念比较容易理解。 ...

给定两个非负整数，返回乘积。由于没有指定整数的位数，需要拓展到大数相乘。一种方法就是用字符串来进行计算。