NowCoder - 召田最帅boy

NC32 求平方根

本文介绍了在 O(log x) 时间、O(1) 空间复杂度约束下实现整数平方根（向下取整）的算法。通过牛顿迭代法先设初始值为 x，不断更新 res = (res + x/res)/2，直至 res ≤ x/res 为止，即得到满足 floor(√x) 的整数结果。代码实现简洁，兼顾 x 为 0 或负数的边界处理，并给出示例输入输出验证。

2022-07-13 20:20:31 阅读

NC103 反转字符串

本文介绍了 NowCoder 练习题 NC103——反转字符串的实现要求。题目要求编写程序接收长度不超过 1000 的字符串，输出其逆序结果，空间复杂度 O(n)，时间复杂度 O(n)。提供了两种 Java 解法：方法一通过字符数组遍历并逐位赋值实现逆序；方法二直接利用 `StringBuilder` 的 `reverse()` 方法简化实现。示例演示了输入 "abcd" 输出 "dcba"，以及空字符串的处理。

2022-07-12 21:19:09 阅读

NC61 两数之和

本文介绍了NowCoder “两数之和”练习：给定整数数组 numbers 和目标值 target，要求在数组中找到两数之和等于 target 的下标（从1起始），返回按升序排列的下标。数据规模为 2 ≤ len(numbers) ≤ 10⁵，要求空间复杂度 O(n) 且时间复杂度 O(n log n)。示例说明了输入输出格式。提供的Java解法采用哈希表存储已遍历元素的值及其下标，在遍历过程中查找 target - numbers[i] 是否已出现，若找到即返回对应下标+1，实现线性时间和线性空间的求解。

2022-07-12 10:36:33 阅读

NC88 寻找第K大

本文介绍了 NC88 “寻找第 K 大” 的算法实现。题目要求在 O(n log n) 时间、O(1) 额外空间内，返回整数数组中第 K 大的元素（保留重复值）。示例说明了不去重的要求。提供了两种解法：① 直接使用 `Arrays.sort` 排序后取下标 `a[n‑K]`；② 利用最大堆（`PriorityQueue` 逆序）插入全部元素，弹出 K‑1 次后取堆顶。两种方法均满足题目复杂度限制。

2022-07-12 09:51:23 阅读

NC15 求二叉树的层序遍历

本文介绍了二叉树层序遍历的实现。题目要求返回每层节点值的列表，节点数可达10⁵。解法采用广度优先搜索（BFS），利用队列按层级逐个弹出节点，记录当前层的节点数（queue.size），将左、右子节点依次入队，并将节点值加入本层列表。遍历结束后返回包含所有层列表的二维数组。代码实现简洁，时间复杂度 O(n)，空间复杂度 O(n)。

2022-07-10 22:34:11 阅读

NC119 最小的K个数

该题要求在长度 n 且可能含重复元素的数组中，找出不去重的最小 k 个数，返回任意顺序。约束为 0≤k,n≤10000，元素值在 0~1000 之间，空间 O(n)，时间 O(n log n)。思路是先对数组使用 Arrays.sort 排序，再取前 k 个元素放入 ArrayList 返回。示例包括普通情况、k 为 0 以及含重复值的数组。

2022-07-10 22:06:37 阅读

NC45 实现二叉树先序，中序和后序遍历

本文介绍了牛客网 NC45 题目——实现二叉树的先序、中序和后序遍历。要求在 O(n) 时间、O(n) 空间内完成，对空树返回空数组。解法使用三个 `ArrayList<Integer>` 分别存储三种遍历结果，递归实现 `firstOrder`、`middleOrder`、`laterOrder`，遍历结束后通过 `toIntArray` 将列表转为 `int[]` 并组装成 `int[3][]` 返回。代码简洁明了，重点在于确定存储结构、递归遍历逻辑以及列表转数组的实现。

2022-07-10 21:07:25 阅读

NC140 排序

题目要求对长度不超过 1000、元素值在 0~10⁹ 范围的整数数组进行升序排序，基本实现需满足 O(n²) 时间、O(n) 空间，进阶要求 O(nlogn) 时间、O(n) 空间。示例展示了输入输出形式，鼓励实现多种排序算法。文中给出 Java 示例代码，直接对非空数组调用 `Arrays.sort` 完成排序并返回结果。

2022-07-07 11:46:55 阅读

NC78 反转链表

本文介绍了单链表原地反转的实现。给定长度不超过1000的链表，要求在 O(n) 时间、O(1) 额外空间内完成反转，空链表直接返回空。核心思路是遍历链表，用三个指针依次记录当前节点、前驱节点和后继节点，在遍历过程中将当前节点的 next 指向前驱，实现逐步翻转。遍历结束后，前驱节点即为新表头。文中提供了完整的 Java 实现代码，代码结构简洁，易于理解。

2022-07-07 11:10:55 阅读

NC1 大数加法

文章介绍了一个大数加法题目：输入两个仅含数字的字符串（长度≤100000），要求在 O(n) 时间内返回它们的和，结果仍为字符串。示例展示了普通加法和空串情况。提供的参考代码采用 Java 的 `BigInteger`，将字符串转换为 `BigInteger` 后直接相加，再转回字符串输出，满足题目要求。

2022-07-06 19:38:23 阅读

1287. 有序数组中出现次数超过25%的元素

给定一个非递减有序整数数组，保证恰好有一个元素出现次数超过数组长度的25%。利用有序性，只需检查每个位置 i 与 i+⌊n/4⌋ 处的值是否相同，若相同则该元素必满足条件，直接返回。代码实现为一次遍历 O(n) 时间、O(1) 空间，若未提前找到则返回 arr[0]（题目保证必有答案）。

2022-03-31 11:39:43 阅读

70. 爬楼梯

本文介绍了经典的爬楼梯问题：给定需要爬 n 阶楼梯，每次可迈 1 或 2 步，求到达顶层的不同方式数。通过示例说明 n=2 时有 2 种方案，n=3 时有 3 种方案，并给出约束 1 ≤ n ≤ 45。解决思路采用动态规划，利用递推关系 f(i)=f(i‑1)+f(i‑2)，并用数组 dp 保存中间结果，特殊处理 n≤2 的情况直接返回 n。代码实现简洁高效，时间复杂度 O(n)，空间复杂度 O(n)。

2022-03-31 11:11:13 阅读