Java中的静态代理与动态代理

发表于 2020-05-17 更新于 2020-05-27 分类于 Java
本文字数： 4k 阅读时长 ≈ 4 分钟

什么是代理模式

人话来讲就是由代理对象来执行目标对象的方法，且还可以在代理对象中增强目标对象方法的一种设计模式。类比生活，像是房产中介。代理模式存在的意义和一个架构设计原则息息相关 —— 开闭原则（对扩展开放，对修改关闭），即一种好的设计模式，都是在不修改原有形态的基础上扩展出新的功能。

为什么需要代理

代理模式的概念很容易理解，但是早期的我即使读懂了代理模式的概念，对为什么要使用代理模式，还是一头雾水。为什么我不直接调用目标对象的方法，非得要借助个代理对象呢？

1. 调用的目标对象在远程主机上，并不在你本地

类似中介就是房东出国了，联系不上，你只能跟我沟通。对应到我们程序设计的时候就是：客户端无法直接操作实际目标对象。为什么无法直接操作？一种情况是你需要调用的对象在另外一台机器上，你需要跨越网络才能访问，如果让你直接编码实现远程调用，你需要处理网络连接、处理打包、解包等等非常复杂的步骤，所以为了简化客户端的处理，我们使用代理模式，在客户端建立一个远程目标对象的代理，客户端就象调用本地对象一样调用该代理，再由代理去跟实际对象联系，对于客户端来说背后这个通信过程是透明的。

2. 你不想理会目标类繁杂的功能，只希望增加一些自己的行为进去

例如常见的例子就是 Spring AOP 实现日志功能，你不必关心目标类究竟如何繁杂，你只是想要在前后调用的时候打印一下日志，那么你就可以使用代理模式，通过 AOP 提供的切面进行编码实现，你通过代理模式达到了在目标对象的方法前后增加了一些自定义行为的目的。类似的例子还有权限校验。这样做的好处有很多，一方面你需要在意目标类的代码，二来你维护了目标类功能的单一性，而不是将日志或者权限校验的功能硬编码到目标类的方法中。

静态代理

静态代理非常简单，就是实现类和代理类均实现同样的接口，然后在代理类中通过构造器将接口或者实现类注入进来，然后就可以在代理类的方法实现中增加一些自己的逻辑。看个例子就懂了：

静态代理的例子

// 接口
public interface BuyHouse {
    void buyHosue();
}

// 实现类
public class BuyHouseImpl implements BuyHouse {
    @Override
    public void buyHosue() {
        System.out.println("HHHHH");
    }
}

// 代理类
public class BuyHouseProxy implements BuyHouse {
    
    private BuyHouse buyHouse;
    // 将接口引入
    public BuyHouseProxy(final BuyHouse buyHouse) {
        this.buyHouse = buyHouse;
    }

    @Override
    public void buyHosue() {
        // 增加一些自己的逻辑
        System.out.println("HHHHH");
        buyHouse.buyHosue();
        System.out.println("66666");

    }
}

静态代理的缺点

很明显，静态代理中，一个代理类只能对一个业务接口的实现类进行包装，如果有多个业务接口的话就要定义很多实现类和代理类才行。而且，如果代理类对业务方法的预处理、调用后操作都是一样的（比如：调用前输出提示、调用后自动关闭连接），则多个代理类就会有很多重复代码。这时我们可以定义这样一个代理类，它能代理所有实现类的方法调用：根据传进来的业务实现类和方法名进行具体调用。即动态代理模式。Java 中常见的有 JDK 动态代理和 CGLib 动态代理，前者只能代理接口，后者可以代理实现类。

JDK 动态代理

JDK 的动态代理使用到 Java reflect 包下的 Proxy 类和 InvocationHandler 接口。

public class DynamicProxyHandler implements InvocationHandler {

    private Object object;

    public DynamicProxyHandler(final Object object) {
        this.object = object;
    }

    @Override
    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
        System.out.println("HHHHH");
        Object result = method.invoke(object, args);
        System.out.println("66666");
        return result;
    }
}

public class DynamicProxyTest {
    public static void main(String[] args) {
        BuyHouse buyHouse = new BuyHouseImpl();
        BuyHouse proxyBuyHouse = (BuyHouse) Proxy.newProxyInstance(BuyHouse.class.getClassLoader(), new Class[]{BuyHouse.class}, new DynamicProxyHandler(buyHouse));
        proxyBuyHouse.buyHosue();
    }
}

DynamicProxyHandler 实现了 InvocationHandler 接口，并复写其 invoke 方法，我们可以看到 invoke 方法的参数是实现类和方法参数列表。测试类中通过 newProxyInstance 这个静态工厂方法创建了代理对象，代理对象的每个执行方法都会替换执行InvocationHandler 中的 invoke 方法。这个方法总共有3个参数：

ClassLoader loader用来指明生成代理对象使用哪个类装载器
Class<?>[] interfaces用来指明生成哪个对象的代理对象，通过接口指定，这就是为什么 JDK 动态代理必须要通过接口的方式
InvocationHandler 用来指明产生的这个代理对象要做什么事情。

newProxyInstance 内部本质上是根据反射机制生成了一个新类。

CGLib 动态代理

CGLib 是针对类来实现代理的，原理是对指定的实现类生成一个子类，并覆盖其中的方法实现代理。因为采用的是继承，所以不能对final 修饰的类进行代理。例子如下：

// 实现类，有没有实现接口无所谓
public class BookFacadeImpl {  
    public void addBook() {  
        System.out.println("新增图书...");  
    }  
}  

public class BookFacadeCglib implements MethodInterceptor {  
    // 业务类对象，供代理方法中进行真正的业务方法调用
    private Object target;
  
    // 相当于JDK动态代理中的绑定
    public Object getInstance(Object target) {  
        // 给业务对象赋值
        this.target = target;  
        // 创建加强器，用来创建动态代理类
        Enhancer enhancer = new Enhancer(); 
        // 为加强器指定要代理的业务类（即：为下面生成的代理类指定父类）
        enhancer.setSuperclass(this.target.getClass());  
        // 设置回调：对于代理类上所有方法的调用，都会调用CallBack，而Callback则需要实现intercept()方法进行拦
        enhancer.setCallback(this); 
       // 创建动态代理类对象并返回 
       return enhancer.create(); 
    }
    // 实现回调方法 
    public Object intercept(Object obj, Method method, Object[] args, MethodProxy proxy) 
    throws Throwable { 
        System.out.println("预处理——————");
        //调用业务类（父类中）的方法
        proxy.invokeSuper(obj, args); 
        System.out.println("调用后操作——————");
        return null; 
    } 
}

// 测试类
public static void main(String[] args) {      
    BookFacadeImpl bookFacade = new BookFacadeImpl()；
    BookFacadeCglib cglib = new BookFacadeCglib();  
    BookFacadeImpl bookCglib = (BookFacadeImpl)cglib.getInstance(bookFacade);  
    bookCglib.addBook(); 
}

参考资料

License

本文遵守创作共享 CC BY-NC-SA 3.0协议

UNIX下的I/O模型

发表于 2020-05-17 分类于 Linux
本文字数： 1.7k 阅读时长 ≈ 2 分钟

开篇

RPC 中很重要的部分就是网络通信，因此这篇叙述一下 Unix 下为解决不同 I/O 问题所设计的 I/O 模型。首先要说明的是，I/O 是个很宽泛的概念，常见的有网络 I/O、磁盘 I/O、内存 I/O 等。

在 Unix 系统下，不论是标准输入还是借助套接字接受网络输入，其实都会有两个步骤，很多文章都提到：

等待数据准备好（Waiting for the data to be ready）
从内核向进程复制数据（Copying the data from the kernel to the process）

这两个阶段涉及到用户空间和内核空间

用户空间和内核空间

对 32 位 OS 而言，它的寻址空间（虚拟存储空间）为 4G。OS 的核心是内核，可以访问底层硬件设备，为了保证用户进程不能直接操作内核从而保证内核的安全，OS 将虚拟空间划分为两部分，一部分为内核空间，一部分为用户空间。

内核空间中存放的是内核代码和数据，例如 Linux 的 OS 和驱动便运行在内核空间，可以操作底层硬件，如果从磁盘读取数据，那么数据会被先载入内核空间的缓冲区中；而进程的用户空间中存放的是用户程序的代码和数据，通常来讲就是应用程序常驻的区域。

因此整个 Linux 内部结构可以分为三部分，从最底层到最上层依次是：硬件、内核空间、用户空间。如下图：

二者间无法直接通信，必须通过系统调用，一般来说系统调用的成本很高。

内核态和用户态

当一个进程经过系统调用而陷入内核代码中执行时，称进程处于内核运行态，简称内核态
当进程在执行用户自己的代码时，则称其处于用户运行态，简称用户态

高性能的Server有什么特点

说完上面的之后，你可能疑惑这和 RPC 的通信设计有什么关系呢？其实正是由于这种内存空间的划分，所以 I/O 一般会在两个地方阻塞，一个是等待数据报到达时，一个是从内核空间拷贝到用户空间时，而阻塞多数情况下我们是无法接受的，因为其损耗性能，而高性能的 server 到底在关注什么？一句话总结：用尽可能少的系统开销处理尽可能多的连接请求。因此诞生了不同的 I/O 模型，它们的不同点总结起来就是对这两个阻塞阶段的处理方式不同

Unix 下的 I/O 模型

Unix 下存在五种 I/O 模型：

阻塞 I/O
非阻塞 I/O
I/O 复用（select和poll）
信号驱动 I/O（SIGIO）
异步 I/O

以下的例子，我们以 UDP 套接字中的 recvfrom 函数作为系统调用来说明I/O模型。recvfrom 函数类似于标准的 read 函数，它的作用是从指定的套接字中读取数据报。

1 、阻塞 I/O

可以看到阻塞 I/O 在两个步骤阶段都是阻塞的，等到数据报准备好和数据报从内核空间拷贝到用户空间之后，才会向用户侧的进程返回结果，此时用户侧的进程才能继续工作。

2 、非阻塞 I/O

非阻塞 I/O 的优化点在于第一阶段不是阻塞的，而是采取轮询的形式，如果数据报没有准备好，立刻返回一个错误 EWOULDBLOCK，此时用户侧进程不需要等待而是立刻得知此次询问的结果，然后进行重试直到数据报准备好再开始，但是再第二阶段拷贝数据报的时候依旧是阻塞的。

3、 I/O 复用

本质上 I/O 复用的优化点在于让内核来负责非阻塞 I/O 时用户侧进程进行的反复重试操作，当内核发现某个套接字的数据报已经就绪时就通知进程。但是这里细心的你会发现，有两个系统调用，select 和 revfrom，但是由于 I/O 复用可以处理多个连接，性能还是有提升。

4 、信号驱动 I/O

进程先创建一个信号处理 handler，然后内核立刻返回，进程可以去处理其他事情，等到数据报就绪，内核通过发送信号给之前的 handler 通知进程，然后进程在拷贝数据报期间阻塞。

5 、异步 I/O

调用 aio_read 函数发起读取操作时其实是告诉内核 “当整个I/O操作完成后通知我们”。该系统调用会立即返回，进程不会被阻塞。当 I/O 阶段两个步骤完成后，内核会产生一个信号通知应用进程对数据报进行处理。

跟信号驱动 I/O 相比是告知进程何时进行数据拷贝操作，而异步 I/O 则是通知进程何时整个 I/O 操作完毕。

参考资料

License

本文遵守创作共享 CC BY-NC-SA 3.0协议

原文链接

智力题-转载

发表于 2020-05-17 分类于逻辑思维
本文字数： 13k 阅读时长 ≈ 11 分钟

1.赛马找最快<腾讯高频>

2.砝码称轻重

3.药瓶毒白鼠<腾讯>

4.绳子两头烧

5.犯人猜颜色

6.猴子搬香蕉

7.高楼扔鸡蛋<谷歌>

8.轮流拿石子<头条>

9.蚂蚁走树枝

10.海盗分金币<不常见>

11.三个火枪手

12.囚犯拿豆子

13.学生猜生日<笔试高频>

1. 赛马找最快<腾讯高频题>

**
**

一般有这么几种问法：

25匹马5条跑道找最快的3匹马，需要跑几次？答案：7

64匹马8条跑道找最快的4匹马，需要跑几次？答案：11

25匹马5条跑道找最快的5匹马，需要跑几次？答案：最少8次最多9次

接下来我们看看详细解法：

25匹马5条跑道找最快的3匹马，需要跑几次？

将25匹马分成ABCDE5组，假设每组的排名就是A1>A2>A3>A4>A5,用边相连，这里比赛5次

第6次，每组的第一名进行比赛，可以找出最快的马，这里假设A1>B1>C1>D1>E1

D1，E1肯定进不了前3，直接排除掉

第7次，B1 C1 A2 B2 A3比赛，可以找出第二，第三名

所以最少比赛需要7次

64匹马8条跑道找最快的4匹马，需要跑几次？

第一步
全部马分为8组，每组8匹，每组各跑一次，然后淘汰掉每组的后四名，如下图（需要比赛8场）

第二步
取每组第一名进行一次比赛，然后淘汰最后四名所在组的所有马，如下图（需要比赛1场）

这个时候总冠军已经诞生，它就是A1，蓝域（它不需要比赛了），而其他可能跑得最快的三匹马只可能是下图中的黄域了（A2,A3,A4,B1,B2,B3,C1,C2,D1，共9匹马）

第三步
只要从上面的9匹马中找出跑得最快的三匹马就可以了，但是现在只要8个跑道，怎么办？那就随机选出8匹马进行一次比赛吧（需要比赛一场）

第四步
上面比赛完，选出了前三名，但是9匹马中还有一匹马没跑呢，它可能是一个潜力股啊，那就和前三名比一比吧，这四匹马比一场，选出前三名。最后加上总冠军，跑得最快的四匹马诞生了！！！（需要一场比赛）

最后，一共需要比赛的场次：8 + 1 + 1 + 1 = 11 场

来源：https://blog.csdn.net/u013829973/article/details/80787928

25匹马5条跑道找最快的5匹马，需要跑几次？

(1) 首先将25匹马分成5组，并分别进行5场比赛之后得到的名次排列如下：

A组： [A1 A2 A3 A4 A5]

B组： [B1 B2 B3 B4 B5]

C组： [C1 C2 C3 C4 C5]

D组： [D1 D2 D3 D4 D5]

E组： [E1 E2 E3 E4 E5]

其中，每个小组最快的马为[A1、B1、C1、D1、E1]。

(2) 将[A1、B1、C1、D1、E1]进行第6场，选出第1名的马，不妨设 A1>B1>C1>D1>E1. 此时第1名的马为A1。

(3) 将[A2、B1、C1、D1、E1]进行第7场，此时选择出来的必定是第2名的马，不妨假设为B1。因为这5匹马是除去A1之外每个小组当前最快的马。

(3) 进行第8场，选择[A2、B2、C1、D1、E1]角逐出第3名的马。

(4) 依次类推，第9，10场可以分别决出第4，5名的吗。

因此，依照这种竞标赛排序思想，需要10场比赛是一定可以取出前5名的。

仔细想一下，如果需要减少比赛场次，就一定需要在某一次比赛中同时决出2个名次，而且每一场比赛之后，有一些不可能进入前5名的马可以提前出局。 当然要做到这一点，就必须小心选择每一场比赛的马匹。我们在上面的方法基础上进一步思考这个问题，希望能够得到解决。

(1) 首先利用5场比赛角逐出每个小组的排名次序是绝对必要的。

(2) 第6场比赛选出第1名的马也是必不可少的。假如仍然是A1马(A1>B1>C1>D1>E1)。那么此时我们可以得到一个重要的结论：有一些马在前6场比赛之后就决定出局的命运了(下面粉色字体标志出局)。

A组： [A1 A2 A3 A4 A5]

B组： [B1 B2 B3 B4 B5 ]

C组： [C1 C2 C3 C4 C5 ]

D组： [D1 D2 D3 D4 D5 ]

E组： [E1 E2 E3 E4 E5 ]

(3) 第7场比赛是关键，能否同时决出第2，3名的马呢？我们首先做下分析：

在上面的方法中，第7场比赛[A2、B1、C1、D1、E1]是为了决定第2名的马。但是在第6场比赛中我们已经得到(B1>C1>D1>E1)，试问？有B1在的比赛，C1、D1、E1还有可能争夺第2名吗？当然不可能，也就是说第2名只能在A2、B1中出现。实际上只需要2条跑道就可以决出第2名，剩下C1、D1、E1的3条跑道都只能用来凑热闹的吗？

能够优化的关键出来了，我们是否能够通过剩下的3个跑道来决出第3名呢？当然可以，我们来进一步分析第3名的情况？

● 如果A2>B1(即第2名为A2)，那么根据第6场比赛中的(B1>C1>D1>E1)。可以断定第3名只能在A3和B1中产生。

● 如果B1>A2(即第2名为B1)，那么可以断定的第3名只能在A2, B2,C1 中产生。

好了，结论也出来了，只要我们把[A2、B1、A3、B2、C1]作为第7场比赛的马，那么这场比赛的第2，3名一定是整个25匹马中的第2，3名。

我们在这里列举出第7场的2，3名次的所有可能情况：

① 第2名=A2，第3名=A3

② 第2名=A2，第3名=B1

③ 第2名=B1，第3名=A2

④ 第2名=B1，第3名=B2

⑤ 第2名=B1，第3名=C1

(4) 第8场比赛很复杂，我们要根据第7场的所有可能的比赛情况进行分析。

① 第2名=A2，第3名=A3。那么此种情况下第4名只能在A4和B1中产生。

● 如果第4名=A4，那么第5名只能在A5、B1中产生。

● 如果第4名=B1，那么第5名只能在A4、B2、C1中产生。

不管结果如何，此种情况下，第4、5名都可以在第8场比赛中决出。其中比赛马匹为[A4、A5、B1、B2、C1]

② 第2名=A2，第3名=B1。那么此种情况下第4名只能在A3、B2、C1中产生。

● 如果第4名=A3，那么第5名只能在A4、B2、C1中产生。

● 如果第4名=B2，那么第5名只能在A3、B3、C1中产生。

● 如果第4名=C1，那么第5名只能在A3、B2、C2、D1中产生。

那么，第4、5名需要在马匹[A3、B2、B3、C1、A4、C2、D1]七匹马中产生，则必须比赛两场才行，也就是到第9场角逐出全部的前5名。

③ 第2名=B1，第3名=A2。那么此种情况下第4名只能在A3、B2、C1中产生。

情况和②一样，必须角逐第9场

④ 第2名=B1，第3名=B2。那么此种情况下第4名只能在A2、B3、C1中产生。

● 如果第4名=A2，那么第5名只能在A3、B3、C1中产生。

● 如果第4名=B3，那么第5名只能在A2、B4、C1中产生。

● 如果第4名=C1，那么第5名只能在A2、B3、C2、D1中产生。

那么，第4、5名需要在马匹[A2、B3、B4、C1、A3、C2、D1]七匹马中产生，则必须比赛两场才行，也就是到第9场角逐出全部的前5名。

⑤ 第2名=B1，第3名=C1。那么此种情况下第4名只能在A2、B2、C2、D1中产生。

● 如果第4名=A2，那么第5名只能在A3、B2、C2、D1中产生。

● 如果第4名=B2，那么第5名只能在A2、B3、C2、D1中产生。

● 如果第4名=C2，那么第5名只能在A2、B2、C3、D1中产生。

● 如果第4名=D1，那么第5名只能在A2、B2、C2、D2、E2中产生。

那么，第4、5名需要在马匹[A2、B2、C2、D1、A3、B3、C3、D2、E1]九匹马中产生，因此也必须比赛两场，也就是到第9长决出胜负。

总结：最好情况可以在第8场角逐出前5名，最差也可以在第9场搞定。

来源：iteye.com/blog/hxraid-662643

2. 砝码称轻重

这一类的题目有很多这里只举几个经典的：

\1. 有一个天平，九个砝码，其中一个砝码比另八个要轻一些，问至少要用天平称几次才能将轻的那个找出来？答案：2次

\2. 十组砝码每组十个，每个砝码都是10g重，但是现在其中有一组砝码每个都只有9g重，现有一个能显示克数的秤，最少称几次能找到轻的那组？答案：1次

有一个天平，九个砝码，一个轻一些，用天平至少几次能找到轻的？

至少2次：第一次，一边3个，哪边轻就在哪边，一样重就是剩余的3个；
第二次，一边1个，哪边轻就是哪个，一样重就是剩余的那个；
答：至少称2次．

有十组砝码每组十个，每个砝码重10g，其中一组每个只有9g，有能显示克数的秤最少几次能找到轻的那一组砝码？

将砝码分组1~10，第一组拿一个，第二组拿两个以此类推。。第十组拿十个放到秤上称出克数x，则y = 550 - x，第y组就是轻的那组

3. 药瓶毒白鼠

有1000个一模一样的瓶子，其中有999瓶是普通的水，有1瓶是毒药。任何喝下毒药的生命都会在一星期之后死亡。现在你只有10只小白鼠和1个星期的时间，如何检验出哪个瓶子有毒药？

答案：

1、将10只老鼠剁成馅儿，分到1000个瓶盖中，每个瓶盖倒入适量相应瓶子的液体，置于户外，并每天补充适量相应的液体，观察一周，看哪个瓶盖中的肉馅没有腐烂或生蛆。（最好不要这样回答）

2.

首先一共有1000瓶，2的10次方是1024，刚好大于1000，也就是说，1000瓶药品可以使用10位二进制数就可以表示。从第一个开始：

第一瓶： 00 0000 0001

第二瓶： 00 0000 0010

第三瓶： 00 0000 0011

……

第999瓶： 11 1111 0010

第1000瓶： 11 1111 0011

需要十只老鼠，如果按顺序编号，ABCDEFGHIJ分别代表从低位到高位每一个位。每只老鼠对应一个二进制位，如果该位上的数字为1，则给老鼠喝瓶里的药。

观察，若死亡的老鼠编号为：ACFGJ，一共死去五只老鼠，则对应的编号为 10 0110 0101，则有毒的药品为该编号的药品，转为十进制数为：613号。（这才是正解，当然前提是老鼠还没被撑死）

4. 绳子两头烧

现有若干不均匀的绳子，烧完这根绳子需要一个小时，问如何准确计时15分钟，30分钟，45分钟，75分钟。。。

15：对折之后两头烧(要求对折之后绑的够紧，否则看45分钟解法)

30：两头烧 45：两根，一根两头烧一根一头烧，两头烧完过了30分钟，立即将第二根另一头点燃，到烧完又过15分钟，加起来45分钟 75：=30+45

。。。

5. 犯人猜颜色

一百个犯人站成一纵列，每人头上随机带上黑色或白色的帽子，各人不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色．
然后从最后一个犯人开始，每人只能用同一种声调和音量说一个字：”黑”或”白”，
如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，
说的答案所有犯人都能听见，
是否说对，其他犯人不知道，
在这之前，所有犯人可以聚在一起商量策略，
问如果犯人都足够聪明而且反应足够快，100个人最大存活率是多少？

答案：这是一道经典推理题

1、最后一个人如果看到奇数顶黑帽子报“黑”否则报“白”，他可能死

2、其他人记住这个值（实际是黑帽奇偶数），在此之后当再听到黑时，黑帽数量减一

3、从倒数第二人开始，就有两个信息：记住的值与看到的值，相同报“白”，不同报“黑”

99人能100%存活，1人50%能活

除此以外，此题还有变种：每个犯人只能看见前面一个人帽子颜色又能最多存活多少人？

答案：在上题基础上，限制了条件，这时上次的方法就不管用了，此时只能约定偶数位犯人说他前一个人的帽子颜色，奇数犯人获取信息100%存活，偶数犯人50几率存活。

6. 猴子搬香蕉

一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，（多了就被压死了），它每走

1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里。（提示：他可以把香蕉放下往返的走，但是必须保证它每走一米都能有香蕉吃。也可以走到n米时，放下一些香蕉，拿着n根香蕉走回去重新搬50根。）

答案：这种试题通常有一个迷惑点，让人看不懂题目的意图。此题迷惑点在于：走一米吃一根香蕉，一共走50米，那不是把50根香蕉吃完了吗？如果要回去搬另外50根香蕉，则往回走的时候也要吃香蕉，这样每走一米需要吃掉三根香蕉，走50米岂不是需要150根香蕉？

其实不然，本题关键点在于：猴子搬箱子的过程其实分为两个阶段，第一阶段：来回搬，当香蕉数目大于50根时，猴子每搬一米需要吃掉三根香蕉。第二阶段：香蕉数《=50，直接搬回去。每走一米吃掉1根。

我们分析第一阶段：假如把100根香蕉分为两箱。一箱50根。

第一步，把A箱搬一米，吃一根。

第二步，往回走一米，吃一根。

第三步，把B箱搬一米，吃一根。

这样，把所有香蕉搬走一米需要吃掉三根香蕉。

这样走到第几米的时候，香蕉数刚好小于50呢？

100-(n3)<50 && 100-(n-13)>50

走到16米的时候，吃掉48根香蕉，剩52根香蕉。这步很有意思，它可以直接搬50往前走，也可以再来回搬一次，但结果都是一样的。到17米的时候，猴子还有49根香蕉。这时猴子就轻松啦。直接背着走就行。

第二阶段：

走一米吃一根。

把剩下的50-17=33米走完。还剩49-33=16根香蕉。

7. 高楼扔鸡蛋

有2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。

问：如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？

首先要说明的是这道题你要是一上来就说出正确答案，那说明你的智商不是超过160就是你做过这题。

所以建议你循序渐进的回答，一上来就说最优解可能结果不会让你和面试官满意。

答案：

1.暴力法

举个栗子，最笨的测试方法，是什么样的呢？把其中一个鸡蛋，从第1层开始往下扔。如果在第1层没碎，换到第2层扔；如果在第2层没碎，换到第3层扔…….如果第59层没碎，换到第60层扔；如果第60层碎了，说明不会摔碎的临界点是第59层。

在最坏情况下，这个方法需要扔100次。

二分法

采用类似于二分查找的方法，把鸡蛋从一半楼层（50层）往下扔。

如果第一枚鸡蛋，在50层碎了，第二枚鸡蛋，就从第1层开始扔，一层一层增长，一直扔到第49层。

如果第一枚鸡蛋在50层没碎了，则继续使用二分法，在剩余楼层的一半（75层）往下扔……

这个方法在最坏情况下，需要尝试50次。

3.均匀法

如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数，尽可能均衡呢？

很简单，做一个平方根运算，100的平方根是10。

因此，我们尝试每10层扔一次，第一次从10层扔，第二次从20层扔，第三次从30层……一直扔到100层。

这样的最好情况是在第10层碎掉，尝试次数为 1 + 9 = 10次。

最坏的情况是在第100层碎掉，尝试次数为 10 + 9 = 19次。

不过，这里有一个小小的优化点，我们可以从15层开始扔，接下来从25层、35层扔……一直到95层。

这样最坏情况是在第95层碎掉，尝试次数为 9 + 9 = 18次。

4.最优解法

最优解法是反向思考的经典：如果最优解法在最坏情况下需要扔X次，那第一次在第几层扔最好呢？

答案是：从X层扔

假设最优的尝试次数的x次，为什么第一次扔就要选择第x层呢？

这里的解释会有些烧脑，请小伙伴们坐稳扶好：

假设第一次扔在第x+1层：

如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x层。

这样一来，我们总共尝试了x+1次，和假设尝试x次相悖。由此可见，第一次扔的楼层必须小于x+1层。

假设第一次扔在第x-1层：

如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-2层。

这样一来，我们总共尝试了x-2+1 = x-1次，虽然没有超出假设次数，但似乎有些过于保守。

假设第一次扔在第x层：

如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-1层。

这样一来，我们总共尝试了x-1+1 = x次，刚刚好没有超出假设次数。

因此，要想尽量楼层跨度大一些，又要保证不超过假设的尝试次数x，那么第一次扔鸡蛋的最优选择就是第x层。

那么算最坏情况，第二次你只剩下x-1次机会，按照上面的说法，你第二次尝试的位置必然是X+（X-1）；

以此类推我们可得：

x + (x-1) + (x-2) + … + 1 = 100

这个方程式不难理解：

左边的多项式是各次扔鸡蛋的楼层跨度之和。由于假设尝试x次，所以这个多项式共有x项。

右边是总的楼层数100。

下面我们来解这个方程：

x + (x-1) + (x-2) + … + 1 = 100 转化为

(x+1)*x/2 = 100

最终x向上取整，得到 x = 14

因此，最优解在最坏情况的尝试次数是14次，第一次扔鸡蛋的楼层也是14层。

最后，让我们把第一个鸡蛋没碎的情况下，所尝试的楼层数完整列举出来：

14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100

举个栗子验证下：

假如鸡蛋不会碎的临界点是65层，那么第一个鸡蛋扔出的楼层是14，27，50，60，69。这时候啪的一声碎了。

第二个鸡蛋继续，从61层开始，61，62，63，64，65，66，啪的一声碎了。

因此得到不会碎的临界点65层，总尝试次数是 6 + 6 = 12 < 14 。

下面是我个人的理解：这个更像是优化版的均匀法，均匀法让你第二次尝试不超过10，但是第一次的位置无法保证（最多要9次，最好一次），这个由于每多一次尝试，楼层间隔就-1，最终使得第一次与第二次的和完全均匀（最差情况）。

但是核心思路是逆向思考，因为即使理解了需要两次的和均匀也很难得到第一次要在哪层楼扔。

一旦理解了这种方法，多少层楼你都不会怕啦~

来源：https://blog.csdn.net/qq_38316721/article/details/81351297

8. 轮流拿石子<头条问过>

问题：一共有N颗石子（或者其他乱七八糟的东西），每次最多取M颗最少取1颗，A，B轮流取，谁最后会获胜？（假设他们每次都取最优解）。

答案：简单的巴什博奕：https://www.cnblogs.com/StrayWolf/p/5396427.html

问题：有若干堆石子，每堆石子的数量是有限的，二个人依次从这些石子堆中拿取任意的石子，至少一个（不能不取），最后一个拿光石子的人胜利。

答案：较复杂的尼姆博弈：https://blog.csdn.net/BBHHTT/article/details/80199541

9. 蚂蚁走树枝

问题：放N只蚂蚁在一条长度为M树枝上，蚂蚁与蚂蚁之间碰到就各自往反方向走，问总距离或者时间。

答案：这个其实就一个诀窍：蚂蚁相碰就往反方向走，可以直接看做没有发生任何事：大家都相当于独立的

A蚂蚁与B蚂蚁相碰后你可以看做没有发生这次碰撞，这样无论是求时间还是距离都很简单了。

10. 海盗分金币

问题：5个海盗抢到了100枚金币，每一颗都一样的大小和价值。

他们决定这么分：

抽签决定自己的号码（1，2，3，4，5）
首先，由1号提出分配方案，然后大家5人进行表决，当半数以上的人同意时（不包括半数，这是重点），按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当半超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
依次类推……

假设每一位海盗都足够聪明，并且利益至上，能多分一枚金币绝不少分，那么1号海盗该怎么分金币才能使自己分到最多的金币呢？

答案：

从后向前推，如果1至3号强盗都喂了鲨鱼，只剩4号和5号的话，5号一定投反对票让4号喂鲨鱼，以独吞全部金币。所以，4号惟有支持3号才能保命。

3号知道这一点，就会提出“100，0，0”的分配方案，对4号、5号一毛不拔而将全部金币归为已有，因为他知道4号一无所获但还是会投赞成票，再加上自己一票，他的方案即可通过。

不过，2号推知3号的方案，就会提出“98，0，1，1”的方案，即放弃3号，而给予4号和5号各一枚金币。由于该方案对于4号和5号来说比在3号分配时更为有利，他们将支持他而不希望他出局而由3号来分配。这样，2号将拿走98枚金币。

同样，2号的方案也会被1号所洞悉，1号并将提出（97，0，1，2，0）或（97，0，1，0，2）的方案，即放弃2号，而给3号一枚金币，同时给4号（或5号）2枚金币。由于1号的这一方案对于3号和4号（或5号）来说，相比2号分配时更优，他们将投1号的赞成票，再加上1号自己的票，1号的方案可获通过，97枚金币可轻松落入囊中。这无疑是1号能够获取最大收益的方案了！答案是：1号强盗分给3号1枚金币，分给4号或5号强盗2枚，自己独得97枚。分配方案可写成（97，0，1，2，0）或（97，0，1，0，2）。

此题还有变种：就是只需要一半人同意即可，不需要一半人以上同意方案就可以通过，在其他条件不变的情况下，1号该怎么分配才能获得最多的金币？

答案：类似的推理过程

4号：4号提出的方案的时候肯定是最终方案，因为不管5号同意不同意都能通过，所以4号5号不必担心自己被投入大海。那此时5号获得的金币为0，4号获得的金币为100。

5号：因为4号提方案的时候，自己获取的金币为0 。所以只要4号之前的人分配给自己的金币大于0就同意该方案。

4号：如果3号提的方案一定能获得通过（原因：3号给5号的金币大于0， 5号就同意因此就能通过），那自己获得的金币就为0，所以只要2号让自己获得的金币大于0就会同意。

3号：因为到了自己提方案的时候可以给5号一金币，自己的方案就能通过，但考虑到2号提方案的时候给4号一个金币，2号的方案就会通过，那自己获得的金币就为0。所以只要1号让自己获得的金币大于0就会同意。

2号：因为到了自己提方案的时候只要给4号一金币，就能获得通过，根本就不用顾及3 号 5号同意不同意，所以不管1号怎么提都不会同意。

1号：2号肯定不会同意。但只要给3号一块金币，5号一块金币（因为5号如果不同意，那么4号分配的时候，他什么都拿不到）就能获得通过。

所以答案是 98，0，1，0，1。

类似的问题也可用类似的推理，并不难

11. 三个火枪手

问题：彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好，十发八中；乙枪法次之，十发六中；丙枪法最差，十发四中。如果三人同时***，并且每人每轮只发一枪；那么枪战后，谁活下来的机会大一些？

答案：

一般人认为甲的枪法好，活下来的可能性大一些。但合乎推理的结论是，枪法最糟糕的丙活下来的几率最大。

那么我们先来分析一下各个枪手的策略。

如同田忌赛马一般，枪手甲一定要对枪手乙先***。因为乙对甲的威胁要比丙对甲的威胁更大，甲应该首先干掉乙，这是甲的最佳策略。

同样的道理，枪手乙的最佳策略是第一枪瞄准甲。乙一旦将甲干掉，乙和丙进行对决，乙胜算的概率自然大很多。

枪手丙的最佳策略也是先对甲***。乙的枪法毕竟比甲差一些，丙先把甲干掉再与乙进行对决，丙的存活概率还是要高一些。

我们根据分析来计算一下三个枪手在上述情况下的存活几率：
第一轮：甲射乙，乙射甲，丙射甲。
甲的活率为24%（40% X 60%）

乙的活率为20%(100% - 80%)

丙的活率为100%（无人射丙）。

由于丙100％存活率，因此根据上轮甲乙存活的情况来计算三人第二轮的存活几率：

情况1：甲活乙死（24% X 80% = 19.2%）
甲射丙，丙射甲：甲的活率为60%，丙的活率为20%。
情况2：乙活甲死（20% X 76% = 15.2%）
乙射丙，丙射乙：乙的活率为60%，丙的活率为40%。
情况3：甲乙同活（24% X 20% = 4.8%）
重复第一轮。
情况4：甲乙同死（76% X 80% = 60.8%）
枪战结束。

据此来计算三人活率：
甲的活率为(19.2% X 60%) + (4.8% X 24%) = 12.672%
乙的活率为(15.2% X 60%) + (4.8% X 20%) = 10.08%
丙的活率为(19.2% X 20%) + (15.2% X 40%) + (4.8% X 100%) + (60.8% X 100%) = 75.52%

通过对两轮枪战的详细概率计算，我们发现枪法最差的丙存活的几率最大，枪法较好的甲和乙的存活几率却远低于丙的存活几率。

来自：https://www.zhihu.com/question/288093713/answer/482192781

12. 囚犯拿豆子

问题：有5个囚犯被***，他们请求上诉，于是法官愿意给他们一个机会。

犯人抽签分好顺序，按序每人从100粒豆子中随意抓取，最多可以全抓，最少可以不抓，可以和别人抓的一样多。

最终，抓的最多的和最少的要被处死。

1、他们都是非常聪明且自私的人。

2、他们的原则是先求保命。如果不能保命，就拉人陪葬。

3、100颗不必都分完。

4、若有重复的情况，则也算最大或最小，一并处死（中间重复不算）。

假设每个犯人都足够聪明，但每个犯人并不知道其他犯人足够聪明。那么，谁活下来的可能性最大？

答案：

不存在“谁活下来的可能性比较大”的问题。实际情况是5个人都要死。答案看起来很扯淡，但推理分析后却发现十分符合逻辑。

根据题意，一号知道有五个人抓豆子，为保性命，他只要让豆子在20颗以内就可以了。但是他足够聪明的话他一定拿20颗，因为无论多拿一颗：2,3,4号的人一定会拿20颗最后死的人就会是最多的1号和最少的5号还是少拿一颗：2,3,4号拿20个后，5号选择也拿20个拉上1234号垫背。（下面会说为什么多拿少拿也只会相差一颗）

2号是知道1号抓了几颗豆子(20)的。那么，对于2号来说，只有2种选择：与1号一样多，或者不一样多。我们就从这里入手。

情况一，假如2号选择与1号的豆子数不一样多，也就是说2号选择比1号多或者比1号少。

我们先要证明，如果2号选择比1号多或者比1号少，那么他一定会选择比1号只多1颗或者只少1颗。

要证明这个并不算太难。因为每个囚犯的第一选择是先求保命，要保命就要尽量使自己的豆子数既不是最多也不是最少。当2号决定选择比1号多的时候，他已经可以保证自己不是最少，为了尽量使自己不是最多，当然比1号多出来的数量越小越好。因为这个数量如果与一号相差大于1的话，那么3号就有机会抓到的居中数，相差越大，二号成为最多的可能性也就越大。反之，当2号决定选择比1号少的时候，也是同样的道理，他会选择只比1号少1颗。既然2号只会会选择比1号多1颗或者比1号少1颗，那么1、2号的豆子数一定是2个连续的自然数，和一定是2n+1（其中1个人是n,另1人是n+1）。

轮到3号的时候，他可以从剩下的豆子数知道1、2号的数量和，也就不难计算出n的值。而3号也只有2个选择：n颗或者n+1颗。为什么呢？这与上面的证明是一样的道理，保命原则，取最接近的数量，这里不再赘述。

不过，3号选择的时候会有一个特殊情况，在这一情况下，他一定会选择较小的n，而不是较大的n+1。这一特殊情况就是，当3号知道自己选择了n后(已保证自己不是最多)，剩下的豆子数由于数量有限，4、5号中一定有人比n要少，这样自己一定可以活下来。计算的话就是 [100-(3n+1)]/2<=n ，不难算出，在这个特殊情况下，n>=20。也就是说，当1、2号选择了20或21颗的时候，3号只要选择20颗，就可以保证自己活下来。

这样一来剩下的豆子只剩39颗，4、5号至少有一人少于20颗的（这个人当然是后选的5号），这样死的将是5号和1、2号中选21颗的那个人。当然，1号、2号肯定不会有人选择21这一“倒霉”的数字（因为他们都是聪明人），这样的话，上述“特殊情况（即3号选择n）”就不会发生了。

综上所述，2345这四个人不难从剩下的豆子数知道前面几个人的数量总和，也就不难进而计算出n的值，而这样一来他们也只有n或者n+1这两种选择。最后的5号也是不难算出n的。在前4个人只选择了2个数字(n和n+1)的情况下，5号已是必死无疑，这时,根据“死也要拉几个垫背”的条件，5号会选择n或n+1，选择5个人一起完蛋。

情况二，如果2号选择了与1号不一样多的话，最终结果是5个人一起死，那么2号只有选择与1号一样多了。

那么1、2号的和就是2n，而3号如果选择n+1或者n -1的话，就又回到第一点的情况去了(前3个人的和是3m+1或3m+2)，于是3号也只能选择n ，当然，4号还是只能选n，最后的结果仍旧是5个人一起完蛋。

“最后处死抓的最多和最少的囚犯”严格执行这句话的话，除非有人舍己为人，死二留三。但这是足够聪明且自私的囚犯，所以这五个聪明人的下场是全死，这道题只不过是找了一个处死所有人的借口罢了. . . . . .

变种问题：如果每个囚犯都知道其他囚犯足够聪明，事情会怎么发展？

答案：

这样的情况下囚犯一也会像我们一样推导出前面的结论，那么根据自私的规定，他会直接拿完100个，大家一起完蛋(反正结局已定)

13. 学生猜生日<笔试高频>

这种题目笔试中出现的次数比较多，用排除法比较好解决

1.

小明和小强都是张老师的学生，张老师的生日是M月N日,

2人都知道张老师的生日是下列10组中的一天，张老师把M值告诉了小明,

把N值告诉了小强，张老师问他们知道他的生日是那一天吗?

3月4日 3月5日 3月8日

6月4日 6月7日

9月1日 9月5日

12月1日 12月2日 12月8日

小明说:如果我不知道的话，小强肯定也不知道.

小强说:本来我也不知道，但是现在我知道了.

小明说:哦，那我也知道了.

请根据以上对话推断出张老师的生日是哪一天?

答案：9月1日

排除法：

1.小明肯定小强不知道是哪天，排除所有月份里有单独日的月份：6月和12月<因为如果小强的M是2或者7的话，小强就知道了，所以把6月7日与12月2日排除>，所以小明拿到的是3或者9

2.小强本来不知道，所以小强拿到的不是2或者7，但是小强现在知道了，说明把6月与12月排除后，小强拿到的是1,4,8中的一个<这里小强肯定没拿到5，否则他不会知道是哪天的>

3.小明现在也知道了，说明小明拿到的不是3，否则他不会知道是3月4日还是3月8日的，所以小明拿到的是9才能唯一确定生日

综上，答案是9月1日

2.

小明和小强是赵老师的学生，张老师的生日是M月N日，张老师

把M值告诉小明，N值告诉小强

给他们六个选项

3月1日 3月3日 7月3日 7月5日

9月1日 11月7日

小明说:我猜不出来

小强说:本来我也猜不出来，但是现在我知道了

问:张老师生日多少

答案：3月1日

排除法：

1.小明说猜不出来，说明小明拿到的不是单独出现的9或者11，说明老师生日只能是3月或者7月

2.小强原本不知道，说明小强拿到的不是单独出现的5或者7，说明老是生日是1日或3日

3.小强现在知道了，说明小强拿到的是1，因为如果拿到的是3，那么小强就不知道是3月3日还是7月3日了

综上，老师生日是3月1日

作者：代码不规范，测试两行泪
链接：https://www.nowcoder.com/discuss/262595
来源：牛客网

LeetCode226

发表于 2020-05-17 分类于 LeetCode
本文字数： 575 阅读时长 ≈ 1 分钟

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

备注:
这个问题是受到 Max Howell 的原问题启发的：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

递归求解

 public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root==null||(root.left==null&&root.right==null)){
            return root;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

LeetCode70

发表于 2020-05-17 分类于 LeetCode
本文字数： 453 阅读时长 ≈ 1 分钟

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

这是一道典型的的规划问题,写出状态转移方程:dp[n]=dp[n-1]+dp[n-2]

class Solution {
    public int climbStairs(int n) {
        if (n<3){return n;}
        int[] dp=new int[n+1];
        for (int i = 0; i < 3; i++) {
            dp[i]=i;
        }
        for (int i = 3; i < n+1; i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

RESTful架构-转载

发表于 2020-05-16 分类于 Web
本文字数： 3.6k 阅读时长 ≈ 3 分钟

越来越多的人开始意识到，网站即软件，而且是一种新型的软件。

这种”互联网软件”采用客户端/服务器模式，建立在分布式体系上，通过互联网通信，具有高延时（high latency）、高并发等特点。

网站开发，完全可以采用软件开发的模式。但是传统上，软件和网络是两个不同的领域，很少有交集；软件开发主要针对单机环境，网络则主要研究系统之间的通信。互联网的兴起，使得这两个领域开始融合，现在我们必须考虑，如何开发在互联网环境中使用的软件。

RESTful架构，就是目前最流行的一种互联网软件架构。它结构清晰、符合标准、易于理解、扩展方便，所以正得到越来越多网站的采用。

但是，到底什么是RESTful架构，并不是一个容易说清楚的问题。下面，我就谈谈我理解的RESTful架构。

一、起源

REST这个词，是Roy Thomas Fielding在他2000年的博士论文中提出的。

Fielding是一个非常重要的人，他是HTTP协议（1.0版和1.1版）的主要设计者、Apache服务器软件的作者之一、Apache基金会的第一任主席。所以，他的这篇论文一经发表，就引起了关注，并且立即对互联网开发产生了深远的影响。

他这样介绍论文的写作目的：

“本文研究计算机科学两大前沿—-软件和网络—-的交叉点。长期以来，软件研究主要关注软件设计的分类、设计方法的演化，很少客观地评估不同的设计选择对系统行为的影响。而相反地，网络研究主要关注系统之间通信行为的细节、如何改进特定通信机制的表现，常常忽视了一个事实，那就是改变应用程序的互动风格比改变互动协议，对整体表现有更大的影响。我这篇文章的写作目的，就是想在符合架构原理的前提下，理解和评估以网络为基础的应用软件的架构设计，得到一个功能强、性能好、适宜通信的架构。“

(This dissertation explores a junction on the frontiers of two research disciplines in computer science: software and networking. Software research has long been concerned with the categorization of software designs and the development of design methodologies, but has rarely been able to objectively evaluate the impact of various design choices on system behavior. Networking research, in contrast, is focused on the details of generic communication behavior between systems and improving the performance of particular communication techniques, often ignoring the fact that changing the interaction style of an application can have more impact on performance than the communication protocols used for that interaction. My work is motivated by the desire to understand and evaluate the architectural design of network-based application software through principled use of architectural constraints, thereby obtaining the functional, performance, and social properties desired of an architecture. )

二、名称

Fielding将他对互联网软件的架构原则，定名为REST，即Representational State Transfer的缩写。我对这个词组的翻译是”表现层状态转化”。

如果一个架构符合REST原则，就称它为RESTful架构。

要理解RESTful架构，最好的方法就是去理解Representational State Transfer这个词组到底是什么意思，它的每一个词代表了什么涵义。如果你把这个名称搞懂了，也就不难体会REST是一种什么样的设计。

三、资源（Resources）

REST的名称”表现层状态转化”中，省略了主语。”表现层”其实指的是”资源”（Resources）的”表现层”。

所谓”资源”，就是网络上的一个实体，或者说是网络上的一个具体信息。它可以是一段文本、一张图片、一首歌曲、一种服务，总之就是一个具体的实在。你可以用一个URI（统一资源定位符）指向它，每种资源对应一个特定的URI。要获取这个资源，访问它的URI就可以，因此URI就成了每一个资源的地址或独一无二的识别符。

所谓”上网”，就是与互联网上一系列的”资源”互动，调用它的URI。

四、表现层（Representation）

“资源”是一种信息实体，它可以有多种外在表现形式。我们把”资源”具体呈现出来的形式，叫做它的”表现层”（Representation）。

比如，文本可以用txt格式表现，也可以用HTML格式、XML格式、JSON格式表现，甚至可以采用二进制格式；图片可以用JPG格式表现，也可以用PNG格式表现。

URI只代表资源的实体，不代表它的形式。严格地说，有些网址最后的”.html”后缀名是不必要的，因为这个后缀名表示格式，属于”表现层”范畴，而URI应该只代表”资源”的位置。它的具体表现形式，应该在HTTP请求的头信息中用Accept和Content-Type字段指定，这两个字段才是对”表现层”的描述。

五、状态转化（State Transfer）

访问一个网站，就代表了客户端和服务器的一个互动过程。在这个过程中，势必涉及到数据和状态的变化。

互联网通信协议HTTP协议，是一个无状态协议。这意味着，所有的状态都保存在服务器端。因此，如果客户端想要操作服务器，必须通过某种手段，让服务器端发生”状态转化”（State Transfer）。而这种转化是建立在表现层之上的，所以就是”表现层状态转化”。

客户端用到的手段，只能是HTTP协议。具体来说，就是HTTP协议里面，四个表示操作方式的动词：GET、POST、PUT、DELETE。它们分别对应四种基本操作：GET用来获取资源，POST用来新建资源（也可以用于更新资源），PUT用来更新资源，DELETE用来删除资源。

六、综述

综合上面的解释，我们总结一下什么是RESTful架构：

　　（1）每一个URI代表一种资源；

　　（2）客户端和服务器之间，传递这种资源的某种表现层；

　　（3）客户端通过四个HTTP动词，对服务器端资源进行操作，实现”表现层状态转化”。

七、误区

RESTful架构有一些典型的设计误区。

最常见的一种设计错误，就是URI包含动词。因为”资源”表示一种实体，所以应该是名词，URI不应该有动词，动词应该放在HTTP协议中。

举例来说，某个URI是/posts/show/1，其中show是动词，这个URI就设计错了，正确的写法应该是/posts/1，然后用GET方法表示show。

如果某些动作是HTTP动词表示不了的，你就应该把动作做成一种资源。比如网上汇款，从账户1向账户2汇款500元，错误的URI是：

　　POST /accounts/1/transfer/500/to/2

正确的写法是把动词transfer改成名词transaction，资源不能是动词，但是可以是一种服务：

　　POST /transaction HTTP/1.1
　　Host: 127.0.0.1
　　
　　from=1&to=2&amount=500.00

另一个设计误区，就是在URI中加入版本号：

　　http://www.example.com/app/1.0/foo

　　http://www.example.com/app/1.1/foo

　　http://www.example.com/app/2.0/foo

因为不同的版本，可以理解成同一种资源的不同表现形式，所以应该采用同一个URI。版本号可以在HTTP请求头信息的Accept字段中进行区分（参见Versioning REST Services）：

　　Accept: vnd.example-com.foo+json; version=1.0

　　Accept: vnd.example-com.foo+json; version=1.1

　　Accept: vnd.example-com.foo+json; version=2.0

作者：阮一峰

日期： 2011年9月12日

为什么 TCP 协议有粘包问题-转载

发表于 2020-05-16 分类于 Web
本文字数： 4.4k 阅读时长 ≈ 4 分钟

TCP/IP 协议簇建立了互联网中通信协议的概念模型，该协议簇中的两个主要协议就是 TCP 和 IP 协议。TCP/ IP 协议簇中的 TCP 协议能够保证数据段（Segment）的可靠性和顺序，有了可靠的传输层协议之后，应用层协议就可以直接使用 TCP 协议传输数据，不在需要关心数据段的丢失和重复问题1。

图 1 - TCP 协议与应用层协议

IP 协议解决了数据包（Packet）的路由和传输，上层的 TCP 协议不再关注路由和寻址2，那么 TCP 协议解决的是传输的可靠性和顺序问题，上层不需要关心数据能否传输到目标进程，只要写入 TCP 协议的缓冲区的数据，协议栈几乎都能保证数据的送达。

当应用层协议使用 TCP 协议传输数据时，TCP 协议可能会将应用层发送的数据分成多个包依次发送，而数据的接收方收到的数据段可能有多个『应用层数据包』组成，所以当应用层从 TCP 缓冲区中读取数据时发现粘连的数据包时，需要对收到的数据进行拆分。

粘包并不是 TCP 协议造成的，它的出现是因为应用层协议设计者对 TCP 协议的错误理解，忽略了 TCP 协议的定义并且缺乏设计应用层协议的经验。本文将从 TCP 协议以及应用层协议出发，分析我们经常提到的 TCP 协议中的粘包是如何发生的：

TCP 协议是面向字节流的协议，它可能会组合或者拆分应用层协议的数据；
应用层协议的没有定义消息的边界导致数据的接收方无法拼接数据；

很多人可能会认为粘包是一个比较低级的甚至不值得讨论的问题，但是在作者看来这个问题还是很有趣的，不是所有人都系统性地学过基于 TCP 的应用层协议设计，也不是所有人对 TCP 协议也没有那么深入的理解，相信很多人学习编程的过程都是自底向上的，所以作者认为这是一个值得回答的问题，我们应该传递正确的知识，而不是负面的和居高临下的情绪。

面向字节流

TCP 协议是面向连接的、可靠的、基于字节流的传输层通信协议3，应用层交给 TCP 协议的数据并不会以消息为单位向目的主机传输，这些数据在某些情况下会被组合成一个数据段发送给目标的主机。

Nagle 算法是一种通过减少数据包的方式提高 TCP 传输性能的算法4。因为网络带宽有限，它不会将小的数据块直接发送到目的主机，而是会在本地缓冲区中等待更多待发送的数据，这种批量发送数据的策略虽然会影响实时性和网络延迟，但是能够降低网络拥堵的可能性并减少额外开销。

在早期的互联网中，Telnet 是被广泛使用的应用程序，然而使用 Telnet 会产生大量只有 1 字节负载的有效数据，每个数据包都会有 40 字节的额外开销，带宽的利用率只有 ~2.44%，Nagle 算法就是在当时的这种场景下设计的。

当应用层协议通过 TCP 协议传输数据时，实际上待发送的数据先被写入了 TCP 协议的缓冲区，如果用户开启了 Nagle 算法，那么 TCP 协议可能不会立刻发送写入的数据，它会等待缓冲区中数据超过最大数据段（MSS）或者上一个数据段被 ACK 时才会发送缓冲区中的数据。

图 2 - Nagle 算法

几十年前还会发生网络拥塞的问题，但是今天的网络带宽资源不再像过去那么紧张，在默认情况下，Linux 内核都会使用如下的方式默认关闭 Nagle 算法：

1	TCP_NODELAY = 1

Linux 内核中使用如下所示的 tcp_nagle_test 函数测试我们是否应该发送当前的 TCP 数据段，感兴趣的读者可以以这段代码为入口详细了解 Nagle 算法在今天的实现：

static inline bool tcp_nagle_test(const struct tcp_sock *tp, const struct sk_buff *skb,
				  unsigned int cur_mss, int nonagle)
{
	if (nonagle & TCP_NAGLE_PUSH)
		return true;

	if (tcp_urg_mode(tp) || (TCP_SKB_CB(skb)->tcp_flags & TCPHDR_FIN))
		return true;

	if (!tcp_nagle_check(skb->len < cur_mss, tp, nonagle))
		return true;

	return false;
}

Nagle 算法确实能够在数据包较小时提高网络带宽的利用率并减少 TCP 和 IP 协议头带来的额外开销，但是使用该算法也可能会导致应用层协议多次写入的数据被合并或者拆分发送，当接收方从 TCP 协议栈中读取数据时会发现不相关的数据出现在了同一个数据段中，应用层协议可能没有办法对它们进行拆分和重组。

除了 Nagle 算法之外，TCP 协议栈中还有另一个用于延迟发送数据的选项 TCP_CORK，如果我们开启该选项，那么当发送的数据小于 MSS 时，TCP 协议就会延迟 200ms 发送该数据或者等待缓冲区中的数据超过 MSS5。

无论是 TCP_NODELAY 还是 TCP_CORK，它们都会通过延迟发送数据来提高带宽的利用率，它们会对应用层协议写入的数据进行拆分和重组，而这些机制和配置能够出现的最重要原因是 — TCP 协议是基于字节流的协议，其本身没有数据包的概念，不会按照数据包发送数据。

消息边界

如果我们系统性地学习过 TCP 协议以及基于 TCP 的应用层协议设计，那么设计一个能够被 TCP 协议栈任意拆分和组装数据包的应用层协议就不会有什么问题。既然 TCP 协议是基于字节流的，这其实就意味着应用层协议要自己划分消息的边界。

如果我们能在应用层协议中定义消息的边界，那么无论 TCP 协议如何对应用层协议的数据包进程拆分和重组，接收方都能根据协议的规则恢复对应的消息。在应用层协议中，最常见的两种解决方案就是基于长度或者基于终结符（Delimiter）。

图 3 - 实现消息边界的方法

基于长度的实现有两种方式，一种是使用固定长度，所有的应用层消息都使用统一的大小，另一种方式是使用不固定长度，但是需要在应用层协议的协议头中增加表示负载长度的字段，这样接收方才可以从字节流中分离出不同的消息，HTTP 协议的消息边界就是基于长度实现的：

HTTP/1.1 200 OK
Content-Type: text/html; charset=UTF-8
Content-Length: 138
...
Connection: close

<html>
  <head>
    <title>An Example Page</title>
  </head>
  <body>
    <p>Hello World, this is a very simple HTML document.</p>
  </body>
</html>

在上述 HTTP 消息中，我们使用 Content-Length 头表示 HTTP 消息的负载大小，当应用层协议解析到足够的字节数后，就能从中分离出完整的 HTTP 消息，无论发送方如何处理对应的数据包，我们都可以遵循这一规则完成 HTTP 消息的重组6。

不过 HTTP 协议除了使用基于长度的方式实现边界，也会使用基于终结符的策略，当 HTTP 使用块传输（Chunked Transfer）机制时，HTTP 头中就不再包含 Content-Length 了，它会使用负载大小为 0 的 HTTP 消息作为终结符表示消息的边界。

当然除了这两种方式之外，我们可以基于特定的规则实现消息的边界，例如：使用 TCP 协议发送 JSON 数据，接收方可以根据接收到的数据是否能够被解析成合法的 JSON 判断消息是否终结。

总结

TCP 协议粘包问题是因为应用层协议开发者的错误设计导致的，他们忽略了 TCP 协议数据传输的核心机制 — 基于字节流，其本身不包含消息、数据包等概念，所有数据的传输都是流式的，需要应用层协议自己设计消息的边界，即消息帧（Message Framing），我们重新回顾一下粘包问题出现的核心原因：

TCP 协议是基于字节流的传输层协议，其中不存在消息和数据包的概念；
应用层协议没有使用基于长度或者基于终结符的消息边界，导致多个消息的粘连；

网络协议的学习过程非常有趣，不断思考背后的问题能够让我们对定义有更深的认识。到最后，我们还是来看一些比较开放的相关问题，有兴趣的读者可以仔细思考一下下面的问题：

基于 UDP 协议的应用层协议应该如何设计？会出现粘包的问题么？
有哪些应用层协议使用基于长度的分帧？又有哪些使用基于终结符的分帧？

如果对文章中的内容有疑问或者想要了解更多软件工程上一些设计决策背后的原因，可以在博客下面留言，作者会及时回复本文相关的疑问并选择其中合适的主题作为后续的内容。

为什么 MD5 不能用于存储密码-转载

发表于 2020-05-15 更新于 2020-05-16 分类于安全
本文字数： 5.2k 阅读时长 ≈ 5 分钟

很多软件工程师都认为 MD5 是一种加密算法，然而这种观点其实是大错特错并且十分危险的，作为一个 1992 年第一次被公开的算法，到今天为止已经被发现了一些致命的漏洞，我们在生产环境的任何场景都不应该继续使用 MD5 算法，无论是对数据或者文件的内容进行校验还是用于所谓的『加密』。

这篇文章的主要目的是帮助读者理解 MD5 到底是什么，为什么我们不应该继续使用它，尤其是不应该使用它在数据库中存储密码，作者也希望使用过 MD5 或者明文存储密码的开发者们能够找到更加合理和安全的方式对用户的这些机密信息进行存储（这样也可以间接提高我在各类网站中存储密码的安全性）。

概述

与『为什么我们不能使用 MD5 来存储密码？』这一问题相似的其实还有『为什么我们不能使用明文来存储密码？』，使用明文来存储密码是一种看起来就不可行的方案，除非我们能够 100% 保证数据库中的密码字段不会被任何人访问到，不仅包括潜在的攻击者，还包括系统的开发者和管理员。

不过这是一个非常理想的情况，在实际的生产环境中，我们不能抵御来自黑客的所有攻击，甚至也不能完全阻挡开发者和管理员的访问，因为我们总需要信任并授权一些人或者程序具有当前数据库的所有访问权限，这也就给攻击者留下了可以利用的漏洞，在抵御外部攻击时我们没有办法做到全面，只能尽可能提高攻击者的成本，这也就是使用 MD5 或者其他方式存储密码的原因了。

很多开发者对于 MD5 的作用和定义都有着非常大的误解，MD5 并不是一种加密算法，而是一种摘要算法，我们也可以叫它哈希函数，哈希函数可以将无限键值空间中的所有键都均匀地映射到一个指定大小的键值空间中；一个好的摘要算法能够帮助我们保证文件的完整性，避免攻击者的恶意篡改，但是加密算法或者加密的功能是 —— 通过某种特定的方式来编码消息或者信息，只有授权方可以访问原始数据，而没有被授权的人无法从密文中获取原文。

由于加密需要同时保证消息的秘密性和完整性，所以加密的过程使用一系列的算法，MD5 确实可以在加密的过程中作为哈希函数使用来保证消息的完整性，但是我们还需要另一个算法来保证消息的秘密性，所以由于 MD5 哈希的信息无法被还原，只依靠 MD5 是无法完成加密的。

在任何场景下，我们都应该避免 MD5 的使用，可以选择更好的摘要算法替代 MD5，例如 SHA256、SHA512。

聊了这么多对于 MD5 的误解，我们重新回到今天最开始的题目，『为什么 MD5 不能用于存储密码』，对于这个问题有一个最简单的答案，也就是 MD5 不够安全。当整个系统中的数据库被攻击者入侵之后，存储密码的摘要而不是明文是我们能够对所有用户的最大保护。需要知道的是，不够安全的不只是 MD5，任何摘要算法在存储密码这一场景下都不够安全，我们在这篇文章中就会哈希函数『为什么哈希函数不能用于存储密码』以及其他相关机制的安全性。

设计

既然我们已经对哈希函数和加密算法有了一些简单的了解，接下来的这一节中分析使用以下几种不同方式存储密码的安全性：

使用哈希存储密码；
使用哈希加盐存储密码；
使用加密算法存储密码；
使用 bcrypt 存储密码；

在分析的过程中可能会涉及到一些简单的密码学知识，也会谈到一些密码学历史上的一些事件，不过这对于理解不同方式的安全性不会造成太大的障碍。

哈希

在今天，如果我们直接使用哈希来存储密码，那其实跟存储明文没有太多的区别，所有的攻击者在今天都已经掌握了彩虹表这个工具，我们可以将彩虹表理解成一张预计算的大表，其中存储着一些常见密码的哈希，当攻击者通过入侵拿到某些网站的数据库之后就可以通过预计算表中存储的映射来查找原始密码。

攻击者只需要将一些常见密码提前计算一些哈希就可以找到数据库中很多用于存储的密码，Wikipedia 上有一份关于最常见密码的列表，在 2016 年的统计中发现使用情况最多的前 25 个密码占了调查总数的 10%，虽然这不能排除统计本身的不准确因素，但是也足以说明仅仅使用哈希的方式存储密码是不够安全的。

哈希加盐

仅仅使用哈希来存储密码无法抵御来自彩虹表的攻击，在上世纪 70 到 80 年代，早期版本的 Unix 系统就在 /etc/passwrd 中存储加盐的哈希密码，密码加盐后的哈希与盐会被一起存储在 /etc/passwd 文件中，今天哈希加盐的策略与几十年前的也没有太多的不同，差异可能在于盐的生成和选择：

1	md5(salt, password), salt

加盐的方式主要还是为了增加攻击者的计算成本，当攻击者顺利拿到数据库中的数据时，由于每个密码都使用了随机的盐进行哈希，所以预先计算的彩虹表就没有办法立刻破译出哈希之前的原始数据，攻击者对每一个哈希都需要单独进行计算，这样能够增加了攻击者的成本，减少原始密码被大范围破译的可能性。

在这种情况下，攻击者破解一个用户密码的成本其实就等于发现哈希碰撞的概率，因为攻击者其实不需要知道用户的密码是什么，他只需要找到一个值 value，这个值加盐后的哈希与密码加盐后的哈希完全一致就能登录用户的账号：

1	hash(salt, value) = hash(salt, password)

这种情况在密码学中叫做哈希碰撞，也就是两个不同值对应哈希相同，一个哈希函数或者摘要算法被找到哈希碰撞的概率决定了该算法的安全性，早在几十年前，我们就在 MD5 的设计中发现了缺陷并且在随后的发展中找到了低成本快速制造哈希碰撞的方法。

1996 年 The Status of MD5 After a Recent Attack —— 发现了 MD5 设计中的缺陷，但是并没有被认为是致命的缺点，密码学专家开始推荐使用其他的摘要算法；
2004 年 How to Break MD5 and Other Hash Functions —— 发现了 MD5 摘要算法不能抵抗哈希碰撞，我们不能在数字安全领域使用 MD5 算法；
2006 年 A Study of the MD5 Attacks: Insights and Improvements —— 创建一组具有相同 MD5 摘要的文件；
2008 年 MD5 considered harmful today —— 创建伪造的 SSL 证书；
2010 年 MD5 vulnerable to collision attacks —— CMU 软件工程机构认为 MD5 摘要算法已经在密码学上被破译并且不适合使用;
2012 年 Flame —— 恶意软件利用了 MD5 的漏洞并伪造了微软的数字签名；

从过往的历史来看，为了保证用户敏感信息的安全，我们不应该使用 MD5 加盐的方式来存储用户的密码，那么我们是否可以使用更加安全的摘要算法呢？不可以，哈希函数并不是专门用来设计存储用户密码的，所以它的计算可能相对来说还是比较快，攻击者今天可以通过 GPU 每秒执行上亿次的计算来破解用户的密码，所以不能使用这种方式存储用户的密码，感兴趣的读者可以了解一下用于恢复密码的工具 Hashcat。

加密

既然今天的硬件已经能够很快地帮助攻击者破解用户的密码，那么我们能否通过其他的方式来取代哈希函数来存储密码呢？有些工程师想到使用加密算法来替代哈希函数，这样能够从源头上避免哈希碰撞的的发生，这种方式看起来非常美好，但是有一个致命的缺点，就是我们如何存储用于加密密码的秘钥。

既然存储密码的仓库能被泄露，那么用于存储秘钥的服务也可能会被攻击，我们永远都没有办法保证我们的数据库和服务器是安全的，一旦秘钥被攻击者获取，他们就可以轻而易举地恢复用户的密码，因为核对用户密码的过程需要在内存对密码进行解密，这时明文的密码就可能暴露在内存中，依然有导致用户密码泄露的风险。

使用加密的方式存储密码相比于哈希加盐的方式，在一些安全意识和能力较差的公司和网站反而更容易导致密码的泄露和安全事故。

bcrypt

哈希加盐的方式确实能够增加攻击者的成本，但是今天来看还远远不够，我们需要一种更加安全的方式来存储用户的密码，这也就是今天被广泛使用的 bcrypt，使用 bcrypt 相比于直接使用哈希加盐是一种更加安全的方式，也是我们目前推荐使用的方法，为了增加攻击者的成本，bcrypt 引入了计算成本这一可以调节的参数，能够调节执行 bcrypt 函数的成本。

当我们将验证用户密码的成本提高几个数量级时，攻击者的成本其实也相应的提升了几个数量级，只要我们让攻击者的攻击成本大于硬件的限制，同时保证正常请求的耗时在合理范围内，我们就能够保证用户密码的相对安全。

“bcrypt was designed for password hashing hence it is a slow algorithm. This is good for password hashing as it reduces the number of passwords by second an attacker could hash when crafting a dictionary attack. “

bcrypt 这一算法就是为哈希密码而专门设计的，所以它是一个执行相对较慢的算法，这也就能够减少攻击者每秒能够处理的密码数量，从而避免攻击者的字典攻击。

func main() {
	for cost := 10; cost <= 15; cost++ {
		startedAt := time.Now()
		bcrypt.GenerateFromPassword([]byte("password"), cost)
		duration := time.Since(startedAt)
		fmt.Printf("cost: %d, duration: %v\n", cost, duration)
	}
}

$ go run bcrypt.go
cost: 10, duration: 51.483401ms
cost: 11, duration: 100.639251ms
cost: 12, duration: 202.788492ms
cost: 13, duration: 399.552731ms
cost: 14, duration: 801.041128ms
cost: 15, duration: 1.579692689s

运行上述代码片段时就能发现 cost 和运行时间的关系，算法运行的成本每 +1，当前算法最终的耗时就会翻一倍，这与 bcrypt 算法的实现原理有关，你可以在 Wikipedia 上找到算法执行过程的伪代码，这可以帮助我们快速理解算法背后的设计。

如果硬件的发展使攻击者能够对使用 bcrypt 存储的密码进行攻击时，我们就可以直接提升 bcrypt 算法的 cost 参数以增加攻击者的成本，这也是 bcrypt 设计上的精妙之处，所以使用 bcrypt 是一种在存储用户密码时比较安全的方式。

总结

这篇文章分析的问题其实是 —— 当数据库被攻击者获取时，我们怎么能够保证用户的密码很难被攻击者『破译』，作为保护用户机密信息的最后手段，选择安全并且合适的方法至关重要。攻击者能否破解用户的密码一般取决于两个条件：

使用的加密算法是否足够安全，使用暴力破解的方式时间成本极高；
足够好的硬件支持，能够支持大规模地高速计算哈希；

抵御攻击者的攻击的方式其实就是提高单次算法运行的成本，当我们将用户的验证耗时从 0.1ms 提升到了 500ms，攻击者的计算成本也就提升了 5000 倍，这种结果就是之前需要几小时破解的密码现在需要几年的时间。

不论如何，使用 MD5、MD5 加盐或者其他哈希的方式来存储密码都是不安全的，希望各位工程师能够避免在这样的场景下使用 MD5，在其他必须使用哈希函数的场景下也建议使用其他算法代替，例如 SHA-512 等。

当然，如何保证用户机密信息的安全不只是一个密码学问题，它还是一个工程问题，任何工程开发商的疏漏都可能导致安全事故，所以我们作为开发者在与用于敏感信息打交道时也应该小心谨慎、怀有敬畏之心。到最后，我们还是来看一些比较开放的相关问题，有兴趣的读者可以仔细思考一下下面的问题：

使用 GPU 每秒可以计算多少 MD5 哈希（数量级）？能够在多长时间破解使用 MD5 加盐存储的密码？
假设计算一次哈希耗时 500ms，破解 bcrypt 算法生成的哈希需要多长时间？
MD5 哈希 23cdc18507b52418db7740cbb5543e54 对应的原文可能是？谈谈你使用的工具和破译的过程。

Reference

转载自https://draveness.me/whys-the-design-password-with-md5/

分布式ID生成方案

发表于 2020-05-15 分类于分布式
本文字数： 2 阅读时长 ≈ 1 分钟

背景

LeetCode173

发表于 2020-05-14 分类于 LeetCode
本文字数： 1.1k 阅读时长 ≈ 1 分钟

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // 返回 3
iterator.next();    // 返回 7
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 9
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 15
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 20
iterator.hasNext(); // 返回 false

提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

class BSTIterator {
       
         Stack<TreeNode> iter;
       public BSTIterator(TreeNode root) {
                       iter=new Stack<>();

           pushStack(root);
          
           
       }
       
       private void pushStack(TreeNode node){
           TreeNode tmp=node;
           while (tmp!=null){
               iter.push(tmp);
               tmp=tmp.left;
           }
       }

       /** @return the next smallest number */
       public int next() {
           if (!iter.isEmpty()){
               TreeNode ans=iter.pop();
               if (ans.right!=null){
                   pushStack(ans.right);
               }
               
               return ans.val;
           }
            return -1;
       }

       /** @return whether we have a next smallest number */
       public boolean hasNext() {
           return !iter.isEmpty();
       }
   }

什么是代理模式

为什么需要代理

1. 调用的目标对象在远程主机上，并不在你本地

2. 你不想理会目标类繁杂的功能，只希望增加一些自己的行为进去

静态代理

静态代理的例子

静态代理的缺点

JDK 动态代理

CGLib 动态代理

参考资料

License

开篇

用户空间和内核空间

内核态和用户态

高性能的Server有什么特点

Unix 下的 I/O 模型

1 、阻塞 I/O

2 、非阻塞 I/O

3、 I/O 复用

4 、信号驱动 I/O

5 、异步 I/O

参考资料

License

1. 赛马找最快<腾讯高频题>

25匹马5条跑道找最快的3匹马，需要跑几次？

64匹马8条跑道找最快的4匹马，需要跑几次？

25匹马5条跑道找最快的5匹马，需要跑几次？

2. 砝码称轻重

有一个天平，九个砝码，一个轻一些，用天平至少几次能找到轻的？

有十组砝码每组十个，每个砝码重10g，其中一组每个只有9g，有能显示克数的秤最少几次能找到轻的那一组砝码？

3. 药瓶毒白鼠

2.

4. 绳子两头烧

15：对折之后两头烧(要求对折之后绑的够紧，否则看45分钟解法)

30：两头烧 45：两根，一根两头烧一根一头烧，两头烧完过了30分钟，立即将第二根另一头点燃，到烧完又过15分钟，加起来45分钟 75：=30+45

5. 犯人猜颜色

6. 猴子搬香蕉

7. 高楼扔鸡蛋

8. 轮流拿石子<头条问过>

9. 蚂蚁走树枝

10. 海盗分金币

11. 三个火枪手

12. 囚犯拿豆子

13. 学生猜生日<笔试高频>

1.

2.

爬楼梯

面向字节流

消息边界

总结

相关文章

推荐阅读

概述

设计

哈希

哈希加盐

加密

bcrypt

总结

Reference

背景