LeetCode Programming

AI 摘要

本文是作者为缓解拖延、练习 Go 语言而开启的 LeetCode 刷题记录，兼作个人题解。文中先介绍 C++ 输入输出加速技巧，通过 ios::sync_with_stdio(false) 解除 C/C++ 流同步、cin.tie(nullptr) 解除 cin 与 cout 绑定来提升效率；随后汇总多道 LeetCode 题解，列出题号、题目、难度及链接，涵盖第1至32题等。

AI 生成 · 仅供参考

# 引言

作为一个社会人, 感觉自己在死瘦宅的路上愈行愈远, 无法自拔~ 也越来越拖延(懒癌晚期)

为了缓解下这种情况, 决定工作学习之余没事刷刷题, 而 LeetCode 就是一个不错的选择(正好也用新入坑的 GO 语言写写代码试试水)~

谨以此文记录下 LeetCode 的刷题之路, 也算是作为一个个人题解 Orz~

LeetCode

# 技巧处理

# C++ 输入输出加速

在刷LeetCode的时候, 习惯性看看最优时间的大佬们的解法, 偶然发现有些题同样的方法别人运行时间就要低上不少, 然后发现这些提交一般都有如下这个 Lambda 表达式。

static const auto __________ = []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

仔细看了看 LeetCode 对于使用 C++ 提交的人, 输入输出默认使用的 C++ 的 io, 而不是 C 的, 上面 Lambda 捕获, 则可以用来解除 C++ 为了兼容 C 而采取的缓存同步机制, 提升 cin, cout 的速度

解惑 ios::sync_with_stdio(false)

因为 C++ 中的std::cin和std::cout为了兼容 C, 保证在代码中同时出现 std::cin 和 scanf 或 std::cout 和 printf 时输出不发生混乱, 所以 C++ 用一个流缓冲区来同步 C 的标准流。通过 std::ios_base::sync_with_stdio 函数可以解除这种同步, 让 std::cin 和 std::cout 不再经过缓冲区, 自然就节省了许多时间。

解惑 cin.tie(nullptr)

std::cin默认是与 std::cout 绑定的, 所以每次操作的时候(也就是调用 << 或者 >>)都要刷新(调用flush), 这样增加了IO的负担, 通过 tie(nullptr) 来解除 std::cin 和 std::cout 之间的绑定, 来降低 IO 的负担使效率提升。

# 题解汇总

沉潜深度源自始终如一的专注。人的生命是有限的, 精力是有限的, 只有专注才能将人的力量发挥到极致。

题解链接	题目名称	难度
0001: 传送门 Click Here!	Two Sum	Easy
0002: 传送门 Click Here!	Add Two Numbers	Medium
0003: 传送门 Click Here!	Longest Substring Without Repeating Characters	Medium
0004: 传送门 Click Here!	Median of Two Sorted Arrays	Hard
0005: 传送门 Click Here!	Longest Palindromic Substring	Medium
0006: 传送门 Click Here!	ZigZag Conversion	Medium
0007: 传送门 Click Here!	Reverse Integer	Easy
0008: 传送门 Click Here!	String to Integer (atoi)	Medium
0009: 传送门 Click Here!	Palindrome Number	Easy
0010: 传送门 Click Here!	Regular Expression Matching	Hard
0011: 传送门 Click Here!	Container With Most Water	Medium
0012: 传送门 Click Here!	Integer to Roman	Medium
0013: 传送门 Click Here!	Roman to Integer	Easy
0014: 传送门 Click Here!	Longest Common Prefix	Easy
0015: 传送门 Click Here!	3Sum	Medium
0016: 传送门 Click Here!	3Sum Closest	Medium
0017: 传送门 Click Here!	Letter Combinations of a Phone Number	Medium
0018: 传送门 Click Here!	4Sum	Medium
0019: 传送门 Click Here!	Remove Nth Node From End of List	Medium
0020: 传送门 Click Here!	Valid Parentheses	Easy
0021: 传送门 Click Here!	Merge Two Sorted Lists	Easy
0022: 传送门 Click Here!	Generate Parentheses	Medium
0023: 传送门 Click Here!	Merge k Sorted Lists	Hard
0024: 传送门 Click Here!	Swap Nodes in Pairs	Medium
0025: 传送门 Click Here!	Reverse Nodes in k-Group	Hard
0026: 传送门 Click Here!	Remove Duplicates from Sorted Array	Easy
0027: 传送门 Click Here!	Remove Element	Easy
0028: 传送门 Click Here!	Implement strStr()	Easy
0029: 传送门 Click Here!	Divide Two Integers	Medium
0030: 传送门 Click Here!	Substring with Concatenation of All Words	Hard
0031: 传送门 Click Here!	Next Permutation	Easy
0032: 传送门 Click Here!	Longest Valid Parentheses	Hard

文章关联

32 篇关联

顺着引用的连线，读见篇章交错的脉络

展开关系图

拖动平移 · Ctrl / ⌘ + 滚轮缩放 · 点击节点阅读使用 + / − 按钮缩放 · 放大视图后可拖动 · 点击节点阅读单指拖动平移 · 使用 + / − 按钮缩放 · 点击节点阅读

当前文章本文引用

引用列表

引用本文0

暂无

本文引用32

LeetCode_9: Palindrome Number
AI 摘要
本文讨论 LeetCode 回文数问题，要求判断整数正反读是否相同。题解指出：0 返回 true；负数或末位为 0 的非零数直接返回 false。随后只需反转数字后半部分，直到反转值不小于剩余前半部分，最后比较反转值是否等于前半部分，或反转值除以 10 是否等于前半部分，以处理奇数位数。时间复杂度 O(n)，并给出 C++ 和 Go 实现代码。
LeetCode_6: ZigZag Conversion
AI 摘要
文章讲解 LeetCode 的 Z 字形变换题：给定字符串和行数，将字符按 Z 字形纵向排列后逐行读取。题解指出这是规律题，逐行扫描并推算每行字符索引。首行和末行每个周期只取一个字符，中间行每周期取两个；周期长度为 2*(numRows-1)。按此规律依次拼接即可，时间复杂度 O(n)，并附有 C++ 与 Go 的 AC 代码实现。
LeetCode_21: Merge Two Sorted Lists
AI 摘要
文章介绍 LeetCode 合并两个有序链表问题，给定两个有序链表，要求合并为一个新的有序链表。示例输入 1->2->4、1->3->4，输出 1->1->2->3->4->4。题解采用归并思路，逐个比较节点值，将较小节点接入结果链表，遍历结束后接上剩余部分。时间复杂度 O(n)，空间复杂度 O(1)，并提供 C++ 和 Go 的 AC 代码。
LeetCode_27: Remove Element
AI 摘要
本文介绍 LeetCode 移除元素题：给定数组 nums 和值 val，要求原地删除所有等于 val 的元素并返回新长度，只能使用 O(1) 额外空间，元素顺序可改变。题解通过一次遍历，用 res 指针记录保留位置，遇到不等于 val 的元素就写入 nums[res] 并递增，等于 val 则跳过。时间复杂度 O(n)，空间复杂度 O(1)，并给出 C++ 和 Go 实现。
LeetCode_30: Substring with Concatenation of All Words
AI 摘要
本文总结了LeetCode“串联所有单词的子串”题。题目给定字符串s和等长单词数组words，要求找出s中所有由words全部单词各用一次拼接而成的子串起始索引。题解采用滑动窗口与哈希表：先统计words词频，再按单词长度分多起点遍历，用窗口内词频与目标比较，动态调整左边界，记录合法起点。时间复杂度O(n)，空间复杂度O(km)。文末给出C++和Go实现。
LeetCode_20: Valid Parentheses
AI 摘要
本文讲解 LeetCode 有效括号题：给定仅含括号的字符串，判断同类型括号是否按正确顺序闭合，空串视为有效。题解指出该过程符合后进先出原则，用栈模拟：遍历字符，若与栈顶匹配则弹出，否则压入，遍历后栈空即有效。时间复杂度 O(n)，空间复杂度 O(n)，并提供 C++ 与 Go 的 AC 代码。
LeetCode_16: 3Sum Closest
AI 摘要
文章讲解 LeetCode 3Sum Closest：给定整数数组和目标值，找出三数之和最接近目标值并返回该和。解法沿用第15题3Sum思路，先排序，固定一个数后用双指针查找，根据当前和与目标大小移动指针并更新最小差值。示例 nums=[-1,2,1,-4], target=1，结果为2。时间复杂度O(n^2)，空间复杂度O(1)，并给出C++和Go实现。
LeetCode_17: Letter Combinations of a Phone Number
AI 摘要
本文讲解 LeetCode 电话号码的字母组合题，给定数字序列，要求返回所有可能字母组合。文章指出可用常规 BFS 或 DFS 搜索解决，并给出 C++ 的 BFS、DFS 实现及 Go 的 BFS 实现。时间复杂度为 O(4^n)，空间复杂度为 O(4^n)，其中 4 表示每个数字最多映射的字符数。核心是按数字映射表逐位扩展或递归拼接字符，最终得到全部组合。
LeetCode_25: Reverse Nodes in k-Group
AI 摘要
本文是 LeetCode“K 个一组翻转链表”的题解，说明给定链表需每 k 个节点翻转一次，剩余不足 k 个节点保持原序，并给出 k=2、k=3 示例。解题采用快慢指针：快指针先走 k 步确定待翻转区间，再原地反转该区间并接回原链表，重复至结束。时间复杂度 O(kn)，空间复杂度 O(1)，代码提供 C++ 和 Go 两种实现。
LeetCode_4: Median of Two Sorted Arrays
AI 摘要
本文讲解 LeetCode“两个有序数组的中位数”解法。题目要求合并两个升序数组并求中位数，官方期望复杂度为 O(log(m+n))。文章先说明中位数取值规则，再给出两种方法：归并扫描法，复杂度 O(m+n)；以及转化为寻找第 k 小数，通过比较两数组第 k/2 个元素并每次剔除一半，递归求得第 k 小，复杂度 O(log(m+n))，并附 C++ 与 Go 实现。
LeetCode_22: Generate Parentheses
AI 摘要
文章总结了 LeetCode“生成括号”题：给定 n 对括号，要求输出所有合法组合。解法采用递归加回溯的 DFS，依次添加括号，并用剪枝条件保证有效：左括号数小于 n 时可加左括号，右括号数小于左括号数时可加右括号；当左右括号数都等于 n 时记录结果。原文给出 C++ 与 Go 实现，并称时间复杂度 O(2^n)、空间复杂度 O(n)。
LeetCode_3: Longest Substring Without Repeating Characters
AI 摘要
文章介绍 LeetCode 无重复字符最长子串问题：给定字符串，求不含重复字符的最长子串长度。题解采用哈希表记录每个字符上次出现的下标，并用滑动窗口维护当前无重复子串起点。遍历字符串时，若字符已出现且其上次位置加一大于当前起点，则更新起点；随后更新字符位置，计算当前子串长度并维护最大值。时间复杂度为 O(n)，文末给出 C++ 与 Go 实现。
LeetCode_28: Implement strStr()
AI 摘要
本文总结了 LeetCode 的 implement strStr() 题：在字符串 haystack 中查找模式串 needle 首次出现的索引，不存在返回 -1，needle 为空时返回 0。题解采用 KMP 算法，先构造 next 数组，再进行线性匹配，时间复杂度 O(n+m)，空间复杂度 O(m)。文中给出了 C++ 与 Go 两种 AC 代码，并提醒空模式串是易错边界。
LeetCode_7: Reverse Integer
AI 摘要
本文介绍LeetCode整数反转题：给定32位整数，输出其翻转后的数字，例如123变321、-123变-321、120变21；若翻转结果超出32位整型范围则返回0。题解提出按位取余并逐次乘10累加的方法，同时处理正负号，复杂度与数字位数相关。文中给出C++和Go实现，C++用long long暂存并判断溢出，Go在循环中预判溢出。
LeetCode_29: Divide Two Integers
AI 摘要
本文讲解 LeetCode 两整数相除问题：在不能使用乘、除、取模运算且仅能存储 int32 的条件下，求整数商并处理溢出。朴素反复减法效率低，题解将商拆成 2 的幂之和，通过位移让除数成倍增长，再用被除数逐次减去 divisor<
LeetCode_19: Remove Nth Node From End of List
AI 摘要
本文讲解LeetCode删除链表倒数第n个节点的题解。题目给定链表和n，要求删除倒数第n个节点后返回链表。核心解法为快慢指针：先行指针先走n步，再与慢指针同步前进，当先行指针到达末尾时，慢指针位于待删节点的前驱，修改next即可删除。时间复杂度O(n)，空间复杂度O(1)，并给出C++和Go的AC代码实现。
LeetCode_13: Roman to Integer
AI 摘要
本文介绍 LeetCode“罗马数字转整数”题目及解法。题目要求按罗马数字规则将字符串转为整数，并说明 I、X、C 可作减法前缀的六种情况。题解采用简单模拟：顺序读取每个符号并累加其数值；若当前符号值大于前一符号，则减去两倍前一符号值，以修正 IV、IX、CM 等特殊情况。时间复杂度为 O(n)，文末给出 C++ 和 Go 实现。
LeetCode_15: 3Sum
AI 摘要
文章讲解 LeetCode 三数之和问题：在整数数组中找出所有和为 0 且不重复的三元组。核心解法是先排序数组，固定第一个数，再用左右双指针在剩余区间夹逼寻找后两个数；根据三数之和与 0 的大小移动指针，并跳过重复元素避免重复结果。若首数大于 0 可提前结束。时间复杂度 O(n^2)，空间复杂度 O(1)，并给出 C++ 与 Go 实现。
LeetCode_24: Swap Nodes in Pairs
AI 摘要
本文讲解 LeetCode“两两交换链表节点”题解。要求交换相邻节点，不能修改节点值，只能用常数级额外空间。思路是创建虚拟头结点统一边界操作，用 pre 和 cur 指针遍历链表，每轮调整指针完成相邻两节点交换，再推进指针。时间复杂度 O(n)，空间复杂度 O(1)。文末附 C++ 与 Go 实现代码。
LeetCode_26: Remove Duplicates from Sorted Array
AI 摘要
本文介绍 LeetCode“删除排序数组中的重复项”题解。题目要求对已排序数组原地去重，仅用 O(1) 额外空间修改输入，返回新长度，超出部分无需处理。核心思路是顺序遍历，用 index 指向下一个待放位置，当当前元素与前一个不同时，将其写入 index 并递增，同时计数。时间复杂度 O(n)，空间复杂度 O(1)，并给出 C++ 与 Go 实现。
LeetCode_8: String to Integer (atoi)
AI 摘要
文章讲解 LeetCode 的 atoi 题：把字符串转换为 32 位整数。需跳过前导空格，识别可选正负号，连续读取数字直到非数字或结束；若首个非空字符非法则返回 0；结果溢出时按符号返回 INT_MAX 或 INT_MIN。题解按题意模拟，逐位累加并提前判断溢出，时间复杂度 O(n)，并给出 C++ 和 Go 实现。
LeetCode_10: Regular Expression Matching
AI 摘要
文章围绕 LeetCode 正则表达式匹配题，要求实现支持“.”和“*”且覆盖整个字符串的匹配。先给出递归法，按模式下一字符是否为“*”分情况处理零次或多次匹配；再给出动态规划法，定义 dp[i][j] 表示 s 前 i 个字符与 p 前 j 个字符是否匹配，并分析普通字符及“*”匹配零次、一次、多次的转移，复杂度 O(m*n)。最后附 C++ 递归、C++ DP 与 Go 代码实现。
LeetCode_5: Longest Palindromic Substring
AI 摘要
本文是LeetCode“最长回文子串”题解。题目要求从给定字符串中找出最长回文子串，字符串长度不超过1000。作者采用Manacher（马拉车）算法，将时间复杂度降至O(n)，通过维护当前回文中心、边界及半径，利用回文对称性减少重复扩展，并给出C++和Go两种实现代码，最终返回最长回文子串。
LeetCode_1: Two Sum
AI 摘要
本文介绍 LeetCode 两数之和题解。题目要求给定整数序列和目标值，找出两个不同元素使它们之和等于目标值，并假设仅有唯一解。核心思路是遍历数组，用哈希表记录已访问数值及其下标；每遇到当前值，先查询目标值与当前值之差是否已在表中，若存在则返回两下标，否则把当前值存入表中。该方法时间复杂度为 O(n)，文中给出 C++ 和 Go 实现代码。
LeetCode_14: Longest Common Prefix
AI 摘要
文章介绍 LeetCode 最长公共前缀题：给定若干单词，求最长公共前缀，若不存在则返回空字符串。解法以第一个单词作为初始前缀，依次与后续单词逐字符比较，遇到不同字符或单词更短时，将前缀结束位置收缩到当前匹配长度，最后返回该前缀子串。时间复杂度 O(nk)，空间复杂度 O(k)，并给出 C++ 和 Go 实现。
LeetCode_31: Next Permutation
AI 摘要
本文讲解 LeetCode“下一个排列”题：给定序列，将其原地调整为字典序下一个更大排列；若不存在，则改为最小排列。解法是从后向前找到首个满足 nums[i]
LeetCode_23: Merge k Sorted Lists
AI 摘要
文章是 LeetCode“合并 K 个排序链表”的题解。题目要求将 k 个已排序链表合并为一个排序列表。题解核心是复用第 21 题“合并两个有序链表”的方法，再借用归并排序的分治思想，对链表两两合并，逐步缩小规模，直到只剩一个链表。时间复杂度为 O(nlogn)，空间复杂度为 O(1)。最后给出 C++ 与 Go 的 AC 代码实现。
LeetCode_18: 4Sum
AI 摘要
本文是 LeetCode 四数之和题解。题目要求在整数数组中找出所有不重复的四元组，使其和等于目标值。思路基于三数之和，先排序，再用两层循环固定前两个数，剩余区间用双指针寻找后两个数；各层通过跳过相同元素去重。时间复杂度 O(n^3)，空间复杂度 O(1)，并给出 C++ 与 Go 实现。
LeetCode_11: Container With Most Water
AI 摘要
该文总结 LeetCode “盛最多水的容器”题。题目给定非负整数数组，每个元素表示垂直线高度，选取两条线与 x 轴构成容器，求最大盛水面积。题解采用双指针：从数组两端向中间移动，面积由较矮高度乘以两线下标差决定；每次移动较矮一侧，并持续更新最大值。时间复杂度 O(n)，空间复杂度 O(1)，并给出 C++ 与 Go 实现。
LeetCode_12: Integer to Roman
AI 摘要
本文是 LeetCode“整数转罗马数字”的题解，先说明罗马数字符号、减法规则及示例，再给出思路：按从大到小列出含 900、400 等特殊组合的映射表，循环比较目标数字，能减则减去对应值并拼接符号，否则后移，从而避免对 4、9 单独判断。时间复杂度 O(n)，空间复杂度 O(n)，并附 C++ 与 Go 的 AC 代码。
LeetCode_2: Add Two Numbers
AI 摘要
文章是 LeetCode“两数相加”的题解。题目用两个倒序链表表示非负整数，每位为一个节点，要求相加后返回倒序链表。题解指出倒序链表正好从低位到高位存储，因此可同时遍历两链表，逐位相加并维护进位。空节点值按 0 处理，新节点存当前和的个位，进位为和除以 10；遍历结束后若仍有进位则追加节点。时间复杂度 O(n)。代码给出 C++ 和 Go 两种实现。
LeetCode_32: Longest Valid Parentheses
AI 摘要
本文介绍LeetCode最长有效括号子串问题，给定仅含左右括号的字符串，求最长有效配对子串长度。解法采用动态规划，dp[i]表示以第i位结尾的最长有效长度。遇到右括号时，判断对应位置是否为左括号，转移为dp[i]=dp[i-1]+2，并加上前一段有效长度。头部添加无效字符避免越界，过程中维护最大值。时间复杂度O(n)，空间复杂度O(n)，附C++和Go实现。

本文作者：Seiun@繁夜
本文链接：https://onlyzyx.com/posts/50504.html
版权声明：本站所有文章除特别声明外，均采用 (CC)BY-NC-SA 许可协议。转载请注明出处！

循着字句，邂逅星光

输入关键词

发现内容

快速直达

LeetCode Programming