LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

算法（Algorithm）

• 《算法导论》（Introduction to Algorithms，由 Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein 合著，取四人名字的一个首字母，简称 CLRS，该书详细介绍了经典算法的原理，并给出了正确性证明）提到：“不正式地说，算法是任何定义明确的计算过程，该过程取某个值或值的集合作为输入，并产生某个值或值的集合作为输出，算法就是这样的把输入转换成输出的计算步骤的一个序列。”

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

• 算法是基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。算法必须具有以下特征：
  • 输入：待计算问题的任一实例，都需要以某种方式交给对应的算法，对所求解问题特定实例的这种描述统称为输入
  • 输出：经计算和处理之后得到的信息，即针对输入问题实例的答案，称作输出
  • 确定性：算法应可描述为由若干语义明确的基本操作组成的指令序列
  • 可行性：每一基本操作在对应的计算模型中均可兑现
  • 有穷性：任意算法都应在执行有限次基本操作之后终止并给出输出

时间复杂度（Time Complexity）

• 由于计算机不是无限快，内存不是免费的，计算时间和空间是一种有限资源，高效的算法可以更好地利用这些资源，因此算法可以像计算机硬件一样视为一种技术。度量算法成本的方式称为复杂度分析，复杂度可分为时间复杂度和空间复杂度。由于运行任一算法的空间消耗都不会多于运行期间进行的基本操作次数，即时间复杂度本身就是空间复杂度的上界，因此复杂度分析主要关注时间复杂度，而时间复杂度分析主要关注最坏情况下的运行时间，即最长运行时间。复杂度分析一般用渐进记号大 O 表示，它用一个函数来描述某个函数的数量级上界。最低复杂度是 O(1)，代表常数时间复杂度，因为不能指望没有任何代价来运行算法。依次递增的常见复杂度层级还有 O(log log n)、O(log n)、O(√n)、O(n)、O(n log n)、O(n ^ 2)、O(n ^ 3）、O(2 ^ n)、O(n!) 等

本项目详细解析的数据结构和算法

• 二分查找
• 经典排序算法
• 滑动窗口
• 贪心算法
• 分治法
• 回溯法
• 全排列
• 二叉树遍历
• 动态规划
• 计算质数
• 位运算
• 最长回文子串
• 字符串查找算法
• 字典树
• 并查集
• 拓扑排序
• 树状数组
• 死锁避免

C++ 中的数据结构（Data Structure）

• 计算机中存储和组织数据的方式称为数据结构，旨在便于访问和修改。没有一种单一的数据结构对所有用途均有效，所以重要的是知道几种数据结构的优势和局限。各种编程语言对于常用数据结构都提供了内置支持，比如哈希表的实现，在 C++ 中是 std::unordered_map，在 Java 中是 HashMap、在 C# 中是 Hashtable、在 JavaScript 中是 Object、在 Python 中是 dict、在 Go 中是 map、在 Rust 中是 std::collections::HashMap
• STL（Standard Template Library）是 C++ 标准规定的模板库接口规范，包括容器(Container)、迭代器(Iterator)、算法(Algorithm)、函数对象（Function Object）等组件
• STL 的历史十分久远，1979年，Alexander Stepanov（ Elements of Programming 作者）开始考虑将常用算法抽象成一套泛型库
• 1987年，Stepanov 和 David Musser 发布了首个 Ada 版本的泛型算法库，但 Ada 在美国国防工业外未被广泛接受。Alexander Stepanov 认为 C++ 通过指针访问内存的计算模型提供了非常高的灵活度，于是开始使用 C++ 开发泛型算法库，由于 C++ 还没有模板机制，泛型库的实现十分笨拙
• 1988 年，Bjarne Stroustrup（C++ 之父，The Design and Evolution of C++ 作者） 在 Denver 召开的 USENIX C++ 会议上首次发表了模板相关的设计
• 1992 年， 惠普实验室的 Meng Lee 加入了 Alexander Stepanov 的项目，成为 HP STL（首个 STL 版本）的另一位主要贡献者
• 1993 年，贝尔实验室的 Andrew Koenig（前 ISO C++ 标准化委员会主席，Ruminations on C++ 作者）得知了这项计划，于是请 Alexander Stepanov 在 1993 年 11 月的 ANSI/ISO C++ 标准委员会会议上展示其计划。此计划得到了委员会的极大反响，被请求于 1994 年 3 月会议前给出正式提案
• 1994 年 3 月会议上，由于 STL 内容过多，仍有部分细节需要给出证明，STL 进入标准的投票延期到下一次会议
• 1994 年 7 月，STL 正式纳入 1994 ANSI/ISO 草案
• 1994 年 8 月，惠普决定在互联网上免费提供 STL 的实现
• STL 是 C++ 标准库的一部分，目前三大操作系统的标准库实现各不相同，Linux 下 GCC 使用的是 libstdc++，Mac OS 下 Clang 使用的是 libc++，Windows 下 Visual Studio 的 MSVC 使用的是 MSVC STL
• STL 提供了一些较为通用的数据结构，这些数据结构在 C++ 中称为容器，C++11 中包含如下容器
  • 序列容器（能按顺序访问）
    • std::array：定长连续数组
    • std::vector：向量，可动态扩展的连续数组，随机访问、末尾插入、末尾移除元素均摊 O(1)，插入或移除元素与到尾后迭代器的距离成线性 O(n)
    • std::deque：双端队列，随机访问、起始或末尾位置插入或移除元素时间复杂度 O(1)，插入或移除元素时间复杂度 O(n)
    • std::forward_list：单向链表，不支持快速随机访问，插入或移除元素时间复杂度 O(1)
    • std::list：双向链表，不支持快速随机访问，插入或移除元素时间复杂度 O(1)
  • 关联容器（以红黑树实现，查找时间复杂度 O(log n)）
    • std::set：唯一键的集合，按照键排序
    • std::map：键值对集合，按照键排序，键唯一
    • std::multiset：键集合，按照键排序，不要求键唯一
    • std::multimap：键值对集合，按照键排序，不要求键唯一
  • 无序关联容器（以哈希表实现，查找时间复杂度均摊 O(1)，最坏情况 O(n)）
    • std::unordered_set：唯一键的集合，不要求有序
    • std::unordered_map：键值对集合，不要求有序
    • std::unordered_multiset：键集合，不要求有序和键唯一
    • std::unordered_multimap：键值对集合，不要求有序和键唯一
  • 容器适配器（基于序列容器实现，提供与容器不同的接口）
    • std::stack：栈，LIFO（后进的元素先出）
    • std::queue：队列，FIFO（先进的元素先出）
    • std::priority_queue：优先队列，即堆，默认为大顶堆，默认比较函数为 std::less
• 此外 C++17 包含如下特殊类型数据结构
  • std::bitset：位图
  • std::tuple：元组，元素类型可以不同
  • std::pair：二元组
  • std::optional：既可以包含值也可以为空，类似于 Haskell 中的 Maybe
  • std::variant：类型安全的 union
  • std::any：单个值的类型安全容器

LeetCode（力扣）

• 2015 年，Winston Tang 创办 LeetCode，Leet 是一种发源于西方国家的 BBS、在线游戏和黑客社区所使用的文字书写方式，通常是把拉丁字母转变成数字或是特殊符号，例如 E 写成 3、A 写成 @ 等，或是将单字写成同音的字母或数字，如 to 写成 2、for 写成 4 等等，Winston Tang 的用户名为 1337c0d3r，是 LeetCoder 的 Leet 写法，由此取名 LeetCode
• 2018 年 2 月，LeetCode 上线中文平台力扣
• LeetCode 是一个上手简单的 OJ（Online Judge） 平台，以程序员求职面试时的编程真题为主，为其提供训练编码能力的实践平台。LeetCode 支持多种编程语言，包括 C、C++、Java、C#、Python、JavaScript、TypeScript、Ruby、Go、Rust、Scala、Swift、Kotlin、PHP
• LeetCode 默认支持 C++17，不需要包含头文件和命名空间，用户只需要关注核心算法的实现过程，答案正确时会给出算法效率的排名，错误时会给出对应的测试用例，使用上十分便捷。此项目采用 C++17 作为解题语言，旨在练习并解释常见的数据结构与经典算法，对于能直接用 STL 实现的，会给出更具体的实现，以阐述 STL 的原理

Category

Tag	中文站	Category
Top Interview Questions-Easy Collection	初级算法	Reference
Top Interview Questions-Medium Collection	中级算法	Reference
Top Interview Questions-Hard Collection	高级算法	Reference
Concurrency	多线程	Reference

Problem

#	Title	中文站	Solution	Code
0001	Two Sum	两数之和	README	C++
0002	Add Two Numbers	两数相加	README	C++
0003	Longest Substring Without Repeating Characters	无重复字符的最长子串	README	C++
0004	Median of Two Sorted Arrays	寻找两个有序数组的中位数	README	C++
0005	Longest Palindromic Substring	最长回文子串	README	C++
0007	Reverse Integer	整数反转	README	C++
0008	String to Integer (atoi)	字符串转换整数 (atoi)	README	C++
0010	Regular Expression Matching	正则表达式匹配	README	C++
0011	Container With Most Water	盛最多水的容器	README	C++
0013	Roman to Integer	罗马数字转整数	README	C++
0014	Longest Common Prefix	最长公共前缀	README	C++
0015	3Sum	三数之和	README	C++
0017	Letter Combinations of a Phone Number	电话号码的字母组合	README	C++
0019	Remove Nth Node From End of List	删除链表的倒数第N个节点	README	C++
0020	Valid Parentheses	有效的括号	README	C++
0021	Merge Two Sorted Lists	合并两个有序链表	README	C++
0022	Generate Parentheses	括号生成	README	C++
0023	Merge k Sorted Lists	合并K个排序链表	README	C++
0026	Remove Duplicates from Sorted Array	删除排序数组中的重复项	README	C++
0028	Implement strStr()	实现 strStr()	README	C++
0029	Divide Two Integers	两数相除	README	C++
0031	Next Permutation	下一个排列	README	C++
0032	Longest Valid Parentheses	最长有效括号	README	C++
0033	Search in Rotated Sorted Array	搜索旋转排序数组	README	C++
0034	Find First and Last Position of Element in Sorted Array	在排序数组中查找元素的第一个和最后一个位置	README	C++
0036	Valid Sudoku	有效的数独	README	C++
0038	Count and Say	外观数列	README	C++
0039	Combination Sum	组合总和	README	C++
0041	First Missing Positive	缺失的第一个正数	README	C++
0042	Trapping Rain Water	接雨水	README	C++
0044	Wildcard Matching	通配符匹配	README	C++
0046	Permutations	全排列	README	C++
0048	Rotate Image	旋转图像	README	C++
0049	Group Anagrams	字母异位词分组	README	C++
0050	Pow(x, n)	Pow(x, n)	README	C++
0051	N-Queens	N皇后	README	C++
0053	Maximum Subarray	最大子序和	README	C++
0054	Spiral Matrix	螺旋矩阵	README	C++
0055	Jump Game	跳跃游戏	README	C++
0056	Merge Intervals	合并区间	README	C++
0062	Unique Paths	不同路径	README	C++
0066	Plus One	加一	README	C++
0069	Sqrt(x)	x 的平方根	README	C++
0070	Climbing Stairs	爬楼梯	README	C++
0071	Simplify Path	简化路径	README	C++
0072	Edit Distance	编辑距离	README	C++
0073	Set Matrix Zeroes	矩阵置零	README	C++
0075	Sort Colors	颜色分类	README	C++
0076	Minimum Window Substring	最小覆盖子串	README	C++
0078	Subsets	子集	README	C++
0079	Word Search	单词搜索	README	C++
0084	Largest Rectangle in Histogram	柱状图中最大的矩形	README	C++
0085	Maximal Rectangle	最大矩形	README	C++
0088	Merge Sorted Array	合并两个有序数组	README	C++
0091	Decode Ways	解码方法	README	C++
0094	Binary Tree Inorder Traversal	二叉树的中序遍历	README	C++
0096	Unique Binary Search Trees	不同的二叉搜索树	README	C++
0098	Validate Binary Search Tree	验证二叉搜索树	README	C++
0101	Symmetric Tree	对称二叉树	README	C++
0102	Binary Tree Level Order Traversal	二叉树的层序遍历	README	C++
0103	Binary Tree Zigzag Level Order Traversal	二叉树的锯齿形层次遍历	README	C++
0104	Maximum Depth of Binary Tree	二叉树的最大深度	README	C++
0105	Construct Binary Tree from Preorder and Inorder Traversal	从前序与中序遍历序列构造二叉树	README	C++
0106	Construct Binary Tree from Inorder and Postorder Traversal	从中序与后序遍历序列构造二叉树	README	C++
0108	Convert Sorted Array to Binary Search Tree	将有序数组转换为二叉搜索树	README	C++
0112	Path Sum	路径总和	README	C++
0114	Flatten Binary Tree to Linked List	二叉树展开为链表	README	C++
0116	Populating Next Right Pointers in Each Node	填充每个节点的下一个右侧节点指针	README	C++
0117	Populating Next Right Pointers in Each Node II	填充每个节点的下一个右侧节点指针 II	README	C++
0118	Pascal’s Triangle	杨辉三角	README	C++
0121	Best Time to Buy and Sell Stock	买卖股票的最佳时机	README	C++
0122	Best Time to Buy and Sell Stock II	买卖股票的最佳时机 II	README	C++
0124	Binary Tree Maximum Path Sum	二叉树中的最大路径和	README	C++
0125	Valid Palindrome	验证回文串	README	C++
0127	Word Ladder	单词接龙	README	C++
0128	Longest Consecutive Sequence	最长连续序列	README	C++
0130	Surrounded Regions	被围绕的区域	README	C++
0131	Palindrome Partitioning	分割回文串	README	C++
0134	Gas Station	加油站	README	C++
0136	Single Number	只出现一次的数字	README	C++
0138	Copy List with Random Pointer	复制带随机指针的链表	README	C++
0139	Word Break	单词拆分	README	C++
0140	Word Break II	单词拆分 II	README	C++
0141	Linked List Cycle	环形链表	README	C++
0144	Binary Tree Preorder Traversal	二叉树的前序遍历	README	C++
0145	Binary Tree Postorder Traversal	二叉树的后序遍历	README	C++
0146	LRU Cache	LRU缓存机制	README	C++
0148	Sort List	排序链表	README	C++
0149	Max Points on a Line	直线上最多的点数	README	C++
0150	Evaluate Reverse Polish Notation	逆波兰表达式求值	README	C++
0151	Reverse Words in a String	翻转字符串里的单词	README	C++
0152	Maximum Product Subarray	乘积最大子数组	README	C++
0153	Find Minimum in Rotated Sorted Array	寻找旋转排序数组中的最小值	README	C++
0155	Min Stack	最小栈	README	C++
0160	Intersection of Two Linked Lists	相交链表	README	C++
0162	Find Peak Element	寻找峰值	README	C++
0165	Compare Version Numbers	比较版本号	README	C++
0166	Fraction to Recurring Decimal	分数到小数	README	C++
0168	Excel Sheet Column Title	Excel表列名称	README	C++
0169	Majority Element	多数元素	README	C++
0171	Excel Sheet Column Number	Excel表列序号	README	C++
0172	Factorial Trailing Zeroes	阶乘后的零	README	C++
0173	Binary Search Tree Iterator	二叉搜索树迭代器	README	C++
0174	Dungeon Game	地下城游戏	README	C++
0179	Largest Number	最大数	README	C++
0189	Rotate Array	旋转数组	README	C++
0190	Reverse Bits	颠倒二进制位	README	C++
0191	Number of 1 Bits	位1的个数	README	C++
0198	House Robber	打家劫舍	README	C++
0200	Number of Islands	岛屿数量	README	C++
0202	Happy Number	快乐数	README	C++
0204	Count Primes	计数质数	README	C++
0206	Reverse Linked List	反转链表	README	C++
0207	Course Schedule	课程表	README	C++
0208	Implement Trie (Prefix Tree)	实现 Trie (前缀树)	README	C++
0210	Course Schedule II	课程表 II	README	C++
0212	Word Search II	单词搜索 II	README	C++
0213	House Robber II	打家劫舍 II	README	C++
0215	Kth Largest Element in an Array	数组中的第K个最大元素	README	C++
0217	Contains Duplicate	存在重复元素	README	C++
0218	The Skyline Problem	天际线问题	README	C++
0221	Maximal Square	最大正方形	README	C++
0227	Basic Calculator II	基本计算器 II	README	C++
0230	Kth Smallest Element in a BST	二叉搜索树中第K小的元素	README	C++
0232	Implement Queue using Stacks	用栈实现队列	README	C++
0234	Palindrome Linked List	回文链表	README	C++
0235	Lowest Common Ancestor of a Binary Search Tree	二叉搜索树的最近公共祖先	README	C++
0236	Lowest Common Ancestor of a Binary Tree	二叉树的最近公共祖先	README	C++
0237	Delete Node in a Linked List	删除链表中的节点	README	C++
0238	Product of Array Except Self	除自身以外数组的乘积	README	C++
0239	Sliding Window Maximum	滑动窗口最大值	README	C++
0240	Search a 2D Matrix II	搜索二维矩阵 II	README	C++
0242	Valid Anagram	有效的字母异位词	README	C++
0258	Add Digits	各位相加	README	C++
0268	Missing Number	缺失数字	README	C++
0273	Integer to English Words	整数转换英文表示	README	C++
0278	First Bad Version	第一个错误的版本	README	C++
0279	Perfect Squares	完全平方数	README	C++
0283	Move Zeroes	移动零	README	C++
0287	Find the Duplicate Number	寻找重复数	README	C++
0289	Game of Life	生命游戏	README	C++
0295	Find Median from Data Stream	数据流的中位数	README	C++
0297	Serialize and Deserialize Binary Tree	二叉树的序列化与反序列化	README	C++
0300	Longest Increasing Subsequence	最长上升子序列	README	C++
0301	Remove Invalid Parentheses	删除无效的括号	README	C++
0309	Best Time to Buy and Sell Stock with Cooldown	最佳买卖股票时机含冷冻期	README	C++
0312	Burst Balloons	戳气球	README	C++
0315	Count of Smaller Numbers After Self	计算右侧小于当前元素的个数	README	C++
0322	Coin Change	零钱兑换	README	C++
0324	Wiggle Sort II	摆动排序 II	README	C++
0326	Power of Three	3的幂	README	C++
0328	Odd Even Linked List	奇偶链表	README	C++
0329	Longest Increasing Path in a Matrix	矩阵中的最长递增路径	README	C++
0334	Increasing Triplet Subsequence	递增的三元子序列	README	C++
0337	House Robber III	打家劫舍 III	README	C++
0341	Flatten Nested List Iterator	扁平化嵌套列表迭代器	README	C++
0344	Reverse String	反转字符串	README	C++
0347	Top K Frequent Elements	前 K 个高频元素	README	C++
0350	Intersection of Two Arrays II	两个数组的交集 II	README	C++
0354	Russian Doll Envelopes	俄罗斯套娃信封问题	README	C++
0365	Water and Jug Problem	水壶问题	README	C++
0371	Sum of Two Integers	两整数之和	README	C++
0378	Kth Smallest Element in a Sorted Matrix	有序矩阵中第K小的元素	README	C++
0380	Insert Delete GetRandom O(1)	常数时间插入、删除和获取随机元素	README	C++
0384	Shuffle an Array	打乱数组	README	C++
0387	First Unique Character in a String	字符串中的第一个唯一字符	README	C++
0406	Queue Reconstruction by Height	根据身高重建队列	README	C++
0412	Fizz Buzz	Fizz Buzz	README	C++
0416	Partition Equal Subset Sum	分割等和子集	README	C++
0419	Battleships in a Board	甲板上的战舰	README	C++
0429	N-ary Tree Level Order Traversal	N叉树的层序遍历	README	C++
0437	Path Sum III	路径总和 III	README	C++
0443	String Compression	压缩字符串	README	C++
0445	Add Two Numbers II	两数相加 II	README	C++
0450	Delete Node in a BST	删除二叉搜索树中的节点	README	C++
0452	Minimum Number of Arrows to Burst Balloons	用最少数量的箭引爆气球	README	C++
0454	4Sum II	四数相加 II	README	C++
0461	Hamming Distance	汉明距离	README	C++
0513	Find Bottom Left Tree Value	找树左下角的值	README	C++
0538	Convert BST to Greater Tree	把二叉搜索树转换为累加树	README	C++
0543	Diameter of Binary Tree	二叉树的直径	README	C++
0547	Friend Circles	朋友圈	README	C++
0559	Maximum Depth of N-ary Tree	N叉树的最大深度	README	C++
0560	Subarray Sum Equals K	和为K的子数组	README	C++
0567	Permutation in String	字符串的排列	README	C++
0589	N-ary Tree Preorder Traversal	N叉树的前序遍历	README	C++
0590	N-ary Tree Postorder Traversal	N叉树的后序遍历	README	C++
0591	Tag Validator	标签验证器	README	C++
0621	Task Scheduler	任务调度器	README	C++
0650	2 Keys Keyboard	只有两个键的键盘	README	C++
0654	Maximum Binary Tree	最大二叉树	README	C++
0672	Bulb Switcher II	灯泡开关 Ⅱ	README	C++
0722	Remove Comments	删除注释	README	C++
0912	Sort an Array	排序数组	README	C++
1114	Print in Order	按序打印	README	C++
1115	Print FooBar Alternately	交替打印FooBar	README	C++
1116	Print Zero Even Odd	打印零与奇偶数	README	C++
1117	Building H2O	H2O 生成	README	C++
1195	Fizz Buzz Multithreaded	交替打印字符串	README	C++
1226	The Dining Philosophers	哲学家进餐	README	C++