ONE NOTE

Rage, rage against the dying of the light.

Posted on In

路径

从书中一个节点到另一个节点之间的分支构成两个节点的路径

结点的路径长度

两节点间路径的分支

树的路径长度

从树根到每一个结点的路径之和

节点数目相等时，完全二叉树最路径长度最短

节点的带权路径长度

路径长度x权重

树的带权路径长度

所有结点的带权路径长度之和

哈夫曼树

带权路径长度最小的二叉树

哈夫曼树的构造方法

说人话就是从小到大，合并（搭建）哈夫曼树

需要注意的是，每次合并，都是选择权值最小的两个树（无论是否为单节点）

哈夫曼编码

构造不等长的前缀编码

Posted on In

树的存储结构

双亲表示法

在每个元素中分为数据域和双亲域，其中双亲域表明了该元素的父元素的位置

特点：找双亲容易，找孩子难。

孩子链表

把每个节点的孩子的指针组成一个链表

特点：找孩子容易，找双亲难

孩子兄弟表示法（二叉树表示法，二叉链表表示法）

树与二叉树的转换

树转二叉树

  • 在兄弟之间加线
  • 对每个结点，除了其左孩子，去除与孩子的联系

二叉树转树

  • 把每个左孩子的右孩子和右孩子的右孩子…沿着分支找到所有的右孩子，与双亲连起来
  • 抹去原二叉树中双亲和右孩子的连线

森林转二叉树

分别把每棵树转化为二叉树后，头节点连起来

二叉树转森林

将二叉树的根节点与所有沿着右分支的右孩子连线全部抹掉

Posted on In

顺序遍历二叉树

先序遍历

  • 访问根节点
  • 访问左子树
  • 访问右子树

递归以上过程

中序遍历

按照“左中右”的顺序访问

简单代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class 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);
        inorder(root.right, res);
    }
}

后序遍历

按照“左右中”的顺序遍历

三种方法比较

层次遍历二叉树

使用队列实现

每个根节点出队时，将他的孩子入队

线索二叉树

利用二叉树的空指针域：

  • 如果某节点左为空，则指向前驱
  • 如果某节点右为空，则指向后继

标志域说明有没有对应子节点

Posted on In

广义表

线性表中每个元素的属性是相同，广义表作为被拓展的线性表，每个元素可以是原子，也可以是另一个线性表。

表头

第一个元素

表尾

除了表头以外的其他元素组成的子表

深度

广义表展开后的括号重数

长度

最外层元素个数

树

节点的“度”

节点拥有的子树数目

森林

n个不相交的树

二叉树的基本性质

  • 二叉树第i层至多有2**（i-1）个节点
  • 深度为k的二叉树至多有2**k-1个节点
  • 叶子树为n0,度为2的节点数为n2,则n0=n2+1

Posted on In

题目

有两个字符串，要求确定较短字符串在较长字符串中的位置。

暴力匹配

使用两层循环，一旦不匹配就将子串后移一位，时间复杂度为O(mn)

KMP算法

NEXT[]数组

构建next数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private 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];
    }
}

匹配过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int strStr(String target, String pattern) {
    if (pattern.length() == 0)
        return 0;
    int t = 0;
    int p = 0;
    int[] next = new int[pattern.length()];
    getNext(pattern, next);
    while (t < target.length() && p < pattern.length()) {
        if (p == -1 || target.charAt(t) == pattern.charAt(p)) {
            t++;
            p++;
        } else {
            p = next[p];
        }
        if (p == pattern.length())
            return t - p;
    }
    return -1;
}

Posted on In

串

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

矩阵的存储

**常规存储：**存储为二维数组，不适合稀疏矩阵，相同值过多的矩阵

**压缩存储：**对数据有规律的矩阵，可以针对特性，进行压缩存储

Posted on In

数据库配置

首先建表：

1
2
3
4
5
6
7
8
9
10
11
12
13
CREATE 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 INTO `user` VALUES ('2', '2@qq.com', '234567', '李四');
INSERT INTO `user` VALUES ('3', '3@qq.com', '345678', '王五');

主程序：

1
2
3
4
5
6
7
8
9
10
11
/**
 * 主程序类
 *
//  * @SpringBootApplication：这是一个SpringBoot应用
 */
@SpringBootApplication
public class MainApplication {
   public static void main(String[] args) {
      SpringApplication.run(MainApplication.class, args);
   }
}

新建一个路由

1
2
3
4
5
6
7
8
9
10
11
12
// @ResponseBody
// @Controller

// 这个注解集成了以上两个
@RestController
public class HelloController {
   @ResponseBody
   @RequestMapping("/hello")
   public String Handle01() {
      return "hello,spring boot";
   }
}

然后运行主程序，应用就运行起来了，在浏览器输入localhost:8080/hello，就能看到消息了。

体会

springboot相比ssm，少了很多配置，使用默认配置来简化开发。

使用父项目来引入依赖(几乎是开发中所有会用到的依赖)，项目不需要自己引入依赖了。

对父项目的依赖版本不满意，可以自己在pom.xml修改

1
2
3
4
<!-- 也可以自己修改版本 -->
<properties>
  <mysql.version>5.1.43</mysql.version>
</properties>

集成了tomcat环境，可以打包成一个完整的项目直接运行，不需要额外配置服务器。