好好刷题吧
if(treeArray[i] != Integer.MIN_VALUE){ if(i2+1 >= P || i2+2>=P){ //是叶子结点 sum+=helper(treeArray,i); } if(treeArray[i*2+1] == Integer.MIN_VALUE){ // 是叶子节点 sum+=helper(treeArray,i); } }
第一个if的意思是：如果当前位置的索引为i， 那么左子节点的索引为i2+1，右子节点的索引为i2+2 如果左子节点和右子节点的索引超过treeArray的长度，表明当前索引i在最后一行，则一定是叶子结点
第二个if的意思是：如果满足了第一个if，也就是说当前的索引i不在最后一行，如果它的左子节点为空，那么一定是叶子节点
// 根据叶子节点求出根节点到该叶子结点的路径长度
static int helper(int[] treeArray,int index){
// 是根节点
if(index == 0){
return treeArray[index];
}
if(index %2==1){
// 是左节点
return treeArray[index]+helper(treeArray,(index-1)/2);
}else{
// 是右节点
return treeArray[index]+helper(treeArray,(index-2)/2);
}
}
叶子节点的路径长度等于其父节点的路径长度加自己的值
空集合也是树，称为空树。空树中没有结点。 结点的度：一个结点含有的子结点的个数称为该结点的度； 叶结点或终端结点：度为0的结点称为叶结点； 非终端结点或分支结点：度不为0的结点； 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 兄弟结点：具有相同父结点的结点互称为兄弟结点； 树的度：一棵树中，最大的结点的度称为树的度； 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推； 树的高度或深度：树中结点的最大层次； 堂兄弟结点：双亲在同一层的结点互为堂兄弟； 结点的祖先：从根到该结点所经分支上的所有结点； 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。 森林：由m（m>=0）棵互不相交的树的集合称为森林；
二叉树索引和其左右叶子节点的关系，，根节点K,左节点2K+1,右节点2K+2
java的标准输入，使用Scanner，一行的输入使用nextline.
public class Test { public static void main(String [] args) { Scanner in = new Scanner(System.in); System.out.print("Input you name:"); String a = in.nextLine(); System.out.println("name = " + a); a = in.nextLine(); // read until find the \n System.out.println(a); } }
str.toString.replace（）函数的使用
public class replace { static String replaceSpace(StringBuffer str){ return str.toString().replace(" ","%20"); } public static void main(String [] arg){ Scanner in =new Scanner(System.in); String a= in.nextLine(); System.out.println(a.toString().replace(" ","%10"));
StringBuffer b=new StringBuffer(a);
System.out.print(replaceSpace(b));
}
}
ArrayList.add(int index, value) // use add() method to add elements in the list arrlist.add(15); arrlist.add(22); arrlist.add(30); arrlist.add(40);
// adding element 25 at third position arrlist.add(2,25);
让我们来编译和运行上面的程序，这将产生以下结果：
Number = 15 Number = 22 Number = 25 Number = 30 Number = 40 java.util.ArrayList.add(int index, E elemen) 方法将指定的元素E在此列表中的指定位置。它改变了目前元素在该位置(如果有的话)和所有后续元素向右移动(将添加一个到其索引)。
为了达到这个目的，java在一个旧的的进程同步模型——监控器（Monitor）的基础上实现了一个巧妙的方案：监控器是一个控制机制，可以认为是一个很小的、只能容纳一个线程的盒子，一旦一个线程进入监控器，其它的线程必须等待，直到那个线程退出监控为止。通过这种方式，一个监控器可以保证共享资源在同一时刻只可被一个线程使用。这种方式称之为同步。（一旦一个线程进入一个实例的任何同步方法，别的线程将不能进入该同一实例的其它同步方法，但是该实例的非同步方法仍然能够被调用）
错误的理解：同步嘛，就是几个线程可以同时进行访问。
同步和多线程关系：没多线程环境就不需要同步;有多线程环境也不一定需要同步。
产生死锁的四个必要条件：
1、互斥条件：一个资源每次只能被一个进程使用。
2、请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
3、不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
4、循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
避免死锁 上面列出了死锁的四个必要条件，我们只要想办法破其中的任意一个或多个条件，就可以避免死锁发生，一般有以下几种方法：
1、按同一顺序访问对象。
2、避免事务中的用户交互。
3、保持事务简短并处于一个批处理中。
4、使用较低的隔离级别。
5、使用基于行版本控制的隔离级别。
6、使用绑定连接。
以上就是有关进程和线程的总结，有什么好的意见欢迎大家留言。
- 加载
加载，是指Java虚拟机查找字节流（查找.class文件），并且根据字节流创建java.lang.Class对象的过程。这个过程，将类的.class文件中的二进制数据读入内存，放在运行时区域的方法区内。然后在堆中创建java.lang.Class对象，用来封装类在方法区的数据结构。
类加载阶段：
（1）Java虚拟机将.class文件读入内存，并为之创建一个Class对象。
（2）任何类被使用时系统都会为其创建一个且仅有一个Class对象。
（3）这个Class对象描述了这个类创建出来的对象的所有信息，比如有哪些构造方法，都有哪些成员方法，都有哪些成员变量等。
- 链接
链接包括验证、准备以及解析三个阶段。
（1）验证阶段。主要的目的是确保被加载的类（.class文件的字节流）满足Java虚拟机规范，不会造成安全错误。
（2）准备阶段。负责为类的静态成员分配内存，并设置默认初始值。
（3）解析阶段。将类的二进制数据中的符号引用替换为直接引用
Synchronized 保证⽅法内部或代码块内部资源（数据）的互斥访问。即同⼀时间、由同⼀个 Monitor（监视锁） 监视的代码，最多只能有⼀个线程在访问。
- Lock Lock 也是 java.util.concurrent 包下的一个接口，定义了一系列的锁操作方法。Lock 接口主要有 ReentrantLock，ReentrantReadWriteLock.ReadLock，ReentrantReadWriteLock.WriteLock 实现类。与 Synchronized 不同是 Lock 提供了获取锁和释
什么是序列化，怎么序列化，为什么序列化，反序列化会遇到什么问题，如何解决。 答案
什么是序列化：在java中，把对象转换成字节序列的过程叫做序列化。 把字节序列转换成对象的过程叫做反序列化。 怎么序列化：在实现了Serializable接口的情况下，便可以序列化。 为什么要序列化： 1.为了我们在内存中的对象能够存储在硬盘文件或数据库需要序列化 2.为了对象在网络中通过套接字进行传输。 3.通过rmi传输对象时需要用到序列化 反序列化会遇到什么问题。 在我们实现了Serializable接口后，没有给serialVersionUID一个固定值。这时候会发生这种情况，当我们序列化之后，然后改变了类中的属性。然后再进行反序列化。这时候程序便会报错，原因在于我们序列化时候的serialVersionUID与我们反序列化时候的serialVersionUID不一致所导致的，这也是为什么我们在实现了Serializable接口后，不给serialVersionUID一个固定值，ide会给我们一个警告。因为我们没有给一个固定的值。系统会根据类的属性自动生成一个值，在我们改变了类中的属性后，这个值自然也会发生变化。
公平锁：当线程A获取访问该对象，获取到锁后，此时内部存在一个计数器num+1，其他线程想访问该对象，就会进行排队等待(等待队列最前一个线程处于待唤醒状态)，直到线程A释放锁(num = 0)，此时会唤醒处于待唤醒状态的线程进行获取锁的操作，一直循环。如果线程A再次尝试获取该对象锁是，会检查该对象锁释放已经被占用，如果被占用，会做一次是否为当前线程占用锁的判断，如果是内部计数器num+1，并且不需要进入等待队列，而是直接回去当前锁。
非公平锁：当线程A在释放锁后，等待对象的线程会进行资源竞争，竞争成功的线程将获取该锁，其他线程继续睡眠。
公平锁是严格的以FIFO的方式进行锁的竞争，但是非公平锁是无序的锁竞争，刚释放锁的线程很大程度上能比较快的获取到锁，队列中的线程只能等待，所以非公平锁可能会有“饥饿”的问题。但是重复的锁获取能减小线程之间的切换，而公平锁则是严格的线程切换，这样对操作系统的影响是比较大的，所以非公平锁的吞吐量是大于公平锁的，这也是为什么JDK将非公平锁作为默认的实现。
协程不是被操作系统内核所管理的，而是完全由程序所控制，也就是在用户态执行。这样带来的好处是性能大幅度的提升，因为不会像线程切换那样消耗资源。
协程不是进程也不是线程，而是一个特殊的函数，这个函数可以在某个地方挂起，并且可以重新在挂起处外继续运行。所以说，协程与进程、线程相比并不是一个维度的概念。
一个进程可以包含多个线程，一个线程也可以包含多个协程。简单来说，一个线程内可以由多个这样的特殊函数在运行，但是有一点必须明确的是，一个线程的多个协程的运行是串行的。如果是多核CPU，多个进程或一个进程内的多个线程是可以并行运行的，但是一个线程内协程却绝对是串行的，无论CPU有多少个核。毕竟协程虽然是一个特殊的函数，但仍然是一个函数。一个线程内可以运行多个函数，但这些函数都是串行运行的。当一个协程运行时，其它协程必须挂起。
进程、线程、协程的对比
协程既不是进程也不是线程，协程仅仅是一个特殊的函数，协程它进程和进程不是一个维度的。 一个进程可以包含多个线程，一个线程可以包含多个协程。 一个线程内的多个协程虽然可以切换，但是多个协程是串行执行的，只能在一个线程内运行，没法利用CPU多核能力。 协程与进程一样，切换是存在上下文切换问题的。
ava关键字final有“这是无法改变的”或者“终态的”含义，它可以修饰非抽象类、非抽象类成员方法和变量。
final类不能被继承，没有子类，final类中的方法默认是final的。
final方法不能被子类的方法覆盖，但可以被继承。
final成员变量表示常量，只能被赋值一次，赋值后值不再改变。
final不能用于修饰构造方法。
注意：父类的private成员方法是不能被子类方法覆盖的，因此private类型的方法默认是final类型的。 1、final类
final类不能被继承，因此final类的成员方法没有机会被覆盖，默认都是final的。在设计类时候，如果这个类不需要有子类，类的实现细节不允许改变，并且确信这个类不会载被扩展，那么就设计为final类。
2、final方法 如果一个类不允许其子类覆盖某个方法，则可以把这个方法声明为final方法。使用final方法的原因有二： ①把方法锁定，防止任何继承类修改它的意义和实现。 ②高效，编译器在遇到调用final方法时候会转入内嵌机制，大大提高执行效率。
例如：
阻塞型IO：最简单的一种IO模型，简单理解就是死等，即进程或线程一直等待莫格条件，不满足则一直等待。
非阻塞型IO：应用进程与内核交互，目的未达到之前会直接返回，然后不断轮询，不停的去问内核数据是否准备好？如果发现准备好了，那就把数据拷贝到用户空间中。应用进程通过 recvfrom 调用不停的去和内核交互，直到内核准备好数据。如果没有准备好，内 核会返回error，应用进程在得到error后，过一段时间再发送recvfrom请求。在两次发送请求的时间段，进程可以先做别的事情。
信号驱动IO：我们会发现非阻塞型IO方式一遍一遍的轮询不如等内核把数据准备好，然后通知进程，当进程收到该通知时，便开始把数据拷贝到用户空间中。 即应用进程预先向内核注册一个信号处理函数，然后用户进程返回，并不阻塞，当内核数据准备就绪时会发送一个信号给进程，用户进程便在信号处理函数中开始把数据拷贝到用户空间中
IO复用模型：顾名思义，即将多个进程I/0注册到同一管道上，这里管道会统一和内核交互。当管道中的某一个请求需要好的数据准备好之后，进程再把对应的数据拷贝到用户空间中。 I/O多路转接是多了一个Select函数，多个进程的IO可以注册到同一个Select中，用户调用该Select。Select会监听所有注册好的I/O，如果所有被监听的I/O需要的数据都没有准备好，Select调用进程会阻塞。当任意一个I/O所需要的数据准备好之后，Select调用就 会返回，然后进程再通过recvfrom来进行数据拷贝。但实际上，它并未向内核注册信号处理函数，所以它并不是非阻塞的。
Lock是一个接口，而synchronized是Java中的关键字，synchronized是内置的语言实现，synchronized是在JVM层面上实现的，不但可以通过一些监控工具监控synchronized的锁定，而且在代码执行时出现异常，JVM会自动释放锁定。
但是使用Lock则不行，lock是通过代码实现的，要保证锁定一定会被释放，就必须将 unLock()放到finally{} 中；
2. synchronized在发生异常时，会自动释放线程占有的锁，因此不会导致死锁现象发生；
而Lock在发生异常时，如果没有主动通过unLock()去释放锁，则很可能造成死锁现象，因此使用Lock时需要在finally块中释放锁
其实上面的四次挥手实质上就相当于是下列的对话：
-客户机：服务器，我想和你断开连接，你同意吗？（FIN=1）
-服务器：我同意（ACK=1）
（在此期间，服务器可能还会向客户机发送数据，但是客户机却不能再向服务器发送数据）
-服务器：客户机，我想要和你断开连接，你同意吗？（FIN=1）
-客户机：我同意。（ACK=1）
再等待2MSL时间后就真正断开了连接。
－客户机：服务器，我想要和你建立连接，你同意吗？（SYN＝１）
－服务器：客户机，我同意和你建立连接（ACK＝１）；我也想和你建立连接，你同意吗？（SYN＝１）
－客户机：服务器，我同意和你建立连接。（ACK＝１）
. 其实，在进行第二次握手时（即服务器向客户机进行应答时），可以看作时发了两次包，先回答客户机的服务请求（ACK＝１，ａｃｋ＝x+１），然后再向客户机发出请求（SYN＝１，ｓｅｑ＝ｙ）
【问题1】为什么连接的时候是三次握手，关闭的时候却是四次握手？
答：因为当Server端收到Client端的SYN连接请求报文后，可以直接发送SYN+ACK报文。其中ACK报文是用来应答的，SYN报文是用来同步的。但是关闭连接时，当Server端收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉Client端，"你发的FIN报文我收到了"。只有等到我Server端所有的报文都发送完了，我才能发送FIN报文，因此不能一起发送。故需要四步握手。
【问题2】为什么TIME_WAIT状态需要经过2MSL(最大报文段生存时间)才能返回到CLOSE状态？
答：虽然按道理，四个报文都发送完毕，我们可以直接进入CLOSE状态了，但是我们必须假象网络是不可靠的，有可以最后一个ACK丢失。所以TIME_WAIT状态就是用来重发可能丢失的ACK报文。在Client发送出最后的ACK回复，但该ACK可能丢失。Server如果没有收到ACK，将不断重复发送FIN片段。所以Client不能立即关闭，它必须确认Server接收到了该ACK。Client会在发送出ACK之后进入到TIME_WAIT状态。Client会设置一个计时器，等待2MSL的时间。如果在该时间内再次收到FIN，那么Client会重发ACK并再次等待2MSL。所谓的2MSL是两倍的MSL(Maximum Segment Lifetime)。MSL指一个片段在网络中最大的存活时间，2MSL就是一个发送和一个回复所需的最大时间。如果直到2MSL，Client都没有再次收到FIN，那么Client推断ACK已经被成功接收，则结束TCP连接。
【问题3】为什么不能用两次握手进行连接？
答：3次握手完成两个重要的功能，既要双方做好发送数据的准备工作(双方都知道彼此已准备好)，也要允许双方就初始序列号进行协商，这个序列号在握手过程中被发送和确认。
现在把三次握手改成仅需要两次握手，死锁是可能发生的。作为例子，考虑计算机S和C之间的通信，假定C给S发送一个连接请求分组，S收到了这个分组，并发 送了确认应答分组。按照两次握手的协定，S认为连接已经成功地建立了，可以开始发送数据分组。可是，C在S的应答分组在传输中被丢失的情况下，将不知道S 是否已准备好，不知道S建立什么样的序列号，C甚至怀疑S是否收到自己的连接请求分组。在这种情况下，C认为连接还未建立成功，将忽略S发来的任何数据分 组，只等待连接确认应答分组。而S在发出的分组超时后，重复发送同样的分组。这样就形成了死锁。
【问题4】如果已经建立了连接，但是客户端突然出现故障了怎么办？
TCP还设有一个保活计时器，显然，客户端如果出现故障，服务器不能一直等下去，白白浪费资源。服务器每收到一次客户端的请求后都会重新复位这个计时器，时间通常是设置为2小时，若两小时还没有收到客户端的任何数据，服务器就会发送一个探测报文段，以后每隔75秒钟发送一次。若一连发送10个探测报文仍然没反应，服务器就认为客户端出了故障，接着就关闭连接。
区别与联系：
1， 一个类只能继承一个父类，存在局限；一个类可以实现多个接口
2， 在实现Runable接口的时候调用Thread的Thread（Runnable run）或者Thread(Runnable run ,String name)构造方法创建进程时，使用同一个Runnable实例，如上程序中使用的都是rt，则建立的多线程的实例变量也是共享的；
但是通过继承Thread类是不能用一个实例建立多个线程；
故而实现Runnable接口适合于资源共享；
当然，继承Thread类也能够共享变量，能共享Thread类的static变量；
3， Runnable接口和Thread之间的联系：
public class Thread extends Object implements Runnable
可以看出Thread类也是Runnable接口的子类
重载和重写的区别有以下几点：
一、定义上的区别：
1、重载是指不同的函数使用相同的函数名，但是函数的参数个数或类型不同。调用的时候根据函数的参数来区别不同的函数。
2、覆盖（也叫重写）是指在派生类中重新对基类中的虚函数（注意是虚函数）重新实现。即函数名和参数都一样，只是函数的实现体不一样。
二、规则上的不同：
1、重载的规则：
①必须具有不同的参数列表。
②可以有不同的访问修饰符。
③可以抛出不同的异常。
2、重写方法的规则：
①参数列表必须完全与被重写的方法相同，否则不能称其为重写而是重载。
②返回的类型必须一直与被重写的方法的返回类型相同，否则不能称其为重写而是重载。
③访问修饰符的限制一定要大于被重写方法的访问修饰符。
④重写方法一定不能抛出新的检查异常或者比被重写方法申明更加宽泛的检查型异常。
三、类的关系上的区别：
重写是子类和父类之间的关系，是垂直关系；重载是同一个类中方法之间的关系，是水平关系
UDP TCP
是否连接 无连接 面向连接 是否可靠 不可靠传输，不使用流量控制和拥塞控制 可靠传输，使用流量控制和拥塞控制 连接对象个数 支持一对一，一对多，多对一和多对多交互通信 只能是一对一通信 传输方式 面向报文 面向字节流 首部开销 首部开销小，仅8字节 首部最小20字节，最大60字节 适用场景 适用于实时应用（IP电话、视频会议、直播等） 适用于要求可靠传输的应用，例如文件传输