NowCoder - 召田最帅boy

NC32 求平方根

本文介绍了 NC32 “求平方根” 编程题的要求：实现 `int sqrt(int x)`，返回 x 的整数平方根（向下取整），数据范围 0 ≤ x < 2³¹−1，空间复杂度 O(1)，时间复杂度 O(log x)。示例说明输入 2 输出 1，输入 2143195649 输出 46294。提供的 Java 解法采用牛顿迭代法：从初始值 x 开始不断更新 `res = (res + x / res) / 2`，直至 `res ≤ x / res`，最终返回 `res` 即为所求平方根。

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

NC103 反转字符串

本文介绍了牛客网 NC103 “反转字符串” 题目，要求在 O(n) 时间、O(n) 空间内将长度不超过 1000 的字符串逆序输出。给出两种 Java 实现：一种手动遍历字符数组并倒序赋值，另一种直接使用 `StringBuilder` 的 `reverse()` 方法。示例演示了普通字符串和空串的输出情况。

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

NC61 两数之和

题目要求在整数数组中找到两数之和等于目标值的下标，返回基于1的升序下标，且保证必有解。数据规模 2≤len≤10⁵，要求空间 O(n)，时间 O(nlogn)（实际可用 O(n)）。解法采用哈希表：遍历数组时记录每个元素的值及其下标，检查 target‑当前值是否已存在于表中，若存在即返回对应的两个下标+1。文中提供了完整的 Java 实现代码。

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

NC88 寻找第K大

本文介绍了在整数数组中寻找第 k 大元素的实现要求：时间复杂度 O(n log n)，空间复杂度 O(1)，不去重且保证答案存在。题目提供了两种参考解法。方法一直接使用 Arrays.sort 对数组升序排序，返回下标 n‑K 处的值，即第 k 大元素。方法二利用最大堆（PriorityQueue 逆序）把所有元素加入堆中，随后弹出 K‑1 次，堆顶即为所求。文中还给出两组示例，说明包含重复元素时的取值规则。

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

NC15 求二叉树的层序遍历

本文介绍了二叉树层序遍历（广度优先搜索）的问题，实现要求返回每层节点值的列表。给定二叉树节点数 1≤n≤10^5，示例说明输入输出格式。解法采用队列逐层遍历：先将根节点入队，循环取队列大小确定当前层节点数，依次弹出节点记录值并将左右子节点加入队列，完成一层后将该层结果加入最终列表。代码实现基于 Java，时间复杂度 O(n)，空间复杂度 O(width)（即最大层宽）。

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 题目中实现二叉树的先序、中序和后序遍历。给定 0≤n≤1000、节点值 0≤val≤100 的二叉树，要求在 O(n) 时间、O(n) 空间内返回三种遍历序列。解法利用递归分别实现三种遍历，将访问顺序保存在 ArrayList 中，再通过流式转换得到 int[][] 结果。代码重点包括递归终止条件、ArrayList 与数组的相互转换以及遍历顺序的正确实现。

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

NC140 排序

本文介绍了牛客网 NC140 排序题目，要求对长度≤1000、元素值≤10⁹的整数数组实现升序排序，基本要求时间复杂度 O(n²)、空间 O(n)，进阶目标 O(nlogn) 与 O(n)。题目提供示例输入输出，并给出参考 Java 实现：先判空再调用 `Arrays.sort` 完成排序，返回排序后的数组。

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

NC78 反转链表

本文介绍了单链表反转的实现。题目要求在 O(n) 时间、O(1) 空间内，将长度不超过 1000 的链表从头结点开始全部逆序，空链表直接返回空。核心思路是遍历链表时使用三个指针：`nowNode` 指向当前结点，`preNode` 保存已反转部分的尾结点，`nextNode` 暂存原链表的后继。循环中依次把 `nowNode.next` 指向 `preNode`，并更新指针，直至遍历完全部结点，最终 `preNode` 即为新表头。代码实现简洁，符合题目时间、空间复杂度要求。

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

NC1 大数加法

文章介绍了“NC1 大数加法”题目：要求以字符串形式读取两个最多 100 000 位的非负整数，计算其和并返回字符串，时间复杂度需为 O(n)。文中给出示例说明输入输出规则，并提供了 Java 解法，利用 `BigInteger` 将字符串转为大整数后相加，最后返回结果的字符串形式，代码简洁直观，满足题目要求。

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

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

该题要求在一个非递减有序整数数组中找到唯一出现次数超过数组长度 25% 的元素。利用数组有序的特性，只需遍历至 `arr.length - arr.length/4`，检查当前位置与其后 `len = arr.length/4` 处的值是否相同；若相同则该值必满足出现次数超过四分之一，直接返回。代码实现简洁，时间复杂度 O(n)，空间复杂度 O(1)。

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

70. 爬楼梯

本文介绍了经典的爬楼梯问题：给定 n 阶台阶，每次可爬 1 或 2 阶，求到达顶层的不同方式数。示例说明 n=2 时有 2 种方案，n=3 时有 3 种方案。约束 1 ≤ n ≤ 45。提供的 Java 解法采用动态规划，初始化 dp[1]=1、dp[2]=2，递推公式 dp[i]=dp[i‑1]+dp[i‑2]，最终返回 dp[n]，时间复杂度 O(n)，空间 O(n)。

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