LeetCode Solutions In Cpp17 Save

算法（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

Problem