经典随机算法小游戏

很多游戏都会涉及地图的随机生成，比如扫雷游戏中地雷的位置应该是随机分布的：

再比如经典炸弹人游戏，障碍物的位置也是有一定随机性的：

介绍

像线性数据结构在查找的时候，⼀般都是使⽤= 或者!= ，在折半查找或者其他范围查询的时候，可能会使⽤< 和> ,理想的时候，我们肯定希望不经过任何的⽐较，直接能定位到某个位置（存储位置），这种在数组中，可以通过索引取得元素。那么，如果我们将需要存储的数据和数组的索引对应起来，并且是⼀对⼀的关系，那不就可以很快定位到元素的位置了么？

只要通过函数f(k) 就能找到k 对应的位置，这个函数f(k) 就是hash 函数。它表示的是⼀种映射关系，但是对不同的值，可能会映射到同⼀个值（同⼀个hash 地址），也就是f(k1) = f(k2) ，这种现象我们称之为冲突或者碰撞。

建图函数

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 图中共有 numCourses 个节点
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        // 添加一条从 from 指向 to 的有向边
        // 边的方向是「被依赖」关系，即修完课程 from 才能修课程 to
        graph[from].add(to);
    }
    return graph;
}

递归算法

递归算法（Recursion Algorithm）是一种重要的编程方法，核心思想是函数通过调用自身来解决问题。在递归中，一个复杂的问题被分解为相同类型但规模更小的子问题，直到达到一个简单到可以直接解决的基本情况（基准情况）。递归算法特别适合解决具有自相似结构的问题，时间复杂度跟递归深度和每层处理的复杂度有关。

递归算法的妙处在于它能用简洁优雅的代码解决看似复杂的问题，但在使用时一定要注意避免无限递归和重复计算等问题。

算法步骤

二分查找

二分查找（Binary Search）是一种高效的查找算法，也叫折半查找。核心思想：对于一个有序的数据集合，每次查找都将查找范围缩小为原来的一半，直到找到目标值或确定目标值不存在。二分查找要求数据必须是有序的，经常应用于数组等支持随机访问的数据结构里。跟线性查找相比，二分查找的效率要高得多，特别是对于大规模数据集。

算法步骤

1. 确定查找范围的左边界 left 和右边界 right
2. 计算中间位置 mid = (left + right) / 2（注意整数溢出问题，更安全的做法是 mid = left + (right - left) / 2）
3. 将中间位置的元素与目标值比较
   • 如果中间元素等于目标值，查找成功，返回中间元素的位置
   • 如果中间元素大于目标值，目标值可能在左半部分，将右边界调整为 mid - 1
   • 如果中间元素小于目标值，目标值可能在右半部分，将左边界调整为 mid + 1
4. 重复步骤2-3，直到找到目标值或者左边界大于右边界（此时表示目标值不存在）

Rabin-Karp算法

Rabin-Karp算法是一种基于哈希函数的字符串匹配算法，由 Michael O. Rabin 和 Richard M. Karp 于1987年提出，核心思想是用哈希函数将模式串和文本串中的子串转换为数值进行比较，避免大量不必要的字符比较。这个算法特别适合多模式串匹配场景，时间复杂度平均为O(n+m)，n是文本串长度，m是模式串长度。

Rabin-Karp算法的关键在于使用滚动哈希函数（Rolling Hash），它可以在常数时间内计算出滑动窗口的新哈希值，保证算法在大多数情况下的高效性。

数据封装解封装

在数据传输过程中要遵循对等层次通信，每一层都与另一方对等层次进行通信 网络层-网络层、数据链路层-数据链路层。 而这些对等通信，并非直接进行的。而是由下层逐层封装来完成对等层交换数据，这就是我们数据的封装。 而解封装，就是上层需要与下层进行通信，于是逐层解封装至目标层进行通信。 这里的上下层就是指的网络参考模型的层次。

上面可能说的有点复杂不易于理解，可以记住下面这句话：数据发送时，从上至下逐层封装；数据接收时，从下至上逐层解封装；只有拆除外层封装，才能看到内层封装。

数据封装过程：

1. 数据从应用层发出，进入传输层
2. 在传输层会为数据打上TCP or UDP头部，里面包含了数据的源端口、目的端口，到这层的时候，数据已经被封装成了数据段。
3. 数据段从传输层发出，进入网络层，在网络层，会为数据段打上一个IP头部里面包含了数据段的源IP 、目的IP，这时候在网络层的数据段被封装成了数据包。
4. 数据包从网络层发出，进入数据链路层，在数据链路层会封装一个以太网帧头部里面包含了二层数据源MAC、目的MAC地址，这时候数据包已经被封装成了数据帧，
5. 最后，数据帧从数据链路层发出，进入物理层，在这里将由物理层将帧转换为01011二进制形式的比特流在网络进行传输。

本文以 Linux 2.6.32 版本的内核作为参考

什么是 TCP 半连接队列和全连接队列？

在 TCP 三次握手的时候，Linux 内核会维护两个队列，分别是：

• 半连接队列，也称 SYN 队列；
• 全连接队列，也称 accept 队列；

服务端收到客户端发起的 SYN 请求后，内核会把该连接存储到半连接队列，并向客户端响应 SYN+ACK，接着客户端会返回 ACK，服务端收到第三次握手的 ACK 后，这也是TCP的三次握手过程，第三次握手之后内核会把连接从半连接队列移除，然后创建新的完全的连接，并将其添加到 accept 队列，等待进程调用 accept 函数时把连接取出来。

演进

如果要让服务器服务多个客户端，那么最直接的方式就是为每一条连接创建线程。

其实创建进程也是可以的，原理是一样的，进程和线程的区别在于线程比较轻量级些，线程的创建和线程间切换的成本要小些，为了描述简述，后面都以线程为例。处理完业务逻辑后，随着连接关闭后线程也同样要销毁了，但是这样不停地创建和销毁线程，不仅会带来性能开销，也会造成浪费资源，而且如果要连接几万条连接，创建几万个线程去应对也是不现实的。

要这么解决这个问题呢？可以使用「资源复用」的方式。也就是不用再为每个连接创建线程，而是创建一个「线程池」，将连接分配给线程，然后一个线程可以处理多个连接的业务。

概述

同步与异步

• 同步： 同步就是发起一个调用后，被调用者未处理完请求之前，调用不返回。此时需要调用者询问处理结果
• 异步： 异步就是发起一个调用后，立刻得到被调用者的回应表示已接收到请求，但是被调用者并没有返回结果，此时调用者来询问处理结果，被调用者通常依靠事件，回调等机制来通知调用者其返回结果。

同步和异步最大的区别在于异步的话调用者不需要等待处理结果，被调用者会通过回调等机制来通知调用者其返回结果。

阻塞和非阻塞

这两个概念是程序级别的。

• 阻塞： 阻塞就是发起一个请求，调用者一直等待请求结果返回，也就是当前线程会被挂起，无法从事其他任务，只有当条件就绪才能继续。
• 非阻塞： 非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程。