剑指 - 链表中倒数第k个结点 题目 输入一个链表，输出该链表中倒数第k个结点。 思路 两种方案，不过空间复杂度都为 O(n)，可以考虑一种计数后再次遍历，空间复杂度 O(1)，但写起来比较麻烦，这里就记录比较容易实现和理解的两种方案了 public class LinkListKthNode { public ListNode FindKthToTail(ListNode head, int k) { if (head == null || k == 0) { return null; } return sol2(head, k); } //第一种方案 ： 栈 private ListNod...

剑指 - 调整数组奇数位于偶数前 题目 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 思路 使用两个队列，一个存奇数，一个存偶数，然后依次将数赋值回原数组   总结 位运算的实践！额外空间复杂度 O(n) ，但比较好理解

Java 输入一直是一个坑，本来一直用 Scanner，但一直搞不懂换行符啥的，就用 BufferReader ，但前不久大疆笔试需要持续输入，早忘了 Scanner 怎么写，而那个场景用 Scanner 很好实现 ...... 就继续在这里记录一下 Scanner 的坑吧  一、next & nextLine 区别  next 不能得到带有空格的字符串 一定要读到有效字符后才可以结束，结束条件是碰到空格、tab 键、enter 键   nextLine 可以获得空白 以回车作为结束符，也就是 nextLine 返回回车之前的所以字符    举例 代码调用分两种： class Scan...

迭代  涂掉最后一级矩形的时候，是用什么方式完成的？   n = 1 的时候 只能横着覆盖，一种   n = 2 的时候 可以横着和竖着覆盖，两种   n = 3 的时候 第三级横着覆盖，用了一级，剩下 n = 2，有两种覆盖方法 第三季竖着覆盖，用了两级，剩下 n = 1，有一种覆盖方法 总共有 3 种   n = 4 的时候 第 4 级横着覆盖，用了一级，剩下 n = 3，有三种覆盖方法 第 4 级竖着覆盖，用了两级，剩下 n = 2，有两种覆盖方法 总共有 5 种方法   n = n 的时候 第 n 级横着覆盖，用了一级，剩下 n = n - 1，所以关注第 n - 1 种有几种覆盖方法...

迭代 本质上是斐波那契数列的变种，普通跳台阶是一步与两步，问题规模缩小到分成最后要跳到第 n 阶可以跳两次或者一次去求解，所以，在普通跳台阶，设置两个临时变量存下跳一次或者两次时，前面会有多少种可能的结果 dp 就是可以由什么状态推导出最后的状态，斐波那契数列是由前两种状态，而这里就是由前 n - 1 种状态推导出 这里用同一个套路来分析一下  若楼梯阶级 n = 3  跳 3 步到 3：没有剩下步数没跳的，只有这样一种跳法 跳 2 步到 3：剩下的是第一步没跳，起始跳到第一步只有一种 跳 1 步到 3：剩下的是第二步没跳，起始跳到第二步有两种  求得，n = 3 时，有 4 种跳法 若楼梯阶...

迭代 本质上还是斐波那契数列，所以迭代也可以求 当成 dp 问题来想的话：首先分析问题，它最终解是由前面的解累积起来的解，如何缩小问题的规模？ 首先可知，第一阶有只能一步，一种；，第二阶可以两次一步、一次两步两种  若楼梯阶级 n = 3 跳 2 步到 3：剩下的是第一步没跳，起始跳到第一步只有一种 跳 1 步到 3：剩下的是第二步没跳，起始跳到第二步有两种    通过分类讨论，问题规模就减少了:  若楼梯阶级 n = n 跳 2 步到 n：剩下的是第 n - 2 步没跳，起始跳到第 n - 2 步设它为 pre2 种 跳 1 步到 n：剩下的是第 n - 1 步没跳，起始跳到第 n - 1 ...

递归 当前 = 前一个 + 前两个，递归极其容易超时 public class Solution { public int Fibonacci(int n) { if(n <= 1){ return n; } return Fibonacci(n-2) + Fibonacci(n-1); } } 迭代 递归容易超时，那是递归在计算的时候，计算过很多次已经计算过的结果，可以保存下来 迭代的时候，只关注当前的数的前一个和前两个，每次用变量临时纪录起来，那么只需相加即可，而不是像递归那样重复计算 public class Solution { public int Fibonacci(int ...

给出三种实现思路，不过还是改进后的暴力最快，256 ms 左右；内置排序是 400ms ，应该是因为基本有序，所以对于快排更不友好  堆 O(n)，因为要将数加入堆中 import java.util.*; public class Solution { public int minNumberInRotateArray(int [] array) { int[] arr = array; if (arr == null || arr.length < 1){ return 0; } PriorityQueue<Integer> minHeap = new PriorityQ...

1. 区别 它们都是应对 http 无状态，为了保存用户状态信息而引入的 检查角度不同  cookie 是通过检查客户身上的“通行证”来确定客户身份 session 是通过检查服务器上的“客户明细表”来确认客户身份，  session 相当于程序在服务器上建立的一份客户档案，客户来访的时候只需要查询客户档案表 存储位置与安全性不同  session 存储在服务器端； cookie 存储在用户浏览器，容易被恶意查看  因此，session 存储的信息更安全 数据复杂性不同  cookie 只能存 ASCII 字符串 session 可以存储任意类型数据  大访问量区别  cookie 最大长度 ...

存储引擎 Mysql 有几种存储引擎：  MyISAM InnoDB MERGE MEMORY(HEAP)  其中，MySQL 5.1 之前默认使用 MyISAM 引擎，5.1 之后默认使用 InnoDB 下面说说，InnoDB 和 MyISAM：  区别：    特点 MyISAM InnoDB    存储限制 无 64TB   事务 不支持 支持   锁机制 表锁 行锁   哈希索引 不支持 支持   全文索引 支持 不支持（5.6.4 开始支持）   外键 不支持 支持   内存与空间使用 较低 较高   相同：    特点 MyISAM InnoDB    B 树索引 支持 支持   ...

TCP 粘包：  发送端：一个数据包中包含了发送端发送的两个数据包的信息 接收端：接收的数据包接收到了两个数据包，两个数据包多出了一块  TCP 拆包：  发送端：发送的一个数据包不完整  出现的原因是：  TCP 面向字节流，数据块间是五结构的字节流，没有边界 TCP 首部没有表示数据长度的字段，比较不好区分块的区别  解决方案：  特殊字符串控制 在包首部添加数据包的长度字段

DNS 解析查找域名的 IP 地址 首先会从本机的 hosts 文件里查找是否有该域名的 IO  如果没有，会递归式地按序去本地 DNS 服务器、根 DNS 服务器、域服务器去依次查询 一旦查找到了，服务器返回 IP 给用户主机，同时缓存下该 IP   建立 TCP 连接 确定主机的端口和主机 IP 后，开始三次握手建立起两台主机代表的 Socket 的 TCP 连接   发送 HTTP 请求 用户主机将指定的 HTTP 请求报文发送给服务器 其中，HTTP 请求报文 = 请求行 + 请求报头 + 请求正文   同时在将请求报文发送给传输层时，可以选择是否进行 HTTPS 传输，若是，则需要进...

有三个组成部分：缓冲区、生产者、消费者 生产者负责往缓冲区添加数据，消费者负责往缓冲区消耗数据，如何保证运行的时候使得生产者在缓冲区满时不添加数据，消费者在缓存空时不消费数据，这样的一个问题，就是生产者消费者问题 Demo 代码实现 使用阻塞队列实现： 生产者： class Producer extends Thread { BlockingQueue<String> buffer; public Producer(BlockingQueue<String> buffer) { this.buffer = buffer; } @Override public void ...