NowCoder - 召田最帅boy

NC137 表达式求值

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

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

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

本文介绍了 NowCoder “NC31 第一个只出现一次的字符”题目：在长度 ≤10000、仅含字母的字符串中，找出第一个仅出现一次的字符并返回其下标（从 0 起），若不存在返回 -1。要求时间、空间均为 O(n)。提供的 Java 解法使用 HashMap 统计字符出现次数，随后遍历字符串定位首个计数为 1 的字符，实现了上述复杂度。

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

NC217 给表达式添加运算符

文章介绍了在仅含数字的字符串中插入 “+”、 “-”、 “*” 三种二元运算符，使表达式的计算结果等于给定目标值的问题。给出长度 ≤10 的字符串和 |target|≤10⁹ 的约束，并通过示例说明期望输出。核心解法采用深度优先搜索回溯：从左到右枚举每段数字的取值长度，避免前导零；在非首位位置尝试三种运算符，并利用累计结果 `res` 与最近乘积 `mul` 处理乘法的优先级（`res - mul + mul*val`）。递归结束时若累计结果等于目标即记录表达式。代码实现了上述思路并返回所有符合条件的表达式集合。

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

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

本文介绍了“只出现一次的数字(二)”题目：在整数数组中唯一出现一次的数其余均出现三次，要求找出该唯一数。给出数组规模 1≤n≤10⁵、元素取值范围 [-2³¹,2³¹‑1] 的约束。解法采用位计数法：遍历数组，对每个位累计出现次数，随后对 3 取模得到唯一数的各位并重构结果。代码实现为 O(n) 时间、O(1) 额外空间的 Java 方法。

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

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

文章介绍了“之字形层序遍历”二叉树的实现要求：从根层左→右，下一层右→左交替进行，时间空间均为O(n)。给出题目示例及输入输出格式，并提供 Java 解法。思路是使用普通队列进行层次遍历，记录每层节点值后根据层号（通过布尔 flag）决定是否反转当前层的结果，随后加入最终列表。代码实现包括空树处理、节点入队、层大小计数以及利用 `Collections.reverse` 完成奇数层的逆序，满足题目全部约束。

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

BM83 字符串变形

文章介绍了“BM83 字符串变形”题目：给定长度 n （1≤n≤10⁶）的只含大小写字母和空格的字符串，需要将单词顺序反转并对每个字符切换大小写，例如 “Hello World” → “wORLD hELLO”。题目要求时间、空间均为 O(n)。文中给出示例及 Java 解法，思路是使用 `split` 按空格切分（保留空串），从右向左遍历每个子串，利用 `Character.isUpperCase` 与 `toLowerCase`/`toUpperCase` 实现大小写转换并拼接空格，最终返回变形后的字符串。

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

NC10 大数乘法

本文介绍了“NC10 大数乘法”练习：读取两个字符串形式的非负整数（0≤n≤10^1000），要求在 O(n) 空间和 O(n²) 时间内返回它们的乘积字符串。示例演示了普通乘法及零乘情况。给出 Java 参考实现，直接利用 `java.math.BigInteger` 将字符串转为大整数相乘，再转回字符串返回。

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

NC109 岛屿数量

本文介绍了在二维01矩阵中统计岛屿数量的问题，岛屿由上下左右相邻的‘1’组成。给出示例输入输出后，提供基于深度优先搜索（DFS）的 Java 解法：遍历矩阵，遇到‘1’即计数并递归将其连通的所有‘1’置为‘0’，确保每个岛屿只计一次。代码实现包括主函数 `solve` 与辅助递归 `dfs`，并处理空矩阵等边界情况。

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

NC54 三数之和

本文介绍了“NC54 三数之和”题目：在长度不超过3000、元素绝对值≤100的数组中寻找所有满足 a+b+c=0 的不重复三元组。要求时间复杂度 O(n²)、空间复杂度 O(n²)。解法先对数组排序以便去重，然后遍历每个元素 i，使用双指针 j、k 在其右侧搜索满足和为零的组合；在找到合法组合后继续跳过相同的 j 值以避免重复。代码实现基于 Java，包含边界检查、排序、去重及指针移动逻辑，能够返回题目示例中的正确结果。

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

NC127 最长公共子串

本文介绍了在长度不超过5000的两个字符串中寻找唯一最长公共子串的问题，要求时间、空间均为 O(n²)。示例输入 "1AB2345CD" 与 "12345EF" 输出 "2345"。解法采用动态规划：使用一维 dp 数组逆序遍历第二个字符串，若对应字符相等则 dp[j+1]=dp[j]+1，否则置为 0；在遍历过程中记录最长子串的长度和其在第一个字符串中的结束位置，遍历结束后通过 substring 截取并返回该子串。文中给出完整的 Java 实现，满足题目约束。

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

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

文章介绍了在链表中删除倒数第 n 个节点的经典题目，要求时间复杂度 O(n) 、空间复杂度 O(1)。通过快指针先前进 n 步，若此时已到链表末尾则删除头节点；否则快慢指针同步向后移动，直至快指针指向最后一个节点，此时慢指针的下一个即为待删除节点，直接跳过即可。代码实现了上述双指针思路，兼顾空链表和 n 为0 的情况，返回处理后的链表头指针。

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

NC52 有效括号序列

给定仅含 '('、')'、'{'、'}'、'['、']' 的字符串，判断其是否为合法括号序列，即每种左括号必须按正确顺序匹配相应右括号。要求时间复杂度 O(n)、空间复杂度 O(n)。解法使用栈：遍历字符，遇左括号时将对应的期望右括号压栈，遇右括号时检查栈顶是否相同并弹出；若不匹配或栈为空则返回 false。遍历结束后，栈为空则序列合法。代码实现简洁，满足题目约束。

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