xhj的博客

MySQL基础 一、数据库的基本操作 1、基本命令 2、数据库储存引擎 二、数据表的基本操作 1、创建数据表 2、修改数据表 3、删除数据表 4、综合案例小结 三、数据类型和运算符 1、MYSQL数据类型介绍 2、如何选择数据类型 3、常见运算符介绍 四、Mysql函数 查询数据 插入、更新与删除数据 索引 一、数据库的基本操作1、基本命令登陆数据库命令: 1 mysql -h localhost -u root -p 创建数据库命令: 1 create database test_db; 查看已经创建的数据库的定义 1 show create database test_db; 查看已经存在的所有数据库: 1 show databases; 删除数据库 1 drop database test_db; 注意删除数据库时要小心，不会给出提示，数据和数据表会一同删除。 2、数据库储存引擎1)、查看引擎命令使用如下命令查看系统所支持的引擎类型: 1 sh...

The Suspects以及并查集总结 题目 基本并查集 Size优化并查集 Rank优化并查集 路径压缩优化一(最好) 路径压缩优化二(递归) 题目链接 http://poj.org/problem?id=1611 题意就是告诉你0号同学被感染了，他还参加了一些社团，给出一些社团以及里面的人，问总共多少人感染。输入给出n表示人数(标号为0~n-1)，m表示社团数目，接下来m行每行第一个数k ，表示该社团有k人，然后是k个人的编号。要你输出有多少个人感染了病毒。 解析题目本身并不难: 把每个社团加入到各自的集合中，然后不断的合并相同的集合，最后看哪些和0号同学在同一个集合中，使用一个变量记录和0号同学在同一个集合中的人数即可； 这里主要是总结并查集几种优化的方式； 基本并查集基本并查集，记录一个每个结点p的父亲结点是parent[p]，然后是一个不断从孩子找父亲的过程: find()操作， while(p != parent[p])p = parent[p]，一直往上找根的过程； union()操作，就是找到两个结点的根节点，然后将其中一个结点的根节点挂到另一个结点的...

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 ...