NowCoder - 召田最帅boy

NC137 表达式求值

本题要求实现一个整数表达式求值器，支持加、减、乘以及圆括号，输入长度不超过100，结果保证在整型范围，时间空间均要求 O(n)。解法采用双栈：一个存放数字，一个存放运算符，并使用映射记录运算符优先级。遍历字符数组时，遇 '(' 入符号栈；遇 ')' 计算至最近的 '('；遇数字连续读取形成完整的整数入数字栈；遇运算符先比较栈顶运算符的优先级，若不低于当前运算符则立即计算。为处理负数在表达式开头或左括号后加入 0。遍历结束后统一计算剩余运算，即得到最终结果。代码实现了上述流程并提供了 `calc` 与 `isNumber` 辅助函数。

2022-08-05 12:01:08 阅读

NC31 第一个只出现一次的字符

本文介绍了在长度≤10000、仅含字母的字符串中查找首个仅出现一次字符并返回其索引（若不存在返回-1）的算法要求，时间复杂度O(n)、空间复杂度O(n)。示例：“google”返回4，“aa”返回-1。提供的Java解法先用HashMap统计每个字符出现次数，再遍历字符串找到首次出现次数为1的字符并返回其下标，若未找到则返回-1。

2022-08-08 10:18:24 阅读

NC217 给表达式添加运算符

文章介绍了在仅含数字的字符串中插入二元运算符“+、-、*”，使表达式计算结果等于给定目标值的问题，并给出 Java 实现。核心思路是深度优先搜索遍历所有切分方式，使用回溯在每个数字前插入运算符；通过维护当前累计结果 `res` 与最近乘法因子 `mul`，在遇到乘法时进行结果修正以保证运算顺序正确。代码中处理了前导零限制、表达式构建以及最终结果收集，返回所有满足目标值的表达式列表。

2022-08-08 20:34:48 阅读

NC227 只出现一次的数字(二)

本文介绍了“只出现一次的数字（二）”题目：在一个整数数组中，唯一出现一次的数其余均出现三次，要求找出该数。数据规模 up to 10⁵，整数范围为 32 位有符号。给出一种位计数解法：用长度为 32 的数组统计每个位上 1 的出现次数，对每个位取模 3，余 1 的位即为唯一数的对应位，最后合成结果返回。代码实现基于 Java，时间 O(n·32)，空间 O(32)。

2022-08-07 12:21:40 阅读

NC14 按之字形顺序打印二叉树

本文介绍了二叉树的之字形层序遍历（奇数层从左至右，偶数层从右至左）的实现要求：时间、空间均为 O(n)。通过广度优先搜索使用队列逐层遍历，记录每层节点值后利用布尔标记在奇数层调用 `Collections.reverse` 实现顺序翻转，最终返回二维列表。文中给出题目描述、示例输入输出以及完整的 Java 解法代码，代码在空树时直接返回空列表，保证符合题目约束。

2022-08-01 11:32:10 阅读

BM83 字符串变形

本文介绍了牛客网 BM83 “字符串变形”题目：给定长度 n （1≤n≤10⁶）的仅含字母和空格的字符串，需要将由空格分隔的单词顺序反转，并将每个字符的大小写互换，例如 “Hello World” → “wORLD hELLO”。题目要求时间、空间均为 O(n)。文中提供了示例输入输出，并给出 Java 实现思路：先使用 `split` 按空格分割（保留空串），从右向左拼接每个子串的大小写转换结果，单词之间补空格；大小写转换在 `reverse` 方法中完成。整体代码实现简洁，满足题目约束。

2022-08-11 09:17:02 阅读

NC10 大数乘法

本文介绍了 NC10 大数乘法题目，要求读取两个表示非负整数的字符串（长度可达 1000 位），计算其乘积并以字符串返回。限定空间复杂度 O(n)、时间复杂度 O(n²)。示例包括 11×99=1089 与 1×0=0。提供的参考解法直接利用 Java 的 `BigInteger` 类，将输入字符串转换为 `BigInteger`，调用 `multiply` 完成运算，再转为字符串返回。

2022-07-28 11:49:37 阅读

NC109 岛屿数量

本文介绍了“岛屿数量”问题：给定只含字符‘0’和‘1’的矩阵，‘1’表示陆地，四方向相连的‘1’构成同一岛屿，要求统计岛屿总数。示例说明输入输出关系。解法为遍历矩阵，遇到‘1’时计数并通过深度优先搜索（DFS）将该岛屿的所有相连‘1’标记为‘0’，防止重复计数。代码实现包括主函数 `solve` 统计岛屿数，以及递归 `dfs` 完成四邻域扩展，时间复杂度 O(n·m)。

2022-08-04 11:35:46 阅读

NC54 三数之和

本文介绍了“NC54 三数之和”题目：在长度不超过3000、元素绝对值≤100的整数数组中，找出所有唯一的三元组 (a,b,c) 使 a+b+c=0，且三元组内部顺序不影响，结果不能出现重复。解法先对数组排序，然后遍历每个元素作为第一个数，使用双指针在其右侧寻找满足条件的另一对数；通过跳过相同值实现去重，时间复杂度 O(n²)，空间复杂度 O(n²)。代码示例展示了排序、去重、指针移动的完整实现。

2022-07-27 20:13:08 阅读

NC127 最长公共子串

本文介绍了求解两个字符串最长公共子串（LCS）的题目，要求在长度不超过5000的字符串上实现 O(n²) 时间与空间复杂度的算法。核心思路是使用动态规划，将二维 DP 表压缩为一维数组 dp，遍历 str1 的每个字符时逆序遍历 str2，若字符相等则 dp[j+1]=dp[j]+1，否则置零。过程中记录当前最长子串的长度 maxLength 和其在 str1 中的结束位置 maxLastIndex，最终通过 substring 提取并返回对应子串。代码实现简洁，符合题目唯一解的前提。

2022-07-25 09:30:27 阅读

NC53 删除链表的倒数第n个节点

本文介绍了在单链表中删除倒数第 n 个节点的实现思路与代码。要求空间复杂度 O(1) 且时间复杂度 O(n)。采用快慢指针（双指针）技巧：先让快指针先前进 n 步，若此时已到链表末尾则删除头节点；否则同步移动快慢指针直至快指针到达末尾，慢指针的下一个即为待删除节点，将其跳过即可。文中给出完整的 Java 实现并说明了边界条件的处理。

2022-07-24 23:31:39 阅读

NC52 有效括号序列

本文介绍了判断仅含 '('、')'、'{'、'}'、'['、']' 六类字符的字符串是否为合法括号序列的问题，要求时间、空间复杂度均为 O(n)。核心思路是使用栈：遍历字符时，遇左括号将对应的右括号压入栈；遇右括号时检查栈顶是否匹配并弹出，若不匹配或栈为空则返回 false。遍历结束后，栈为空即为合法序列。代码实现基于 Java 的 `Stack<Character>`，通过上述方式实现了 O(n) 的解法。

2022-07-24 23:16:55 阅读