题意

在一维数轴上给出 $m$ 个线段，每个线段都都有 $l,r,w$ 三个数据代表这个线段的左右端点和这个区间权值。 从中取出若干个不相交的线段(区间端点可以共用)，在覆盖满 $[1,n]$ 的情况下，取出的线段中 $权重的最大值]$ 最小能为多少？

Solution

$dp[i]$ 代表覆盖满 $[1,i]$ 最大权值最小为多少，然后按左端点从小到大枚举线段，就有 $dp[r_i]=min(dp[r_i],max(dp[l_i],w_i))$。

题意

给你两组点，其中第一组中有 $size1$ 个点，第二组中有 $size2$ 个点，且 $size1 >= size2$。

任意两点间的连接成本 $cost$ 由大小为 size1 x size2 矩阵给出，其中 $cost[i][j]$ 是第一组中的点 $i$ 和第二组中的点 $j$ 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

事物四个特性ACID

事务指的是满足 ACID 特性的一组操作，可以通过 Commit 提交一个事务，也可以使用 Rollback 进行回滚。

1. 原子性：事务操作要么要么全部成功，要么全部失败回滚，操作失败不能对数据库有任何影响。
2. 一致性：事务执行前后必须处于一致性。简单来说，A和B的钱加起来是1000，无论他们之间怎么转账，事务结束后他们的钱加起来还是1000。
3. 隔离性：多个并发事务要互相隔离，即不能互相干扰。
4. 持久性：事物一旦被提交，改变就是永久性的，即使系统故障也不会丢失事物的操作。

隔离级别

先举例说明并发操作数据库可能出现的问题：

1. 更新丢失
   丢失修改指一个事务的更新操作被另外一个事务的更新操作替换。一般在现实生活中常会遇到，例如：T1 和 T2 两个事务都对一个数据进行修改，T1 先修改并提交生效，T2 随后修改，T2 的修改覆盖了 T1 的修改。
2. 读脏数据
   读脏数据指在不同的事务下，当前事务可以读到另外事务未提交的数据。例如：T1 修改一个数据但未提交，T2 随后读取这个数据。如果 T1 撤销了这次修改，那么 T2 读取的数据是脏数据。
3. 不可重复读
   不可重复读指在一个事务内多次读取同一数据集合。在这一事务还未结束前，另一事务也访问了该同一数据集合并做了修改，由于第二个事务的修改，第一次事务的两次读取的数据可能不一致。例如：T2 读取一个数据，T1 对该数据做了修改。如果 T2 再次读取这个数据，此时读取的结果和第一次读取的结果不同。
4. 幻读，本质上也属于不可重复读的情况，T1 读取某个范围的数据，T2 在这个范围内插入新的数据，T1 再次读取这个范围的数据，此时读取的结果和和第一次读取的结果不同。

产生并发不一致性问题的主要原因是破坏了事务的隔离性，解决方法是通过并发控制来保证隔离性。并发控制可以通过封锁来实现，但是封锁操作需要用户自己控制，相当复杂。数据库管理系统提供了事务的隔离级别，让用户以一种更轻松的方式处理并发一致性问题。

隔离级别：

1. 未提交读（READ UNCOMMITTED）：事务中的修改，即使没有提交，对其它事务也是可见的。
2. 提交读（READ COMMITTED）：一个事务只能读取已经提交的事务所做的修改。换句话说，一个事务所做的修改在提交之前对其它事务是不可见的。
3. 可重复读（REPEATABLE READ）：保证在同一个事务中多次读取同一数据的结果是一样的。
4. 可串行化（SERIALIZABLE）：强制事务串行执行，这样多个事务互不干扰，不会出现并发一致性问题。该隔离级别需要加锁实现，因为要使用加锁机制保证同一时间只有一个事务执行，也就是保证事务串行执行。

隔离级别越高，越能保证数据的完整性和一致性，但是对并发性能的影响也越大。对于多数应用程序，可以优先考虑把数据库系统的隔离级别设为Read Committed。它能够避免脏读取，而且具有较好的并发性能。尽管它会导致不可重复读、幻读和第二类丢失更新这些并发问题，在可能出现这类问题的个别场合，可以由应用程序采用悲观锁或乐观锁来控制。大多数数据库的默认级别就是Read committed，比如Sql Server , Oracle。MySQL的默认隔离级别就是Repeatable read。

乐观锁悲观锁

数据库的隔离级别可以解决大多数问题，但是灵活度较差，为此又提出了悲观锁和乐观锁的概念。

悲观锁：对外界修改数据持保守态度。认为外界会修改数据。具有强烈的独占和排他特性。悲观锁的实现往往依靠数据库提供的锁机制。

• 共享锁：又称读锁，简称S锁。就是多个事务对于同一数据可以共享一把锁，但是只能读不能修改。
• 互斥锁：又称写锁，简称X锁。就是不能与其他锁并存，如果一个事务获取了一个数据行的互斥锁，其他事务就不能再获取该行的其他锁，包括共享锁和互斥锁，但是获取互斥锁的事务是可以对数据行读取和修改。

适合于写操作多的情况，为数据安全提供保障，但因为加锁也降低了效率，增加了产生死锁的机会，降低了并发性。

乐观锁：假设认为数据一般情况下不会造成冲突，在提交的时候才去判断是不是存在冲突。如果发现冲突了，则返回用户错误的信息，让用户决定如何去做。适合于读操作多的情况，较好的实现了并发性。
乐观锁的实现一般有两种方式：

• 使用版本号：为数据增加一个版本标识，一般是为数据库增加一个数字类型的version字段来实现。读取数据时，讲version一同取出，每更新一次，version加1。提交更新时，判断表当前version是否与第一次取出一致，否则认为是过期数据。
• 使用时间戳：增加一个字段，类型为时间戳，和第一种同理。

MySQL索引

Mysql索引原理
Mysql索引详解
主键索引和非主键索引

数据库索引是为了增加查询速度而对表字段附加的一种标识，可以认为是数据库的目录。

优点在于查询速度快，但增删改慢，因为要去同步维护索引文件。

1. 普通索引：加快数据查询速度，应该只为那些经常被查询的数据列创建索引。查找到满足条件的第一个记录后，一直查找到不满足的第一个记录为止。
2. 唯一索引：保证数据的唯一性，找到第一个满足条件的记录后就停止。
3. 主键索引：使用主键作为索引，叶子结点存放的是整行数据，又被称为聚簇索引，建议主键自增，这样每次插入时就只要插入到最后一个位置即可，就不需要调整树结构。
   非主键索引，叶子结点存放的是主键，通过非主键索引搜索到主键ID，然后再通过主键索引搜索数据。因此也被称为二级索引。
4. 联合索引：对表的多个列进行索引，与其它索引相比，键值数量大于1。
   最左匹配原则：在MySQL建立联合索引时会遵守最左前缀匹配原则，即最左优先，在检索数据时从联合索引的最左边开始匹配，遇到范围查询条件就停下来。Mysql会自动优化查询语句使得与索引排序顺序保持一致。因此，应该将最经常查询的字段放在左边。
   如 where a = 3 and b = 4 and c > 5 and d = 6，如果建立的是(a,b,c,d) 联合索引，则d是用不到索引的，如果建立的是(a,b,d,c)的话就都可以用到。
   使用联合索引可以减少开销，建一个等于多个，因为无需访问多个索引，因此减少了很多不必要的IO操作，提高了效率。

B树和B+树的区别：

• B树每个节点都存储了key和data值，B+树只有叶子结点才存储data值，其它结点都存储key值，因此一个结点可以存储更多key值
• B树不需要到叶子结点就可以找到对应数据，B+树必须到叶子结点才能找到，相对稳定
• B+树的叶子结点用链表维护起来，支持区间查询

索引使用的数据结构还有哈希索引，底层就是哈希表，只包含哈希值和指针，只支持等值比较查询，不能用于范围查询，因为哈希值是无序的。

InnoDB和MyISAM

1. MyISAM采用表级锁，InnoDB支持行级锁和表级锁,默认为行级锁。
2. MyISAM强调性能，执行速度更快，但不提供事务支持。InnoDB支持事务，回滚，崩溃修复和事务安全。
3. InnoDB支持外键。
4. InnoDB是聚簇索引，MylSAM是非聚簇索引。
5. 仅InnoDB支持MVCC，应对高并发事务，MVCC比加锁更高效。

聚簇索引：将数据存储与索引放到了一块，找到索引也就找到了数据
非聚簇索引：将数据存储于索引分开结构，索引结构的叶子节点指向了数据的对应行。

表级锁：粒度最大的锁，对整张表加锁，实现简单，资源消耗少，触发锁冲突概率最高，并发度最低。
行级锁：粒度最小的锁，只针对当前操作的行进行加锁，大大减少数据库操作的冲突，并发度高，但加锁的开销也很大。

数据库语句执行很慢，可能迟迟拿不到锁，或者是没有使用索引或者选错索引。

多版本并发控制MVCC

是一种实现并发控制的方法，用更好的方式去处理读写冲突。

当前读：想select lock in share mode，select for update；这些操作都是一种当前读，因为它读取的是记录的最新版本，还要保证其它并发事务不能修改当前记录，会对读取的记录进行加锁。

快照读：

概念

什么是常量

用final修饰的成员变量表示常量，值一旦给定就无法改变！

final修饰的变量有三种：静态变量、实例变量和局部变量，分别表示三种类型的常量。

Class文件中的常量池

在Class文件结构中，最头的4个字节用于存储魔数Magic Number，用于确定一个文件是否能被JVM接受，再接着4个字节用于存储版本号，前2个字节存储次版本号，后2个存储主版本号，再接着是用于存放常量的常量池，由于常量的数量是不固定的，所以常量池的入口放置一个U2类型的数据(constant_pool_count)存储常量池容量计数值。

CMake简介：

CMake是一种跨平台的开源项目管理工具，所做的事其实就是告诉编译器如何去编译链接源代码。与之相似的是直接编写makefile文件，但makefile最大的缺点就是不能跨平台，一旦更换环境就要重新编写，于是我们可以使用CMake编写CMakeLists文件来解决此问题。

检查是否安装CMake

首先检查是否安装CMake，在终端输入cmake —version来检查，若显示未安装，可以使用sudo apt-get install camke ( ubuntu)，或者brew install cmake (macos)，windows直接去官网下载，来安装CMake。

定义

定义一种算法，将每个算法都封装起来，并且使它们之间可以互换。是一种行为类模式。

举例

为了通俗易懂，我们拿各国的税率计算来举例子：

假设当前我们的程序只能支持计算中国和美国的税率：

什么是单例模式

单例模式，顾名思义，就是整个系统就只有一个实例存在。

特点

1. 单例类只能有一个实例。
2. 单例类必须自己创建自己的唯一实例。
3. 单例类必须给所有其他对象提供这一实例。

题目

给定一个 $m$ 个元素的集合，问 $1-n$ 中有多少个数能被集合中至少一个元素整除。$(n <= 1e9, m <= 20)$

Solution

容斥原理，二进制枚举集合的所有子集，求子集的 $lcm$，如果子集大小是奇数，则 $res += n / lcm$，否则 $res-= n / lcm$。

题目1

体积和价值可能为负数的01背包。

Solution

逆向思维，对于体积为负的物品，我们可以一开始就装进去，背包对应的进行扩容，物品的体积和价值也对应取反。这样在进行背包dp 的时候就代表移除这个物品，答案取最大值即可。

什么是语法糖

语法糖（Syntactic Sugar），也称糖衣语法，指在计算机语言中添加的某种语法，这种语法对语言的功能并没有影响，但是更方便程序员使用。简而言之，语法糖让程序更加简洁，有更高的可读性。

解语法糖

前面提到过，语法糖的存在主要是方便开发人员使用。但其实，Java虚拟机并不支持这些语法糖。这些语法糖在编译阶段就会被还原成简单的基础语法结构，这个过程就是解语法糖。说到编译，大家肯定都知道，Java语言中，javac命令可以将后缀名为.java的源文件编译为后缀名为.class的可以运行于Java虚拟机的字节码。如果你去看com.sun.tools.javac.main.JavaCompiler的源码，你会发现在compile()中有一个步骤就是调用desugar()，这个方法就是负责解语法糖的实现的。Java 中最常用的语法糖主要有泛型、变长参数、条件编译、自动拆装箱、内部类等。

糖块一： switch 支持 String 与枚举

从Java 7 开始，switch 开始支持 String。其实Java中的switch自身原本就支持基本类型。比如int、char等。对于int类型，直接进行数值的比较。对于char类型则是比较其 ascii 码。