算法

浏览该分类下的所有文章

链表

本文围绕单向链表的常见面试题展开，首先介绍使用快慢指针判断链表是否成环的原理；随后指出在哈希桶中使用链表存储会导致查找、插入、删除效率低下；接着给出奇数位升序、偶数位降序链表转为整体升序的思路——按奇偶位拆分为两链表、将偶数链表逆序再合并，并提供完整实现代码；随后展示 O(1) 额外空间的随机指针链表复制算法；最后给出标准的单链表反转实现。整体阐述了链表环检测、性能缺陷、排序合并、深拷贝及反转等关键技术要点。

2023-03-01 18:05:02 阅读

数组

本文介绍了几道常见的数组面试题及其核心思路：① 用层层交换实现二维矩阵顺时针旋转90°；② 利用全体异或找出唯一不成对的元素；③ 通过哈希表在 O(n) 时间内求和为 S 的两数下标；④ 使用 Kadane 算法求连续子数组最大和；⑤ 采用快排划分（或堆）实现前 K 大元素的快速查找。每个实现均给出关键代码示例。

2023-03-01 18:06:42 阅读

排序

本文先给出Java实现的冒泡排序代码示例，随后列出常见排序算法分类：插入、交换、选择、归并、分配等，并简要说明各子类。接着阐述归并排序的分治合并过程、堆排序通过构建大（小）顶堆并不断取堆顶的原理。再介绍在数据流中实时获取中位数的做法：使用最大堆保存左半部分、最小堆保存右半部分，插入为O(log n)，取中位数为O(1)。最后给出快速排序的划分思路及双指针交换过程。

2023-03-01 18:08:45 阅读

堆与栈

文章阐述了 Java 内存划分：堆区存放对象实例，由所有线程共享，需通过 new 分配，由垃圾回收器回收；栈区为每线程私有，仅存基本类型值和对象引用，由编译器自动分配释放，访问速度快；方法区（静态区）存放类信息、static 与全局变量，同样共享。对比堆与栈：堆容量大、手动/GC 分配、访问相对慢；栈容量小、自动分配、后进先出、访问快。并通过字符串创建示例说明两者在实际使用中的差异。

2023-03-01 18:10:11 阅读

队列

Java PriorityQueue 是基于堆实现的无界队列，元素按自然顺序或自定义比较器排序。创建时可指定比较器，队列不接受 null 值。它不是线程安全的，入队和出队的时间复杂度均为 O(log n)。

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

高级算法

文章介绍了几种常见的面试算法及实现要点。首先阐述了LRU（最近最少使用）缓存的原理、get/put 接口及其命中率、复杂度等特性。随后简述逆波兰（后缀）表达式无需括号的优势。接着给出基于 MD5 的 URL 短链压缩思路。随后详细说明 SnowFlake 分布式全局唯一自增 ID 的 64 位结构、优缺点。最后提供了 LFU（最不经常使用）缓存的 O(1) 时间复杂度实现代码，包括节点和哈希表的设计。

2023-03-01 18:15:09 阅读

NC26 括号生成

本文介绍了“括号生成”问题：给定 n 对括号，生成所有合法的组合，如 n=3 时的五种排列。要求空间 O(n)、时间 O(2^n)，n 的取值范围 0≤n≤10。提供了 Java 解法，使用递归回溯遍历，维护已使用的左、右括号数；当左括号未用完时继续放“(”，当右括号少于左括号且未用完时放“)”。当左右括号均用完即得到一个合法组合并加入结果列表。代码实现简洁，符合题目复杂度要求。

2022-10-28 16:52:44 阅读

NC93 设计LRU缓存结构

本文介绍了在容量固定的情况下实现 O(1) 时间复杂度的 LRU（最近最少使用）缓存。题目要求提供构造函数、`get(key)` 与 `set(key,value)` 两个接口，并在缓存超出容量时淘汰最久未使用的键值对。核心实现思路是结合哈希表快速定位节点和双向链表维护使用顺序：每次 `get` 或 `set` 都将对应节点移动到链表头部；插入新键时若容量已满则删除链表尾部节点。代码给出 Java 实现，包括节点类、插入、移动、删除等辅助方法，完整满足题目 O(1) 的性能要求。

2022-09-09 09:05:09 阅读

NC57 反转数字

题目要求在不使用 64 位整数的前提下，对 32 位有符号整数的数字部分进行翻转，保留符号位，若翻转后超出 \[-2³¹, 2³¹‑1\] 范围则返回 0。解法思路是循环取出原数的最低位（x % 10），累乘 10 并加到结果 res 中，同时将 x 除以 10。为判断溢出，使用 long 类型暂存结果，最后检查 `(int)res == res`，若相等返回转化后的 int，否则返回 0。示例包括正数、负数、含尾零以及溢出情况。

2022-09-07 18:23:04 阅读

NC35 编辑距离(二)

本文介绍了编辑距离的变形问题：在给定插入、删除和替换三个操作代价的前提下，求将字符串 str1 编辑为 str2 的最小总代价。要求时间复杂度为 O(n²)，空间复杂度为 O(n)。文章通过动态规划构建二维数组 dp[i][j]，表示将 str1 前 i 个字符转换为 str2 前 j 个字符的最小代价，初始化第一行和第一列分别对应纯插入或删除的成本，随后递推考虑字符相等、插入、删除和替换四种情况，最终返回 dp[len1][len2]。提供了完整的 Java 实现代码示例，并给出两组示例输入输出验证算法正确性。

2022-09-05 16:43:03 阅读

NC38 螺旋矩阵

本题要求对任意 m × n 矩阵按顺时针螺旋顺序输出所有元素，数据规模 0 ≤ m,n ≤ 10，元素绝对值 ≤ 100，时间、空间均需 O(mn)。解法采用四个边界指针 left、right、up、down，循环在边界未交叉时依次遍历上边从左至右、右边从上至下、下边从右至左、左边从下至上，并在每次遍历后收缩相应边界，直至完成。代码实现简洁，先排除空矩阵，随后在 while 循环中按上述顺序加入结果列表，满足题目要求。

2022-09-04 12:37:38 阅读

NC20 数字字符串转化成IP地址

该题要求将仅含数字的字符串切分为四段，使每段在 0~255 范围内，形成合法 IP 地址并返回所有可能组合。长度限制为 0–12，需采用深度优先搜索+回溯遍历所有切割点，剪枝条件包括段长度不超过 3、首位为 0 时只能为单个 0、数值不超过 255。代码使用 `process` 递归遍历，`path` 保存当前分段，满足四段且遍历完字符串时加入结果；`isValid` 实现上述合法性检查。整体空间、时间复杂度均为 O(n!)，符合题目要求。

2022-08-18 19:19:52 阅读