多数元素

多数元素

解题思路

1. 以空间换时间，用哈希表来记录元素出现的次数
2. 摩尔投票法，因为多数元素是指出现次数大于一半的元素，因此多数元素的个数 - 其他元素的个数 >= 1，相当于每个多数元素和其他元素两两抵消，最后至少剩余一个多数元素

索引概述

索引是用于MySQL高效获取数据的数据结构，用于快速查找

优点

• 提高数据检索效率，降低磁盘IO
• 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性
• 在实现数据的参考完整性方面，可以加速表和表之间的连接
• 可以减少查询中分组和排序的时间

缺点：

• 创建和维护索引需要耗费时间，且随着数据量的增加，所耗费的时间也会增加
• 索引需要占用磁盘空间
• 虽然索引提高了查询速度，但会同时降低更新表的速度。当对表进行增删改数据的时候，索引也需要动态的维护（保持数据的有序性）

如果需要频繁的更新表，最好的方法就是，先删除索引，更新完数据后，最后再创建索引。

逻辑架构

概述

MySQL逻辑架构分为3层

• 连接层
  • Connection Pool：提供多个与客户端进行连接的线程
• 服务层
  • SQL Interface：接收SQL命令，返回查询结果
  • Parser：对SQL语句进行语法解析、语义解析，生成语法树
  • Optimizer：对解析结果进行优化，生成一个执行计划
  • Caches & Buffers：查询缓存，以key-value的方式缓存查询语句和结构
• 引擎层
  • Storage Engines：负责MySQL中数据的存储和提取，与底层文件系统进行交互

各级别的字符集

MySQL有4个级别的字符集：

• 服务器级别
• 数据库级别
• 表级别
• 列级别

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 查询字符集
show variables like '%character%';
+--------------------------+-------------------------------------------+
| Variable_name            | Value                                     |
+--------------------------+-------------------------------------------+
| character_set_client     | gbk                                       |
| character_set_connection | gbk                                       |
| character_set_database   | utf8mb4                                   |
| character_set_filesystem | binary                                    |
| character_set_results    | gbk                                       |
| character_set_server     | utf8mb4                                   |
| character_set_system     | utf8mb3                                   |
| character_sets_dir       | D:\MySQL\MySQL Server 8.0\share\charsets\ |
+--------------------------+-------------------------------------------+

• character_set_server：服务器级别的字符集
• character_set_database：当前数据库的字符集
• character_set_client：服务器解码请求时使用的字符集
• character_set_connection：服务器处理请求时会把请求字符串从character_set_client转为character_set_connection
• character_set_results：服务器向客户端返回数据时使用的字符集

视图概述

视图，一个或者多个数据表里的数据的逻辑显示，视图并不存储数据

• 视图是一种虚拟表，本身是不含有数据的
  • 视图可以看作是存储起来的SELECT语句
• 视图建立在已有表的基础上，视图依赖建立的这些表称为基表

约束( constraint ) 概述

约束是对表中字段的限制

数据完整性

为了保证数据完整性，SQL规范以约束的方式对表数据进行额外的条件限制。从以下四个方面考虑：

• 实体完整性：同一个表中，不存在两条完全相同无法区分的记录
• 域完整性：字段的取值范围，如年龄1-150
• 引用完整性：员工表中的员工所在部门，可以在部门表中找到该部门
• 用户自定义完整性：用户名唯一、密码不为空等

求根节点到叶节点数字之和

求根节点到叶节点数字之和

解题思路

在二叉树的后序遍历算法中，访问一个节点时，栈中保存的是其所有的祖先。可以根据二叉树的后序遍历算法，当访问到叶子节点时，栈中保存的就是从根节点到叶子节点的所有数字，将栈中节点转换为数字，加入到sum中。后序遍历结束后，即可得到从根节点到叶节点生成的所有数字之和sum

解题代码

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    stack := make([]*TreeNode, 0)   // 栈
    cur := root // 当前遍历节点
    var pre *TreeNode   // 上一个遍历过的节点
    var sum int // 数字之和

    for len(stack) >0 || cur != nil {
        for cur != nil {
            // 入栈
            stack = append(stack, cur)
            // 进入左子树
            cur = cur.Left
        }
        if len(stack) > 0 {
            cur = stack[len(stack)-1]
            if cur.Right == nil || pre == cur.Right {
                // 若栈顶节点无右子树，或者右子树刚刚访问过，则访问栈顶节点
                if cur.Left == nil && cur.Right == nil {
                    // 是叶子节点
                    // 计算数字之和
                    sum = sum + stackToInt(stack)
                }
                pre = cur   // 记录上一次访问的节点
                // 栈顶元素访问完成，弹出栈顶
                stack = stack[:len(stack)-1]
                cur = nil
            } else {
                // 否则进入右子树
                cur = cur.Right
            }
        }
    }

    return sum
}

func stackToInt(stack []*TreeNode) int {
    // 将栈中节点转换为数字
    var res int
    for i := 0; i < len(stack); i++ {
        res = res*10 + stack[i].Val
    }

    return res
}

整数类型

类型介绍

整数类型一共有 5 种，包括 TINYINT、SMALLINT、MEDIUMINT、INT（INTEGER）和 BIGINT

最小栈

最小栈

解题思路

利用一个辅助栈，用来记录当前已压栈元素中的最小元素。在进行压栈操作时，不仅更新数据栈，还要更新辅助栈。其中，辅助栈的更新策略：

• 如果当前压栈元素小于辅助栈的栈顶元素，则将当前压栈元素压入辅助栈
• 否则，将辅助栈的栈顶元素再一次压入辅助栈中

插入数据

VALUES

• 没有指明添加字段，一定按照声明字段的先后顺序添加

1
2

INSERT INTO emp1
VALUES (1, 'Tom', '2000.12.21', 3400);

• 指明要添加的字段

1
2

INSERT INTO emp1 (id, hire_date, salary, `name`)
VALUES (2, '1999-09-09', 4000, 'Jerry');

• 一次添加多个记录

1
2
3
4

INSERT INTO emp1 (id, hire_date, salary, `name`)
VALUES
(3, '1999-06-17', 8000, 'Dawn'),
(4, '1999-05-02', 7000, 'Rain');