网络网络层传输层 TCP、UDP 特点 UDP：无连接，尽最大可能交付数据，面向报文，支持一对一、一对多、多对一、多对多的交互通信，不可靠（快、实时性好） DNS、TFTP TCP：面向连接，可靠交付，有流量控制、拥塞控制，全双工通信，面向字节流，只能点对点（一对一） HTTP、FTP、TELENT、SMTP TCP三次握手 防止失效的连接请求到达服务器，导致服务器打开...

基本概念说明理解Linux的IO模型之前，首先要了解一些基本概念，才能理解这些IO模型设计的依据 用户空间和内核空间操作系统使用虚拟内存来映射物理内存，对于32位的操作系统来说，虚拟地址空间为4G（2^32）。操作系统的核心是内核，为了保护用户进程不能直接操作内核，保证内核安全，操作系统将虚拟地址空间划分为内核空间和用户空间。内核可以访问全部的地址空间，拥有访问底层硬件设备的权限，普通的应用...

LeetCode No.146 LRU缓存机制 LRU（Least Recent Used）策略：优先淘汰最近最少使用的数据，常用于缓存淘汰机制，如Linux系统的内存淘汰、Redis的缓存淘汰等。 基于哈希表和双向链表实现LRU核心思路是，利用双向链表存储键值对，哈希表存储键在链表中对应的节点指针，如下图所示 这样的好处是使访问和更新操作时间复杂度都在O(1)。 PUT操作 判断哈希表中k...

动态规划的关键思想在于将问题转换成较小的子问题，然后根据子问题的结果总结出一个状态转移方程，最后得到整个问题的解 7.1 打家劫舍LeetCode No.198 问题描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非...

分治的思想为将大问题分解为子问题，子问题再分解为更小的子问题，直到不能再拆分，然后再合并子问题的结果，通常需要用到递归。关键是要找对如何拆解问题。 5.1 不同的二叉搜索树LeetCode No.95 问题描述：给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。 思路：根据二叉搜索树的特点，左子树的所有节点值均小于根节点，右子树的所有节点值均大于根节点，同时对于每一...

分治的思想为将大问题分解为子问题，子问题再分解为更小的子问题，直到不能再拆分，然后再合并子问题的结果，通常需要用到递归。关键是要找对如何拆解问题。 5.1 不同的二叉搜索树LeetCode No.95 问题描述：给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。 思路：根据二叉搜索树的特点，左子树的所有节点值均小于根节点，右子树的所有节点值均大于根节点，同时对于每一...

3.1 深度优先DFS 问题1：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。Input: “23”Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”] 思路：深度优先搜索，从根节点到每个叶子节点的所有路径即结果，深度为子串的长度...

二分查找是一种在有序列表中查找元素的高效方法，时间复杂度（logN），二分查找思路和时间都比较简单，但是实际问题中的细节不可忽视。 3.1 搜索插入位置LeetCode No.35 问题描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置，你可以假设数组中无重复元素。 思路：按照二分查找法，定义low，high两个指...

2.1 快速排序 题目描述：实现快速排序 思路：采用交换法，选第一个数为基准数pivot，在pl <= pr的前提下，指针pl从基准数+1的位置向右走，直到碰到比pivot大的数，指针pr从最右边向左走，直到碰到比pivot小的数，交换arr[pl], arr[pr]，循环结束时pr = pl - 1，将基准数和pr交换。递归调用对基准数位置两边的区间调整。 示...

双指针通常用在有序数组，链表的数据结构上，根据题目条件移动对应的指针。比如判断子串、链表是否有环的问题。 1.1 最长子串LeetCode No.524 题目描述：给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串输入:s = “abpcpl...