在上一篇文章 算法模式：双指针 介绍了双指针模式。本篇文章，再介绍一种即可以用在数组，又可以用在链表中的算法模式：快慢指针。快慢指针，其实是双指针模式的一个变种。所以，两者在很多地方有相通之处。
快慢指针 快慢指针模式，有一个非常出名的名字，叫龟兔赛跑。大家肯定都知道龟兔赛跑啦。但还是再解释一下快慢指针：这种算法的两个指针的在数组上（或是链表上，序列上）的移动速度不一样。还别说，这种方法在解决有环的链表和数组时特别有用。
通过控制指针不同的移动速度（比如在环形链表上），这种算法证明了他们肯定会相遇的。快的一个指针肯定会追上慢的一个（可以想象成跑道上面跑得快的人套圈跑得慢的人）。
咋知道需要用快慢指针模式勒？
问题需要处理环上的问题，比如环形链表和环形数组
当你需要知道链表的长度或是某个特别位置的信息的时候
那啥时候用快慢指针而不是上面的双指针呢？
有些情形下，咱们不应该用双指针，比如我们在单链表上不能往回移动的时候。一个典型的需要用到快慢指针的模式的是当你需要去判断一个链表是否是回文的时候。
LeetCode 141. 环形链表 LeetCode - 141. 环形链表 给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
在上一篇文章 算法模式：改进的二分查找 介绍了二分查找以及相关变种。本篇文章，继续介绍数组相关的算法模式：区间合并。
区间合并 区间合并模式是一个用来处理有区间重叠的很高效的技术。在涉及到区间的很多问题中，通常咱们需要要么判断是否有重叠，要么合并区间，如果他们重叠的话。这个模式是这么起作用的。
给两个区间，一个是 a，另外一个是 b。别小看就两个区间，他们之间的关系能跑出来6种情况。详细的就看图啦。
图 1. 区间关系 观察这六种排序，明显后三种排序是前三种排序的一个“变种”：对区间根据起点和终点进行排序，就是剩下前三种排序了。再对其进行合并就很简单了：
没有重叠，则直接开启新区间。
有重叠，起点和终点分别取最大值和最小值即可：由于区间已经排序，则相邻两个区间的起点是前面区间的起点，重点则是两个区间终点的最大值。
LeetCode 56. 合并区间 LeetCode - 56. 合并区间 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
在上一篇文章 算法模式：前缀和 介绍了前缀和的算法模式。本篇文章，继续介绍数组相关的算法模式：改进的二分查找。
二分查找 二分查找相比每一个学过计算机算法的小伙伴都了解，时间复杂度是： \$\log_2N\$，是一个非常高效的数组查找算法。当然，前提是数组必须有序。过程如下：
图 1. 二分查找 LeetCode 704. 二分查找 就是一个标准的二分查找的算法题。代码如下：
/** * @author D瓜哥 · https://www.diguage.com * @since 2024-09-14 19:52:26 */ public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } 除了在排序数组中查找特定的值，二分查找还可以用于找边界和在旋转数组中查值。
找边界：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 LeetCode - 34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 \$log_2n\$ 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 示例 3：
输入：nums = [], target = 0 输出：[-1,-1] 提示：
在上一篇文章 算法模式：差分数组，本篇文章，继续介绍数组相关的算法模式：前缀和。
前缀和 前缀和可以简单理解为「数列的前 n 项的和」。具体过程如图所示：
图 1. 前缀和 这是一种重要的预处理方式，也就是需要额外的空间并且提前计算好这些值。如果使用得当，能大大降低查询的时间复杂度。
LeetCode 303. 区域和检索 - 数组不可变 LeetCode - 303. 区域和检索 - 数组不可变 给定一个整数数组 nums，处理以下类型的多个查询:
计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的元素的 总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right] )
Christopher Alexander 在 《建筑的永恒之道》 中说：“每一个模式描述了一个在我们周围不断重复发生的问题，以及该问题的解决方案的核心。这样，你就能一次又一次地使用该方案而不必做重复劳动。”受此影响，GoF 总结经验，写出了著名的 《设计模式》。
在算法中，也有很多类似设计模式这样的解决方案。D瓜哥称其为“算法模式”。后面，慢慢写文章一一介绍一下。由浅及深，今天先来介绍最简单的一个模式：差分数组。
差分数组 差分数组：差分数组就是原始数组相邻元素之间的差。举例如下：
下标 0 1 2 3 4 5 原始数组
5
9
2
6
5
3
差分数组
5
4
-7
4
-1
-2
差分数组是从原始数组构造出来的一个辅助数组，表示相邻元素直接的差值。可用于解决需要对数组一个区间内同时做加减的操作。比如：随着公交站各个站台上下车，判断公交车是否超载。
LeetCode 370. 区间加法 LeetCode - 370. 区间加法 假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。
在 单调栈实践（一）：入门 中对单调栈做了一个初步介绍，同时使用一个类似单调栈的题目做了入门的尝试。在本文中，将分析正式单调栈的使用案例。
实践： LeetCode 503. 下一个更大元素 II 单调栈主要就是为了解决选择下一个更大或者更小元素的相关问题。来看一下 LeetCode 503. 下一个更大元素 II。
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
如果熟悉单调栈，这道题的解法就一目了然：将数组从后向前遍历，如果单调栈栈顶元素比当前元素小，就将栈顶元素弹出；重复上述操作，直到栈顶元素大于当前元素，或者栈为空。如果栈不为空，则栈顶元素就是当前元素的后继更大元素。代码如下：
/** * LeetCode 503. 下一个更大元素 II * * @author D瓜哥 · https://www.diguage.com * @since 2024-07-05 23:08:39 */ public int[] nextGreaterElements(int[] nums) { if (nums == null || nums.length == 0) { return nums; } int[] result = new int[nums.length]; Deque<Integer> stack = new LinkedList<>(); // 只需要将数组“拼接”，遍历两遍数组，就可以解决所有元素后继更大元素的问题 // 从后向前遍历，再加上单调递增栈，就是时间复杂度为 O(n) 的解决方案 for (int i = 2 * nums.length - 1; i >= 0; i--) { // 取余即可获取当前需要处理的元素 int index = i % nums.length; // 在单调栈不为空的情况下，将栈中小于等于当前元素的值都弹出 while (!stack.isEmpty() && stack.peek() <= nums[index]) { stack.pop(); } // 剩下元素既是比当前元素大的后继元素。为空则是没有更大元素 // 这里还有一个隐含变量： // 由于栈是从后向前添加，则栈顶元素距离当前元素更近。 // 如果栈不为空，则栈顶元素就是符合条件的元素。 result[index] = stack.isEmpty() ? -1 : stack.peek(); stack.push(nums[index]); } return result; } 使用单调栈，一个关键点是确定使用的是单调递增栈，还是单调递减栈。 这里给大家留一个思考题：本文提供的答案是从后向前遍历数组。尝试一下从前向后遍历数组的解决方案。 实践： LeetCode 42. 接雨水 下面再来看一下： LeetCode 42. 接雨水。
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
最近刷 LeetCode 算法题中，遇到了一些需要单调栈的题目，就顺便学习了一下单调栈。分享出来，以备后续深入学习。
学习单调栈之前，先了解一些栈。
栈 Stack 栈是一个众所周知的线性数据结构，它遵循先入后出（First In Last Out，简称 FILO）或后入先出（Last In First Out，简称 LIFO）的访问顺序。操作示意图如下：
图 1. 入栈与出栈 单调栈 Monotonic Stack 单调栈是一种特殊的栈，添加了一些限制条件：内部元素只能是递增或递减的顺序存储；添加元素时，如果新元素不符合单调性，则将其内部元素弹出，直到符合添加时，才添加元素。根据元素顺序，又可分为单调递增栈和单调递减栈。操作示意图如下：
图 2. 单调递增栈 图 3. 单调递减栈 代码示例 在写代码时，一般基于 Deque 来实现，通常用到以下四个方法：
deque.isEmpty()：如果 deque 不包含任何元素，则返回 true，否则返回 false。因为要栈顶元素在满足要求的时候要弹出，所以需要进行空栈判断。有些场景，可能栈一定不会空的时候，就不需要该方法进行空栈判断。
deque.push(e)：将元素 e 入栈。
deque.pop()：将栈顶元素弹出，并返回当前弹出的栈顶元素。
deque.peek()：获取栈顶元素，不弹出。
// 定义一个单调栈 Deque<Integer> stack = new LinkedList<>(); // 第一个元素，直接添加 stack.push(0); // 这里存的是数组下标 for (int i = 1; i < nums.length; i++) { // 单调递增栈这里就是大于，即 nums[i] > nums[deque.peek()] if (nums[i] < nums[stack.peek()]) { stack.push(i); } else if (nums[i] == nums[stack.peek()]) { stack.push(i); // 此处除了入栈，在有些场景下，还有可能有其他操作 // .............. } else { // 循环比较，直到遇到当前元素小于栈顶的元素情况，跳出循环 // 单调递增栈，这里是小于，即nums[i] < nums[deque.peek()] while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { //主要逻辑 // ............ // ............ // 弹出栈顶元素 stack.pop(); } stack.push(i); } } 应用： LeetCode 155. 最小栈 来看一个 LeetCode 算法提： LeetCode 155. 最小栈，D瓜哥愿意称之为单调栈入门最佳试题。
文章还没写完，提前放出防止出现 404。稍后慢慢更新，敬请期待： 细说编码与字符集 - "地瓜哥"博客网
文章还没写完，提前放出防止出现 404。稍后慢慢更新，敬请期待： 细说编码与字符集 - "地瓜哥"博客网
文章还没写完，提前放出防止出现 404。稍后慢慢更新，敬请期待： 细说编码与字符集 - "地瓜哥"博客网
前段时间要研究 Hessian 编码格式，为了搞清楚 Hessian 对字符串的编码，就顺路查了好多编码和字符集的工作，理清了很多以前模糊的知识点。下面整理一下笔记，也梳理一下自己的思路和理解。
ASCII 码 计算机起源于美国，他们对英语字符与二进制位之间的对应关系做了统一规定，并制定了一套字符编码规则，这套编码规则被称为 American Standard Code for Information Interchange，简称为 ASCII 编码
其实，ASCII 最早起源于电报码。最早的商业应用是贝尔公司的七位电传打字机。后来于 1963 年发布了该标准的第一版。在网络交换中使用的 ASCII 格式是在 1969 年发布的，该格式在 2015 年发展成为互联网标准。点击 RFC 20: ASCII format for network interchange，感受一下 1969 年的古香古色。
ASCII 编码一共定义了128个字符的编码规则，用七位二进制表示（0x00 - 0x7F）, 这些字符组成的集合就叫做 ASCII 字符集。完整列表如下：
ASCII 码可以说是现在所有编码的鼻祖。
编码乱战及 Unicode 应运而生 ASCII 编码是为专门英语指定的编码标准，但是却不能编码英语外来词。比如 résumé，其中 é 就不在 ASCII 编码范围内。
随着计算机的发展，各个国家或地区，甚至不同公司都推出了不同的编码标准，比如中国推出了 GB2312、GBK 以及 GB18030；微软推出了 Windows character sets 。
在上一篇文章中，通过阅读 《In Search of an Understandable Consensus Algorithm》 前三节的内容，对论文的大致内容做了简介，简单说明了一下 Replicated state machines 的用途以及 Paxos 本身存在的问题。
4. Designing for understandability several goals in designing Raft:
it must providea complete and practical foundation for system building;
it must be safe under all conditions and available under typical operating conditions;
it must be efficient for common operations.
Our most important goal — and most difficult challenge — was understandability.
从这里可以看出，Raft 设计的初衷就是为了易于理解和便于构建。
There were numerous points in the design of Raft where we had to choose among alternative approaches. In these situations we evaluated the alternatives based on understandability.
前一段时间，在一次开组会的时候，给小组成员简单介绍了一下 Raft 协议。大概四年前读过 Raft 的论文，这次分享的时候，好多好多细节都忘了。所以，再次把 《In Search of an Understandable Consensus Algorithm》 这篇论文找出来，重读一遍，做个笔记和摘要，方便后续学习和复习。
Abstract Raft is a consensus algorithm for managing a replicated log. 开篇摘要就点出了 Raft 的特点： Raft 是一种管理复制日志的共识算法。
In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforcesa stronger degree of coherency to reduce the number of states that must be considered. 为了增强可理解性，Raft 将共识分解成几个关键元素，例如 Leader 选举，日志复制，以及安全性等；同时，为了降低需要考虑的状态的数量，还强制实施了更强的一致性。
1. Introduction Consensus algorithms allow a collection of machines to work as a coherent group that can survive the failures of some of its members.
