算法

浏览该分类下的所有文章

NC3 链表中环的入口结点

本文介绍了在长度不超过 10000 的单链表中检测环并找出环入口节点的方法。要求空间 O(1)、时间 O(n)。通过快慢指针判断是否存在环，若相遇则说明有环；随后让一个指针回到链表头，与相遇点同步前进，首次相遇即为环入口。代码实现包括 `hasCycle` 用于返回相遇节点，`EntryNodeOfLoop` 返回环入口，若无环返回 null。示例演示了有环、无环以及单节点环的情况。

2022-07-24 12:39:58 阅读

NC22 合并两个有序的数组

本文介绍了在 NowCoder 上的 NC22 题目——将有序整数数组 B 合并到已预留足够空间的有序数组 A 中，使 A 成为整体升序。要求在 A 的前 m 位已有序，B 的前 n 位已有序，且不返回新数组，只需在原 A 中完成合并。文章给出示例说明输入输出，并提供了 Java 实现：使用双指针遍历 A、B，比较取较小元素填入新建的临时数组 sorted，遍历结束后将 sorted 内容拷贝回 A，实现了在 O(m+n) 时间、O(m+n) 额外空间下的合并。

2022-07-23 23:17:36 阅读

NC4 判断链表中是否有环

本文介绍了判断单链表是否存在环的问题，要求空间 O(1)、时间 O(n)。通过 Floyd 快慢指针法实现：若链表为空直接返回 false；否则让快指针每次走两步、慢指针走一步，若两指针相遇则说明有环，遍历至末尾仍未相遇则无环。文中提供了题目描述、示例及完整 Java 实现代码。

2022-07-23 08:20:44 阅读

盛水最多的容器

给定长度为 n 的数组 height，数组每个元素表示坐标轴上对应点的高度，要求在任意两点之间形成不倾斜的容器，计算该容器能够容纳的最大水量。若 n<2 则返回 0，且结果保证不超过 2³¹‑1。解法采用双指针：左指针指向数组首部，右指针指向末尾，计算当前宽度 (right‑left) 乘以两端较小高度得到容量，并用 max 维护最大值。随后移动较短边的指针，以期找到更高的边可能产生更大容量，直至左右指针相遇。时间复杂度 O(n)，空间复杂度 O(1)。

2025-09-09 11:51:29 阅读

分糖果问题

本文介绍了“分糖果”问题：给定孩子们的得分数组，要求每个孩子至少分到一颗糖，且相邻得分更高的孩子糖数必须更多，返回最少糖果总数。要求时间 O(n)、空间 O(n)。解法采用双向遍历的动态规划：首次从左至右若得分递增则糖数加一；随后从右至左若得分递减且当前糖数不大于右侧，则更新为右侧+1。最终累加所有糖数即为答案。代码实现基于上述思路，时间复杂度线性，空间使用额外数组存储每个孩子的糖数。

2025-09-09 11:40:26 阅读

编辑距离(一)

本文介绍了求两个仅含小写字母的字符串之间最少编辑操作数的问题，操作包括插入、删除和修改。给出示例说明计算过程，并提供基于动态规划的 O(n·m) 解法。实现中使用两行滚动数组 dp，分别记录当前行和前一行的最优值，通过字符相等与否分别处理转移，最终返回 dp[str1.length % 2][str2.length] 即编辑距离。

2025-09-09 11:25:19 阅读

浅谈分布式唯一ID生成方案

分布式唯一ID需全局唯一、有序、高可用且不泄露信息。文中比较了UUID、数据库自增、Redis计数、Zookeeper节点版和Snowflake（64位结构、趋势递增但受时钟回拨影响）。随后介绍号段模式及美团Leaf、滴滴Tinyid、微信序列号等实现，降低DB压力并提升容错。最后阐述Snowflake改进（多时间线、Leaf‑snowflake、百度UidGenerator），处理时钟回拨，兼顾唯一与有序。

2022-07-18 18:29:01 阅读

NC69 链表中倒数最后k个结点

本文介绍了在单链表中查找倒数第k个节点的题目及实现。要求时间 O(n)，进阶空间 O(1)。采用快慢指针法：快指针先走 k 步，随后与慢指针同步前进，快指针到达链表末尾时慢指针即指向倒数第k个节点；若链表长度不足 k 则返回空链表。文中给出完整的 Java 代码实现。

2023-04-04 10:31:58 阅读

NC21 链表内指定区间反转

本文介绍了链表区间反转问题：在长度≤1000的单链表中，将第 m 到第 n 个节点的子序列逆序，要求时间O(n)。示例 1→2→3→4→5，m=2、n=4，结果为1→4→3→2→5。文章给出一种实现思路：遍历链表，将目标区间的节点值压入栈；再次遍历时弹栈并覆盖原节点值，从而完成逆序。该代码时间复杂度为O(n)，但使用了栈导致空间复杂度为O(n)，未满足进阶要求的O(1)空间。

2023-04-03 10:39:51 阅读

哈希

hashCode() 与 equals() 决定了键在 HashMap 中的定位与比较，若实现不当会导致冲突或误判相等，直接影响集合的准确性。HashMap 以键值对存储，使用键的 hashCode 计算数组下标并在冲突时通过链表或 JDK8 起的红黑树保存，支持 put/get 的快速访问；容量与负载因子决定扩容时机，扩容后桶数保持 2 的幂次。HashMap 不是同步的，key、value 可为 null，映射无序。构造一致性哈希时在 2³² 环上放置节点，按键的 hash 顺时针定位最近节点，提升扩缩容时的路由稳定性。作为键的对象必须保证 hashCode 在生命周期内不变。HashSet 仅保存唯一元素，内部基于 HashMap 实现，存取无序。

2023-03-01 18:00:04 阅读

树

本文围绕树结构的常见面试考点展开，首先说明 TreeSet 与 TreeMap 在排序时分别要求元素或键实现 Comparable 接口，或在 Collections.sort 中提供 Comparator 实现自定义比较；随后给出实现 Comparable 的 Student 示例以及 TreeSet 的使用演示。接着介绍二叉树的层序遍历、深度求解（递归与非递归两种实现）以及计算任意两节点最长路径的思路，并提供相应的 Java 代码片段。最后简要比较 B+ 树与 B‑树：前者内部节点不存数据、叶层链表化、查询复杂度固定为 log n，适合外部存储和区间查询；后者键值同存、查询复杂度随键位置变化。

2023-03-01 18:01:43 阅读

遍历

本文通过两个 Java 示例说明遍历的基本思想。第一个示例实现二叉树的 Z 字型层序遍历，利用队列逐层访问节点并通过布尔标记在奇偶层之间切换顺序，必要时对当前层结果进行反转。第二个示例演示文件系统的递归遍历，使用 `File` 类遍历指定目录，若遇文件直接输出名称，若遇子目录则递归调用以遍历其全部子文件，实现对整个文件夹及其子文件夹的完整遍历。两段代码均突出遍历的实现方式和常用技巧。

2023-03-01 18:03:34 阅读