五分之一过去了，还有两天就美团面试了，自己还是学的一团糟，感觉要当炮灰了😥😥
今天还是继续学动态规划继续刷面经
查一个不会的问题发现一个另不会的问题，然后又去查又发现一个，开始套娃：然后就不知道哪个是哪个了，我人裂开。。。
算法题：
1.颜色分类（力扣每日一题）：双指针，一次遍历，遇到1交换至nums[p],遇到0交换到nums[q]，但是遇到0交换时可能将之前交换过来的1又交换出去了，所以再将交换出去的和nums[p]交换一次；
做完每日一题又找了几个常考的动态规划题看了看
2.爬楼梯（这个还算比较简单的了）：dp[i] = dp[i - 1] + dp[i - 2]; base:dp[0] = 1;dp[2] = 2;
3.剪绳子：
1、数学算法，根据公式推导出极大值点为e，最接近e的整数是2或3，判断出3更优；在以3为长度划分的情况下，最后一段可能剩下1或者2的两种情况，若剩下的是2则直接保留，若剩下的是1则和前一段3重新划分为2和2；
2、动态规划：长度为i的绳子可以考虑分成j和i - j，
dp[i] = max(i-j * j,j * dp[i - j])，遍历j的所有取值，每个取值的dp[i]都要记录所以最终的公式为dp[i] = max(dp[i],(i - j) * j,j*dp[i - j]);
1、数学算法，根据公式推导出极大值点为e，最接近e的整数是2或3，判断出3更优；在以3为长度划分的情况下，最后一段可能剩下1或者2的两种情况，若剩下的是2则直接保留，若剩下的是1则和前一段3重新划分为2和2；
2、动态规划：长度为i的绳子可以考虑分成j和i - j，
dp[i] = max(i-j * j,j * dp[i - j])，遍历j的所有取值，每个取值的dp[i]都要记录所以最终的公式为dp[i] = max(dp[i],(i - j) * j,j*dp[i - j]);
4.分割等和子集：（0-1背包问题）
题意可以理解为从数组中挑出一些数字的组合使组合的和为数组总和的一半；dp[i][j]表示从[0,i]这个子区间内挑选组合是否可以等于j，如果可以为true，不可以则为false；转移方程的思路有点类似于递推回溯，分为选取当前值和不选两种情况，如果选取了当前值，那么dp[i][j] = dp[i - 1][j - nums[i]]，如果没选当前值则dp[i][j] = dp[i - 1][j]，还有一种情况是nums[i] = j，那么dp[i][j]直接可以为true；
特别有几个需要注意的地方：
1、dp数组是length行targer+1列的，target+1是因为要考虑target为0的情况（虽然我也没看懂为什么要考虑0的情况）；
2、如果数组总和不是偶数的话结果是一定无法成立的
题意可以理解为从数组中挑出一些数字的组合使组合的和为数组总和的一半；dp[i][j]表示从[0,i]这个子区间内挑选组合是否可以等于j，如果可以为true，不可以则为false；转移方程的思路有点类似于递推回溯，分为选取当前值和不选两种情况，如果选取了当前值，那么dp[i][j] = dp[i - 1][j - nums[i]]，如果没选当前值则dp[i][j] = dp[i - 1][j]，还有一种情况是nums[i] = j，那么dp[i][j]直接可以为true；
特别有几个需要注意的地方：
1、dp数组是length行targer+1列的，target+1是因为要考虑target为0的情况（虽然我也没看懂为什么要考虑0的情况）；
2、如果数组总和不是偶数的话结果是一定无法成立的
（这是我查到的一些经典的题目，可以全部做一遍） 后面看了看一个叫做背包九讲的帖子，是力扣的题解里推荐去看的，结果看了以后发现光是背包问题就有这么多中情况，太难了，一头包
面试题：
1.数据库索引：这次是模拟假如自己在真正的面试，该如何组织语言，结果就是一塌糊涂，感觉自己都懂，但是就是说不出来，又重新看了一会练了练怎样讲出来；
思路：什么是索引-索引的数据结构-B+树对比hash和B树的优势-Myisam和Innodb索引的区别-使用索引的场景
2.最左匹配原则：有的面试会问到具体的例子判断是否可以使用索引，尤其是联合索引的情况；
最左优先，以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停止匹配。
3.本地方法栈和虚拟机栈的区别：
虚拟机栈存放的是基本数据类型、对象的引用和实例的方法，具体的形式是栈帧，每调用一个方法就会创建一个栈帧，栈帧存储局部变量表、操作数栈、动态链接，方法出口等信息；
而本地方法栈负责执行本地方法（Native method），一般是非Java语言的底层方法，比如C语言编写的方法；
4.老年代区域除了老年代对象还存放了大对象（字符串或数组超过了设定值的对象）以及survivor区放不下的对象；
5.老年代的标记-清除是如何标记的，遍历时的起点和终点分别是什么：
标记：遍历所有的GC Roots，然后将所有的GC Roots可达的对象标记为存活的对象（下文mark=1已标记，mark=0未标记）
清除：清除的过程将遍历所有堆中的对象，将没有标记的对象（mark=0）全部清除掉
总结：在程序运行过程中，当可用内存被消耗待尽的时候，GC线程就会被处罚并将程序暂停，随后将GC Roots可达的对象标记为1，最后将堆中所有没有标记为1的对象全部清除掉，恢复程序运行，GC Roots可达的对象标记重新置为0；
清除：清除的过程将遍历所有堆中的对象，将没有标记的对象（mark=0）全部清除掉
总结：在程序运行过程中，当可用内存被消耗待尽的时候，GC线程就会被处罚并将程序暂停，随后将GC Roots可达的对象标记为1，最后将堆中所有没有标记为1的对象全部清除掉，恢复程序运行，GC Roots可达的对象标记重新置为0；
起点和终点没查到，只知道是遍历堆。。。
6.如何理解永久代和方法区：
永久代是HotSpot的概念，方法区是Java虚拟机规范中的定义，是一种规范，而永久代是一种实现，物理上是堆的一部分，和年轻代老年代是连续的，一个是标准一个是实现。其他的虚拟机实现并没有永久代这一说法。在1.7之前在(JDK1.2 ~ JDK6)的实现中，HotSpot 使用永久代实现方法区，HotSpot 使用 GC分代来实现方法区内存回收；1.8中永久代被元空间所代替，元空间是本地内存，存储类的元信息，静态变量和常量池等并入堆中，相当于永久代的数据被分到了堆和元空间中。
7.如何理解常量池：
常量池分两种：静态常量池和运行时常量池，每个类在编译之后都会生成class文件，而class文件中就包含有静态常量池静态常量池编译完成之后就会保存再class文件中，当class文件中类被加载到内存中的时候，静态常量池中的常量最终都会存放到运行时常量池中，我们最终使用的都是运行时常量池的常量。在JDK6.0及之前版本，字符串常量池是放在Perm Gen区(也就是方法区)中；在JDK7.0版本，字符串常量池被移到了堆中了，JDK8中又被移到了元空间中，它由一个StringTable类实现的，它是一个Hash表。这个哈希表在每个HotSpot虚拟机的实例只有一份，被所有的类共享。字符串常量由一个一个字符组成，并且相同字符串只保留一份。
8.可见性（Volatile）：Volatile保证两件事：
1、 线程1工作内存中的变量更新会强制立即写入到主内存；
2、 线程2工作内存中的变量会强制立即失效，这使得线程2必须去主内存中获取最新的变量值。
所以这就理解了Volatile保证了变量的可见性，因为线程1对变量的修改能第一时间让线程2可见。
1、 线程1工作内存中的变量更新会强制立即写入到主内存；
2、 线程2工作内存中的变量会强制立即失效，这使得线程2必须去主内存中获取最新的变量值。
所以这就理解了Volatile保证了变量的可见性，因为线程1对变量的修改能第一时间让线程2可见。
9.sleep和wait的区别：主要是有个CPU时间片不确定，两者在调用时都会让出CPU时间片（有争议好像，暂且先这样记着吧）；
10.IP地址和MAC地址：
MAC地址用于在网络中唯一标示一个网卡，一台设备若有一或多个网卡，则每个网卡都需要并会有一个唯一的MAC地址。
IP地址是IP协议提供的一种统一的地址格式，它为互联网上的每一个网络和每一台主机分配一个逻辑地址，每个Internet包必须带有IP地址，每个Internet 服务提供商（ISP）必须向有关组织申请一组IP地址，然后一般是动态分配给其用户，一般让系统给自动分配IP地址。
IP地址是IP协议提供的一种统一的地址格式，它为互联网上的每一个网络和每一台主机分配一个逻辑地址，每个Internet包必须带有IP地址，每个Internet 服务提供商（ISP）必须向有关组织申请一组IP地址，然后一般是动态分配给其用户，一般让系统给自动分配IP地址。
11.乐观锁（CAS）和悲观锁（锁机制）：悲观锁其实是通过了排他锁来实现的，对某一资源加排他锁，自身可以进行增删改查，其他人无法进行任何操作；
而乐观锁则一般是通过版本控制和CAS机制来实现；
12.HashSet底层：底层也是一个HashMap，存放的元素作为Key存放，而Value存放的是一个Present的Object对象；
13.TreeSet底层：红黑树，还有一系列阿巴阿巴各种操作，下次再看下次再看。。。
14.想使类可按我们的想法去排序：实现java.lang.Comparable接口，并实现其compareTo()方法或实现java.util.Comparator接口，并实现compare()方法；
全部评论
(2) 回帖