本质上就是前序遍历的框架。前序数组的第一个是根节点，找到中序数组它的索引 （可用map降低时间复杂度），中序数组以它为中心，左边是左子树，右边是右子树。将大问题化成小问题，利用递归。 而指针可以在每轮递归中作为通信的工具。上一层递归告诉下一层“你该缩小范围找了”。left每一层递归返回给上一层的是刚刚遍历完的根节点的下一个，而right返回的是刚刚遍历完的（根节点当前位置 + 左子树的节点个数）的下一个。这跟前序数组的前序遍历性质有关，而我们又是基于前序数组来重构二叉树的。 class Solution { public TreeNode buildTree(int[] preorde...

TCP TCP基本认识 TCP是面向连接的、可靠的、基于字节流的传输层通信协议。 面向连接：一定是「一对一」才能连接，不能像 UDP 协议 可以一个主机同时向多个主机发送消息，也就是一对多是无法做到的； 可靠的：无论的网络链路中出现了怎样的链路变化，TCP 都可以保证一个报文一定能够到达接收端，因为有重传机制。 字节流：消息是「没有边界」的，所以无论我们消息有多大都可以进行传输。并且消息是「有序的」，当「前一个」消息没有收到的时候，即使它先收到了后面的字节已经收到，那么也不能扔给应用层去处理，同时对「重复」的报文会自动丢弃。 TCP的头格式 控制位： ACK：该位为 1 时，「确认应...

TopK问题，不管是求前K大/前K小/第K大/第K小等，都有下面四种解法： O(N)：用快排变形最最最高效解决TopK问题 O(NlogK)：大根堆（前K小）/小根堆（前K大） O(NlogK)：二叉搜索树 O(N): 对于数据范围有限的情况可以直接计数排序O(N)高效解决 我们上一道例题： 方法一 快排：时间复杂度为O(n) class Solution { public int[] getLeastNumbers(int[] arr, int k) { if(k == 0 || arr.length == 0){ return ne...

进程的状态、控制和上下文切换可以看https://wardseptember.gitee.io/mynotes/#/docs/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E8%BF%9B%E7%A8%8B%E5%92%8C%E7%BA%BF%E7%A8%8B?id=%e8%bf%9b%e7%a8%8b

内存及内存管理 为什么会有内存管理，因为每个进程都有一定的数据和指令；而CPU只跟内存打交道，内存虽然访问速度很快但是空间很少，而外存很大但是访问速度慢；所以就出现了==虚拟内存技术==，让内存能够不死板地动态存储超过它容量的程序。而怎么动态存储会更好就涉及到了==分段==和==分页==管理方式。 虚拟内存 要理解虚拟技术的思想前，必须先了解计算中著名的局部性原理。 时间局部性： 若程序中某条指令一旦执行，不久后该指令可能再次执行；又或者是数据再次被访问。这是因为程序中会存在大量的循环操作。 空间局部性：一旦程序访问了某个存储单元，不久后其附近的存储单元也将被访问。这是因为指令通常是顺...

假设链表一走到相同节点的距离为a,链表二为b，从相同节点到末尾的距离为c；我们可以让两个链表走相同的路，若走到相同节点，就返回。算法核心： a+b+c = b+c+c就算它们走完都没有相同节点，也不碍事，返回的都是null也是相等的。 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode p1 = pHead1; ListNode p2 = pHead2; while(p1 != p2){ p1 = (p1 ...

使用动态规划法，定义一个dp数组记录从第一个数字开始到当前数字的最大累加和。每当前一个累加和大于0时，进行dp[i]的更新。最后遍历dp数组，取最大的dp[i]返回。过程可以看注释： public int maxsumofSubarray (int[] arr) { // write code here int len = arr.length; int res = 0; //用tmp数组记录从0出发到当前数字能累加的最大数 int[] dp = new int[len]; //先初始化它 ...

单例模式详解 饿汉式 /** * 饿汉模式（静态变量） */ public class HungryMan { //构造器私有化 (防止 new ) private HungryMan(){} //类的内部创建对象 private final static HungryMan hungryMan = new HungryMan(); //对外暴露一个静态的公共方法 public static HungryMan getInstance(){ return hungryMan; } } /** * 饿汉模式（静态代...

装饰者模式 假设现在有一块蛋糕，加上奶油就是奶油蛋糕，再加上巧克力就是巧克力奶油蛋糕，再要是加上水果，就是巧克力水果奶油蛋糕，当然我们也可以做水果奶油蛋糕。这就是装饰的过程。 几大roles Componet (被装饰者接口/抽象类) 就是蛋糕的API ConcreteComponent （具体的被装饰者） 具体蛋糕 Decorator （装饰者接口/抽象类） 同样继承/实现被装饰者 装饰物 ConcreteDecorator （具体装饰者） 由奶油/巧克力/水果...来扮演 UML图： 优点 接口（API）的透明性 装饰物和装饰对象都继承了Component类，说明装饰...

代理模式 顾名思义，代理模式提供了一个“代理人”对象，当“本人”太忙时，有些工作可以交给代理人。好比如一个手机工厂，一开始它负责生产手机和卖手机，后来为了把人力充分利用到生产手机上，找了代理商来向客户卖手机。 几大roles Subject （目标接口/抽象类） RealSubject （“本人”） Proxy （“代理人”） Client （用户或主程序） UML图看清关系: 好处 能够在目标对象实现的基础上，扩展功能； 能实现业务的分工，可以将公共的操作交给代理人，减少代码冗余性。 在真正需要“本人”才能做的“重活时”再生成“本人”实例，使用代理人来提升速度。 有主要...

本文参考了几篇题解区大佬的文章，对以下做过的子串问题进行解析和总结。 找到字符串的最长无重复字符子串 方法一 滑动窗口法： 我们可以使用双指针模拟一个滑动窗口。 初始化窗口为 (left, right]。 所以left从-1开始。 窗口不断往右扩大。 根据题目的要求，即遇到有重复数字的，在窗口左侧缩小。 在每次滑动时，对窗口的大小进行比较，保留最大的长度。 代码实现： public int maxLength (int[] arr) { int res = 0, left = -1; //用来存放窗口存放过的数字 HashMa...

何时才能变强

观察者模式 在该模式中，当观察对象的状态发生变化时，会通知给观察者，观察者再对变化的状态进行处理。类似你叫了一个外卖，你的订单是被观察对象，而提供给用户看的第三方（美团、饿了么）就是观察者。 该模式中几大roles Subject （被观察对象） 订单这个家伙定义了注册观察者和删除观察者的方法，同时声明了“获取现在的状态”的方法。 ConcreteSubject （具体的观察对象）当自身状态发生改变时，会通知所有注册的观察者。 Observer （观察者）它定义了update方法负责接收来自Subject的状态变化的通知，然后进行处理。可以是抽象类，也可以是接口。 ConcreteOb...

责任链模式 为请求创建了一个接收者对象的链，可以对请求的发送者和接收者进行解耦。该模式中通常每个接收者都包含对另一个接收者的引用。如果一个对象不能处理该请求，那么它会把相同的请求传给下一个接收者，以此类推。属于行为型模式。 UML图： 举个栗子：学校OA系统的采购审批项目：需求是 1) 采购员采购教学器材2) 如果金额 小于等于5000, 由教学主任审批 （0<=x<=5000）3) 如果金额 小于等于10000, 由院长审批 (5000<x<=10000)4) 如果金额 小于等于30000, 由副校长审批 (10000<x<=30000)5) 如果金额 ...