算法 - 召田最帅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 只出现一次的数字(二)

本文介绍了“只出现一次的数字(二)”题目：在整数数组中唯一出现一次的数其余均出现三次，要求找出该数。给出 Java 实现思路：利用 32 位计数数组统计每个位上 1 的出现次数，随后对 3 取模得到唯一数的对应位，最终合成答案。代码简洁、时间 O(n)、空间 O(1)。

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

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

文章介绍了二叉树之字形层序遍历的实现要求：在 O(n) 时间、O(n) 空间内返回每层节点值，奇数层从右到左、偶数层从左到右。给出示例输入输出，并提供 Java 代码。解法采用广度优先搜索，用队列按层遍历节点，使用布尔标记决定当前层是否反转，必要时调用 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 岛屿数量

给定一个仅含字符'0'和'1'的二维矩阵，'1'表示陆地，'0'表示海洋，若上下左右相邻的'1'属于同一岛屿。任务是统计矩阵中岛屿的数量。文章首先说明了题目要求和示例，随后给出基于深度优先搜索（DFS）的解法：遍历矩阵，遇到'1'时计数并递归将其上下左右相连的所有'1'置为'0'，从而将整座岛屿“擦除”。遍历结束后计数即为岛屿总数。代码实现了 `solve` 方法进行遍历计数，`dfs` 方法完成四方向的递归标记，能够处理空矩阵等边界情况。

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

NC54 三数之和

本文介绍了“NC54 三数之和”算法题：在长度≤3000、数值绝对值≤100的数组中找出所有满足 a+b+c=0 的不重复三元组。要求时间复杂度 O(n²)，空间复杂度 O(n²)。解法先对数组排序，利用双指针在固定第一个元素后搜索剩余两数，遇到和为0时记录并跳过重复值，和小于0时左指针右移，和大于0时右指针左移。代码实现基于 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 一定有效。解法采用双指针技巧：先让指针 cur 先行 n 步，若此时 cur 为 null 则删除头节点；否则同步移动 cur 和前驱指针 pre，直至 cur 到达链表末尾，此时 pre 指向待删除节点的前驱，修改 pre.next 跳过目标节点即可。代码实现了上述思路，并对空链表和 n 为0 的情况作了防护。

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

NC52 有效括号序列

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

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