算法 - 召田最帅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 反转字符串

本题要求编写程序接受一个长度不超过1000的字符串，输出其反转结果，空间复杂度 O(n)，时间复杂度 O(n)。示例：输入 "abcd" 返回 "dcba"，空串返回空串。提供两种实现：①将字符串转为字符数组，逐位赋值为对应的倒序字符后构造新字符串；②直接利用 `StringBuilder(str).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大

本文介绍了 NC88 “寻找第K大” 的算法实现。题目要求在整数数组中（含重复元素）返回第 K 大的数，时间复杂度 O(nlogn)，空间复杂度 O(1)。示例说明不去重的第 K 大可能与去重后不同。提供两种参考代码：一种直接对数组使用 `Arrays.sort`，返回 `a[n‑K]`；另一种利用大根堆（PriorityQueue）逐个弹出前 K‑1 大元素后取顶部即为答案。

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

NC15 求二叉树的层序遍历

本文介绍了二叉树层序遍历的实现。给定节点数 ≤10⁵ 的二叉树，要求按层从左到右返回每层节点值的列表。解法采用广度优先搜索，使用队列记录当前层节点数，遍历时依次弹出节点并将其左右子节点入队，完成一层后将该层结果加入最终列表。代码实现为 Java 方法 `levelOrder(TreeNode root)`，时间复杂度 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 实现二叉树先序，中序和后序遍历

本文介绍了在二叉树上实现先序、中序和后序遍历的解法，要求时间、空间均为 O(n)。通过递归分别完成三种遍历，将节点值存入 ArrayList，再转为 int[][] 返回。代码重点包括递归终止条件、ArrayList 与数组的转换以及结果矩阵的构造，适用于节点数 ≤1000、值范围 0~100 的树。

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 阅读