给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
注意空字符串可被认为是有效字符串。
示例 1:1
2输入: "()"
输出: true
示例 2:1
2输入: "()[]{}"
输出: true
示例 3:1
2输入: "(]"
输出: false
示例 4:1
2输入: "([)]"
输出: false
示例 5:1
2输入: "{[]}"
输出: true
利用栈，遍历，左括号压入栈，遇到右括号则判断栈顶是否为对应左扩号，一致则pop出栈顶元素。注意，遍历完后还需要判断栈是否为空
1 | func isValid(s string) bool { |
常识点：英文“hash”,中文有翻译为哈希的，也有翻译成散列的。
哈希算法：将任意长度的二进制值串映射为固定长度二进制值串，这个映射规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。
我们常见的用于加密的哈希算法有
对于加密算法，以上四点有两点格外重要
知识扩展：鸽巢原理
哈希算法产生的哈希值是有固定长度的，如之前的MD5哈希值，是固定的128位二进制串，能表示的数据是有限的，最多能表示 2^128个数据。而如果我们要对2^128+1个数据求哈希值，则必然存在哈希相同的情况。一般情况下，哈希值越长的哈希算法，哈希冲突的概率也就越低。
越复杂，越难破解的哈希算法，需要的计算时间也越长。
例子：海量图库搜寻一张图是否存在。
将图片的二进制码选取头尾字节，MD5得到哈希值，作为图片的唯一标识。放入散列表(键是哈希值，值是图片的路径)，这样搜索的时间复杂度是O(1),找到图片后再对比二进制信息是否一致。
下载文件，如何知道文件是否被篡改过？种子文件里有文件的哈希值，下载完成后将文件用相同的哈希函数生成哈希值，如果与种子文件里的哈希值一致就说明未被篡改。
散列函数是设计散列表的一个关键，它直接决定了散列冲突的概率和散列表的性能。不过，相对于哈希函数的其他应用，散列函数对散列算法冲突的要求低很多。即便出现个别散列冲突，也可以通过开放寻址法或开链法解决。
不仅如此，散列函数对于散列计算得到的散列值，能够被反向解密也不关系。这里更加关注散列得到的值能否均匀分布，除此之外，散列算法的计算快慢，也影响散列表的性能。所以，散列函数用的散列算法一遍都比较简单，比较追求效率。
负载均衡的算法：加权、随机、加权轮询等。如果要实现一个会话粘滞的负载均衡算法，那么最简单的方案就是维护一个映射表（客户端id或会话id与服务器编号的映射关系），但这种方案有些弊端：
借助哈希算法，对客户端IP或会话ID进行哈希计算，将取得的哈希值与服务器列表大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这种方式来保证同一个IP过来的请求都路由到同一台服务器。
这种哈希取模算法，也存在因扩容、缩容导致路由不一致的问题。那么应该也需要记住一致性哈希算法的原理去处理。
个人觉得，处理这种session会话使用分布式缓存方案会比较好，服务器保持无状态。
通过哈希算法对处理的海量数据进行分片，多机分布式处理，可以突破单机资源的限制。
使用一致性哈希算法原理，解决分布式缓存系统扩容、缩容导致数据迁移的问题。（分布式缓存中，节点挂掉后，可以直接让这部分缓存失效即可，不必做数据迁移）
二叉搜索树（Binary Search Tree)也叫二叉查找树。
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
示例 1:1
2
3
4
5输入:
2
/ \
1 3
输出: true
示例 2：1
2
3
4
5
6
7
8
9输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
利用二叉搜索树中序遍历得到是一个升序数组的特点，使用一个全局变量记录前一个节点，递归与当前节点比较，如果都比当前节点小，那么就是一个二叉搜索树
1 | type TreeNode struct { |
多个进程竞争CPU的时候并没有真正运行，为什么还会导致系统负载的升高呢？CPU上下文切换就是罪魁祸首
Linux是个多任务操作系统，多个任务并发执行并不是同时执行，而是系统将CPU轮流分配给这些任务，造成多任务同时运行的错觉。
而每个任务运行前，CPU需要知道任务从哪里加载，又从哪里开始运行，也就是说，需要系统帮他设置好CPU寄存器和程序计数器，他们都是CPU在运行任何任务之前，必须的依赖环境，因此也被叫做CPU上下文。
CPU上下文切换，就是把前一个CPU的上下文（CPU寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指向的新位置，开始运行新的任务。
而这些保存起来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来，这样就能保证任务原来的状态不受影响，让任务看起来是连续运行的。
操作系统管理的这些“任务”到底是什么？
任务就只是进程或线程吗？其实不止，硬件通过触发信号，会导致中断处理程序的调用，这也是一种常见的任务。
所以，根据任务的不同，CPU上下文切换可以分为几个不同的场景：
Linux按照特权等级，把进程的运行空间分为内核空间和用户空间
系统调用过程中，发生了CPU上下文切换（CPU寄存器里原来用户态的指令，需要先保存起来。接着，为了执行内核态代码，CPU寄存器需要更新为内核态指令的新位置，最后才是跳转到内核态运行内核任务。而系统调用结束后，CPU寄存器需要回复原来保存的用户态，然后再切换到用户空间，继续运行。所以，一次系统调用发生了两次CPU上下文切换）
那么，进程上下文切换与系统调用又有什么区别呢？
进程是由内核来管理和调度的，进程的切换只能发生在内核态。所以，进程的上下文仅包括了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的状态。
因此，进程的上下文切换就比系统调用多了一步：在保存当前进程的内核状态和寄存器之前，需要先把该进程的虚拟内存、栈等保存下来；而加载了下一进程的内核态后，还需要刷新进程的虚拟内存和用户态。
进程上下文的频繁切换，导致CPU将大量的时间耗费在寄存器、内核栈以及虚拟内存等资源的保护和恢复上，进而大大缩短了真正运行进程的时间。
什么时候才会发生进程上下文切换？
进程切换时才需要切换进程上下文（即只有在进程调度时，才需要切换进程上下文）
Liunx为每个CPU都维护了一个就绪队列，将活跃进程（也就是正在运行和正在等待CPU的进程）按照优先级及等待CPU的时间排序，然后选择最需要CPU的进程，也就是优先级最高和等待CPU时间最长的进程来运行。
进程在什么时候才会被调度到CPU上运行？
线程与进程的最大区别在于：线程是调度的基本单位，进程是资源拥有的基本单位。所谓内核中的任务调度，实际调度的对象是线程；而进程给线程提供了虚拟内存、全局变量等资源。
因此，线程上下文的切换也就有以下两种情况：
为了快速响应硬件的事件，中断处理会打断进程的正常调度和执行，转而调用中断处理程序，响应设备事件。而在打断其他进程时，就需要将进程当前的状态保存下来，这样在中断结束后，进程仍然可已从原来的状态恢复运行。
跟进程_上下文不同，中断上下文切换并不涉及到进程的用户态。所以，即便中断过程打断了一个正处在用户态的进程，也不需要保存和恢复这个进程的虚拟内存、全局变量等用户态资源。中断上下文，其实只包括内核态中断服务程序执行所必需的状态，包括CPU寄存器、内核堆栈、硬件中断参数等。
对同一个CPU来说，中断处理比进程拥有更高的优先级，所以中断上下文切换并不会与进程上下文切换同时发生。同样道理，由于中断会打断正常进程的调度和执行，所以大部分中断处理程序都短小精悍，以便尽可能快的执行结束。
中断：中断是系统用来响应硬件设备请求的一种机制，它会打断进程的正常执行和调度，然后调用内核中的中断处理程序来响应设备的请求。
中断的形象化描述：取外卖场景
1.中断是一种异步的事件处理机制，能提高系统的并发处理能力
2.为了减少对正常进程运行进行影响，中断处理程序需要尽快运行
3.中断分为，上下两个部分
(1)上半部用来快速处理中断，在中断禁止模式下，主要处理跟硬件紧密相关的或时间敏感的工作
(2)下半部用来延迟处理上半部未完成的工作，通常以内核线程的方式运行。
小结:
实际上，上半部会打断CPU正在执行的任务，然后立即执行终端处理程序。而下半部分以内核线程的方式执行，并且每个CPU都对应一个软中断内核线程，名为“ksoftirq/cpu编号”。
软中断除了硬件设备中断处理程序的下半部分，还包括一些内核自定义的事件，如:内核调度RCU锁
4.proc文件系统是一种内核空间和用户空间进行通信的机制，可以用来查看内核的数据结构或者用来动态修改内核配置，如:
网卡接收到数据包后，会通过硬件中断的方式，通知内核有新的数据到了。这时，内核就会调用中断处理程序来响应它。
在这个案例中，上半部和下半部负责的工作：
磁盘是一个存储设备（切确的说是块设备），可以被划分为不同的磁盘分区。而在磁盘或者说磁盘分区上，还可以创建文件系统，并挂载到系统的某个目录中。这样，系统就可以通过这个挂载目录，来读写文件。
磁盘是存储数据的块设备，也是文件系统的载体。所以，文件系统其实还是需要通过磁盘来保证数据的持久化存储。
Linux中一切皆文件，可以通过相同的文件接口，来访问磁盘和文件（比如 open,read,write,close等）
在读写普通文件时，I/O请求会首先通过文件系统，然后有文件系统负责与磁盘进行交互。而在读写块设备时，会跳过文件系统，直接与磁盘交互，即所谓的“裸I/O”。
这两种读写方式使用的缓存自然不同。文件系统管理的缓存，其实就是Cache的一部分。而裸磁盘的缓存，用的是Buffer.
用ls -l命令查看 /dev 目录1
2
3
4
5
6//块设备文件
-Port
brw-r----- 1 root operator 1, 0 2 13 10:13 disk0
//字符设备文件
crw------- 1 root wheel 18, 1 3 25 10:28 afsc_type5
我们知道，使用varchar类型存储时，需要使用1或2个字节记录字符串的长度：如果列的最大长度小于或等于255字节，则只使用一个字节表示，否则使用两个字节。
假设以下描述使用的都是UTF-8编码，存入英文字符。
即varchar(255)使用了256个字节，而varchar(256)则使用了258个字节。
那么问题来了，我们在设计表的时候，如果不确定字段的最大长度，使用了变长字符串varchar类型，那么是不是不管三七二十一直接上varchar(255)呢（假设最大长度不超过255），按照之前的理论，varchar(10)和varchar(255)存储“hello”的空间开销都是一样的，即都是使用了5个字符的硬盘存储空间，但这个数据加载到内存的时候，就会使用固定大小的内存块来保存值。简单来说，就是两种方式在硬盘中存储空间开销并无二致，但在内存中就大有不同。
varchar(10)在内存中使用10个字符的内存空间，varchar(255)在内存中使用255个字符的内存空间。这对于排序或者临时表（需要通过内存操作来实现）作业会产生比较大的不利影响。
所以如果某些字段会涉及到文件排序或者基于磁盘的临时表时，分配VARCHAR数据类型时仍然不能够太过于慷慨。还是要评估实际需要的长度，然后选择一个最长的字段来设置字符长度。如果为了考虑冗余，可以留10%左右的字符长度。千万不能认为其为根据实际长度来分配存储空间，而随意的分配长度，或者说干脆使用最大的字符长度。
另一个问题：varchar的允许的最大字节长度是65535字节，那么varchar(?)这个？最大能是多少呢。
以上的结论是以UTF-8编码及全部存入英文字符为前提的理想状态，但实际上使用UTF-8时，varchar(?)到不了65532那么大，因为一个字符最大占用三个字节，MySQL默认存入以最大字节数来计算。
所以最大到达21844，21845*3=65535字节，虽然符合最大字节限制，但没有空间存放字符串长度的记录了。
查看数据库默认字符集1
2
3
4
5
6
7mysql> show variables like 'character_set_database';
+------------------------+-------+
| Variable_name | Value |
+------------------------+-------+
| character_set_database | utf8 |
+------------------------+-------+
1 row in set (0.01 sec)
将varchar设置为21844,创建成功1
2mysql> create table test_varchar(v1 varchar(21844));
Query OK, 0 rows affected (0.03 sec)
大于21844则报错1
2
3
4
5
6
7mysql> mysql> create table > create table test_varchar(v1 varchar(65535))' at line 1
mysql> create table test_varchar(v1 varchar(65535));
ERROR 1074 (42000): Column length too big for column 'v1' (max = 21845); use BLOB or TEXT instead
mysql> create table test_varchar(v1 varchar(21845));
ERROR 1118 (42000): Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes storage overhead, check the manual. You have to change some columns to TEXT or BLOBs
ssh 登陆时，遇到 host key verifycation failed 的情况1
2
3
4
5
6
7
8
9
10
11
12
13@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the ECDSA key sent by the remote host is
SHA256:MU0btYHPprmjRMfcs6mtciH407u1hCJzz71wG7EuUUE.
Please contact your system administrator.
Add correct host key in /Users/banshee/.ssh/known_hosts to get rid of this message.
Offending ECDSA key in /Users/banshee/.ssh/known_hosts:12
ECDSA host key for [xxx.xxx.xxx.xx]:xxxx has changed and you have requested strict checking.
Host key verification failed.
出现这种情况的原因是，第一次 SSH 连接服务器时，会生成一个公钥，存储在客户端的 known_ host 文件里。而我的服务器重装了系统，生成了新的公钥，而客户端known_hsot 里还保存着旧的公钥。所以会出现以上错误。
解决方式也很简单：
1 | ssh-keygen -R xx.xx.xx.xx:pp(IP:PORT) |
或者直接vim 进去删除服务器IP对应的记录。
再次连接，会出现接受服务器公钥的询问，输入 yes 即可。
我们在设计表时，根据要存储的数据，选择使用哪种数据类型来保存数据，那么，选择时有哪些经验可以参考或者原则可以遵循的呢？
为列选择数据类型时，第一部是确定合适的大类型：数字、字符串，时间等。这些都是很明确就能确定的，下一步就是要选择具体的数据类型了，这时就需要你对 Mysql 的数据类型有很清晰的认知，知道哪个才是最适合的。
例如：DATETIME 和 TIMESTAMP 列都可以存储相同类型的数据：时间和日期，精确到秒。那么，我们需要选择哪个呢？
这时，就需要看需求了，DATETIME 只使用了4个字节存储数据，而 TIMESTAMP 使用了8个字节，前者能表示的时间范围更小，而且受设置的时区所影响。TIMESTAMP 可表示范围:1970-01-01 00:00:00~2038-01-09 03:14:07，DATETIME 支持的范围更宽1000-01-01 00:00:00 ~ 9999-12-31 23:59:59。
还有，char 类型 和 varchar 类型都能存储字符串，那么，选择哪个比较合适呢？
varchar 类型用于存储可变成字符串，它仅使用必要的空间，比定长类型更节省空间。以下情况适合使用 varchar 类型：
char 类型是定长的：Mysql根据定义的长度分配空间，即使你并不需要用到那么多空间。所以，我们一般使用 char 类型来存储长度一般确定（或者说所有值都接近同一个长度）的数据。对于经常变更的数据， char 类型 也比 varchar更好，因为定长的 char 类型不容易产生碎片。
之前用Windows时买了个移动硬盘，换成MAC后插上硬盘发现只能读，不能写入。查了下都是说要购买软件来写入的，其实，不用花这个冤枉钱，用命令可以搞定。
首先在桌面新建 文件夹 Windows1
mkdir Windows
使用 diskutil list 命令查看硬盘列表，可以看到 在/dev/disk2 就是移动硬盘，而 disk2s1 就是ntfs格式的数据硬盘成员。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 diskutil list
/dev/disk0 (internal, physical):
#: TYPE NAME SIZE IDENTIFIER
0: GUID_partition_scheme *251.0 GB disk0
1: EFI EFI 209.7 MB disk0s1
2: Apple_APFS Container disk1 250.8 GB disk0s2
/dev/disk1 (synthesized):
#: TYPE NAME SIZE IDENTIFIER
0: APFS Container Scheme - +250.8 GB disk1
Physical Store disk0s2
1: APFS Volume Macintosh HD 89.5 GB disk1s1
2: APFS Volume Preboot 21.8 MB disk1s2
3: APFS Volume Recovery 509.8 MB disk1s3
4: APFS Volume VM 2.1 GB disk1s4
/dev/disk2 (external, physical):
#: TYPE NAME SIZE IDENTIFIER
0: GUID_partition_scheme *1.0 TB disk2
1: Microsoft Basic Data Elements 1.0 TB disk2s1
使用 sudo umount /dev/disk2s1 推出部分硬盘1
sudo umount /dev/disk2s1
然后再将硬盘挂载到桌面 Windows 文件夹
sudo mount_ntfs -o rw,nobrowse1
sudo mount_ntfs -o rw,nobrowse /dev/disk2s1 ~/Desktop/Windows
nobrowse 表示在 Finder 中不显示这个分区，不带上这个选项是挂载不成功的。