树的存储和二叉树化与还原
树的存储结构双亲表示法在每个元素中分为数据域和双亲域，其中双亲域表明了该元素的父元素的位置 特点：找双亲容易，找孩子难。 孩子链表把每个节点的孩子的指针组成一个链表 特点：找孩子容易，找双亲难 孩子兄弟表示法（二叉树表示法，二叉链表表示法） 树与二叉树的转换树转二叉树 在兄弟之间加线 对每个结点，除了其左孩子，去除与孩子的联系 二叉树转树 把每个左孩子的右孩子和右孩子的右孩子…沿着分支找到所有的右孩子，与双亲连起来 抹去原二叉树中双亲和右孩子的连线 森林转二叉树分别把每棵树转化为二叉树后，头节点连起来 二叉树转森林将二叉树的根节点与所有沿着右分支的右孩子连线全部抹掉
二叉树
顺序遍历二叉树先序遍历 访问根节点 访问左子树 访问右子树 递归以上过程 中序遍历按照“左中右”的顺序访问 简单代码 12345678910111213141516class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); inorder(root, res); return res; } public void inorder(TreeNode root, List<Integer> res) { if (root == null) { return; } inorder(root.left, res); res.add(root.val); inord ...
数据结构与算法·广义表与非线性结构的树
广义表线性表中每个元素的属性是相同，广义表作为被拓展的线性表，每个元素可以是原子，也可以是另一个线性表。 表头第一个元素 表尾除了表头以外的其他元素组成的子表 深度广义表展开后的括号重数 长度最外层元素个数 树 节点的“度”节点拥有的子树数目 森林n个不相交的树 二叉树的基本性质 二叉树第i层至多有2**（i-1）个节点 深度为k的二叉树至多有2**k-1个节点 叶子树为n0,度为2的节点数为n2,则n0=n2+1
字符串匹配——KMP算法
题目有两个字符串，要求确定较短字符串在较长字符串中的位置。 暴力匹配 使用两层循环，一旦不匹配就将子串后移一位，时间复杂度为O(mn) KMP算法NEXT[]数组 构建next数组1234567891011121314private void getNext(String p, int next[]) { int len = p.length(); int right = 0; int left = -1; next[0] = -1; while (right < len - 1) { if (left == -1 || p.charAt(right) == p.charAt(left)) { right++; left++; next[right] = left; } else left = next[left]; }} 匹配过程123456789101112131 ...
数据结构与算法·串，数组
串0个或多个任意字符组成的有限序列称为串 子串串中任意个连续的字符称为该串的子串（包括空串） 子串位置子串第一个字符在父串中的位置 空格串由空格字符组成的串 串的链式存储结构由于串的单个字符占用空间小，所以一个节点只存储一个字符的话，存储密度太低，故而一个节点存储多个字符 串的匹配-KMP算法BF算法，是指经典的循环遍历方法，复杂度为O(n*m) KMP算法是一种牺牲空间来加快速度的算法 https://zhuanlan.zhihu.com/p/83334559这篇文章讲的很清楚，有时间整理一下 简单来说，kmp算法先构建出一份图谱来确定不同状态前进或者回退，以及回退多少步。 数组二维数组数组中套娃数组，形成二维数组。 二维数组的逻辑结构 线性结构：每个元素是定长的数组 非线性结构：每个元素既在行表中，又在列表中。 二维数组的存储结构以行序为主序a[i][j]的位置在LOC(i,j)=LOC(0,0)+(n*i+j)*L 矩阵的存储常规存储：存储为二维数组，不适合稀疏矩阵，相同值过多的矩阵 压缩存储：对数据有规律的矩阵，可以针对特性，进行压缩存储
SpringBoot初试
数据库配置首先建表： 12345678910111213CREATE TABLE `user` ( `id` int(11) NOT NULL AUTO_INCREMENT COMMENT 'ID', `email` varchar(255) NOT NULL COMMENT '邮箱', `password` varchar(255) NOT NULL COMMENT '密码', `username` varchar(255) NOT NULL COMMENT '姓名', PRIMARY KEY (`id`), UNIQUE KEY `email` (`email`) USING BTREE) ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=utf8;INSERT INTO `user` VALUES ('1', '1@qq.com', '123456', '张三');INSERT ...
数据结构与算法·其八
队列一端插入，一端删除 线性表中表尾插入，表头删除 队列的顺序表结构存储一个头指针front，一个尾指针rear，表长度Length。 缺点是在入队出队的过程中，头尾指针均会向表尾移动导致最终发生溢出（rear==MaxQSize） 真假溢出真溢出是指顺序表完全占满， 假溢出指顺序表仍有空位(fromt!=0)，但是rear==MaxQSize 解决假溢出 将所有元素向表头移动（浪费时间） 将存储空间头尾逻辑上连接在一起，变成循环表（具体实现使用模运算） ps:模运算有某种“循环”的意义。 队列的链表结构与顺序表结构相比，没有假溢出的问题，其他操作类似，不再赘述。