xhj的博客

LeetCode - 208. Implement Trie (Prefix Tree)以及实现字典树(前缀树) 基础知识和结构 字符串的插入 统计某个字符串的数量 || 查询是否有某个字符串 统计以某个字符串为前缀的字符串数量 || 是否有某个前缀 字符串的删除 完整测试代码 题目解析 使用Map来保存next 更多字典树 基础知识和结构Map和Trie的差别，关于映射集合等可以看这篇博客。 字典树也叫做前缀树，可以存储一组元素(一般是字符串)，可以快速的查找某个字符串在树中的个数以及寻找以某个字符串为前缀的字符串的个数，先看下图为一些字符串插入到字典树中的情形。 字典树的存储结构: 首先字母是画在树的边上的； 而结点中的path代表的是经过这个结点的字母的次数； 为了方便前缀的计算，而end表示的是以这个结点结尾的字符串的数量，方便统计树中某个字符串的数量。 而next表示的是多个儿子结点，因为可以有大小写字母，所以我初始化为52(如果是小写字母的就为26)(也可以使用Map来存储)。 1 2 3 4 5 6 7 8 9 10 11 12 13 ...

最大值减去最小值小于等于aim的子数组数量(单调队列(最大值和最小值更新结构)) 注意: 子数组必须是下标连续的，而且i ~ i自己也算一个子数组。 解析这个题目也是使用单调队列(窗口内更新最大值和最小值)的结构来做，如果不懂单调队列先看这个博客。 先准备两个双端队列，分别是最大值更新结构和最小值更新结构： 先生成两个双端队列qmax和qmin，当子数组为arr[L...R]时，qmax维护了窗口子数组arr[L...R]的最大值更新结构，qmin维护了窗口子数组arr[L....R]的最小值更新结构； 当子数组arr[L....R]向右扩一个位置变成arr[L....R+1]时，qmax和qmin可以在O(1)时间内完成更新；并且可以在O(1)时间内得到窗口的最大值和最小值； 当子数组arr[L....R]左边缩一个位置变成arr[L+1....R]是，qmax和qmin可以在O(1)时间内完成更新；并且可以在O(1)时间内得到窗口的最大值和最小值； 然后，我们需要证明两个结论: 下面看具体过程: 找到一个L，此时令R不断向右移动，表示arr[L...R]一直向右扩大，并...

单调栈介绍以及构造数组的MaxTree问题 单调栈介绍 单调栈解决构造数组的MaxTree问题 堆解决构造数组的MaxTree问题 完整测试代码 题目(构造数组的MaxTree问题) 单调栈介绍单调栈最初解决的问题就是寻找一个数组中 ，每一个数的左右两边离它最近的数。 遍历一个数组，如果栈为空或者栈顶比当前数大(或者相等，相等的话就多个下标对应一个值)，就把当前数入栈； 如果栈顶比当前数小，那么就处理这个栈顶，即这个栈顶右边第一个比它大的数就是当前数，左边第一个比它大的数就是在栈里面它的下面的那个数，也就是它出栈之后的栈顶； 当遍历完所有的数之后，栈中还有数，这时，逐个判断栈中的数，每一个数，它的右边不存在比它大的，如果这个数在栈里面它的下面还有数，它左边离他最近的大的数就是它下面的数； 单调栈解决构造数组的MaxTree问题按照下面的方法来建树 每一个树的父节点是它左边第一个比它大的数和它右边第一个比它大的数中，比较小的那个； 如果左边没有没有比它大的数，右边也没有。也就是说，这个数是整个数组的最大值，那么这个数是MaxTree的头结点； 按照大根堆和上面的方案放...

将单链表按某值划分成左边小，中间相等，右边大的形式 普通方法，将链表节点放到数组然后partition 进阶方法，将链表划分成三个子链表，然后合并 普通方法，将链表节点放到数组然后partition 这个方法比较简单，直接将链表中的值保存到一个数组中，然后按照荷兰国旗的划分方式，将数组划分成左边小于那个数，中间等于那个数，右边大于那个数的形式，(荷兰国旗问题用于快速排序中的partition过程)； 划分完之后，再把数组中的值用链表的形式连接起来。　但是这个方法需要额外的O(n)的空间复杂度，而且partition不能达到稳定性(就是会改变原来的相对顺序)； 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 static class Node { public int value; publ...

找到二叉树中的最大搜索二叉子树 递归 技巧的写法 完整测试代码 题目 递归解析:这种题目的解题过程分为三步: 列出所有可能性； **列出结点需要的信息，并整合信息(成一个结构体)**； 改递归 ，先假设左和右都给我信息(黑盒)，然后怎么利用左边和右边的信息组出来我该返回的信息，最后basecase(边界)填什么； 具体到这个题目：第一步，列出所有可能性： 第一种可能性，以node为头的结点的最大二叉搜索子树可能来自它左子树； 第二种可能性，以node为头的结点的最大二叉搜索子树可能来自它右子树； 第三种可能性，左树整体是搜索二叉树，右树整体也是搜索二叉树，而且左树的头是node.left，右树的头是node.right，且左树的最大值< node.value，右树的最小值 > node.value， 那么以我为头的整棵树都是搜索二叉树； 第二步，列出结点需要的信息: 信息一: 左树最大搜索二叉树大小； 信息二: 右树最大搜索二叉树大小； 信息三: 左树上最大搜索二叉树的头部是什么； 信息四: 右树上最大搜索二叉树的头部是什么； 信息五: 左树上的最大值； ...

在一颗二叉树中寻找一个结点的后继结点(前驱结点) 找后继结点 找前驱结点 找后继结点首先知道什么是后继结点，就是二叉树中序遍历的序列中，某个结点紧随的那个结点比如下面的二叉树以及对应的中序遍历顺序。 则4的后继是2 ，2的后继是5，7的后继是null。 在树的结构中，每个结点有一个指向父亲的域parent，看如下结构 1 2 3 4 5 6 7 8 9 10 11 static class Node{ public int value; public Node left; public Node right; public Node parent; public Node(int value) { this.value = value; } } 那么如何快速的寻找当前结点node后继结点呢? 其实只需要分为两种情况 第一，如果node结点有右子树，那么就是右子树上最左的结点，例如上图的２的右子树上的最左结点是5，5的右子树上最左的结点是8，1的右子树上最左的结点是9，3的右子树上最左的结...

如何直观的打印一颗二叉树打印的结果是需要顺时针旋转90度的，如下面的结果打印出来是这样的。 如何打印呢? 需要处理以下四个问题： 遍历树的顺序是　右子树->根->左子树； 因为要避免数字长度影响对齐的因素，所以两边补上空格(有一个总长度可以自己确定)； 在结点的两边加上特定的字符串标记区分孩子和父亲以及位置，使用 H、 ^、 v 这个几个标记 和高度有关系的 height * len， 打印相应前面的空格长度； 代码如下 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 public class PrintBinaryTree { static class Node{ public int value; public Node ...

二叉树之Morris遍历 递归理解以及morris遍历 由morris遍历改成前序遍历 由morris遍历改成中序遍历 由morris遍历改成后续遍历 完整测试代码 递归理解以及morris遍历 1 2 3 4 5 6 7 8 static void rec(Node head) { if (head == null) return; System.out.print(head.value + " "); //这里打印就是前序遍历 rec(head.left); System.out.print(head.value + " "); //这里打印就是中序遍历 rec(head.right); System.out.print(head.value + " "); //这里打印就是后续遍历 } 这是我们用递归写的三种遍历方法，如果是下面的例子，上面程序输出如下： 程序输出: 1 1 2 4 8 8 8 4 4 2 5 5 9 9 9 ...

二叉树结点间的最大距离问题 递归 改进的写法 完整测试代码 题目 递归解析这个也是一个二叉树的问题，分为三步: 列出所有可能性； 列出结点需要的信息，并整合信息(成一个结构体)； 改递归 ，先假设左和右都给我信息(黑盒)，然后怎么利用左边和右边的信息组出来我该返回的信息，最后basecase(边界)填什么； 具体到这个题目:第一步，列出可能性： 一个以node为头的树上，最大距离只可能来自下面三种情况: 不需要经过node这个点，node的左子树上自己的最大距离； 不需要经过node这个点，node的右子树上自己的最大距离； 要经过node这个点，此时就是左子树的高度 + 右子树的高度 + 1 ； 第二步，确定结点需要的信息，并整合: 信息一: 返回的以node为头的树的最大距离； 信息二: 返回的以node为头的高度； 第三步，封装信息，写出递归 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ...

二叉树的各种操作(递归和非递归遍历,树深度,结点个数等等) 建立二叉树 1、根据下标关系 2、前序输入(cin)建立 前序遍历 1、递归前序 2、非递归前序 中序遍历 1、递归中序 2、非递归中序 后序遍历 1、递归后序 2、非递归后序 层次遍历 寻找树中有没有值为x的结点 统计树中结点的个数 计算树的高度 判断两颗树是不是相等 完整测试代码 二叉树建立先给出结点结构: 1 2 3 4 5 6 7 8 9 static class Node { public int val; public Node left; public Node right; public Node(int val) { this.val = val; } } 两种建立方式: 可以根据二叉树根节点和左右子结点的下标关系递归建立二叉树，层次输入二叉树结点； 也可以使用输入流前序建立二叉树(注意空树要输入-1)； 1、根据下标关系 1 2 3 4 5 6 7 8 9 ```...