复试冲刺20天

专业课

网络

USP是一个智能化的网络数据库统一检索平台。它通过一个统一界面帮助用户在多个网络数据库搜索平台中实现信息检索操作，是对外网络中的多种检索工具的智能化整合
NAT即网络地址转换（Network Address Translation），是一种将IP数据包中的IP地址转换为另一个IP地址的技术

1. 静态NAT
   • 功能：实现内部IP与公网IP的一对一固定映射，常用于需要公网访问的服务器（如Web服务器），确保外部可通过固定公网IP访问内部设备
2. 动态NAT
   • 功能：从定义的公网IP地址池中动态分配IP，内部设备随机获取公网IP，用完后释放，适用用户数不固定的场景
3. 端口地址转换(PAT/NAPT(Network Address Port Translation，网络地址端口转换))
   • 功能：多个内部IP共享一个公网IP，通过端口号区分不同连接，极大节省IP地址，是家庭、企业最常用的NAT方式

DS

广义表的长度是指广义表第一层元素的个数，不包括递归子表内部的元素个数

1. 普通表：如(ab,c)，长度为3
2. 嵌套表：如(a,(b),d)，长度为3

广义表的深度是指广义表的最大嵌套层数

1. 空表：深度为1
2. 普通表：如(a,b,c)，深度为1
3. 嵌套表：如(a,(b,c),d)，深度为2，因为(b,) 是第一层中的子表，深度为1，整体深度为2

软工

问题定义->可行性分析->需求分析->设计->开发阶段->测试->运行与维护
主要的软件开发方法:

1. 结构化方法：面向数据流，自顶向下逐层分解，进行结构化分析、结构化设计、结构化程序设计。适用数据处理领域，不适用大且复杂、需求一直变化的场景
2. jackson方法：面向数据结构，通过问题的输入输出数据结构来分析，推出相应程序结构。适用小规模

软件测试与开发模型:

1. 软件测试的目的：验证软件是否符合需求，发现缺陷，确保质量,验证功能，避免风险
2. 软件测试的类型：单元测试（模块级）、集成测试（模块间交互）、系统测试（整体功能）、验收测试（分为Alpha测试和Beta测试）
3. 软件测试的方法：白盒测试（代码逻辑）、黑盒测试（功能验证）、自动化测试（工具辅助）
4. 模型：
   1. 瀑布模型：线性流程（需求-设计-开发-测试-部署），适合需求明确的项目
   2. 演化模型：初始的原型逐步演化成最终软件产品的过程，演化模型适用于对软件需求缺之准确认识的情况。典型的演化模型有：增量模型、原型型、旋模型
   3. 增量模型：从一组给定的需求开始，一次构造一段增量，逐步完善待开发的系统。增量模型强调每一个增量都发布一个可运行的产品，可较快产生能操作的系统
   4. 敏捷模型：迭代开发，快速交付，适应需求变化（如Scrum、看板）
   5. 螺旋模型：是瀑布模型和演化模型的结合，增加了风险分析，客户参与开发，适合大型复杂项目
   6. 原型模型：先构建原型供用户反馈，收集用户的反馈意见，再优化开发
   7. 喷泉模型：支持面向对象开发的过程模型。该模型认为软件开发过程自下而上周期的各阶段是相互迭代和无间隙的。迭代是指软件的某个部分常常被重复工作多次，相关功能在每次迭代中随之加入渐进的软件成分。无间隙指在各项活动之间无明显边界，如分析和设计活动之间没有明显的界限

软件维护主要分为以下四种类型:

1. 修正性维护（Corrective Maintenance）:
   • 概念:针对发现的软件错误或缺陷进行修复和更正的维护活动
   • 目的:消除软件中存在的错误,提高软件的可靠性和正确性
2. 适应性维护（Adaptive Maintenance）:
   • 概念:对软件进行修改和调整,使其能够适应硬件环境、操作系统或其他外部条件的变化
   • 目的:确保软件能够持续运行并满足用户的需求
3. 完善性维护（Perfective Maintenance）:
   • 概念:在不改变软件原有功能的情况下,对软件进行优化和改进,以提高其性能和可用性
   • 目的:提升软件的质量,增强用户体验
4. 预防性维护（Preventive Maintenance）:
   • 概念:对软件进行系统性的分析和检查,以检测和预防潜在的问题
   • 目的:降低软件故障发生的概率,延长软件的使用寿命

白盒测试，也称为结构化测试、基于代码的测试，是一种测试用例设计方法，它从程序的控制结构导出测试用例。用白盒测试产生的测试用例能够

1. 保证一个模块中的所有独立路径至少被使用一次
2. 对所有逻辑值均需测试true和false
3. 在上下边界及可操作范围内运行所有循环
4. 检查内部数据结构以确保其有效性

黑盒测试也称功能测试，通过测试来检测每个功能是否都能正常使用。在完全不考虑程序内部结构和内部特性的情况下，对程序接口进行测试，以用户的角度，从输入数据与输出数据的对应关系出发进行测试

提高软件质量:

1. 复审：是在软件生命周期每个阶段结束之前都采用一定的标准对该段产生的软件进行检测
2. 复查：是检查已有的材料，以断定在软件生命周期某个阶段的工作是否能够开始或继续
3. 管理复审：是向管理人员提供有关项目的总体状况、成本和进度等方面的情况，以便管理

软件形式化：在严格数学基础上的软件开发方法，基于数学的方法来描述软件属性的技术
三要素: 方法，工具，过程

数据库

候选码：可以唯一标识一个元组的最少的属性集合
主键：一个列或多列的组合，其值能唯一地标识表中的每一行，通过它可强制表的实体完整性,主键是候选键的子集
超键（Super Key） 是一个或多个属性的集合，这个集合可以唯一标识关系表中的每一行记录,候选键是一个最小的超键

存储过程是一组为了完成特定功能的语句集合，经编译后存储在数据库中。它可接收输入参数、输出参数，也可包含逻辑控制语句和数据操作语句等。用户通过调用存储过程来执行这些预定义的操作，可实现代码复用，提高数据库操作的效率和安全性，减少网络传输量
触发器是一种特殊的存储过程，它在特定的数据库事件（如INSERT、UPDATE、DELETE操作）发生时自动执行。触发器可用于实现数据的完整性约束、数据审计、日志记录等功能，能在数据发生变化时自动进行一些额外的操作或检查，确保数据库中的数据符合特定的业务规则和要求

数据库中的死锁是指两个或多个事务在执行过程中，因争夺资源而造成的一种互相等待的现象

外接是指两个表在进行操作时，不仅返回符合连接和查询条件的元组，还返回不符合条件的一些元组；
左外连接是指返回左表中仅符合连接条件不符合查询条件的元组：
右外连接是指返回右表中仅符合连接条件不符合查询条件的元组：
全外连接是左外连接和右外连接去掉重复项的元组集并集

索引是存储在数据库中的一个物理结构，是实际存在的，相当于一本书的目录，常用B+树实现
键是一个逻辑概念，不是数据库中的物理部分

视图是从一个或几个基本表中导出的表，是一个虚表。数据库中只存放视图的定义，而不存放视图对应的数据。基本表中的数据发生变化时，从视图中查询出来的数据也就随之发生变化
作用：

• 能够简化用户的操作
• 使用户能以多种角度看待同一数据
• 在一定程度上提供了数据的逻辑独立性
• 能够对秘密数据提供安全保护

游标：将查询出来的结果集作为一个单元来进行处理，适用于逐行处理数据

安全性技术：用户标识和鉴别、多层存取控制、审计、视图、数据加密
存取控制是指确保只授权给有资格的用户访问数据库的权限，且令所有未被授权的人员无法接近数据
两个部分：定义用户权限和合法权限检查；两种方法：

1. 自主存取控制（DAC）：用户对不同的数据库对象有不同的存取权限，不同的用户对同一对象也有不同的权限
   
2. 强制存取控制（MAC）：每一个数据库对象被标以一定的密级，每一个用户也被授予一定级别的许可证，只有具有合法许可证的用户才可以进行存取

断言是指更具有一般性的约束，断言创建后，任何涉及到断言中的关系的操作会引发数据库对断言的检查，任何使断言为假的操作都会被拒绝执行

悲观锁:总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁（共享资源每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程）。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。Java中synchronized和ReentrantLock等独占锁就是悲观锁思想的实现
乐观锁:总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号机制和CAS算法实现。乐观锁适用于多读的应用类型， 这样可以提高吞吐量 ，像数据库提供的类似于write_condition机制，其实都是提供的乐观锁。在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS(compare and swap)实现的
ABA 问题:如果一个变量V初次读取的时候是A值，并且在准备赋值的时候检查到它仍然是A值，那我们就能说明它的值没有被其他线程修改过了吗？很明显是不能的，因为在这段时间它的值可能被改为其他值，然后又改回A，那CAS操作就会误认为它从来没有被修改过。这个问题被称为CAS操作的 "ABA"问题

MVCC，全称Multi-Version Concurrency Control，即多版本并发控制。MVCC是一种并发控制的方法，一般在数据库管理系统中，实现对数据库的并发访问，在编程语言中实现事务内存

DBA(Database Administrator)

三级模式结构是描述数据库系统中数据抽象层次的概念模型,它包括:

• 外模式（External Model）
  • 也称为用户视图或应用程序视图
  • 描述数据库中针对特定用户或应用程序的数据视图
  • 用户只能看到和操作外模式所定义的数据子集
• 概念模式（Conceptual Model）
  • 也称为逻辑模型或数据库模型
  • 描述数据库中全部数据的逻辑结构和特性
  • 这是数据库的整体数据模型,独立于任何硬件或软件实现
• 内模式（Internal Model）
  • 也称为存储模型或物理模型
  • 描述数据在计算机内部如何存储和组织的细节
  • 包括数据存储结构、存储介质、存取路径等物理存储细节

三级模式结构提供了以下优点:

1. 数据独立性:
   • 外模式独立于概念模式,概念模式独立于内模式
   • 可以在不影响上层的情况下修改底层模式
2. 灵活性和可扩展性:
   • 用户可根据需求定制外模式
   • 数据库可根据应用需求进行修改和扩展
3. 安全性和隐私性:
   • 通过外模式控制用户对数据的访问权限
   • 内模式的物理存储细节对用户是隐藏的

完整性约束:

• 实体完整性：关系模式中的主码不能为空值
• 参照完整性：关系模式中的外码只能是空值或者另一关系模式的主码
• 用户定义完整性：关系模式中针对某一属性的约束

SQL（Structured Query Language）是一种专门用于管理和操作关系型数据库的标准化查询语言。它主要包括以下几个方面:

1. 数据定义语言（DDL）:
   • 用于创建、修改和删除数据库对象,如数据库、表、视图等
   • 常用命令包括 CREATE、ALTER、DROP 等
2. 数据操作语言（DML）:
   • 用于对数据库中的数据进行增删改查等操作
   • 常用命令包括 SELECT、INSERT、UPDATE、DELETE 等
3. 数据控制语言（DCL）:
   • 用于管理数据库的访问权限和安全策略
   • 常用命令包括 GRANT、REVOKE 等
4. 事务控制语言（TCL）:
   • 用于管理数据库事务,确保数据的完整性和一致性
   • 常用命令包括 COMMIT、ROLLBACK 等

自然连接是等值连接的一种特殊情况：
等值连接要求连接的是值相等的分量，两个关系中可以没有相同的属性；进行自然连接的两个关系中必须有相同的属性
等值连接不要求去掉重复属性列；自然连接时需要除掉重复的属性列
左/右外连接是在两表进行自然连接，只把左/右表要舍弃的保留在结果集中
全外连接是在两表进行自然连接，只把左表和右表要舍弃的都保留在结果集中，相对应的列上填null

ACID特性包括：

• 隔离性：一个事务的执行不能被其他事务所于扰
• 原子性：事务是一个不可分割的单位，要么全做，要么全不做
• 一致性：事务执行的结果必须使数据库从一个一致性状态变到另一个一致性状态
• 永久性：一旦事务被提交，它对数据库的改变就是永久的

日志文件、后备副本可用于数据库恢复

排他锁（写锁）：当数据被加上写锁，其他事务不能对该数据进行读和写
共享锁（S读锁）：当数据被加上读锁，允许其他事务对该数据进行读，不允许写

封锁协议:

1. 一级封锁协议：事务在修改数据之前加写锁，真到事务结束才释放。该协议可以防止丢失修改
   
2. 二级封锁协议：在一级封锁协议的基础上，加上了事务在读取数据之前对其加读锁，读完后即可释放读锁。该协议避免了读脏数据
   
3. 三级封锁协议：在一级封锁协议的基础上，加上了事务在读取数据之前必须加上读锁，直到事务结束才释放。该协议解决了不可重复读问题

范式(normal form):

第一范式要求数据库表中的每一列都是不可分割的原子值，即表中的每个字段都只能存储单一值，不能包含集合、数组或多值字段
第二范式要求数据库表满足第一范式，并且表中的每个非主属性（不属于候选键的属性）必须完全依赖于主键，不能存在部分依赖(非主属性依赖于主键的一部分，而不是整个主键)
第三范式要求数据库表满足第二范式，并且表中的每个非主属性必须直接依赖于主键，不能存在传递依赖(非主属性依赖于另一个非主属性，而另一个非主属性依赖于主键)
BC范式要求数据库表满足第二范式，并且所有属性（包括主属性）都必须依赖于候选键，任何属性都不能依赖于非候选键，即表中每个非平凡函数依赖(X->Y，但Y不是X的子集) X → Y 中，X 必须是超键

类型	描述
函数依赖	一个属性的值唯一确定另一个属性的值
部分依赖	非主属性依赖于主键的一部分
全依赖	非主属性依赖于主键的全部字段
传递依赖	非主属性通过另一个非主属性间接依赖于主键
多值依赖	一个属性的值确定多个属性的值，但这些属性彼此独立

1. 由1NF到2NF，消除了非主属性对主属性的部分函数依赖
2. 由2NF到3NF，消除了非主属性对主属性的传递函数依赖
3. 由3NF到BCNF，消除了主属性对码的部分函数依赖和传递函数依赖

常见的启发式优化规则包括:

1. 选择性规则:
   • 优先选择选择性高的索引或条件,即缩小数据范围的索引或条件
   • 这样可以尽早对数据进行过滤,减少后续处理的数据量
2. 顺序规则:
   • 优先执行成本较低的操作,如索引扫描等
   • 将成本较高的操作,如全表扫描、排序等放在最后执行
3. 嵌套规则:
   • 优先处理内层的子查询或表达式
   • 将外层的操作放在最后执行
4. 分区规则:
   • 优先利用分区表的分区信息进行数据过滤
   • 尽可能缩小扫描的分区范围
5. 物化视图规则:
   • 优先利用已经物化的视图进行查询
   • 可以避免重复计算

同步问题:

• 当前读：像select lock in share mode(共享锁), select for update ; update, insert ,delete(排他锁)这些操作都是一种当前读，为什么叫当前读？就是它读取的是记录的最新版本，读取时还要保证其他并发事务不能修改当前记录，会对读取的记录进行加锁
• 快照读：像不加锁的select操作就是快照读，即不加锁的非阻塞读；快照读的前提是隔离级别不是串行级别，串行级别下的快照读会退化成当前读；之所以出现快照读的情况，是基于提高并发性能的考虑，快照读的实现是基于多版本并发控制，即MVCC,可以认为MVCC是行锁的一个变种，但它在很多情况下，避免了加锁操作，降低了开销；既然是基于多版本，即快照读可能读到的并不一定是数据的最新版本，而有可能是之前的历史版本

MVCC就是为了实现读-写冲突不加锁，而这个读指的就是快照读, 而非当前读，当前读实际上是一种加锁的操作，是悲观锁的实现
导致 MySQL 索引失效的常见场景：

1. 联合索引不满足最左匹配原则
2. 模糊查询最前面的为不确定匹配字符
3. 索引列参与了运算
4. 索引列使用了函数
5. 索引列存在类型转换
6. 索引列使用 is not null 查询

OS

操作系统的特征：并发性、共享性、异步性、虚拟性:

1. 并发和共享互为存在的条件
2. 虚拟以并发和资源共享为前提：为使并发进程能更方便、更有效地共享资源,操作系统常采用多种虚技未来在逻辑上增加CPU和设备的数量以及存储器的容量，从而解决众多并发进程对有限的系统资源的争用问题
3. 异步性是并发和共享的必然结果

ai

云计算(Cloud Computing)是一种基于互联网的计算模式,它通过网络提供按需获取和使用计算资源的服务。云计算主要包括以下特点:

1. 资源共享:
   • 云计算将硬件、软件等IT资源集中管理和运营,用户可以按需使用
   • 资源按需分配,提高了资源利用率
2. 按需服务:
   • 用户可以根据实际需求灵活调配和使用云计算资源
   • 按需付费,用多少付多少
3. 高可用性:
   • 云计算平台具有高可靠性和容错性,能确保服务的可用性
   • 能够应对硬件故障、网络中断等情况
4. 规模弹性:
   • 云计算能根据用户需求自动扩展或收缩资源
   • 用户可根据业务需求随时调整资源使用量
5. 虚拟化:
   • 云计算基于虚拟化技术,可将物理硬件抽象为可编程的虚拟资源
   • 提高了资源利用率和管理效率

主要服务模式包括:

• IaaS(基础设施即服务)
• PaaS(平台即服务)
• SaaS(软件即服务)

区块链(Blockchain)是一种基于分布式账本技术的数字记录系统,具有以下主要特点:

1. 分布式账本
   • 区块链是一种去中心化的分布式账本,没有单一的中心控制节点
   • 账本信息存储在全网各节点的数据库中,形成分布式的数据存储
2. 链式数据结构
   • 账本信息以时间顺序组织成一个个数据块(区块),并以加密方式链接在一起
   • 每个新区块都包含前一个区块的信息,形成一个不可篡改的链式结构
3. 加密安全性
   • 区块链使用密码学技术(如哈希、数字签名)确保数据的安全性和完整性
   • 一旦记录进入区块链,就难以被删除或篡改
4. 点对点传输
   • 区块链网络采用点对点的通信模式,交易信息在网络中直接传播
   • 不需要中心化的第三方中介机构参与
5. 共识机制
   • 区块链节点通过共识算法(如工作量证明、权益证明等)达成对交易记录的共识
   • 确保整个网络的数据一致性和可靠性

区块链的主要应用包括:

• 加密货币(比特币、以太坊等)
• 供应链管理
• 数字资产交易
• 身份认证
• 智能合约

ai专业名词:

• 损失函数：用于衡量模型预测结果与真实标签之间的差异，如均方误差、交叉熵等，训练的目标是最小化损失函数
• 优化算法：用于更新模型参数以最小化损失函数的方法，如随机梯度下降及其变种Adagrad、 Adadelta、Adam等
• 准确率：分类任务中，预测正确的样本数占总样本数的比例
• 召回率：在分类任务中，真实为正例的样本中被正确预测为正例的比例
• F1值：综合考虑准确率和召回率的评估指标，是二者的调和平均数
• 超参数：在模型训练前需要手动设置的参数，如学习率、迭代次数、神经网络的层数、隐藏层节点数等，它们影响模型的训练过程和最终性能，通常需要通过调参来确定最优值

分类(Classification)和聚类(Clustering)区别:

1. 监督学习 vs 无监督学习:
   • 分类是一种监督学习任务,需要有预先标记的训练数据
   • 聚类是一种无监督学习任务,不需要预先标记的训练数据
2. 目标不同:
   • 分类的目标是将新的数据样本分类到预定义的类别中
   • 聚类的目标是发现数据中自然存在的分组(簇)
3. 输出形式不同:
   • 分类输出的是预定义的类别标签
   • 聚类输出的是数据被划分到的不同簇
4. 应用场景不同:
   • 分类常用于预测任务,如垃圾邮件识别、信用评级等
   • 聚类常用于探索性数据分析,如客户细分、异常检测等

评估:

• 分类任务：准确率（Accuracy）、精确率
• (Precision）、召回率（Recall）、F1Score。回归任务：均方误差（MSE）、平均绝对误差(MAE)
• 泛化能力验证：交叉验证（Cross+ Validation)

过拟合（Overfitting）
表现：模型在训练集表现好，测试集差
解决：增加数据量、正则化、减少模型复杂度、早停法（EarlyStopping）
欠拟合（Underfitting）
表现：模型在训练集和测试集均表现差
解决：增加模型复杂度、添加更多特征、减少正则化

科研

knowledge

梯度

梯度的定义和性质如下:
定义: 设 f(x1, x2, ..., xn) 是一个多变量函数, 梯度是一个 n 维列向量:∇f = [∂f/∂x1, ∂f/∂x2, ..., ∂f/∂xn]^T
其中 ∂f/∂xi 表示 f 对 xi 的偏导数
几何意义:

• 梯度指向函数值增长最快的方向
• 梯度的方向就是函数值增长最快的方向, 梯度的模长就是函数值增长最快的速率

性质:

• 梯度为 0 的点是函数的临界点, 可能是极大值、极小值或鞍点
• 沿着梯度方向移动, 函数值会单调增加
• 梯度下降法利用这一性质, 通过不断沿负梯度方向移动来求解优化问题的最小值

应用:

• 在机器学习中, 梯度被用于训练各种模型, 如线性回归、神经网络等
• 在优化算法中, 如 Interior-Point 算法中的牛顿法, 梯度被用于计算搜索方向
• 在数值分析中, 梯度被用于求解偏微分方程

R 树

一棵 R 树满足如下的性质

1. 除非它是根结点之外，所有叶子结点包含有 m 至 M 个记录索引（条目）作为根结点的叶子结点所具有的记录个数可以少于 m通常，m=M/2
2. 对于所有在叶子中存储的记录（条目），I 是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）
3. 每一个非叶子结点拥有 m 至 M 个孩子结点，除非它是根结点
4. 对于在非叶子结点上的每一个条目，i 是最小的可以在空间上完全覆盖这些条目所代表的店的矩形（同性质 2）
5. 所有叶子结点都位于同一层，因此 R 树为平衡树

结点：

• 叶子结点所保存的数据形式为：(I, tuple-identifier)
  • 其中，tuple-identifier 表示的是一个存放于数据库中的 tuple，也就是一条记录，它是 n 维的I 是一个 n 维空间的矩形，并可以恰好框住这个叶子结点中所有记录代表的 n 维空间中的点
• R 树的非叶子结点存放的数据结构为：(I, child-pointer)
  • 其中，child-pointer 是指向孩子结点的指针，I 是覆盖所有孩子结点对应矩形的矩形

HMM

HMM 是 Hidden Markov Model 的缩写, 即隐马尔可夫模型它是一种重要的概率图模型, 广泛应用于语音识别、自然语言处理、生物信息学等领域

隐马尔可夫模型的主要特点如下:

• 状态空间: HMM 包含一组隐藏的状态, 这些状态不能直接观测到, 而是通过观测数据来推断
• 状态转移: 模型在隐藏状态之间进行马尔可夫转移, 即每个状态只依赖于前一个状态
• 观测概率: 每个隐藏状态都与一个观测数据相关联, 并有一个观测概率分布

Top-k Hidden Markov Model (Top-k HMM) 算法是一种用于高效计算 HMM 中 Top-k 概率最高的状态路径的算法它的主要思想如下:

• 初始化: 将 HMM 的初始状态概率分布、转移概率矩阵和观测概率矩阵作为输入 设置需要计算的 Top-k 个状态路径的数量 k
• 动态规划过程: 使用动态规划的方法, 递推计算每个时刻 t 的 Top-k 状态路径 在每个时刻 t, 保留 Top-k 概率最高的状态路径
• 回溯过程: 从最后一个时刻 T 开始, 根据保留的 Top-k 状态路径, 逐步回溯得到 Top-k 概率最高的完整状态路径
• 输出结果: 输出计算得到的 Top-k 概率最高的状态路径

编程

机试参考

devcpp开启调试功能:

1. 点击“工具”菜单--编译选项--“代码生成/优化”--连接器--“产生调试信息”为YES,单击“确定”实现调试过程中，选择指定变量，即可显示相应变量的值，并且随着程序的变化而变化
2. 点击”工具“菜单--环境选项--”浏览DEBUG变量“--选择”查看鼠标指向的变量

#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <sstream>
#include <unordered_map>
#include <map>
#include <functional>
#include <unordered_set>
#include <stack>
#include <set>
#include <queue>
using namespace std;

vector

vector包含着一系列连续存储的元素,其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成，而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度

构造函数:

• vector(); 无参数 - 构造一个空的vector
• vector(size_type num); 数量(num) - 构造一个大小为num，值为Type默认值的Vector
• vector(size_type num, const TYPE &val); 数量(num)和值(val) - 构造一个初始放入num个值为val的元素的Vector
• vector(const vector &from); vector(from) - 构造一个与vector from 相同的vector
• vector(input_iterator start, input_iterator end); 迭代器(start)和迭代器(end) - 构造一个初始值为[start,end)区间元素的Vector(注:半开区间).
• vector(initializer_list<value_type> il, const allocator_type& alloc = allocator_type());C++11新提供的方法，类似如下方式：
  • std::vector<int>a{1, 2, 3, 4, 5};
  • std::vector<int>a = {1, 2, 3, 4, 5};

常用API：

• Operators : 对vector进行赋值或比较
  • v1 == v2
  • v1 != v2
  • v1 <= v2
  • v1 >= v2
  • v1 < v2
  • v1 > v2
  • v[]
• assign()对Vector中的元素赋值
• at() : 返回指定位置的元素
• back() : 返回最末一个元素
• begin() : 返回第一个元素的迭代器
• capacity() : 返回vector所能容纳的元素数量(在不重新分配内存的情况下)
• clear() : 清空所有元素
• empty() : 判断Vector是否为空（返回true时为空）
• end() : 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)
• erase() : 删除指定元素
• front() : 返回第一个元素
• get_allocator() : 返回vector的内存分配器
• insert() : 插入元素到Vector中
• max_size() : 返回Vector所能容纳元素的最大数量（上限）
• pop_back() : 移除最后一个元素
• push_back() : 在Vector最后添加一个元素
• rbegin() : 返回Vector尾部的逆迭代器
• rend() : 返回Vector起始的逆迭代器
• reserve() : 设置Vector最小的元素容纳数量
• resize() : 改变Vector元素数量的大小
• size() : 返回Vector元素数量的大小
• swap() : 交换两个Vector

stack

C++ stack（堆栈）实现了一个先进后出（FILO）的数据结构

构造函数：

• stack<T> stkT; : 采用模板类实现，stack对象的默认构造形式
• stack(const stack &stk); : 拷贝构造函数

常用方法：

• size(): 返回栈中的元素数
• top(): 返回栈顶的元素
• pop(): 从栈中取出并删除元素
• push(x): 向栈中添加元素x
• empty(): 在栈为空时返回true

set

集合中以一种特定的顺序保存唯一的元素
构造函数:

• set(); 无参数 - 构造一个空的set
• set(InputIterator first, InputIterator last) : 迭代器的方式构造set
• set(const set &from); : copyd的方式构造一个与set from 相同的set
• set(input_iterator start, input_iterator end); 迭代器(start)和迭代器(end)
• 构造一个初始值为[start,end)区间元素的Vector(注:半开区间)
• set (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());C++11新提供的方法，类似如下方式：
  • std::set<int>a{1, 2, 3, 4, 5};

常用API：

• begin() : 返回指向第一个元素的迭代器
• clear() : 清除所有元素
• count() : 返回某个值元素的个数
• empty() : 如果集合为空，返回true
• end() : 返回指向最后一个元素的迭代器
• equal_range() : 返回集合中与给定值相等的上下限的两个迭代器
• erase() : 删除集合中的元素
• find() : 返回一个指向被查找到元素的迭代器
• get_allocator() : 返回集合的分配器
• insert() : 在集合中插入元素
• lower_bound() : 返回指向大于（或等于）某值的第一个元素的迭代器
• key_comp() : 返回一个用于元素间值比较的函数
• max_size() : 返回集合能容纳的元素的最大限值
• rbegin() : 返回指向集合中最后一个元素的反向迭代器
• rend() : 返回指向集合中第一个元素的反向迭代器
• size() : 集合中元素的数目
• swap() : 交换两个集合变量
• upper_bound() : 返回大于某个值元素的迭代器
• value_comp() : 返回一个用于比较元素间的值的函数

unordered_set

begin	指定受控序列的开头
bucket	获取键值的存储桶编号
bucket_count	获取存储桶数
bucket_size	获取存储桶的大小
cbegin	指定受控序列的开头
cend	指定受控序列的末尾
clear	删除所有元素
contains	检查 unordered_set 中是否包含具有指定键的元素。
count	查找与指定键匹配的元素数，非multi的情况下非0即1。
emplace	添加就地构造的元素
emplace_hint	添加就地构造的元素，附带提示
empty	测试元素是否存在
end	指定受控序列的末尾
equal_range	查找与指定键匹配的范围
erase	移除指定位置处的元素
find	查找与指定键匹配的元素
get_allocator	获取存储的分配器对象
hash_function	获取存储的哈希函数对象
insert	添加元素
key_eq	获取存储的比较函数对象
load_factor	对每个存储桶的平均元素数进行计数
max_bucket_count	获取最大的存储桶数
max_load_factor	获取或设置每个存储桶的最多元素数
max_size	获取受控序列的最大大小
rehash	重新生成哈希表
size	对元素数进行计数
swap	交换两个容器的内容
unordered_set	构造容器对象

queue

C++队列是一种容器适配器，它给予程序员一种先进先出(FIFO)的数据结构

构造函数：

• explicit queue (const container_type& ctnr);
• explicit queue (container_type&& ctnr = container_type());
• template <class Alloc> explicit queue (const Alloc& alloc);
• template <class Alloc> queue (const container_type& ctnr, const Alloc& alloc);
• template <class Alloc> queue (container_type&& ctnr, const Alloc& alloc);
• template <class Alloc> queue (const queue& x, const Alloc& alloc);
• template <class Alloc> queue (queue&& x, const Alloc& alloc);

常用API：

• back() : 返回最后一个元素
• empty() : 如果队列空则返回真
• front() : 返回第一个元素
• pop() : 删除第一个元素
• push() : 在末尾加入一个元素
• size() : 返回队列中元素的个数

list

Lists将元素按顺序储存在链表中. 与 向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢.

构造函数：

• list (const allocator_type& alloc = allocator_type());
• list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type());
• template <class InputIterator> list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
• list (const list& x);

常用API：

• assign() : 给list赋值
• back() : 返回最后一个元素
• begin() : 返回指向第一个元素的迭代器
• clear() : 删除所有元素
• empty() : 如果list是空的则返回true
• end() : 返回末尾的迭代器
• erase() : 删除一个元素
• front() : 返回第一个元素
• get_allocator() : 返回list的配置器
• insert() : 插入一个元素到list中
• max_size() : 返回list能容纳的最大元素数量
• merge() : 合并两个list
• pop_back() : 删除最后一个元素
• pop_front() : 删除第一个元素
• push_back() : 在list的末尾添加一个元素
• push_front() : 在list的头部添加一个元素
• rbegin() : 返回指向第一个元素的逆向迭代器
• remove() : 从list删除元素
• remove_if() : 按指定条件删除元素
• rend() : 指向list末尾的逆向迭代器
• resize() : 改变list的大小
• reverse() : 把list的元素倒转
• size() : 返回list中的元素个数
• sort() : 给list排序
• splice() : 合并两个list
• swap() : 交换两个list
• unique() : 删除list中重复的元素

map

C++ Maps是一种关联式容器，包含“关键字/值”对

构造函数：

• map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
• template <class InputIterator> map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type());
• map (const map& x);
• map (const map& x, const allocator_type& alloc);
• map (map&& x);
• map (map&& x, const allocator_type& alloc);
• map (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

常用API：

• begin() : 返回指向map头部的迭代器
• clear() : 删除所有元素
• count() : 返回指定元素出现的次数
• empty() : 如果map为空则返回true
• end() : 返回指向map末尾的迭代器
• equal_range() : 返回特殊条目的迭代器对
• erase() : 删除一个元素
• find() : 查找一个元素
• get_allocator() : 返回map的配置器
• insert() : 插入元素
• key_comp() : 返回比较元素key的函数
• lower_bound() : 返回键值>=给定元素的第一个位置
• max_size() : 返回可以容纳的最大元素个数
• rbegin() : 返回一个指向map尾部的逆向迭代器
• rend() : 返回一个指向map头部的逆向迭代器
• size() : 返回map中元素的个数
• swap() : 交换两个map
• upper_bound() : 返回键值>给定元素的第一个位置
• value_comp() : 返回比较元素value的函数

unordered_map

类型定义	说明
allocator_type	用于管理存储的分配器的类型
const_iterator	受控序列的常量迭代器的类型
const_local_iterator	受控序列的常量存储桶迭代器的类型
const_pointer	元素的常量指针的类型
const_reference	元素的常量引用的类型
difference_type	两个元素间的带符号距离的类型
hasher	哈希函数的类型
iterator	受控序列的迭代器的类型
key_equal	比较函数的类型
key_type	排序键的类型
local_iterator	受控序列的存储桶迭代器的类型
mapped_type	与每个键关联的映射值的类型
pointer	指向元素的指针的类型
reference	元素的引用的类型
size_type	两个元素间的无符号距离的类型
value_type	元素的类型

成员函数	说明
at	查找具有指定键的元素
begin	指定受控序列的开头
bucket	获取键值的存储桶编号
bucket_count	获取存储桶数
bucket_size	获取存储桶的大小
cbegin	指定受控序列的开头
cend	指定受控序列的末尾
clear	删除所有元素
count	查找与指定键匹配的元素数
contains	检查 unordered_map 中是否包含具有指定键的元素
emplace	添加就地构造的元素
emplace_hint	添加就地构造的元素，附带提示
empty	测试元素是否存在
end	指定受控序列的末尾
equal_range	查找与指定键匹配的范围
erase	移除指定位置处的元素
find	查找与指定键匹配的元素
get_allocator	获取存储的分配器对象
hash_function	获取存储的哈希函数对象
insert	添加元素
key_eq	获取存储的比较函数对象
load_factor	对每个存储桶的平均元素数进行计数
max_bucket_count	获取最大的存储桶数
max_load_factor	获取或设置每个存储桶的最多元素数
max_size	获取受控序列的最大大小
rehash	重新生成哈希表
size	对元素数进行计数
swap	交换两个容器的内容
unordered_map	构造容器对象

运算符	说明
unordered_map::operator[]	查找或插入具有指定键的元素
unordered_map::operator=	复制哈希表

string

c++字符串数组需要指定长度，如vec.push_back(string(1,char c)) ，将字符串转化为字面数字需要用stoi(来自string库)函数 栈3

1.string构造函数

• string();//创建一个空的字符串
• string(const string& str);//使用一个string对象初始化另一个string对象
• string(const char* s);//使用字符串s初始化
• string(int n,char c);//使用n个字符c初始化

2.string基本赋值操作

• string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
• string& operator=(const string &s);//把字符串s赋值给当前的字符串
• string& operator=(char c);//字符赋值给当前的字符串
• string& assign(const char* s);//把字符串s赋值给当前的字符串
• string& assign(const char* s,int n);//把字符串s的前n个字符赋值给当前的字符串
• string& assign(const string &s);//把字符串s赋值给当前的字符串
• string& assign(int n,char c);//用n个字符c赋值给当前字符串
• string& assign(const string &s,int start,int n);//将s从start开始n个字符赋值给字符串

3.string存取字符操作

• char& operator[](int n);//通过[]方式取字符
• char& at(int n);//通过at方法获取字符

4.string拼接操作

• string& operator+=(const string& str);//重载+=运算符
• string& operator+=(const char* str);//重载+=运算符
• string& operator+=(const char c);//重载+=运算符
• string& append(const char *s);//把字符串s连接到当前字符串结尾
• string& append(const char *s,int n);//把字符串s的前n个字符连接到当前字符串结尾
• string& append(const string &s);//同operator+=（）
• string& append(const string &s,int pos,int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
• string& append(int n,char c);//在当前字符串结尾添加n个字符c

5.string查找和替换

• int find(const string& str,int pos = 0)const;//查找str第一次出现的位置，从pos开始查找
• int find(const char* s,int pos = 0)const;//查找s第一次出现位置，从pos开始查找
• int find(const char *s,int pos,int n)const;//从pos位置查找s的前n个字符第一次位置
• int find(const char c,int pos = 0)const;//查找字符c第一次出现位置
• int rfind(const string& str, int pos = npos)const;//查找str最后一次出现位置，从pos开始查找
• int rfind(const char* s,int pos = npos)const;//查找s最后一次出现位置，从pos开始查找
• int rfind(const char* s,int pos,int n )const;//从pos查找s的前n个字符最后一次位置
• int rfind(const char c,int pos = 0)const;//查找字符c最后一次出现位置
• string& replace(int pos,int n,const string& str);//替换从pos开始的n个字符为字符串str
• string& replace(int pos,int n,const char* s);//替换从pos开始的n个字符为字符串s

6.string 比较操作

• int compare(const string &s)const;//与字符串s比较
• int compare(const char*s)const;//与字符串s比较
• compare函数在>时返回1，<时返回-1，相等时返回0，比较区分大小写，逐个字符比较

7.string子串

• string substr(int pos = 0,int n = npos)const;//返回由pos开始的n个字符组成的字符串

8.string插入和删除操作

• string& insert(int pos,const char* s);//插入字符串
• string& insert(int pos,const string &str);//插入字符串
• string& insert(int pos,int n,char c);//在指定位置插入n个字符c
• string& erase(int pos,int n = npos);//删除从pos开始的n个字符

deque

deque是Double-Ended Queues(双向队列)的缩写

双向队列和向量很相似，但是它允许在容器头部快速插入和删除（就像在尾部一样）

1.deque构造函数

• deque<T> queT;//queue采用模板类实现，queue对象的默认构造形式
• deque<T> queT(size);//构造大小为size的deque，其中值为T类型的默认值
• deque<T> queT(size, val);//构造大小为size的deque，其中值为val
• deque(const deque &que);//拷贝构造函数
• deque(input_iterator start, input_iterator end);//迭代器构造函数

2.deque存取、插入和删除操作

• back();//返回最后一个元素
• front();//返回第一个元素
• insert();//
• pop_back();//删除尾部的元素
• pop_front();//删除头部的元素
• push_back();//在尾部加入一个元素
• push_front();//在头部加入一个元素
• at();//访问指定位置元素

3.deque赋值操作

• operator[] (size_type n);//重载[]操作符

4.deque大小操作

• empty();//判断队列是否为空
• size();//返回队列的大小

priority_queue

优先队列类似队列， 但是在这个数据结构中的元素按照一定的规则排列有序

在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高优先级先出 （first in, largest out）的行为特征

首先要包含头文件#include<queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的

构造函数： priority_queue<Type, Container, Functional>

• Type 就是数据类型，
• Container 就是容器类型（Container必须是具备随机存取能力的容器，支持如下方法：empty(), size(), front(), push_back(),pop_back()。比如vector,deque等等，但不能用list。STL里面默认用的是vector）。可选
• Functional 就是比较的方式。可选

当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆(Functional是less)

api和队列基本操作相同:

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

cpp vector

algorithm

adjacent_find	搜索相等或满足指定条件的两个相邻元素
all_of	当给定范围中的每个元素均满足条件时返回 true
any_of	当指定元素范围中至少有一个元素满足条件时返回 true
binary_search	测试已排序的范围中是否有等于指定值的元素，或在二元谓词指定的意义上与指定值等效的元素
clamp
copy	将一个源范围中的元素值分配到目标范围，循环访问元素的源序列并将它们分配在一个向前方向的新位置
copy_backward	将一个源范围中的元素值分配到目标范围，循环访问元素的源序列并将它们分配在一个向后方向的新位置
copy_if	复制给定范围中对于指定条件为 true 的所有元素
copy_n	复制指定数量的元素
count	返回范围中其值与指定值匹配的元素的数量
count_if	返回范围中其值与指定条件匹配的元素的数量
equal	逐个元素比较两个范围是否相等或是否在二元谓词指定的意义上等效
equal_range	在排序的范围中查找符合以下条件的位置对：第一个位置小于或等效于指定元素的位置，第二个位置大于此元素位置，等效意义或用于在序列中建立位置的排序可通过二元谓词指定
fill	将相同的新值分配给指定范围中的每个元素
fill_n	将新值分配给以特定元素开始的范围中的指定数量的元素
find	在范围中找到具有指定值的元素的第一个匹配项位置
find_end	在范围中查找与指定序列相同的最后一个序列，或在二元谓词指定的意义上等效的最后一个序列
find_first_of	在目标范围中搜索若干值中任意值的第一个匹配项，或搜索在二元谓词指定的意义上等效于指定元素集的若干元素中任意元素的第一个匹配项
find_if	在范围中找到满足指定条件的元素的第一个匹配项位置
find_if_not	返回指示的范围中不满足条件的第一个元素
for_each	将指定的函数对象按向前顺序应用于范围中的每个元素并返回此函数对象
for_each_n
generate	将函数对象生成的值分配给范围中的每个元素
generate_n	将函数对象生成的值分配给范围中指定数量的元素，并返回到超出最后一个分配值的下一位置
includes	测试一个排序的范围是否包含另一排序范围中的所有元素，其中元素之间的排序或等效条件可通过二元谓词指定
inplace_merge	将两个连续的排序范围中的元素合并为一个排序范围，其中排序条件可通过二元谓词指定
is_heap	如果指定范围中的元素形成堆，则返回 true
is_heap_until	如果指定范围形成直到最后一个元素的堆，则返回 true
is_partitioned	如果给定范围中对某个条件测试为 true 的所有元素在测试为 true 的所有元素之前，则返回 false
is_permutation	确定给定范围的元素是否形成有效排列
is_sorted	如果指定范围中的元素按顺序排序，则返回 true
is_sorted_until	如果指定范围中的元素按顺序排序，则返回 true
iter_swap	交换由一对指定迭代器引用的两个值
lexicographical_compare	逐个元素比较两个序列以确定其中的较小序列
lower_bound	在排序的范围中查找其值大于或等效于指定值的第一个元素的位置，其中排序条件可通过二元谓词指定
make_heap	将指定范围中的元素转换到第一个元素是最大元素的堆中，其中排序条件可通过二元谓词指定
max	比较两个对象并返回较大对象，其中排序条件可通过二元谓词指定
max_element	在指定范围中查找最大元素的第一个匹配项，其中排序条件可通过二元谓词指定
merge	将两个排序的源范围中的所有元素合并为一个排序的目标范围，其中排序条件可通过二元谓词指定
min	比较两个对象并返回较小对象，其中排序条件可通过二元谓词指定
min_element	在指定范围中查找最小元素的第一个匹配项，其中排序条件可通过二元谓词指定
minmax	比较两个输入参数，并按最小到最大的顺序将它们作为参数对返回
minmax_element	在一次调用中执行由 min_element 和 max_element 执行的操作
mismatch	逐个元素比较两个范围是否相等或是否在二元谓词指定的意义上等效，并找到出现不同的第一个位置
<alg> move	移动与指定范围关联的元素
move_backward	将一个迭代器的元素移动到另一迭代器移动从指定范围的最后一个元素开始，并在此范围的第一个元素结束
next_permutation	重新排序范围中的元素，以便使用按字典顺序的下一个更大排列（如果有）替换原有排序，其中“下一个”的意义可通过二元谓词指定
none_of	当给定范围中没有元素满足条件时返回 true
nth_element	对范围内的元素分区，正确找到范围中序列的第 n 个元素，以使序列中位于此元素之前的所有元素小于或等于此元素，位于此元素之后的所有元素大于或等于此元素
partial_sort	将范围中指定数量的较小元素按非降序顺序排列，或根据二元谓词指定的排序条件排列
partial_sort_copy	将源范围中的元素复制到目标范围，其中源元素按降序或二元谓词指定的其他顺序排序
partition	将范围中的元素分为两个不相交的集，满足一元谓词的元素在不满足一元谓词的元素之前
partition_copy	将条件为 true 的元素复制到一个目标，将条件为 false 的元素复制到另一目标元素必须来自于指定范围
partition_point	返回给定范围中不满足条件的第一个元素元素经过排序，满足条件的元素在不满足条件的元素之前
pop_heap	移除从堆顶到范围中倒数第二个位置之间的最大元素，然后将剩余元素形成新堆
prev_permutation	重新排序范围中的元素，以便使用按字典顺序的下一个更大排列（如果有）替换原有排序，其中“下一个”的意义可通过二元谓词指定
push_heap	将范围末尾的元素添加到包括范围中前面元素的现有堆中
random_shuffle	将范围中 N 个元素的序列重新排序为随机 N! 种序列中的 可能排列之一
remove	从给定范围中消除指定值，而不影响剩余元素的顺序，并返回不包含指定值的新范围的末尾
remove_copy	将源范围中的元素复制到目标范围（不复制具有指定值的元素），而不影响剩余元素的顺序，并返回新目标范围的末尾
remove_copy_if	将源范围中的元素复制到目标范围（不复制满足谓词的元素），而不影响剩余元素的顺序，并返回新目标范围的末尾
remove_if	从给定范围中消除满足谓词的元素，而不影响剩余元素的顺序，并返回不包含指定值的新范围的末尾
replace	检查范围中的每个元素，并替换与指定值匹配的元素
replace_copy	检查源范围中的每个元素，并替换与指定值匹配的元素，同时将结果复制到新的目标范围
replace_copy_if	检查源范围中的每个元素，并替换满足指定谓词的元素，同时将结果复制到新的目标范围
replace_if	检查范围中的每个元素，并替换满足指定谓词的元素
reverse	反转范围中元素的顺序
reverse_copy	反转源范围中元素的顺序，同时将这些元素复制到目标范围
rotate	交换两个相邻范围中的元素
rotate_copy	交换源范围中两个相邻范围内的元素，并将结果复制到目标范围
sample
search	在目标范围中搜索其元素与给定序列中的元素相等或在二元谓词指定的意义上等效于给定序列中的元素的序列的第一个匹配项
search_n	在范围中搜索具有特定值或按二元谓词的指定与此值相关的指定数量的元素
set_difference	将属于一个排序的源范围、但不属于另一排序的源范围的所有元素相并到一个排序的目标范围，其中排序条件可通过二元谓词指定
set_intersection	将属于两个排序的源范围的所有元素相并为一个排序的目标范围，其中排序条件可通过二元谓词指定
set_symmetric_difference	将属于一个而不是两个排序的源范围的所有元素相并为一个排序的目标范围，其中排序条件可通过二元谓词指定
set_union	将至少属于两个排序的源范围之一的所有元素相并为一个排序的目标范围，其中排序条件可通过二元谓词指定
sort	将指定范围中的元素按非降序顺序排列，或根据二元谓词指定的排序条件排列
shuffle	使用随机数生成器重新排列给定范围中的元素
sort_heap	将堆转换为排序的范围
stable_partition	将范围中的元素分为两个不相交的集，满足一元谓词的元素在不满足一元谓词的元素之前，并保留等效元素的相对顺序
stable_sort	将指定范围中的元素按非降序顺序排列，或根据二元谓词指定的排序条件排列，并保留等效元素的相对顺序
swap	在两种类型的对象之间交换元素值，将第一个对象的内容分配给第二个对象，将第二个对象的内容分配给第一个对象
swap_ranges	将一个范围中的元素与另一大小相等的范围中的元素交换
transform	将指定的函数对象应用于源范围中的每个元素或两个源范围中的元素对，并将函数对象的返回值复制到目标范围
unique	移除指定范围中彼此相邻的重复元素
unique_copy	将源范围中的元素复制到目标范围，彼此相邻的重复元素除外
upper_bound	在排序的范围中查找其值大于指定值的第一个元素的位置，其中排序条件可通过二元谓词指定

functional

提供一系列有用的函数对象，包括常用的二元谓词(由于是模板函数，使用需要提供类型)

binary_function	空基类，定义可能由提供二元函数对象的派生类继承的类型 （在 C++11 中已弃用，在 C++17 中已移除）
divides	此类提供预定义的函数对象，后者对指定值类型的元素执行除法算术运算
equal_to	此二元谓词测试指定类型的一个值是否等于该类型的另一个值
greater	此二元谓词测试指定类型的一个值是否大于该类型的另一个值
greater_equal	此二元谓词测试指定类型的一个值是否大于或等于该类型的另一个值
less	此二元谓词测试指定类型的一个值是否小于该类型的另一个值
less_equal	此二元谓词测试指定类型的一个值是否小于或等于该类型的另一个值
logical_and	此类提供预定义的函数对象，后者对指定值类型的元素执行合取逻辑运算，并测试结果是 ture 还是 false
logical_not	此类提供预定义的函数对象，后者对指定值类型的元素执行求反逻辑运算，并测试结果是 ture 还是 false
logical_or	此类提供预定义的函数对象，后者对指定值类型的元素执行析取逻辑运算，并测试结果是 ture 还是 false
minus	此类提供预定义的函数对象，后者对指定值类型的元素执行减法算术运算
取模	此类提供预定义的函数对象，后者对指定值类型的元素执行取模算术运算
multiplies	此类提供预定义的函数对象，后者对指定值类型的元素执行乘法算术运算
negate	此类提供预定义的函数对象，后者返回元素值的负值
not_equal_to	此二元谓词测试指定类型的一个值是否不等于该类型的另一个值
plus	此类提供预定义的函数对象，后对指定值类型的元素执行加法算术运算
unary_function	空基类，定义可能由提供一元函数对象的派生类继承的类型 （在 C++11 中已弃用，在 C++17 中已移除）

算法范式

来自hello-algo

回溯

之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择
例如在二叉树查找值为7的节点:

/* 前序遍历：例题二 */
void preOrder(TreeNode *root) {
    if (root == nullptr) return;
    // 尝试
    path.push_back(root);
    if (root->val == 7) res.push_back(path);
    preOrder(root->left);
    preOrder(root->right);
    // 回退
    path.pop_back();
}

以上是最标准的回溯，通俗易懂地说就是穷举，对比较复杂的问题很容易就能超过多项式复杂度，到达阶乘这种程度
因此需要考虑对其的优化，例如剪枝
此外当然也可以用例如a star之类的启发式选择算法，俗称经验公式

/* 回溯算法框架 */
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

常见例题:

搜索问题：这类问题的目标是找到满足特定条件的解决方案

• 全排列问题：给定一个集合，求出其所有可能的排列组合
• 子集和问题：给定一个集合和一个目标和，找到集合中所有和为目标和的子集
• 汉诺塔问题：给定三根柱子和一系列大小不同的圆盘，要求将所有圆盘从一根柱子移动到另一根柱子，每次只能移动一个圆盘，且不能将大圆盘放在小圆盘上

约束满足问题：这类问题的目标是找到满足所有约束条件的解

• N皇后：在 n × n 的棋盘上放置N个皇后，使得它们互不攻击
• 数独：在 n × n 的网格中填入数字 0 ~ 9 ，使得每行、每列和每个 3 × 3 子网格中的数字不重复
• 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同

组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解

• 0-1 背包问题：给定一组物品和一个背包，每个物品有一定的价值和重量，要求在背包容量限制内，选择物品使得总价值最大
• 旅行商问题：在一个图中，从一个点出发，访问所有其他点恰好一次后返回起点，求最短路径
• 最大团问题：给定一个无向图，找到最大的完全子图，即子图中的任意两个顶点之间都有边相连

全排列

全排列问题是回溯算法的一个典型应用。它的定义是在给定一个集合（如一个数组或字符串）的情况下，找出其中元素的所有能的排列

/* 回溯算法：全排列 I */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
    // 当状态长度等于元素数量时，记录解
    if (state.size() == choices.size()) {
        res.push_back(state);
        return;
    }
    // 遍历所有选择
    for (int i = 0; i < choices.size(); i++) {
        int choice = choices[i];
        // 剪枝：不允许重复选择元素
        if (!selected[i]) {
            // 尝试：做出选择，更新状态
            selected[i] = true;
            state.push_back(choice);
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.pop_back();
        }
    }
}

/* 全排列 I */
vector<vector<int>> permutationsI(vector<int> nums) {
    vector<int> state;
    vector<bool> selected(nums.size(), false);
    vector<vector<int>> res;
    backtrack(state, nums, selected, res);
    return res;
}

考虑有相同元素的情况:

/* 回溯算法：全排列 II */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
    // 当状态长度等于元素数量时，记录解
    if (state.size() == choices.size()) {
        res.push_back(state);
        return;
    }
    // 遍历所有选择
    unordered_set<int> duplicated;
    for (int i = 0; i < choices.size(); i++) {
        int choice = choices[i];
        // 剪枝：不允许重复选择元素 且 不允许重复选择相等元素
        if (!selected[i] && duplicated.find(choice) == duplicated.end()) {
            // 尝试：做出选择，更新状态
            duplicated.emplace(choice); // 记录选择过的元素值
            selected[i] = true;
            state.push_back(choice);
            // 进行下一轮选择
            backtrack(state, choices, selected, res);
            // 回退：撤销选择，恢复到之前的状态
            selected[i] = false;
            state.pop_back();
        }
    }
}

/* 全排列 II */
vector<vector<int>> permutationsII(vector<int> nums) {
    vector<int> state;
    vector<bool> selected(nums.size(), false);
    vector<vector<int>> res;
    backtrack(state, nums, selected, res);
    return res;
}

子集和

给定一个正整数数组nums和一个目标正整数target，请找出所有可能的组合，使得组合中的元素和等于target。给定数组无重复元素，每个元素可以被选取多次。请以列表形式返回这些组合，列表中不应包含重复组合

要求:

• 输入集合中的元素可以被无限次重复选取
• 子集不区分元素顺序

默认已排序，如果题目不提供排序数组，可以手动排……

/* 回溯算法：子集和 I */
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
    // 子集和等于 target 时，记录解
    if (target == 0) {
        res.push_back(state);
        return;
    }
    // 遍历所有选择
    // 剪枝二：从 start 开始遍历，避免生成重复子集
    for (int i = start; i < choices.size(); i++) {
        // 剪枝一：若子集和超过 target ，则直接结束循环
        // 这是因为数组已排序，后边元素更大，子集和一定超过 target
        if (target - choices[i] < 0) break;
        // 尝试：做出选择，更新 target, start
        state.push_back(choices[i]);
        // 进行下一轮选择
        backtrack(state, target - choices[i], choices, i, res);
        // 回退：撤销选择，恢复到之前的状态
        state.pop_back();
    }
}

/* 求解子集和 I */
vector<vector<int>> subsetSumI(vector<int> &nums, int target) {
    vector<int> state;              // 状态（子集）
    sort(nums.begin(), nums.end()); // 对 nums 进行排序
    int start = 0;                  // 遍历起始点
    vector<vector<int>> res;        // 结果列表（子集列表）
    backtrack(state, target, nums, start, res);
    return res;
}

如果提供的choices有重复元素，即相同元素只能按顺序被选择，记录一个start表示本次选择开始位置，相同元素如果遍历到索引大于start时说明这一轮只能先选前面那个，后面这个重复元素必须被跳过；如果是不同元素或者这轮第一个该元素则正常进行:

/* 回溯算法：子集和 II */
void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
    // 子集和等于 target 时，记录解
    if (target == 0) {
        res.push_back(state);
        return;
    }
    // 遍历所有选择
    // 剪枝二：从 start 开始遍历，避免生成重复子集
    // 剪枝三：从 start 开始遍历，避免重复选择同一元素
    for (int i = start; i < choices.size(); i++) {
        // 剪枝一：若子集和超过 target ，则直接结束循环
        // 这是因为数组已排序，后边元素更大，子集和一定超过 target
        if (target - choices[i] < 0) break;
        // 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
        if (i > start && choices[i] == choices[i - 1]) continue;
        // 尝试：做出选择，更新 target, start
        state.push_back(choices[i]);
        // 进行下一轮选择
        backtrack(state, target - choices[i], choices, i + 1, res);
        // 回退：撤销选择，恢复到之前的状态
        state.pop_back();
    }
}

/* 求解子集和 II */
vector<vector<int>> subsetSumII(vector<int> &nums, int target) {
    vector<int> state;              // 状态（子集）
    sort(nums.begin(), nums.end()); // 对 nums 进行排序
    int start = 0;                  // 遍历起始点
    vector<vector<int>> res;        // 结果列表（子集列表）
    backtrack(state, target, nums, start, res);
    return res;
}

N皇后

根据国际象棋的规则，皇后可以攻击与同处一行、一列或一条斜线上的棋子。给定n个皇后和n×n棋盘，寻找摆放位置

先考虑怎么表示这个约束条件

1. 行约束可以通过逐行选择放入位置解决
2. 列约束可以使用一个列选择数组
3. 注意到主对角线上所有格子的行索引减列索引为恒定值,可以用数组 diags1 记录每条主对角线上是否有皇后
4. 同理，次对角线上的所有格子的行索引加列索引是恒定值。我们同样也可以借助数组 diags2 来处理次对角线约束

/* 回溯算法：n 皇后 */
void backtrack(int row, int n, vector<vector<string>> &state, vector<vector<vector<string>>> &res, vector<bool> &cols,
               vector<bool> &diags1, vector<bool> &diags2) {
    // 当放置完所有行时，记录解
    if (row == n) {
        res.push_back(state);
        return;
    }
    // 遍历所有列
    for (int col = 0; col < n; col++) {
        // 计算该格子对应的主对角线和次对角线
        int diag1 = row - col + n - 1;
        int diag2 = row + col;
        // 剪枝：不允许该格子所在列、主对角线、次对角线上存在皇后
        if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
            // 尝试：将皇后放置在该格子
            state[row][col] = "Q";
            cols[col] = diags1[diag1] = diags2[diag2] = true;
            // 放置下一行
            backtrack(row + 1, n, state, res, cols, diags1, diags2);
            // 回退：将该格子恢复为空位
            state[row][col] = "#";
            cols[col] = diags1[diag1] = diags2[diag2] = false;
        }
    }
}

/* 求解 n 皇后 */
vector<vector<vector<string>>> nQueens(int n) {
    // 初始化 n*n 大小的棋盘，其中 'Q' 代表皇后，'#' 代表空位
    vector<vector<string>> state(n, vector<string>(n, "#"));
    vector<bool> cols(n, false);// 记录列是否有皇后
    vector<bool> diags1(2 * n - 1, false); // 记录主对角线上是否有皇后
    vector<bool> diags2(2 * n - 1, false); // 记录次对角线上是否有皇后
    vector<vector<vector<string>>> res;

    backtrack(0, n, state, res, cols, diags1, diags2);

    return res;
}

动态规划

dp与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题，我们可以将前一个子问题转移到下一个状态视为一个决策，然后用回溯，这是一种穷举
但动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性

1. 最优子结构:原问题的最优解是从子问题的最优解构建得来的，如带代价的楼梯问题中：dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
   
2. 无后效(马尔科夫)性：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关
   1. 并不是有无后效性就适合dp解决，计算和存储状态必然有开销，当开销过大时用dp会超时
   2. 通过增加状态的范围，可以使状态转移更复杂的问题也满足无后效性，但往往开销较大

例如，爬楼梯问题改成:每步可以上1阶或者2阶，但不能连续两轮跳1阶，就需要记录上一轮跳了1还是2阶
状态dp[i,j]表示处在第i阶并且上一轮跳了j阶:

/* 带约束爬楼梯：动态规划 */
int climbingStairsConstraintDP(int n) {
    if (n == 1 || n == 2) return 1;
    // 初始化 dp 表，用于存储子问题的解
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    // 初始状态：预设最小子问题的解
    dp[1][1] = 1; dp[1][2] = 0; dp[2][1] = 0; dp[2][2] = 1;
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];//也可以是dp[i] = dp[i-2] + dp[i-3]
    }
    return dp[n][1] + dp[n][2];
}

解题思路:

1. 假定我们在一个状态，思考这个状态可以怎么表示，用例如一个n维向量记忆，由于是dp问题，我们假定每个状态都是截止目前最优的
2. 找出状态转移的方式，例如爬楼梯问题只依赖于n-1和n-2的情况
3. 选取一个特定的顺序开始遍历解决问题，需要确保
   1. 填满初始化状态
   2. 确保之后每个状态依赖的子问题已经被算出了
   3. 选取合适终止条件

理论上讲，为了空间最优，每层计算只需要依赖子问题数量的空间复杂度，对一维dp来说:一般是O(1)，但一般来说存储马尔科夫链上的所有状态复杂度相对也可以接受(一般是O(N))

0-1背包问题

给定n个物品，第i个物品的重量为wgt[i-1]、价值为val[i-1]，和一个容量为cap的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值

很容易想到，我们应该把重量排序，然后依次决策，因此需要一个i状态表示当前物品编号，以及一个目前限制容量c，dp[i,c]则表示遍历到i为止限制容量是c时的最大价值
选到i时，如果不选i，那和i-1一样，如果选i，此时容量减少，价值增加，且因为不能重复选择，也退回到i-1
dp状态转移: $d p[i,c]=(d p[i-1,c],d p[i-1,c-w g t[i-1]]+v a l[i-1]) $
而依赖关系呢？dp[i,c]依赖dp[i - 1][c], dp[i - 1][c - wgt[i - 1]]，也就是i只依赖i-1好知道，c依赖范围是取决于wgt的，因此i应该放外侧，每一行c都知道了才能到下一个i

/* 0-1 背包：记忆化搜索 */
int knapsackDFSMem(vector<int> &wgt, vector<int> &val, vector<vector<int>> &mem, int i, int c) {
    // 若已选完所有物品或背包无剩余容量，则返回价值 0
    if (i == 0 || c == 0) return 0;
    // 若已有记录，则直接返回
    if (mem[i][c] != -1) return mem[i][c];
    // 若超过背包容量，则只能选择不放入背包
    if (wgt[i - 1] > c) return knapsackDFSMem(wgt, val, mem, i - 1, c);
    // 计算不放入和放入物品 i 的最大价值
    int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
    int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
    // 记录并返回两种方案中价值更大的那一个
    mem[i][c] = max(no, yes);
    return mem[i][c];
}

/* 0-1 背包：动态规划 */
int knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c];// 若超过背包容量，则不选物品 i
            else dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);// 不选和选物品 i 这两种方案的较大值
        }
    }
    return dp[n][cap];
}

空间优化

完全背包问题

给定n个物品，第i个物品的重量为wgt[i-1]、价值为val[i-1]，和一个容量为cap的背包。每个物品可以重复选取，问在限定背包容量下能放入物品的最大价值。示例如图14-22所示

类似0-1背包，选到i时，如果不选i，那和i-1一样，但如果选i，此时容量减少，价值增加，且因为可以重复选择，不用退回到i-1,还是i
状态转移: \(d p[i,c]=\operatorname*{max}(d p[i-1,c],d p[i,c-w g t[i-1]]+v a l[i-1])\)
而依赖关系呢？dp[i,c]依赖dp[i - 1][c], dp[i][c - wgt[i - 1]]，依赖方向依旧是左和上，但这次都是轴向，像之前一样的遍历顺序也是可以的

/* 完全背包：动态规划 */
int unboundedKnapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
    int n = wgt.size();
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c];// 若超过背包容量，则不选物品 i
            else dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);// 不选和选物品 i 这两种方案的较大值
        }
    }
    return dp[n][cap];
}

空间优化

找零问题

给定n种硬币,第i种硬币的面值为coins[i-1]，目标金额为amt,每种硬币可以重复选取,问能够凑出目标金额的最少硬币数量。如果无法凑出自标金额，则返回-1

零钱兑换可以看作完全背包问题的一种特殊情况，两者具有以下联系与不同点

• 两道题可以相互转换，“物品”对应“硬币”、“物品重量”对应“硬币面值”、“背包容量”对应“目标金额”
• 优化目标相反，完全背包问题是要最大化物品价值，零钱兑换问题是要最小化硬币数量
• 完全背包问题是求“不超过”背包容量下的解，零钱兑换是求“恰好”凑到目标金额的解

状态i,a对应的子问题为:前i种硬币能够凑出金额a的最少硬币数量,记为 dp[i,a]
如果不能找i硬币，那么和i-1一样，否则要和dp[i][a-coins[i-1]]取一个较小值
事实上，类似完全背包，找零只有左和上方的依赖，这就意味着要实现最佳找a元，本质上只依赖于所有a-coin的最优解的最小值，也就是固定一个a，遍历i一遍就可以找到a的对应最优解，可以优化为一维dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);//遍历每个可找的i

/* 零钱兑换：动态规划 */
int coinChangeDP(vector<int> &coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;//处理无解情况
    // 初始化 dp 表
    vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
    // 状态转移：首行首列
    for (int a = 1; a <= amt; a++) dp[0][a] = MAX;
    // 状态转移：其余行和列
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) dp[i][a] = dp[i - 1][a];//若超过目标金额，则不选硬币 i
            else dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);//不选和选硬币 i 这两种方案的较小值
        }
    }
    return dp[n][amt] != MAX ? dp[n][amt] : -1;
}

找零问题2

给定n种硬币,第i种硬币的面值为coins[i-1]，目标金额为amt,每种硬币可以重复选取,问出目标金额的硬币组合数量

状态转移: \(d p[i,a]=d p[i-1,a]+d p[i,a-c o i n s[i-1]]\)
即对每个i \(d p[a]=d p[a]+d p[a-c o i n s[i-1]]\)

/* 零钱兑换 II：空间优化后的动态规划 */
int coinChangeIIDPComp(vector<int> &coins, int amt) {
    int n = coins.size();
    // 初始化 dp 表
    vector<int> dp(amt + 1, 0);
    dp[0] = 1;
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) dp[a] = dp[a]; // 若超过目标金额，则不选硬币 i
            else dp[a] = dp[a] + dp[a - coins[i - 1]]; // 不选和选硬币 i 这两种方案之和
        }
    }
    return dp[amt];
}

编辑距离问题

输入两个字符串s和t，返回将s转换为t所需的最少编辑步数
你可以在一个字符串中进行三种编辑操作：插入一个字符、删除一个字符、将字符替换为任意一个字符

字符串s和t的长度分别为 n和m，我们先考虑两字符串尾部的字符s[n-1],t[m-1]

• 若相同，我们可以跳过它们,考虑n-2和m-2情况
• 若不同，需要对s进行一次编辑（插入、删除、替换），使得两字符串尾部的字符相同，从而可以跳过它们

状态转移如图所示，公式为 \(d p[i,j]=\operatorname*{min}(d p[i,j-1],d p[i-1,j],d p[i-1,j-1])+1\)
dp[i][j]依赖左方、上方、左上方的解，依旧可以两层遍历
tip:插入短字符串和删除长字符串在该问题里其实是等价的，可以省去一次计算

/* 编辑距离：动态规划 */
int editDistanceDP(string s, string t) {
    int n = s.length(), m = t.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    // 状态转移：首行首列
    for (int i = 1; i <= n; i++) dp[i][0] = i;
    for (int j = 1; j <= m; j++) dp[0][j] = j;
    // 状态转移：其余行和列
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // 若两字符相等，则直接跳过此两字符
            else dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1; // 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
        }
    }
    return dp[n][m];
}

空间优化略麻烦……

贪心

贪心算法（greedy algorithm）是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解
只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解，这种条件相对苛刻，证明起来也很麻烦，因此没有完全把握最好不要用贪心
典型的贪心算法问题：

• 硬币找零问题：在某些硬币组合下，贪心算法总是可以得到最优解
• 区间调度问题：假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么贪心算法就可以得到最优解
• 分数背包问题：给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大。如果每次都选择性价比最高（价值 / 重量）的物品，那么贪心算法在一些情况下可以得到最优解
• 股票买卖问题：给定一组股票的历史价格，你可以进行多次买卖，但如果你已经持有股票，那么在卖出之前不能再买，目标是获取最大利润
• 霍夫曼编码：霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树，每次选择出现频率最低的两个节点合并，最后得到的霍夫曼树的带权路径长度（编码长度）最小
• Dijkstra 算法：解决给定源顶点到其余各顶点的最短路径问题的贪心算法

分数背包问题

给定n个物品，第i个物品的重量为wgt[i-1]、价值为val[i-1]，和一个容量为cap的背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问在限定背包容量下背包中物品的最大价值

很容易用反证法证明，每次选择价格重量比最高的物品是最优策略，因为如果选择非最高的，那么换成最高的必然更优

/* 物品 */
class Item {
  public:
    int w; // 物品重量
    int v; // 物品价值

    Item(int w, int v) : w(w), v(v) {
    }
};

/* 分数背包：贪心 */
double fractionalKnapsack(vector<int> &wgt, vector<int> &val, int cap) {
    // 创建物品列表，包含两个属性：重量、价值
    vector<Item> items;
    for (int i = 0; i < wgt.size(); i++) items.push_back(Item(wgt[i], val[i]));
    // 按照单位价值 item.v / item.w 从高到低进行排序
    sort(items.begin(), items.end(), [](Item &a, Item &b) { return (double)a.v / a.w > (double)b.v / b.w; });
    // 循环贪心选择
    double res = 0;
    for (auto &item : items) {
        if (item.w <= cap) {
            // 若剩余容量充足，则将当前物品整个装进背包
            res += item.v;
            cap -= item.w;
        } else {
            // 若剩余容量不足，则将当前物品的一部分装进背包
            res += (double)item.v / item.w * cap;
            // 已无剩余容量，因此跳出循环
            break;
        }
    }
    return res;
}

最大容量问题

输入一个数组ht，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器
谷器的容量等于高度和宽度的乘积（面积），其中高度由较短的隔板决定，宽度是两入隔板的数组索引之差，请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量

从最大的宽度开始收缩，只有往短板方向收缩可能有更优情况

/* 最大容量：贪心 */
int maxCapacity(vector<int> &ht) {
    // 初始化 i, j，使其分列数组两端
    int i = 0, j = ht.size() - 1;
    // 初始最大容量为 0
    int res = 0;
    // 循环贪心选择，直至两板相遇
    while (i < j) {
        // 更新最大容量
        int cap = min(ht[i], ht[j]) * (j - i);
        res = max(res, cap);
        // 向内移动短板
        if (ht[i] < ht[j]) i++;
        else j--;
    }
    return res;
}

最大切分乘积问题

给定一个正整数n，将其切分为至少两个正整数的和，所有整数的乘积最大是多少

• 当n>= 4时,切分出一个2后乘积会变大(2(n-2) ≥n)，这说明大于等于4的整数都应该被切分
  
• 如果有3个2，乘积不如两个3，因此在切分方案中，最多只应存在两个2从而获得更大的乘积

综上所述，可推理出以下贪心策略:

1. 输入整数n，从其不断地切分出因子3，直至余数为0、1、2
2. 当余数为0时,代表n是3的倍数，因此不做任何处理
3. 3.当余数为2时，不继续划分，保留
4. 当余数为 1时,由于2 × 2 > 1 × 3,因此应将最后一个3替换为2

/* 最大切分乘积：贪心 */
int maxProductCutting(int n) {
    // 当 n <= 3 时，必须切分出一个 1
    if (n <= 3) return 1 * (n - 1);
    // 贪心地切分出 3 ，a 为 3 的个数，b 为余数
    int a = n / 3; int b = n % 3;
    if (b == 1) return (int)pow(3, a - 1) * 2 * 2;//当余数为 1 时，将一对 1 * 3 转化为 2 * 2
    if (b == 2) return (int)pow(3, a) * 2;//当余数为 2 时，不做处理
    // 当余数为 0 时，不做处理
    return (int)pow(3, a);
}

cpp基本输入输出

和考研无关但知道也不错:

• C 中的输入输出函数，如 scanf() 和 printf() 等，是非类型安全的：
  • 它们依赖于格式化字符串来指示输入/输出数据的类型
  • 如果格式化字符串不正确，就会导致不可预测的结果，如缓冲区溢出和未定义的行为
• C++ 中的输入输出函数，如 std::cin 和 std::cout 等，是类型安全的：
  • 它们使用类型安全的 C++ 流语义，其中数据类型是静态确定的，而不是动态确定的
  • 这意味着数据类型在编译时就已经确定，而不是在运行时根据格式化字符串动态确定
  • 这种静态类型检查可以在编译时检测到类型不匹配的错误，从而使 C++ 的输入输出更加类型安全
• 因此，scanf() 的参数需要使用格式化字符串来指定输入数据的类型，而 cin 和 std::cin 可以自动识别输入数据的类型

cin 和 cout 是 C++ 的输入输出流，可以使用它们来实现控制台的输入输出操作 同步流（synchronized stream）的概念：

• 同步流意味着在程序流中输出数据时，程序必须等到数据完全输出到设备上，然后才能继续执行后面的代码
• 同样，当程序尝试从输入设备读取数据时，程序会等待用户输入完整的数据，然后才能继续执行后面的代码
• 不止c++,c的scanf() 和 printf() 也实现了同步流，但其缓冲区的实现更为底层，效率更高
• 总得来说，c++输入输出依旧为了同步等高级功能牺牲了一定性能，但这些开销可以被我们手动关闭；关闭后每次读取输入时，输出缓存区不会被刷新

• getchar()函数从标准输入（stdin）中读取一个字符，返回该字符的 ASCII 码值
  • 通常用于读取单个字符或者字符数组，可以实现简单的输入操作
  • 使用时需要注意的是，由于输入的字符是直接通过键盘输入的，因此需要按下回车键才能将输入的字符送入缓冲区，此时getchar()才能够读取到输入的内容
• getline()函数从输入流中读取一行文本(可以指定分隔符)，并将其存储到一个字符串对象中，可以读取包含空格在内的一整行输入
  • 使用时需要注意的是，如果使用默认的分隔符 \n，getline() 会将换行符读取到缓冲区，如果下一次使用 getline() 读取输入，就会导致缓冲区中的换行符被读取，而不是期望的输入。此时可以通过调用cin.ignore()来清除缓冲区中的字符，或者指定其他分隔符
  • c++输入输出,当cin>>从缓冲区中读取数据时，若缓冲区中第一个字符是空格、tab或换行这些分隔符时，cin>>会将其忽略并清除，继续读取下一个字符，若缓冲区为空，则继续等待但是如果读取成功，字符后面的分隔符是残留在缓冲区的
• stringstream 是 C++ 标准库提供的一种数据流对象，用于在内存中对字符串进行输入输出操作
  • 它可以像 cin 和 cout 一样进行输入输出，并且具有和输入输出流相似的接口和方法，例如 << 和 >> 操作符
  • 它提供了将一个字符串转换成一个数据类型的方法，方便程序员进行数据处理
  • 在 C++ 中，stringstream 也是类型安全的

getline() 其参数实际上有三个，第三个参数为分隔符参数，即 getline() 会以该参数分割处理数据，默认缺省该参数的情况下，getline() 会以\n为分隔符，即默认我们使用的是getline(cin, s, '\n');
例如:

getline(cin, s);  //读入 string 类型 s
cout << "First: " << s << endl;  //输出 s
getline(cin, s);  //在此读入
cout << "Second: " << s << endl;  //再次输出 s

//由于默认换行符分割，此次输出符合预期

getline(cin, s, ',');  //读入 string 类型 s，并以 ',' 为分隔符
cout << "First: " << s << endl;  //输出 s
getline(cin, s, ',');  //在此读入
cout << "Second: " << s << endl;  //再次输出 s，并以 ',' 为分隔符

//由于分隔符换成','，输入流残留的'\n'会被下次输入时读取，产生以下输出
First: 114
Second:
514 

//建议对策:
getline(cin, s, ',');  //读入 string 类型 s
cout << "First: " << s << endl;  //输出 s
// 使用 cin.ignore() 忽略掉输入缓冲区中的换行符
// 也可以使用 cin.get() 读取缓冲区中的换行符
cin.ignore();
// cin.get();
getline(cin, s, ',');  //在此读入
cout << "Second: " << s << endl;  //再次输出 s

stringstream 和 cin、cout 等输入输出流都有类似的接口和方法，可以进行输入输出操作，但它们的作用域不同。cin、cout 等输入输出流通常用于标准输入输出流，而 stringstream 通常用于字符串的处理 通常我们可以使用 stringstream 对字符串进行分割、转换、拼接等操作，然后再使用 cin 或 cout 输出到标准输入输出流中：

int main() {
    stringstream s;
    string name = "yjsp";
    int age = 24;
    double height = 170.5;
    string status = "is dust";
    s << "Name: " << name << ", Age: " << age << ", Height: " << height << ", Status: " << status;
    string str = s.str();//将所有插入的数据转换为一个字符串
    cout << str << endl;

    string s;
    getline(cin, s);
    stringstream ss(s);
    string str;
    while(ss >> str){
        cout << str << endl;//不断通过空格的划分赋值给str
    }

    return 0;
}

例题:

//1. 计算a+b
void a_plus_b() {
    cout << "please input two numbers : " << '\n';
    int a, b;
    while (cin >> a >> b) cout << "a+b is " << a + b << '\n';
}

int main() {
    int s;
    while (cin >> s && s) {
        int a;
        int sum=0;
        while (s!= 0) {
            --s;
            cin >> a;
            sum+=a;
        }
        cout << sum <<'\n';
    }
}

int main() {
    int s;
    while (cin >> s && s) {
        int a;
        int sum=0;
        while (s!= 0) {
            --s;
            cin >> a;
            sum+=a;
        }
        cout << sum <<'\n';
    }
}

int main() {
    string l;
    while(getline(cin,l)){
        stringstream ss(l);
        int sum = 0,num;
        while(ss>>num) sum+=num;
        cout<<sum<<'\n';
    }
    return 0;
}

//读取字符串并排序输出
void read_from_line() {
    string l;
    while (getline(cin, l)) {
        stringstream ss(l);
        int sum = 0, num;
        while (ss >> num) sum += num;
        cout << sum << '\n';
    }
}

void sort_strings() {
    string s;
    vector<string> vec;
    while (getline(cin, s)) {
        stringstream ss(s);//初始化语法
        s.clear();
        while (ss >> s) vec.push_back(s);
        sort(vec.begin(), vec.end());
        for (auto i = vec.begin();i != vec.end();i++) cout << *i << ' ';
        cout << '\n';
        vec.clear();
    }
}

void strings_withdot() {
    string s;
    while (getline(cin, s)) {
        stringstream ss(s);
        vector<string> vec;
        while (getline(ss, s, ',')) vec.push_back(s);//getline属于string头文件，可以指定分隔符 
        sort(vec.begin(), vec.end());
        for (int i = 0;i < vec.size() - 1;i++) cout << vec[i] << ',';
        cout << vec.back() << '\n';
    }
}

int main() {
    int a;
    cin >> a;
    vector<string> vec;
    while (a) {
        --a;
        string t;
        cin >> t;
        vec.push_back(t);
    }
    sort(vec.begin(),vec.end());
    for (auto i = vec.begin();i!=vec.end();i++) cout << *i << ' ';
}

int main() {
    string s;
    vector<string> vec;
    while (getline(cin, s)) {
        stringstream ss(s);//初始化语法
        s.clear();
        while (ss >> s) vec.push_back(s);
        sort(vec.begin(),vec.end());
        for (auto i = vec.begin();i!=vec.end();i++) cout << *i << ' ';
        cout << '\n';
        vec.clear();
}

int main() {
    string s;
    while (getline(cin, s)) {
        stringstream ss(s);
        vector<string> vec;
        while (getline(ss ,s ,',')) vec.push_back(s);
        sort(vec.begin(),vec.end());
        for (int i =0;i<vec.size()-1;i++) cout << vec[i]<< ',';
        cout << *(--vec.end()) <<'\n';
}

力扣热题 100 道题解

哈希

题号:1 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素
对数组的每个元素：

1. 查找哈希表是否有其元素值对应的<k,v>,如果有，该<k,v>的 v 值就是其匹配的数组索引号
2. 将 target 与该元素值的差作为 k，其索引作为 v 写入哈希表

vector<int> twoSum(vector<int>& nums, int target) {// 暴力解法，O(N^2)
    vector<int> temp, result;
    for (auto i = nums.begin(); i != nums.end();i++) temp.push_back(target - *i);
    int index1 = 0;
    for (auto i = nums.begin(); i != nums.end();i++) {
        int index2 = index1 + 1;
        auto it = temp.begin();
        for (int t = 0;t < index2;t++) it++;
        while (it != temp.end()) {
            if (*i == *it) {
                result.push_back(index1);
                result.push_back(index2);
                return result;
            }
            it++;
            index2++;
        }
        index1++;
    }
    return result;
};

vector<int> twoSum2(vector<int>& nums, int target) {
    /*
    */
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size();i++) {
        if (hash.find(nums[i]) != hash.end()) return { i,hash[nums[i]] };
        hash[target - nums[i]] = i;
    }
    return {};
}

题号:2 字母异位词分组
给你一个字符串数组，请你将 字母异位词(字母相同排列不同的单词) 组合在一起可以按任意顺序返回结果列表
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键, 值则是字符串数组，最后将这些数组返回

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> um;
    vector<vector<string>> res;
    for (auto s : strs) {
        string t = s;
        sort(t.begin(), t.end());
        um[t].emplace_back(s);
    }
    for (auto i : um) res.push_back(i.second);
    return res;
}

题号:3 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度
请你设计并实现时间复杂度为 O(n) 的算法解决此问题
不需要在原数组连续，因此可以用一个哈希集合去重，然后我们开始找连续序列，对遍历中遇到的任意值 x，如果它在一个连续序列中，那么必有从序列最大或者最小值开始找起的连续序列是存在x的序列中最长的这个性质，因此对遍历中的 x，先找到其所在序列末端，再一边删一遍记录长度
时间复杂度：O(n)
空间复杂度：O(n)

int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;
    unordered_set<int> us;
    int max_len = 0;
    for (auto i : nums) us.emplace(i);
    while (!us.empty()) {
        int i = *us.begin();
        int len = 0;
        while (us.count(i + 1)) ++i;
        while (us.count(i)) {
            ++len;
            us.erase(i);
            --i;
        }
        max_len = max(max_len, len);
    }
    return max_len;
}

双指针

题号:1 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
请注意 ，必须在不复制数组的情况下原地对数组进行操作
设置慢指针用于遍历 0，快指针用于遍历慢指针后第一个非 0 元素

1. 初始快慢指针均为 0
2. while 指针不越界，循环:
   1. 如果慢指针处元素为 0:
      1. 快指针移动到第一个非 0 元素或者越界函数终止
      2. 交换快慢指针的元素
   2. 快慢指针均+1

void moveZeroes(vector<int>& nums) {
    int n = nums.size(), slow = 0, fast = 0;
    if (n <= 1) return;
    while (fast < n && slow<n) {
        if (nums[slow] == 0) {
            while (fast <n && nums[fast] == 0) ++fast;
            if (fast >= n) return;
            nums[slow] = nums[fast];
            nums[fast] = 0;
        }
        ++slow;++fast;
    }
}

也可以优先让快指针动:

void moveZeroes(vector<int>& nums) {
    int n = nums.size(), left = 0, right = 0;
    while (right < n) {
        if (nums[right]) {
            swap(nums[left], nums[right]);
            left++;
        }
        right++;
    }
}

题号:2 盛最多水的容器
给定一个长度为 n 的整数数组 height 有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水 返回容器可以储存的最大水量 很明显最大水量是x轴差值乘以最短边，要更大就需要增加x轴距离或者加长最短边
从x轴最远两端开始，如果改变相对长边，那么水量必然减少，移动相对短边则水量有可能增加，因此只要不断这样遍历记录最大水量就好了

int maxArea(vector<int>& height) {
    int i = 0, j = height.size() - 1, max_ar = (j - i) * min(height[i], height[j]);
    while (i < j) {
        if (height[i] < height[j]) ++i;
        else --j;
        max_ar = max(max_ar, (j - i) * min(height[i], height[j]));
    }
    return max_ar;
}

题号:3 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 请你返回所有和为 0 且不重复的三元组

1. 先排序，然后开始遍历(遍历时跳过重复值)
2. 再给定一个值，很容易就能判断有没有第三个值k满足条件

vector<vector<int>> threeSum(vector<int>& nums) {
    if (nums.size() <= 2) return {};
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (int i = 0;i < nums.size();i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int k = nums.size() - 1;
        for (int j = i + 1;j < nums.size();j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int t = nums[i] + nums[j];
            while (k > j && t + nums[k] > 0) --k;
            if (j == k) continue;
            if (nums[i] + nums[j] + nums[k] == 0) res.push_back({ nums[i], nums[j], nums[k] });
        }
    }
    return res;
}

官方解双指针:

vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    // 枚举 a
    for (int first = 0; first < n; ++first) {
        // 需要和上一次枚举的数不相同
        if (first > 0 && nums[first] == nums[first - 1]) continue;
        // c 对应的指针初始指向数组的最右端
        int third = n - 1;
        int target = -nums[first];
        // 枚举 b
        for (int second = first + 1; second < n; ++second) {
            // 需要和上一次枚举的数不相同
            if (second > first + 1 && nums[second] == nums[second - 1]) continue;
            // 需要保证 b 的指针在 c 的指针的左侧
            while (second < third && nums[second] + nums[third] > target) --third;
            // 如果指针重合，随着 b 后续的增加
            // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
            if (second == third) break;
            if (nums[second] + nums[third] == target) res.push_back({nums[first], nums[second], nums[third]});
        }
    }
    return res;
}

时间复杂度：O( \(N^2\) )，其中 N 是数组 nums 的长度
空间复杂度：O(logN)我们忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 O(N)

题号:4 接雨水(hard)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) leftMax[i] = max(leftMax[i - 1], height[i]);

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) rightMax[i] = max(rightMax[i + 1], height[i]);

        int res = 0;
        for (int i = 0; i < n; ++i) res += min(leftMax[i], rightMax[i]) - height[i];
        return res;
}

滑动窗口

题号:1 无重复字符的最长子串
给定一个字符串s,请你找出其中不含有重复字符的最长的长度
用i,j表示子串，对特定的i，用一个哈希集合可以得出当前最长不重复子串长度
随后固定j，i向前滑动一个位置，集合移除其对应的字符，循环直到j滑到字符串尾

int lengthOfLongestSubstring(string s) {
    if (s.size() <= 1) return s.size();
    unordered_set<char> hash;
    size_t max_len = 1;
    int i = 0, j = 1;
    hash.insert(s[i]);
    while (1) {
        while (j < s.size() && !hash.count(s[j])) {
            hash.insert(s[j]);
            ++j;
        }
        max_len = max(max_len, hash.size());
        if (j == s.size()) break;
        else {
            hash.erase(s[i]);
            ++i;
        }
    }
    return max_len;
}

题号:2 找到字符串中所有字母异位词
给定两个字符串s和p，找到s中所有p的异位词(对原词的重排列，用到所有原字符刚好一次)的子串，返回这些子串的起始索引不考虑答案输出的顺序

1. 用一个26字符长的数组存储字符，如果我们把s和p窗口内相同的字符抵消掉，数组非0元素数即为他们差异数
2. 此题窗口范围为plen,先计算第一个窗口情况，如果差异为0直接退出
3. 开始右移，对每次右移:
   1. 减去左侧字符，加上右侧字符，并判断差异变化
   2. 如果差异为0，退出，否则继续循环

vector<int> findAnagrams(string s, string p) {
    int sLen = s.size(), pLen = p.size();
    if (sLen < pLen) return {};
    vector<int> res;
    vector<int> count(26);
    for (int i = 0; i < pLen; ++i) {//计算第一个窗口的字符情况
        ++count[s[i] - 'a'];
        --count[p[i] - 'a'];
    }
    int differ = 0;//子串和p不同的字母数量
    for (int j = 0; j < 26; ++j) if (count[j] != 0) ++differ;//不为0的元素说明有差异
    if (differ == 0) res.emplace_back(0);
    for (int i = 0; i < sLen - pLen; ++i) {
        --count[s[i] - 'a'];//i右移移除对应count，正式的+1由for循环完成,接下来处理differ变化
        if (count[s[i] - 'a'] == 0) --differ;  // 如果i处是多余字符，即count的对应值为1，i右移后differ会减少
        else if (count[s[i] - 'a'] == -1)  ++differ; // 如果i处正好相抵，i右移后differ会增加
        
        ++count[s[i + pLen] - 'a'];
        if (count[s[i + pLen] - 'a'] == 0)  --differ; 
        else if (count[s[i + pLen] - 'a'] == 1)  ++differ; 

        if (differ == 0) res.emplace_back(i + 1);
    }
    return res;
}

子串

题号:1 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数
子数组是数组中元素的连续非空序列

1. 创建一个哈希表，其k存储子数组和，其v存储对应这个和的子数组的数量
2. 遍历原数组逐步向哈希表添加1~k的前缀和
   1. 如果我们找到一个sum(i,j)满足题意，那么可得sum(0,j)-sum(0,i)==sum(i,j)==k
   2. 也就是说，sum(0,j)-k==sum(0,i),在哈希表里找到n个prefix-k,就有n个满足题意的子数组

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    mp[0] = 1;
    int count = 0, pre = 0;
    for (auto& x : nums) {
        pre += x;
        if (mp.count(pre - k)) {
            count += mp[pre - k];
        }
        mp[pre]++;
    }
    return count;
}

数组

题号:1 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

1. 类似上一题，子数组的和可以用两端前缀和差表示，这次我们只需要最大值，因此只需要保留一个量，即当前元素之前的最小差，用目前为止的前缀和减去它就行了
2. 事实上可以进一步化简，如果存储到前一个元素为止的最优解sum(i-1),最优解就是sum(i)和nums[i]二选一

int maxSubArray(vector<int>& nums) {
    unordered_map<int, int> mp;
    if (nums.size() == 1) return nums[0];
    int max_sum = nums[0], pre_sum = max_sum, min_sum = min(0, nums[0]);
    for (int i = 1;i < nums.size();i++) {
        min_sum = min(min_sum, pre_sum);
        pre_sum += nums[i];
        max_sum = max(max_sum, pre_sum - min_sum);
    }
    return max_sum;
}

int maxSubArray_sol2(vector<int>& nums) {
    int pre = 0, maxres = nums[0];
    for (const auto &x: nums) {
        pre = max(pre + x, x);
        maxres = max(maxres, pre);
    }
    return maxres;
}

题号:2 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间

可以合并的区间在排序后必然是连续的，排序后逐个遍历合并即可

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    if (intervals.size() == 1) return intervals;
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res = { intervals[0] };
    for (int i = 1;i < intervals.size();i++) {
        int tail = res.size() - 1;
        if (intervals[i][0] <= res[tail][1]) {
            res[tail][1] = max(intervals[i][1], res[tail][1]);
        }
        else res.emplace_back(intervals[i]);
    }
    return res;
}

题号:3 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数

先分两部分转，最后整体转

void reverse(vector<int>& nums, int start, int end) {
    for (int i = 0;i < (end - start + 1) / 2;i++) swap(nums[start + i], nums[end - i]);
}

void rotate(vector<int>& nums, int k) {
    k %= nums.size();
    if (k == 0) return;
    reverse(nums, 0, nums.size() - k - 1);
    reverse(nums, nums.size() - k, nums.size() - 1);
    reverse(nums, 0, nums.size() - 1);
}

题号:4 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 result ，其中 result[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积
题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32位整数范围内
请不要使用除法，且在O(n)时间复杂度内完成此题

1. 对任意一个元素,要求的积就是它的前后缀积之积，因此先求前缀积数组(由于是积，第一个元素为1)
2. 从后往前可以一步步算后缀积和前缀积数组对应元素相乘，减少计算量

vector<int> productExceptSelf(vector<int>& nums) {
    const int size = nums.size();
    vector<int> res(nums.size());
    res[0] = 1;
    for (int i = 1;i < size;i++) res[i] = res[i - 1] * nums[i - 1];
    int right_product = nums[size - 1];
    for (int j = size - 2;j >= 0;--j) {
        res[j] *= right_product;
        right_product *= nums[j];
    }
    return res;
}

矩阵

题号:1 矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 请使用 原地 算法

标记行列，然后清零
有空间上更优的解法，但逻辑很麻烦，感觉记也记不住……

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<int> row(m), col(n);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!matrix[i][j]) {
                row[i] = col[j] = true;
                break;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (row[i] || col[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

题号:2 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素

每四个方向是一圈，而对每个方向来说，其起始点和遍历数量只与圈数有关，因此可以不断循环直到结果数组满足要求

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> res;
    int m = matrix.size();
    int n = matrix[0].size();
    int dire = 0, cycle = 0;
    while (1) {
        if (res.size() >= m * n) return res;
        switch (dire) {
        case 0:
        for (int j = cycle;j < n - cycle;++j) res.emplace_back(matrix[cycle][j]);
        dire = 1;
        break;
        case 1:
        for (int i = cycle + 1;i < m - cycle;++i) res.emplace_back(matrix[i][n - 1 - cycle]);
        dire = 2;
        break;
        case 2:
        for (int j = n - cycle - 2;j >= cycle;--j) res.emplace_back(matrix[m - 1 - cycle][j]);
        dire = 3;
        break;
        case 3:
        for (int i = m - 2 - cycle;i >= 1 + cycle;--i) res.emplace_back(matrix[i][cycle]);
        dire = 0;
        ++cycle;
        break;
        }
    }
    return res;
}

题号:3 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像请你将图像顺时针旋转 90 度
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵请不要 使用另一个矩阵来旋转图像

画个图就能看出，矩阵第k行被翻转到结果矩阵的n-1-k列,k从0开始 即关键等式: matrix[row][col]=matrixnew​[col][n−row−1]
可以递推坐标映射公式,更方便的做法是先行翻转得到matrixnew​[n−row−1][col]然后对角线翻转得到matrixnew​[col][n−row−1]

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < (n + 1) / 2; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - j - 1][i];
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
            matrix[j][n - i - 1] = temp;
        }
    }
}

void rotate2(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n / 2; ++i) for (int j = 0; j < n; ++j) swap(matrix[i][j], matrix[n - i - 1][j]);
    for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) swap(matrix[i][j], matrix[j][i]);
}

题号:4 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 该矩阵具有以下特性：

• 每行的元素从左到右升序排列
• 每列的元素从上到下升序排列

鉴于矩阵各行行内的有序性，可以直接在各行内二分查找

对任意元素，如果存在的话，其右侧和下方元素比它更大，左侧和上方元素比它小,因此:

1. 从右上角或者左下角开始，不断舍弃矩阵不正确的部分
2. 若当前元素大于target,其左上方元素必然比它小，舍弃，即向右或者向下
3. 相反情况下，其右下方元素必然比它大，舍弃，即向左或者向上
4. 大小情况下各自只能在上下，左右方向里选不同的一对情况舍入，否则会提前跑出范围

bool searchMatrix(vector<vector<int>>& matrix, int target) {
     for (const auto& row: matrix) {
            auto it = lower_bound(row.begin(), row.end(), target);
            if (it != row.end() && *it == target) return true;
        }
        return false;
}

bool searchMatrix2(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) return true;
            else if (matrix[x][y] > target) --x;
            else ++y;
        }
        return false;
    }

bool searchMatrix3(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int x = m-1, y =0;
    while (x >=0 && y < n) {
        if (matrix[x][y] == target) return true;
        else if (matrix[x][y] > target) --x;
        else ++y;
    }
    return false;
}

链表

题号:1 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点如果两个链表不存在相交节点，返回 null

这题有很多思路，例如用哈希表检测碰撞，求出两者长度然后让遍历长链表到和短链表有相同剩余长度的位置，再一起同步检测
下面是使用双指针的做法:

只有当链表 headA 和 headB 都不为空时，两个链表才可能相交因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null
当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点具体做法如下

• 每步操作需要同时更新指针 pA 和 pB
• 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点
• 如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点
• 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null

相当于同时遍历A+B和B+A,假设没有公共点，会在遍历完两链表相加的长度后终止，否则会在各自遍历完一次各自的链表后交换后的那次遍历中间相遇(除非两链表长度一致)

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
    ListNode* pA = headA;
    ListNode* pB = headB;
    while (pA != pB) {
        pA = pA == NULL ? headB : pA->next;
        pB = pB == NULL ? headA : pB->next;
    }
    return pA;
    }

题号:2 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

迭代法很基础，递归法需要先压栈到最后一个节点，然后每轮修改后一个节点的指向到前一个节点

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* p = head, * q = head->next;
    p->next = nullptr;
    while (q) {
        auto t = q->next;
        q->next = p;
        p = q;
        q = t;
    }
    return p;
}

/**
     * 以链表1->2->3->4->5举例
     */
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        /*
            直到当前节点的下一个节点为空时返回当前节点
            由于5没有下一个节点了，所以此处返回节点5
            */
        return head;
    }
    //递归传入下一个节点，目的是为了到达最后一个节点
    ListNode newHead = reverseList(head.next);
            /*
        第一轮出栈，head为5，head.next为空，返回5
        第二轮出栈，head为4，head.next为5，执行head.next.next=head也就是5.next=4，
                    把当前节点的子节点的子节点指向当前节点
                    此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4.next=null
                    此时链表为1->2->3->4<-5
                    返回节点5
        第三轮出栈，head为3，head.next为4，执行head.next.next=head也就是4.next=3，
                    此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
                    此时链表为1->2->3<-4<-5
                    返回节点5
        第四轮出栈，head为2，head.next为3，执行head.next.next=head也就是3.next=2，
                    此时链表为1->2<->3<-4<-5，由于2与3互相指向，所以此处要断开2.next=null
                    此时链表为1->2<-3<-4<-5
                    返回节点5
        第五轮出栈，head为1，head.next为2，执行head.next.next=head也就是2.next=1，
                    此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1.next=null
                    此时链表为1<-2<-3<-4<-5
                    返回节点5
        出栈完成，最终头节点5->4->3->2->1
        */
    head.next.next = head;
    head.next = null;
    return newHead;
}

题号:3 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为 回文链表 如果是，返回 true ；否则，返回 false

容易想到先转化数组再比对
不顾及优雅的话，可以用一个外部变量正向迭代，辅以递归反向迭代(我个人喜欢创造函数局部值然后辅助函数传引用)
也可以用快慢指针，慢指针走到中点，然后从中点开始反转链表(n/2复杂度)，再逐个比较

ListNode* frontPointer;
bool recursivelyCheck(ListNode* currentNode) {
    if (currentNode != nullptr) {
        if (!recursivelyCheck(currentNode->next)) {
            return false;
        }
        if (currentNode->val != frontPointer->val) {
            return false;
        }
        frontPointer = frontPointer->next;
    }
    return true;
}

bool isPalindrome_recur(ListNode* head) {
    frontPointer = head;
    return recursivelyCheck(head);
}

//判断该链表是否为回文链表
bool isPalindrome(ListNode* head) {
    ListNode* slow = head, * fast = head;
    while (fast) {
        slow = slow->next;
        fast = fast->next;
        if (!fast) break;
        fast = fast->next;
    }
    slow = reverseList(slow);
    while (head && slow) {
        if (head->val != slow->val) return 0;
        head = head->next;
        slow = slow->next;
    }
    return 1;
}

题号:4 环形链表 给你一个链表的头节点 head ，判断链表中是否有环
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）注意：pos 不作为参数进行传递 仅仅是为了标识链表的实际情况
如果链表中存在环 ，则返回 true 否则，返回 false

经典的快慢指针例题，不赘述
此外，这种找环的通解也可以用哈希做

bool hasCycle(ListNode *head) {
    ListNode* slow = head, * fast = head;
    while (fast) {
        slow = slow->next;
        fast = fast->next;
        if (!fast) return 0;
        fast = fast->next;
        if (slow == fast) return 1;
    }
    return 0;
}

bool hasCycle_hash(ListNode *head) {
    unordered_set<ListNode*> seen;
    while (head != nullptr) {
        if (seen.count(head)) {
            return true;
        }
        seen.insert(head);
        head = head->next;
    }
    return false;
}

题号:5 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点 如果链表无环，则返回 null
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）如果 pos 是 -1，则在该链表中没有环注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况
不允许修改链表

经典解法哈希和上一题类似

还是用上一题的快慢指针,设链表中环外部分的长度为 aslow 指针进入环后，又走了 b 的距离与 fast 相遇,到环前最后一个结点剩下距离为c此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc
即a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置最终，它们会在入环点相遇

ListNode *detectCycle(ListNode *head) {
    ListNode* slow = head, * fast = head;
    while (fast != nullptr) {
        slow = slow->next;
        fast = fast->next;
        if (fast == nullptr) return nullptr;
        fast = fast->next;
        if (fast == slow) {
            ListNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    return nullptr;
}

题号:6 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回新链表是通过拼接给定的两个链表的所有节点组成的

基础链表题之一，迭代和递归都很好理解

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* head = new ListNode{};
    ListNode* tail = head, * t;
    while (list1 && list2) {
        t = list1->val < list2->val ? list1 : list2;
        if (t == list1) list1 = list1->next;
        else list2 = list2->next;
        tail->next = t;
        tail = tail->next;
    }
    tail->next = (!list1) ? list2 : list1;
    return head->next;
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    } else if (l2 == null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

题号:7 两数相加
给你两个 非空 的链表，表示两个非负的整数它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字
请你将两个数相加，并以相同形式返回一个表示和的链表
你可以假设除了数字 0 之外，这两个数都不会以 0 开头

模拟位加法，记得保留进位信息

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *head = nullptr, *tail = nullptr;
    int carry = 0;
    while (l1 || l2) {
        int n1 = l1 ? l1->val: 0;
        int n2 = l2 ? l2->val: 0;
        int sum = n1 + n2 + carry;
        if (!head) head = tail = new ListNode(sum % 10);
        else {
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
        }
        carry = sum / 10;
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }
    if (carry > 0) tail->next = new ListNode(carry);
    return head;
}

题号:8 删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

双指针的又一次奇技淫巧,让快指针先跑n步，然后快慢指针一起遍历到结束
小心几个边界情况:

1. 要删去倒数第n个节点，准确地说我们需要这个节点的前一个节点，因此可以让它空过一次或者从一个无实值头结点开始，也可以像我这样直接做一个Pre指针出来
2. 如果要删头结点，也就是没有Pre的情况，需要特别判断

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* fast = head, * slow = head, * pre =slow;
    for (int i = 0;i < n; i++) fast = fast->next;
    while (fast) {
        pre = slow;
        slow = slow->next;
        fast = fast->next;
    }
    if (pre == slow) return head->next;
    pre->next = slow->next;
    return head;
}

题号:9 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）

递归:找不出一对相邻节点时终止返回,返回值实际上作为每一对的下个节点，也就是原来的左节点指向后继节点，随后把原来的右节点指向左节点，就完成了每层的任务
迭代:类似递归一对一对地进行，但需要加一个头结点存储结果和保留先驱节点

public ListNode swapPairs_recur(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = head.next;
    head.next = swapPairs_recur(newHead.next);
    newHead.next = head;
    return newHead;
}

ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead =new ListNode();
    dummyHead->next = head;
    ListNode* temp = dummyHead;
    while (temp->next != nullptr && temp->next->next != nullptr) {//之后两个节点都存在时才可以交换
        ListNode* node1 = temp->next;
        ListNode* node2 = temp->next->next;
        temp->next = node2;
        node1->next = node2->next;
        node2->next = node1;
        temp = node1;
    }
    ListNode* res = dummyHead->next;
    return res;
}

题号:10 随机链表的复制 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点
构造这个链表的 深拷贝 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态复制链表中的指针都不应指向原链表中的节点
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y
返回复制链表的头节点

本题主要难点在于，如何指向一个随机(可能还没有被复制)的结点:

1. 最简单的做法莫过于用哈希表存储原节点到复制结点的映射，然后再一一把随机指针迭代创建，这样相当于需要遍历两次，复杂度的数量级还是n，但数值较高
2. 类似的思路也可以用递归做，每轮如果查哈希表失败，就创建新节点，然后对next和random指针也递归，最后返回被复制的节点给上层使用
   
3. 为了把空间复杂度降到常数级，可以将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→C，我们可以将其拆分为 A→A′→B→B′→C→C′对于任意一个原节点 S，其拷贝节点 S′ 即为其后继节点但对尾节点需要进行特别处理

Node* copyRandomList(Node* head) {
    unordered_map<Node*, Node*> cachedNode;
    if (head == nullptr) return head;
    Node* t = head;
    while (t) {
        Node* headNew = new Node(t->val);
        cachedNode[t] = headNew;
        t = t->next;
    }
    for (auto n : cachedNode) {
        Node* n0 = n.first;
        Node* n1 = n.second;
        n1->next = n0->next == nullptr ? nullptr : cachedNode[n0->next];
        n1->random = n0->random == nullptr ? nullptr : cachedNode[n0->random];
    }
    return cachedNode[head];
}

unordered_map<Node*, Node*> cachedNode;
Node* copyRandomList_recur(Node* head) {
    if (head == nullptr) return nullptr;
    if (!cachedNode.count(head)) {
        Node* headNew = new Node(head->val);
        cachedNode[head] = headNew;
        headNew->next = copyRandomList_recur(head->next);
        headNew->random = copyRandomList_recur(head->random);
    }
    return cachedNode[head];
}

Node* copyRandomList_best(Node* head) {
    if (head == nullptr) {
        return nullptr;
    }
    for (Node* node = head; node != nullptr; node = node->next->next) {
        Node* nodeNew = new Node(node->val);
        nodeNew->next = node->next;
        node->next = nodeNew;
    }
    for (Node* node = head; node != nullptr; node = node->next->next) {
        Node* nodeNew = node->next;
        nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
    }
    Node* headNew = head->next;
    for (Node* node = head; node != nullptr; node = node->next) {
        Node* nodeNew = node->next;
        node->next = node->next->next;
        nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
    }
    return headNew;
}

题号:11 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表

说起排序链表，最自然的想法必然是插入排序，但这样时间复杂度较高
再比如可以用哈希表,k为链表结点值，v是链表指针，根据k排序完再组起来，这样空间复杂度很高
最完美的办法就只有归并了，而且为了空间能O(1),还得自底向上

大致的思路:

ListNode* sortList(ListNode* head) {
    if (head == nullptr) {
        return head;
    }
    int length = 0;
    ListNode* node = head;
    while (node != nullptr) {
        length++;
        node = node->next;
    }
    ListNode* dummyHead = new ListNode(0, head);
    for (int subLength = 1; subLength < length; subLength <<= 1) {
        ListNode* prev = dummyHead, *curr = dummyHead->next;
        while (curr != nullptr) {
            ListNode* head1 = curr;
            for (int i = 1; i < subLength && curr->next != nullptr; i++) {
                curr = curr->next;
            }
            ListNode* head2 = curr->next;
            curr->next = nullptr;
            curr = head2;
            for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {
                curr = curr->next;
            }
            ListNode* next = nullptr;
            if (curr != nullptr) {
                next = curr->next;
                curr->next = nullptr;
            }
            ListNode* merged = merge(head1, head2);
            prev->next = merged;
            while (prev->next != nullptr) {
                prev = prev->next;
            }
            curr = next;
        }
    }
    return dummyHead->next;
}

ListNode* merge(ListNode* head1, ListNode* head2) {
    ListNode* dummyHead = new ListNode(0);
    ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
    while (temp1 != nullptr && temp2 != nullptr) {
        if (temp1->val <= temp2->val) {
            temp->next = temp1;
            temp1 = temp1->next;
        } else {
            temp->next = temp2;
            temp2 = temp2->next;
        }
        temp = temp->next;
    }
    if (temp1 != nullptr) {
        temp->next = temp1;
    } else if (temp2 != nullptr) {
        temp->next = temp2;
    }
    return dummyHead->next;
}

题号:12 LRU缓存

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

二叉树

题号:1 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历

递归实现非常基础，迭代法需要用到栈:

1. 一路往左子树走入栈
2. 无路可走后，出栈一个节点输出
3. 往出栈节点的右子树走

类似的，遍历可以只用出入栈操作实现
先序(中左右):初始入栈根节点，每次出栈输出一个节点，然后以右左子节点顺序入栈
后序(左右中):一路往左子树走，每次出栈时我们需要一个flag标志保存最后一个输出节点(标记右子树有没有走过)，如果没有右孩子或者flag==右孩子直接输出，否则右节点先入栈

vector<int> inorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> res;
    stack<TreeNode*> st;
    while (root || !st.empty()) {
        if (root) {
            st.emplace(root);
            root = root->left;
        }
        else {
            root = st.top();st.pop();
            res.push_back(root->val);
            root = root->right;
        }
    }
    return res;
}

题号:2 二叉树最大深度
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

题号:3 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

void invert_helper(TreeNode* node) {
    if (!node) return;
    swap(node->left, node->right);
    invert_helper(node->left);
    invert_helper(node->right);
}

TreeNode* invertTree(TreeNode* root) {
    invert_helper(root);
    return root;
}

题号:4 对称二叉树
判断二叉树是否对称
你可能会自然想到递归，但问题是我们需要沿着对称轴递归判断，也就是需要两个参数
迭代实现就是两个栈同步在两个子树上出入栈

bool isSymmetric(TreeNode* root) {
    if (!root) return 1;
    stack<TreeNode*> st1, st2;
    TreeNode* p1 = root;
    TreeNode* p2 = p1;
    st1.emplace(p1);
    st2.emplace(p2);
    while (!st1.empty()) {
        p1 = st1.top();st1.pop();
        p2 = st2.top();st2.pop();
        if ((p1 && !p2) || (p2 && !p1)) return 0;
        else if (!p1) continue;
        else if (p1->val != p2->val) return 0;
        else {
            st1.push(p1->left);
            st1.push(p1->right);
            st2.push(p2->right);
            st2.push(p2->left);
        }
    }
    return 1;
}

题号:5 二叉树的直径
给你一棵二叉树的根节点，返回该树的直径
二叉树的直径是指树中任意两个节点之间最长路径的长度这条路径可能经过也可能不经过根节点 root
两节点之间路径的长度由它们之间边数表示

int maxd =0;
int depth(TreeNode* node) {
    if(node==NULL) return 0;
    int Left = depth(node->left);
    int Right = depth(node->right);
    maxd=max(Left+Right,maxd);//将每个节点最大直径(左子树深度+右子树深度)当前最大值比较并取大者
    return max(Left,Right)+1;//返回节点深度
}
int diameterOfBinaryTree(TreeNode* root) {
    depth(root);
    return maxd;
}

题号:6 二叉树层序遍历

迭代做很简单，逐层入队列就行
递归需要带深度信息，例如父节点的索引号

vector<vector<int>> levelOrder(TreeNode* root) {
    vector <vector <int>> ret;
    if (!root) return ret;

    queue <TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int currentLevelSize = q.size();
        ret.push_back(vector <int> ());
        for (int i = 1; i <= currentLevelSize; ++i) {
            auto node = q.front(); q.pop();
            ret.back().push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    
    return ret;
}

题号:7 将有序数组转化为平衡二叉搜索树
平衡条件可以直观地想到每次二分法建树
要注意的是，此题的树形不唯一，这里直接用c++的除法(向下取整)找根节点
每次递归传入一个数组范围，若范围只有一个元素，直接返回新节点，否则建立根节点，递归左右子节点再返回根节点

TreeNode* sortedArrayToBST_helper(vector<int>& nums, int head, int tail) {
    if (head > tail) return nullptr;
    if (head == tail) return new TreeNode(nums[head]);
    TreeNode* node = new TreeNode;
    int mid = (tail + head) / 2;
    node->val = nums[mid];
    node->left = sortedArrayToBST_helper(nums, head, mid - 1);
    node->right = sortedArrayToBST_helper(nums, mid + 1, tail);
    return node;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
    if (nums.empty()) return nullptr;
    int mid = nums.size() / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBST_helper(nums, 0, mid - 1);
    root->right = sortedArrayToBST_helper(nums, mid + 1, nums.size() - 1);
    return root;
}

题号:8 验证二叉搜索树
此题中左右子节点有严格大小关系
本题难点在于，想从上而下校验需要知道子节点的最大最小值才能判断，因此需要逆转思路，不是从上至下校验，而是从上至下限制范围，每次往下递归，都增加一个最大或者最小值限制，只要有不满足的子节点就判false
此外对BST中序遍历必然是一个升序序列，可以以此判断 此外，此题阴的是数值范围是long long，用int过不了用例

void isValidBST_helper(TreeNode* root, long long min_val, long long max_val, bool& res) {
    if (!res || !root) return;//检验失败或root为空则退出
    if (min_val >= root->val || root->val >= max_val) { res = 0;  return; }
    isValidBST_helper(root->left, min_val, root->val, res);
    isValidBST_helper(root->right, root->val, max_val, res);
}
bool isValidBST(TreeNode* roots) {
    bool i = 1;
    isValidBST_helper(roots, LONG_MIN, LONG_MAX, i);
    return i;
}

bool isValidBST_iter(TreeNode* root) {
    stack<TreeNode*> stack;
    long long inorder = (long long)INT_MIN - 1;

    while (!stack.empty() || root != nullptr) {
        while (root != nullptr) {
            stack.push(root);
            root = root -> left;
        }
        root = stack.top();
        stack.pop();
        // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
        if (root -> val <= inorder) {
            return false;
        }
        inorder = root -> val;
        root = root -> right;
    }
    return true;
}

题号:9 二叉搜索树中第 K 小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）

迭代法可以模拟中序遍历来不断根据大小顺序生成元素，这样只有h+k的复杂度，但这个h是一路往左的子树，最坏情况有n长 考虑要多次进行这样操作的情况，例如可以新建一个结点类，带一个序号值，或者只用一个哈希表存储各个节点的左侧结点数
只要查一次的话可以省略哈希表，不断根据左侧结点数选择要往哪走，这样做最坏情况会O(N)，即左子树有n-1个结点，而我们要找最小元素，之后就会一个个地往左走，总共2n左右次操作,性能和迭代差不多

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode *> stack;
    while (root != nullptr || stack.size() > 0) {
        while (root != nullptr) {
            stack.push(root);
            root = root->left;
        }
        root = stack.top();
        stack.pop();
        --k;
        if (k == 0) break;
        root = root->right;
    }
    return root->val;
}

int node_num_of_tree(TreeNode* root) {
    if (!root) return 0;
    else return 1 + node_num_of_tree(root->left) + node_num_of_tree(root->right);
}

int kthSmallest_helper(TreeNode* root, const int& k, int n) {//n表示root这个节点的大小顺序
    if (!root) return 0;
    if (n == k) return root->val;
    else if (n < k) return kthSmallest_helper(root->right, k, node_num_of_tree(root->right->left) + n + 1);//由于题目必然有解，此时root必存在右孩子
    else return kthSmallest_helper(root->left, k, n - node_num_of_tree(root->left->right) - 1);
}

int kthSmallest(TreeNode* root, int k) {
    return kthSmallest_helper(root, k, 1 + node_num_of_tree(root->left));
}

题号:10 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值
实际上就是需要遍历每一层的最右侧节点:

1. 深度遍历，优先从右侧走，也就是左节点先入栈，但同时需要维护深度信息，用一个深度栈维护
2. 广度遍历，由于走到每层的最后就是我们要找的节点，所以不需要深度信息，这里我使用的两栈交替法解决判断每层结束，这样空间复杂度会稍高，但逻辑很好理解

vector<int> rightSideView_dfs(TreeNode* root) {
    unordered_map<int, int> rightmostValueAtDepth;
    int max_depth = -1;

    stack<TreeNode*> nodeStack;
    stack<int> depthStack;
    nodeStack.push(root);
    depthStack.push(0);

    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();nodeStack.pop();
        int depth = depthStack.top();depthStack.pop();

        if (node != NULL) {
            // 维护二叉树的最大深度
            max_depth = max(max_depth, depth);

            // 如果不存在对应深度的节点我们才插入
            if (!rightmostValueAtDepth.count(depth)) rightmostValueAtDepth[depth] =  node -> val;

            nodeStack.push(node -> left);
            nodeStack.push(node -> right);
            depthStack.push(depth + 1);
            depthStack.push(depth + 1);
        }
    }

    vector<int> rightView;
    for (int depth = 0; depth <= max_depth; ++depth) rightView.push_back(rightmostValueAtDepth[depth]);

    return rightView;
}

vector<int> rightSideView_bfs(TreeNode* root) {
    if (!root) return {};
    queue<TreeNode*> qe1, qe2;
    qe1.emplace(root);
    vector<int> res = { root->val };
    while (1) {
        while (!qe1.empty()) {
            auto t = qe1.front();qe1.pop();
            if (t->left) qe2.emplace(t->left);
            if (t->right) qe2.emplace(t->right);
        }
        if (qe2.empty()) return res;
        res.emplace_back(qe2.back()->val);
        swap(qe1, qe2);
    }
    return res;
}

题号:11 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null
• 展开后的单链表应该与二叉树 先序遍历 顺序相同

先序遍历也就是中左右顺序，也就是需要不断把左子树插进父节点和右节点之间，可以理解为不断把左子树的最右节点(根据先序遍历顺序，该节点必是右子树的前驱)插入右子树前 或者 不断把左子树插到父节点与右节点之间(左子树根节点必然是父节点的直接后驱)
我们可以用使用以上操作的(迭代)先序遍历实现算法，我们知道先序遍历的栈实现就是不断以右左顺序压栈，而栈顶元素必然是最后一个访问元素prev的最左孩子(直接后驱)，因此可以在遍历过程中不断把prev节点的左子树清空，右子树改成栈顶节点

要省下栈空间，可以不断寻找前驱节点，由于我们只需要不断处理左子树:

1. 根节点开始向右走直到遇到左子树l，寻找前驱节点pre，即左子树的最右节点
2. "断开"右子树r，把前驱节点连到被断开部分的开头
3. 把l连到父节点p的右子树上，并将父节点的左子树设为空此时连接关系是p->l->pre->r但l和r里可能还有左子树
4. 对p处理结束后，转到1继续循环直到遇到叶节点

本题的关键就是理解链接的顺序，即不断从根节点开始链接最左的孩子，直到所有节点没有左孩子
例如最后一种的递归做法，维护一个last表示链表尾,对有左子树的当前链表，递归将左子树与根节点链接，对只有右子树的当前链表，将目前链表尾接到右子树上再递归
也就是说不断找前驱和不断找后驱都是可以的

void flatten(TreeNode* root) {
    if (root == nullptr) return;
    auto stk = stack<TreeNode*>({root});
    TreeNode* prev = nullptr;
    while (!stk.empty()) {
        TreeNode* curr = stk.top(); stk.pop();
        if (prev != nullptr) {
            prev->left = nullptr;
            prev->right = curr;
        }
        TreeNode* left = curr->left, * right = curr->right;
        if (right != nullptr) stk.push(right);
        if (left != nullptr) stk.push(left);
        prev = curr;
    }
}

void flatten_best(TreeNode* root) {
    TreeNode* curr = root;
    while (curr != nullptr) {
        if (curr->left != nullptr) {
            TreeNode* next = curr->left;
            TreeNode* predecessor = next;
            while (predecessor->right != nullptr) predecessor = predecessor->right;
            predecessor->right = curr->right;//对一个节点来说，其右孩子先序遍历的前驱是左孩子最右的子节点
            curr->left = nullptr;
            curr->right = next;
        }
        curr = curr->right;
    }
}

public void flatten_recur(TreeNode root) {
    if(root==null) return;
    subflatten(root);
}
public TreeNode subflatten(TreeNode root){
    TreeNode left = root.left;
    TreeNode right = root.right;
    TreeNode last = root; //左右为空时返回root
    root.left=null;
    if(left!=null) {
        root.right = left;
        last = subflatten(left);
    }
    if(right!=null){
        last.right = right;
        last = subflatten(right);
    } 
    return last;//返回链表的最后一位
}

题号:12 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点
这题属于原理容易理解但实现复杂的类型,个人认为掌握递归法就够了

TreeNode* BuildTree_helper(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right, const unordered_map<int, int>& index) {
    if (preorder_left > preorder_right) return nullptr;
    // 前序遍历中的第一个节点就是根节点
    int preorder_root = preorder_left;
    // 在中序遍历中定位根节点
    int inorder_root = index.at(preorder[preorder_root]);
    TreeNode* root = new TreeNode(preorder[preorder_root]);
    int size_left_subtree = inorder_root - inorder_left;
    // 递归地构造左子树，并连接到根节点
    // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
    root->left = BuildTree_helper(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1, index);
    // 递归地构造右子树，并连接到根节点
    // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
    root->right = BuildTree_helper(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right, index);
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> index;
    int n = preorder.size();
    // 构造哈希映射，用于快速定位根节点
    for (int i = 0; i < n; ++i) {
        index[inorder[i]] = i;
    }
    return BuildTree_helper(preorder, inorder, 0, n - 1, 0, n - 1, index);
}

TreeNode* buildTree_iter(vector<int>& preorder, vector<int>& inorder) {
    if (!preorder.size()) {
        return nullptr;
    }
    TreeNode* root = new TreeNode(preorder[0]);
    stack<TreeNode*> stk;
    stk.push(root);
    int inorderIndex = 0;
    for (int i = 1; i < preorder.size(); ++i) {
        int preorderVal = preorder[i];
        TreeNode* node = stk.top();
        if (node->val != inorder[inorderIndex]) {
            node->left = new TreeNode(preorderVal);
            stk.push(node->left);
        }
        else {
            while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {
                node = stk.top();
                stk.pop();
                ++inorderIndex;
            }
            node->right = new TreeNode(preorderVal);
            stk.push(node->right);
        }
    }
    return root;
}

题号:13 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）

虽然是二叉树，但本题完全可以看做动态规划问题来做(只需要求路径数量)，通过在遍历时缓存前缀和大小及数量，就可以以线性复杂度解决此题
还有一个问题是对任意结点，它能查到的前缀和必然是它的父级节点所有的，也就在这条dst路径上，因此在遍历完子节点后必须删除计数值
以及，此题又非常幽默地用了long long输入范围，也不知道图什么

int pathSum_helper(TreeNode* root, long long curr, int targetSum, unordered_map<long long, int>& prefix) {
    if (!root) return 0;
    int ret = 0;
    curr += root->val;
    if (prefix.count(curr - targetSum)) ret = prefix[curr - targetSum];
    prefix[curr]++;
    ret += pathSum_helper(root->left, curr, targetSum, prefix);
    ret += pathSum_helper(root->right, curr, targetSum, prefix);
    prefix[curr]--;
    return ret;
}

int pathSum(TreeNode* root, int targetSum) {
    unordered_map<long long, int> prefix;
    prefix[0] = 1;
    return pathSum_helper(root, 0, targetSum, prefix);
}

题号:14 最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

1. 递归:由于递归会先递归到叶节点然后自底向上匹配，所以匹配成功的必然是最近公共祖先，而这个祖先有两种情况
   1. 左右侧各有这两个节点中的一个
   2. 祖先本身是一个节点，还有一个是其子节点
   3. 根据两个条件可以建立相应递归函数，注意lson,rson判定和祖先判定是两种逻辑
2. 建立子节点到父节点的哈希表，标记一个节点的所有父节点匹配另一个节点

TreeNode* res;
bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) return false;
    bool lson = dfs(root->left, p, q);
    bool rson = dfs(root->right, p, q);
    if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
        res = root;
    } 
    return lson || rson || (root->val == p->val || root->val == q->val);
}
TreeNode* lowestCommonAncestor_recur(TreeNode* root, TreeNode* p, TreeNode* q) {
    dfs(root, p, q);
    return res;
}

void lowestCommonAncestor_helper(TreeNode* root, unordered_map<int, TreeNode*>& fa) {//构建子节点到父节点的链接
    if (root->left != nullptr) {
        fa[root->left->val] = root;
        lowestCommonAncestor_helper(root->left, fa);
    }
    if (root->right != nullptr) {
        fa[root->right->val] = root;
        lowestCommonAncestor_helper(root->right, fa);
    }
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    unordered_map<int, TreeNode*> fa;
    unordered_map<int, bool> vis;
    fa[root->val] = nullptr;
    lowestCommonAncestor_helper(root, fa);
    while (p != nullptr) {//一路标记p的父节点
        vis[p->val] = true;
        p = fa[p->val];
    }
    while (q != nullptr) {
        if (vis[q->val]) return q;
        q = fa[q->val];
    }
    return nullptr;
}

题号:15 BST的AVL化
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过1，我们就称这棵二叉搜索树是平衡的

此题可以转化为中序序列建树问题，当然为什么能转化需要证明，见题解
考场上不需要证明，直接写就行了，毕竟这个结论很符合直觉

vector<int> inorderSeq;

void getInorder(TreeNode* o) {
    if (o->left) getInorder(o->left);
    inorderSeq.push_back(o->val);
    if (o->right) getInorder(o->right); 
}

TreeNode* build(int l, int r) {
    int mid = (l + r) / 2;
    TreeNode* o = new TreeNode(inorderSeq[mid]);
    if (l <= mid - 1) o->left = build(l, mid - 1);
    if (mid + 1 <= r) o->right = build(mid + 1, r);
    return o;
}

TreeNode* balanceBST(TreeNode* root) {
    getInorder(root);
    return build(0, inorderSeq.size() - 1);
}

图论

题号:1 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
此外，你可以假设该网格的四条边均被水包围

此题可以用bfs做，但有些麻烦的细节，写的时候要小心四个方向的索引别写错，每次找到新岛屿再建队列等小问题
可以使用如下题的方向向量数组优化

bool is_outside(int i, int j, const int& m, const int& n, vector<vector<char>>& grid) {
    return (i < 0 || i >= n || j < 0 || j >= m);
}
int numIslands(vector<vector<char>>& grid) {
    int n = grid.size();//行数
    int m = grid[0].size();//列数
    int res = 0;
    for (int i = 0;i < n;++i) {
        for (int j = 0;j < m;++j) {
            if (grid[i][j] == '1') {
                ++res;
                queue<pair<int, int>> qe;
                qe.emplace(i, j);
                while (!qe.empty()) {
                    auto p = qe.front();qe.pop();
                    int ti = p.first, tj = p.second;
                    if (grid[ti][tj] == '0') continue;//遇到水终止操作
                    grid[ti][tj] = '2'; cout << i << ':' << j << '\n';
                    if (!is_outside(ti - 1, tj, m, n, grid) && grid[ti - 1][tj] == '1') { qe.emplace(ti - 1, tj); grid[ti - 1][tj] = '2'; }
                    if (!is_outside(ti + 1, tj, m, n, grid) && grid[ti + 1][tj] == '1') { qe.emplace(ti + 1, tj); grid[ti + 1][tj] = '2'; }
                    if (!is_outside(ti, tj - 1, m, n, grid) && grid[ti][tj - 1] == '1') { qe.emplace(ti, tj - 1); grid[ti][tj - 1] = '2'; }
                    if (!is_outside(ti, tj + 1, m, n, grid) && grid[ti][tj + 1] == '1') { qe.emplace(ti, tj + 1); grid[ti][tj + 1] = '2'; }
                }
                
            }
        }
    }
    return res;
}

题号:2 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格
• 值 1 代表新鲜橘子
• 值 2 代表腐烂的橘子

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1

本题的特点在于，可能有多个腐蚀源头，因此需要以多个源头开始进行广度遍历

1. 找到所有腐烂橘子位置，并用一个队列存储
2. 遍历1.中的队列，对每个腐烂橘子，污染其邻居，如果有新鲜橘子也将其入队
3. 2.遍历一轮后，时间加一，如果有新橘子腐烂继续循环
4. 最后需要判别有没有新鲜橘子剩下来，最简单的做法是再遍历一次，但在之前过程中一直对新鲜橘子计数也可以做到

int orangesRotting(vector<vector<int>>& grid) {
    queue<pair<int, int>> q;
    int dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
    int m = grid.size(), n = grid[0].size();
    bool flag = false;//是否有新鲜橘子
    for (int i = 0;i < m;i++)
        for (int j = 0;j < n;j++)
            if (grid[i][j] == 2)//找到第一轮腐烂橘子
                q.push({ i,j });
            else if (grid[i][j] == 1)
                flag = 1;
    if (q.empty() && flag)//如果没有腐烂橘子并且有新鲜橘子，则新鲜橘子不可能腐烂
        return -1;
    int res = 0;
    while (!q.empty()) {
        int t = q.size();//遍历同一时间感染的橘子
        for (int k = 0;k < t;k++) {
            pair<int, int>p = q.front(); q.pop();
            for (auto dir : dirs) {
                int x = p.first + dir[0];
                int y = p.second + dir[1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)//找到新感染的橘子
                {
                    grid[x][y] = 2;
                    q.push({ x,y });
                }
            }
        }
        if (!q.empty())//如果当前轮有新感染的橘子，时间加一
            res++;
    }
    for (int i = 0;i < m;i++)
        for (int j = 0;j < n;j++)
            if (grid[i][j] == 1)//检查是否有未感染的新鲜橘子
                return -1;
    return res;
}

题号:3 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false

此题表示图的方法比较非主流，只给了无序的边集合，想要发掘图的拓扑关系，应该将边以起始顶点来聚类，形成一个嵌套数组，也就是408里的邻接表
然后可以分为dfs,bfs两种思路:

1. 深度遍历:深度遍历的思路是后面遍历到的边的入点不能是之前访问过的点，这样就会形成一个环而无法拓扑排序
   1. 一个易错点是，由于图未必联通，可能有多个子图，因此需要区分不同的有连接关系的拓扑序列，也就是结点分为3种状态
      1. 完全未访问
      2. 已访问，但仍在一个深度遍历的过程中，这些节点在同一个联通图内
      3. 访问且深度遍历完，是有联通关系的拓扑序列的一部分，但和其他序列无关
   2. 用栈理解更直观，如果只在相邻节点都已经搜索完成时入栈一个节点，那么如果可以全部入栈一个图，就可以拓扑排序
2. 广度遍历:即所谓的kahn算法:
   1. 可以拓扑排序的图，一定同时有入度和出度为0的节点，也就是序列的首尾，我们可以不断移除入度为0的节点，令其相邻节点的入度减1
   2. 循环终止后我们发现所有边都被移除，就存在拓扑序列，否则不存在
   3. 觉得眼熟？408的死锁检测也用了类似算法

void dfs_course(vector<int>& courses, const vector<vector<int>>& edges, int node, bool& res) {
    if (!res) return;
    courses[node] = 1;
    auto es = edges[node];//该节点连向的其他节点
    for (auto e : es) {
        if (courses[e] == 1) { res = 0; return; }
        else if (courses[e] == 0) dfs_course(courses, edges, e, res);
    }
    courses[node] = 2;
}

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> courses(numCourses, 0);//课程状态数组，0表示未遍历过
    vector<vector<int>> edges(numCourses, vector<int>());
    bool res = 1;
    for (const auto& e : prerequisites) edges[e[1]].push_back(e[0]);
    for (int i = 0;i < numCourses && res;++i) if (courses[i] == 0) dfs_course(courses, edges, i, res);
    return res;
}

bool canFinish_bfs(int numCourses, vector<vector<int>>& prerequisites) {
    edges.resize(numCourses);
    indeg.resize(numCourses);
    for (const auto& info: prerequisites) {
        edges[info[1]].push_back(info[0]);
        ++indeg[info[0]];
    }

    queue<int> q;
    for (int i = 0; i < numCourses; ++i) {
        if (indeg[i] == 0) {
            q.push(i);
        }
    }

    int visited = 0;
    while (!q.empty()) {
        ++visited;
        int u = q.front();
        q.pop();
        for (int v: edges[u]) {
            --indeg[v];
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }

    return visited == numCourses;
}

题号:4 前缀树

• Trie() 初始化前缀树对象
• void insert(String word) 向前缀树中插入字符串 word
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false

前缀树可以视为树状存储的字符串，根节点为空字符串，根节点到每个节点的路径则是一个特定前缀，而对这个前缀，最多可以有26(此题固定位小写字母)个子节点形成下一个单词前缀。此外，如果想表示字符串终止，需要一个特定的flag，也就是每个有end标记的节点会特定一个字符串，可以看做一种编码体系
看着手搓数据结构比较吓人，其实很简单，实现上就是一个26叉树，其插入就是顺着单词一路创建(如果原先没有的话)，最后标一个end;查找前缀也很容易理解，查找单词就是查找一个有end标记的前缀

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (!node->children[ch] ) return nullptr;
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26,nullptr), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (!node->children[ch]) node->children[ch] = new Trie();
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};

回溯

回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试
这样听上去暴力的算法感觉很简单，但其实对有性能要求的场合，优化起来会很麻烦
总得来说，回溯的思路是:

1. 每层传入给下一层目前为止的选择集，同样也收到上一层的选择集，对每层来说:
2. 如果没有选择或者满足终止条件，退出
3. 遍历所有选择
   1. 添加一个选择到选择集传给下一层
   2. 移除该选择集

需要注意的是，虽然递归后需要回溯，但如果传入下层的选择是一个副本而不是引用，就不需要回溯操作，遍历后到达作用域终点当前的选择信息也会被自动释放
一般来说优化性能有两个方向:

1. 预处理输入，例如如果可以简单判断无解的情况就不要回溯
2. 记忆化，记忆已经做过的选择或者其他信息避免重复计算

题号:1 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案

例如对此题来说，简单的思路是通过一个状态数组维护已排列和未排列部分，然后不断递归穷举，这样很直观，但空间开销极大
如果要省略这个状态数组，可以不断在穷举未排序部分时交换即将放入排序部分的元素和未排序部分边界的元素，这样就可以把拓展边界操作统一为右移一位边界，避免状态数组的开销

void permute_helper(vector<vector<int>>& res, vector<int>& output, int first, int len) {
    // 所有数都填完了
    if (first == len) {
        res.emplace_back(output);
        return;
    }
    for (int i = first; i < len; ++i) {//[0,first]部分为已填过的数
        // 动态维护数组
        swap(output[i], output[first]);
        // 继续递归填下一个数
        permute_helper(res, output, first + 1, len);
        // 撤销操作
        swap(output[i], output[first]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int> > res;
    permute_helper(res, nums, 0, (int)nums.size());
    return res;
}

题号:2 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集
解集不能包含重复的子集。你可以按 任意顺序 返回解集

子集和排列问题不同的是，无需考虑顺序，只需要考虑各个元素的有无，如果用递归做，每层只有两种可能,即放入和不放入一个元素，也就是其决策树画出来是颗满二叉树，每个叶节点对应一个子集
眼熟？没错，这也是一种编码，我们完全可以用n位二进制数编码所有子集，k位对应第k个元素的有无

vector<vector<int>> subsets(vector<int>& nums) {
    vector<int> t;
    vector<vector<int>> res;
    int n = nums.size();
    for (int mask = 0; mask < (1 << n); ++mask) {//n位二进制掩码表示子集
        t.clear();
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                t.push_back(nums[i]);
            }
        }
        res.push_back(t);
    }
    return res;
}

vector<int> t;
vector<vector<int>> res;

void dfs(int cur, vector<int>& nums) {
    if (cur == nums.size()) {
        res.push_back(t);
        return;
    }
    t.push_back(nums[cur]);
    dfs(cur + 1, nums);
    t.pop_back();
    dfs(cur + 1, nums);
}

vector<vector<int>> subsets(vector<int>& nums) {
    dfs(0, nums);
    return res;
}

题号:3 电话号码的字母排列
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回

相当于指定层数的回溯，每一层查表得到三个字母，依次送入下一层回溯，事实上，决策树是三叉树，最后结果数量也是 \(3^n\)

void letterCombinations_helper(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
    if (index == digits.length()) combinations.push_back(combination);
    else {
        char digit = digits[index];
        const string& letters = phoneMap.at(digit);
        for (const char& letter : letters) {
            combination.push_back(letter);
            letterCombinations_helper(combinations, phoneMap, digits, index + 1, combination);
            combination.pop_back();
        }
    }
}

vector<string> letterCombinations(string digits) {//电话数字能表示的字母组合
    if (digits.empty()) return {};
    vector<string> combinations;
    unordered_map<char, string> phoneMap{
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
    };
    string combination;
    letterCombinations_helper(combinations, phoneMap, digits, 0, combination);
    return combinations;
}

题号:4 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的 对于给定的输入，保证和为 target 的不同组合数少于 150 个

同样是标准回溯题，此题有一个大小关系约束，可以先对candidates排序，这样对相加结果大于target之后的元素就可以跳过了

void combinationSum_helper(vector<vector<int>>& res, const vector<int> candidates, const int& target, int pre_sum, vector<int> pre_select, int index) {//每次进入的初始状态是pre_sum是所有pre_select的元素和，所以先判断是否满足条件可以结束
    if (pre_sum == target) {//大于的情况不会调用递归，所以只可能小于等于
        res.emplace_back(pre_select);
    }
    else {
        for (int i = index;i < candidates.size();++i) {
            int sum = pre_sum + candidates[i];
            if (sum > target) break;
            else {
                pre_select.emplace_back(candidates[i]);
                combinationSum_helper(res, candidates, target, sum, pre_select, i);
                pre_select.pop_back();
            }
        }
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    sort(candidates.begin(), candidates.end());
    int size = candidates.size();
    combinationSum_helper(res, candidates, target, 0, {}, 0);
    return res;
}

题号:5 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合(这是卡特兰数问题的一个例子)

此题依旧没脱出回溯的模板，但规则上与之前不同的是强调成对性，也就是左括号数永远需要大于等于右括号数
对其的优化可以是用左右括号计数来约束每次回溯的选择，左括号数小于对数才可以放左括号，右括号数小于左括号数才可以放右括号

void backtrack(vector<string>& res, string& cur, int open, int close, int n) {
    if (cur.size() == n * 2) {
        res.push_back(cur);
        return;
    }
    if (open < n) {
        cur.push_back('(');
        backtrack(res, cur, open + 1, close, n);
        cur.pop_back();
    }
    if (close < open) {
        cur.push_back(')');
        backtrack(res, cur, open, close + 1, n);
        cur.pop_back();
    }
}
vector<string> generateParenthesis(int n) {
    vector<string> result;
    string current;
    backtrack(result, current, 0, 0, n);
    return result;
}

题号:6 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用

字符串匹配麻烦之处在于从任何索引开始都可能匹配上，但不管怎么说，如果能匹配，那么必然有一个开始点，因此意见可以穷举整个矩阵来解决
虽然无法避免穷举矩阵的开销，但可以在遍历过程中设置一个visited数组，避免单次匹配过程中重复

void exist_helper(const vector<vector<char>>& board, const string& word, const vector<pair<int, int>>& dire, int index, pair<int, int> coord, bool& res, vector<vector<bool>>& visited) {
    //index对应当前匹配的word字符串索引,coord则是当前所在矩阵位置
    if (res || word[index] != board[coord.first][coord.second]) return;
    else if (index == word.length() - 1) res = 1;
    else {
        visited[coord.first][coord.second] = 1;
        for (auto dir : dire) {
            if (res) break;
            int x = coord.first + dir.first; int y = coord.second + dir.second;
            if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || visited[x][y])continue;
            exist_helper(board, word, dire, index + 1, { x,y }, res, visited);
        }
        visited[coord.first][coord.second] = 0;
    }
}

bool exist(vector<vector<char>>& board, string word) {
    bool res = 0;
    int m = board.size(), n = board[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, 0));
    vector<pair<int, int>> directions = { {-1,0},{1,0},{0,1},{0,-1} };
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            exist_helper(board, word, directions, 0, { i,j }, res, visited);
            if (res) return true;
        }
    }
    return res;
}

题号:7 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串 ，使每个子串都是回文 。返回 s 所有可能的分割方案
很麻烦的一题，分割有顺序性，因此必须从左到右遍历，这点可以用双指针实现，即i<=j
计算回文开销很大，因此必须预处理或者记忆化
我们用一个n长方阵存储双指针，0表示未访问，1表示是回文，2表示不是回文:

1. 预处理，对任何i>=j,这个指针对视为回文(递归中要用)
2. 每次查找回文时，先递归<i+1,j-1>这一对，<i,j>是不是回文取决于,i,j处字符是否相等且<i+1,j-1>是否是回文
3. 记忆化:计算前先查表i,j，如果非0说明已经计算过

回溯过程:

1. i从0到n遍历
   1. j从i到n遍历
      1. 如果此时i,j是回文，分割并回溯
      2. 否则什么都不做

void backtrack_string(const string& s, int i, vector<vector<string>>& res, vector<string> selection, vector<vector<uint8_t>>& sym_word) {
    int n = s.size();
    if (i == n) {
        res.emplace_back(selection);
        return;
    }
    for (int j = i; j < n; ++j) {
        find_symmetry(s, sym_word, i, j);
        if (sym_word[i][j] == 1) {
            selection.emplace_back(s.substr(i, j - i + 1));
            backtrack_string(s, j + 1, res, selection, sym_word);
            selection.pop_back();
        }
    }

}

void find_symmetry(const string& s, vector<vector<uint8_t>>& sym_word, int i, int j) {
    if (sym_word[i][j] != 0) return;
    if (i >= j) sym_word[i][j] = 1;
    else {
        find_symmetry(s, sym_word, i + 1, j - 1);
        sym_word[i][j] = (s[i] == s[j] && sym_word[i + 1][j - 1]==1) ? 1 : 2;
    }
}

vector<vector<string>> partition(string s) {
    int n = s.length();
    vector<vector<uint8_t>> sym_word(n, vector<uint8_t>(n, 0));
    for (int j = 0; j < n;++j) {
        for (int i = j;i < n;++i) sym_word[i][j] = 1;
    }
    vector<vector<string>> res;
    vector<string> selection;
    backtrack_string(s, 0, res, selection, sym_word);
    return res;
}

二分查找

题号:1 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置
请使用时间复杂度为 O(log n) 的算法

经典，没什么好说的

int searchInsert(vector<int>& nums, int target) {
    int head = 0, tail = nums.size() - 1;
    while (head <= tail) {
        int mid = (head + tail) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) head = mid + 1;
        else tail = mid - 1;
    }
    return head;
}

题号:2 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列
• 每行的第一个整数大于前一行的最后一个整数

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false

做两次二分搜索，一次找行,即行首小于等于target,下一行首严格大于target;再一次找行内
也可以把矩阵映射成一维数组，即逐行相接，然后二分搜索

bool midsearch(vector<int>& nums, int target) {
    int head = 0, tail = nums.size() - 1;
    while (head <= tail) {
        int mid = (head + tail) / 2;
        if (nums[mid] == target) return 1;
        else if (nums[mid] < target) head = mid + 1;
        else tail = mid - 1;
    }
    return 0;
}

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    //先找一个行首小于等于目标，下一行首大于目标的行
    int up = 0, row = matrix.size() - 1, down = row, mid = down / 2;
    while (up <= down) {
        mid = (up + down) / 2;
        if (mid == row || (matrix[mid][0] <= target && matrix[mid + 1][0] > target)) return midsearch(matrix[mid], target);
        else if (matrix[mid][0] > target) down = mid - 1;
        else up = mid + 1;
    }
    return midsearch(matrix[mid], target);
}

题号:3 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置
如果数组中不存在目标值 target，返回 [-1, -1]
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

此题难点在怎么找数组首尾，当然随便找一个然后首尾顺着找也是个简单粗暴的方法，但极端情况可能有O(N)复杂度不达标
因此还是需要二分找到范围首尾，这里可以用一个flag改变二分行为，但没必要这么麻烦，左右各自做一个函数更方便，也没什么开销
需要注意的是由于等于的情况也会继续二分，最后有可能在不等于target的情况下结束，你可能想加一不就行了，但同样也有可能在等于情况下结束，例子就先略过了，当然也很好解决，加一个int存储最后一次匹配target的值就行了
最后如何判断找没找到呢?看两个索引是否是target的值就行了，此外，先判索引是否有效也是基操，在此题里，索引越界也表示没找到target

int binarySearch_lft(const vector<int>& nums, int target) {
    int lft = 0, rht = nums.size() - 1, res;
    while (lft <= rht) {
        int mid = (lft + rht) / 2;
        if (nums[mid] >= target) {
            rht = mid - 1;
            res = mid;
        }
        else lft = mid + 1;
    }
    return res;
}

int binarySearch_rht(const vector<int>& nums, int target) {
    int lft = 0, rht = nums.size() - 1, res;
    while (lft <= rht) {
        int mid = (lft + rht) / 2;
        if (nums[mid] <= target) {
            lft = mid + 1;
            res = mid;
        }
        else rht = mid - 1;
    }
    return res;
}

vector<int> searchRange(vector<int>& nums, int target) {
    if (nums.size() == 0) return { -1,-1 };
    int lft = binarySearch_lft(nums, target);
    int rht = binarySearch_rht(nums, target);
    if (lft < 0 || rht >= nums.size() || nums[lft] != target || nums[rht] != target) lft = rht = -1;
    return { lft,rht };
}

题号:4 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题

此题麻烦在边界问题很难处理，我们先设想任意一个旋转数组，可分为两个部分，x和y长度的两个有序子数组，任意选一个点，要么正好就是两个子数组交接处，要么在一个子数组中间，知道这个性质后有两种思路:

1. 先找分界点，也就是数组的最大/最小值
   1. 由于条件是数组已经旋转过，那么0索引必然是一个子数组开头，并且不是最小值，利用这点，不断找比0处元素更小的部分
   2. 找到后对某个区间二分
2. 不管分界点，对每个中点必然至少有一侧有序，可以常数复杂度观察是否在有序区间内，然后跳转
   1. 边界条件是mid在边界上如何判断，因此有序需要加一个左右边界相等的条件

bool is_sorted(const vector<int>& nums, int lft, int rht) {
    return lft ==rht || nums[lft] < nums[rht];
}

int search_rotate(vector<int>& nums, int target) {
    int lft = 0, rht = nums.size() - 1, mid;
    while (lft <= rht) {
        mid = (lft + rht) / 2;
        if (nums[mid] == target) return mid;
        if (is_sorted(nums, lft, mid)) {
            if (target >= nums[lft] && target <= nums[mid]) rht = mid - 1;
            else lft = mid + 1;
        }
        else {
            if (target >= nums[mid] && target <= nums[rht]) lft = mid + 1;
            else rht = mid - 1;
        }
    }
    return -1;
}

题号:5 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题

思路上一题说过，注意两个边界情况:

1. 如果数组旋转0，也就是没旋转，就不会触发对最小值的更改，需要将其默认值设为0索引元素
2. 对mid等于0索引的情况也应该右移(条件是严格升序，此时能等于0索引，说明lft=0,rht=1,只有这两个元素有可能更小，0是默认返回值，因此搜一下1)

int findMin(vector<int>& nums) {
    int lft = 0, rht = nums.size() - 1, mid, rotate_start = nums[0], min;
    while (lft <= rht) {
        mid = (lft + rht) / 2;
        if (rotate_start <= nums[mid]) lft = ++mid;
        else {
            min = nums[mid];
            rht = --mid;
        }
    }
    return min;
}

栈

题号:1 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合
2. 左括号必须以正确的顺序闭合
3. 每个右括号都有一个对应的相同类型的左括号

经典题，为了方便拓展可以用哈希表匹配括号

bool isValid(string s) {
    stack<char> st;
    set<char> se = { '(','{','[' };
    if (se.find(s[0]) == se.end()) return 0;
    unordered_map<char, char> ma = { {')','('},{']','['},{'}','{'} };
    for (char c : s) {
        if (se.find(c) != se.end()) st.push(c);//左括号直接入栈
        else {//c是右括号
            if (st.empty() || ma[c] != st.top()) return 0;
            else st.pop();
        }
    }
    return st.empty();
}

题号:2 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈

实现 MinStack 类:

• MinStack() 初始化堆栈对象
• void push(int val) 将元素val推入堆栈
• void pop() 删除堆栈顶部的元素
• int top() 获取堆栈顶部的元素
• int getMin() 获取堆栈中的最小元素

用一个辅助栈同步基础栈的出入栈操作，但每次存取的是基础栈当前状态的最小元素

class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

题号:3 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入

此题细节上非常麻烦，但框架很清晰，遍历字符串的过程中不断压栈，遇到]就取出来将k次字符串放入栈末尾，最后需要把栈内的所有字符串加起来
细节上，为了优化存取，对连续字符应该放到一个string存储，数字如果是多位的也需要放入一个多位string存储，此外c++字符串数组需要指定长度，如vec.push_back(string(1,char c)) ，将字符串转化为字面数字需要用stoi(来自string库)函数

string decodeString(string s) {
    string res;
    vector<string> vec;
    int i = 0, end = 0;
    string temp;
    while (i < s.size()) {
        temp.clear();
        if (isalpha(s[i])) {
            while (isalpha(s[i])) {
                temp.push_back(s[i]); ++i;
            }
            vec.emplace_back(temp);
        }
        else if (s[i] == '[') {
            vec.emplace_back(string(1, s[i]));
            ++i;
        }
        else if (isdigit(s[i])) {
            while (isdigit(s[i])) {
                temp.push_back(s[i]); ++i;
            }
            vec.emplace_back(temp);
        }
        else {//右括号
            while (1) {
                string ss = vec.back(); vec.pop_back();
                if (ss == "[") {
                    int times = stoi(vec.back());vec.pop_back();
                    string t;
                    for (int i = 0;i < times;++i) t += temp;
                    vec.emplace_back(t);break;
                }
                else temp.insert(0, ss);
            }
            ++i;
        }
    }
    for (int i = 1;i < vec.size();++i)vec[0] += vec[i];
    return vec[0];
}

题号:4 每日温度
定一个整数数组 temperatures ，表示每天的温度，返回一个数组 result ，其中 result[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替

1. 设置一个辅助数组，用于存储对应温度的最小索引，初始均为无穷大
   1. 反向遍历温度数组，对每个i，若有的话找到比其高的最低温度，并不断更新辅助数组里对应温度的索引
2. 单调栈:正向遍历温度列表，对于温度列表中的每个元素 temperatures[i]:
   1. 如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex]和当前温度temperatures[i]
   2. 如果temperatures[i]更高，则将prevIndex 移除，并将prevIndex对应的等待天数赋为i - prevIndex，否则i入栈
   3. 重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将i进栈

单调栈的性质是:栈底到栈顶序列是单调的，此题中是严格递减关系。为什么可以用单调栈？因为此题有索引递增顺序，符合栈的序列性，又要大小要求，符合单调性
每次匹配到一个较大元素，都是符合题意的首个更高温，因此可以出栈，每次匹配到一个较小元素，都说明这个元素和之前的元素都需要等一个更高温

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> res(n,0);
    vector<unsigned> temper(71, 0x7fffffff);//对i索引，表示30+i度温度出现的最小索引号
    for (int i = n - 1;i >= 0;--i) {
        unsigned warmer = 0x7fffffff;
        for (int t = temperatures[i] + 1; t <= 100; ++t) warmer = min(warmer, temper[t - 30]);
        if (warmer != 0x7fffffff) res[i] = warmer - i;
        temper[temperatures[i] - 30] = i;
    }
    return res;
}

vector<int> dailyTemperatures_stack(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> res(n);
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
            int previousIndex = s.top();
            res[previousIndex] = i - previousIndex;
            s.pop();
        }
        s.push(i);
    }
    return res;
}

堆

题号:1 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题
基础堆排序，用快排也行

int quickselect(vector<int> &nums, int l, int r, int k) {
    if (l == r)
        return nums[k];
    int partition = nums[l], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (nums[i] < partition);
        do j--; while (nums[j] > partition);
        if (i < j)
            swap(nums[i], nums[j]);
    }
    if (k <= j)return quickselect(nums, l, j, k);
    else return quickselect(nums, j + 1, r, k);
}

int findKthLargest_qsort(vector<int> &nums, int k) {
    int n = nums.size();
    return quickselect(nums, 0, n - 1, n - k);
}

void maxheap(vector<int>& heap, int parent, const int& heapsize) {
    int lft = (parent << 1) + 1, rht = (parent << 1) + 2;
    int max_one = (lft < heapsize && heap[lft] > heap[parent]) ? lft : parent;
    max_one = (rht < heapsize && heap[rht] > heap[max_one]) ? rht : max_one;
    if (max_one != parent) {
        swap(heap[parent], heap[max_one]);
        maxheap(heap, max_one, heapsize);
    }
}

void build_maxheap(vector<int>& heap, const int& heapsize) {
    for (int i = heapsize / 2 - 1; i >= 0; --i) {
        maxheap(heap, i, heapsize);
    }
}

int findKthLargest(vector<int>& nums, int k) {
    int heapsize = nums.size();
    build_maxheap(nums, heapsize);
    for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
        swap(nums[0], nums[i]);
        --heapsize;
        maxheap(nums, 0, heapsize);
    }
    return nums[0];
}

题号:2 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案

可以用一个哈希表存储<值，次数>对，然后维护一个k长度的最小堆，注意这里最小堆(优先队列的写法),首个参数是存储对象，第二个参数vector是存储形式，第三个参数是比较函数的函数类型
同样也可以用快排处理哈希表键值对组成的数组

bool cmp(pair<int, int>& m, pair<int, int>& n) {
    return m.second > n.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> occurrences;
    for (auto& v : nums) {
        occurrences[v]++;
    }
    // pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
    for (auto& [num, count] : occurrences) {
        if (q.size() == k) {
            if (q.top().second < count) {
                q.pop();
                q.emplace(num, count);
            }
        } else {
            q.emplace(num, count);
        }
    }
    vector<int> ret;
    while (!q.empty()) {
        ret.emplace_back(q.top().first);
        q.pop();
    }
    return ret;
}

void qsort(vector<pair<int, int>>& v, int start, int end, vector<int>& ret, int k) {
    int picked = rand() % (end - start + 1) + start;
    swap(v[picked], v[start]);

    int pivot = v[start].second;
    int index = start;
    for (int i = start + 1; i <= end; i++) {
        // 使用双指针把不小于基准值的元素放到左边，
        // 小于基准值的元素放到右边
        if (v[i].second >= pivot) {
            swap(v[index + 1], v[i]);
            index++;
        }
    }
    swap(v[start], v[index]);

    if (k <= index - start) {
        // 前 k 大的值在左侧的子数组里
        qsort(v, start, index - 1, ret, k);
    } else {
        // 前 k 大的值等于左侧的子数组全部元素
        // 加上右侧子数组中前 k - (index - start + 1) 大的值
        for (int i = start; i <= index; i++) {
            ret.push_back(v[i].first);
        }
        if (k > index - start + 1) {
            qsort(v, index + 1, end, ret, k - (index - start + 1));
        }
    }
}

vector<int> topKFrequent(vector<int>& nums, int k) {
    // 获取每个数字出现次数
    unordered_map<int, int> occurrences;
    for (auto& v: nums) {
        occurrences[v]++;
    }

    vector<pair<int, int>> values;
    for (auto& kv: occurrences) {
        values.push_back(kv);
    }
    vector<int> ret;
    qsort(values, 0, values.size() - 1, ret, k);
    return ret;
}

贪心

题号:1 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false

如果是dp做就用dp表示可达性然后遍历，但这题跳跃长度可选，因此与其维护dp数组，不如维护可以可以跳到的边界，一旦边界到达最右侧，就返回

bool canJump(vector<int>& nums) {
    int n = nums.size();
    int rightmost = 0;
    for (int i = 0; i < n; ++i) {
        if (i <= rightmost) {
            rightmost = max(rightmost, i + nums[i]);
            if (rightmost >= n - 1) return true;
        }
    }
    return false;
}

题号:2 跳跃游戏II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

设所处位置为i，可跳k步，对i来说每次的最优解是跳到一个j(i_{i+k范围)处，j+nums[j]是范围里i}i+k的最大值
也就是说，我们每次不仅维护一个最大范围，还要根据这个范围寻找一个下次最优解，每次跳到下次最优解时更新step

int jump(vector<int>& nums) {
    int maxPos = 0, n = nums.size(), end = 0, step = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (maxPos >= i) {
            maxPos = max(maxPos, i + nums[i]);
            if (i == end) {
                end = maxPos;
                ++step;
            }
        }
    }
    return step;
}

//更容易理解的版本
int jump2(vector<int>& nums) {
    if (nums.size()==1) return 0;
    int maxPos = 0, n = nums.size(), end = 0, step = 0, i = 0, max_index = 0;
    while (1) {
        maxPos = i + nums[i];
        if (maxPos >= n - 1) return ++step;//此时相当于可以跳到终点，需要先加一再返回
        for (int j = i;j <= maxPos;++j) {
            if (j + nums[j] > max_index+nums[max_index]) max_index = j;
        }
        i = max_index;maxPos = max_index + nums[max_index];
        step++;
    }
    return step;
}

题号:3 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s
返回一个表示每个字符串片段的长度的列表

由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。每次根据这个位置取片段，取如果取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。由于每次取的片段都是符合要求的最短的片段，因此得到的片段数也是最多的
例如，s第一个字符是a，我们必须把截止最后一个a的长度填进去，然后遍历这个子串，看里面有没有其他需要填进去的字母，例如满足a的条件需要长度3，第二个字符是b，b最后出现在s第四个字符，就需要长度再加一

1. 从左到右遍历字符串，遍历的同时维护当前片段的开始下标 start 和结束下标 end，初始时 start=end=0
2. 对于每个访问到的字母 c，得到当前字母的最后一次出现的下标位置 endc​，则当前片段的结束下标一定不会小于 endc​，因此令 end=max(end,endc​)
3. 当访问到下标 end 时，当前片段访问结束，当前片段的下标范围是 [start,end]，长度为 end−start+1，将当前片段的长度添加到返回值，然后令 start=end+1，继续寻找下一个片段
4. 重复上述过程，直到遍历完字符串

vector<int> partitionLabels(string s) {
    int last[26];
    int length = s.size();
    for (int i = 0; i < length; i++) last[s[i] - 'a'] = i;
    vector<int> partition;
    int start = 0, end = 0;
    for (int i = 0; i < length; i++) {
        end = max(end, last[s[i] - 'a']);
        if (i == end) {
            partition.push_back(end - start + 1);
            start = end + 1;
        }
    }
    return partition;
}

动态规划

斐波那契类型

题号:1 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

假设已经爬到了x级(x<=n)，上一个状态可能是x-1或x-2，因此可得f(n)=f(n-1)+f(n-2)，也就是斐波那契数列
这么一来只需要不断保留x-1和x-2项计算就行了，设置一个数组{结果，旧值，更旧值}，每次旧和更旧值相加存到结果值，下一轮的旧值是现在的结果，更旧值是现在的旧值,因此一一赋值

int climbStairs(int n) {
    if (n <= 2) return n;
    int steps = 2;
    vector<int> memory = { 0,2,1 };
    while (steps < n) {
        memory[0] = memory[1] + memory[2];
        memory[2] = memory[1];
        memory[1] = memory[0];
        steps++;
    }
    return memory[0];
}

题号:2 第 N 个泰波那契数
泰波那契序列(三个数之和版的斐波那契数)
给你整数 n，请返回第 n 个泰波那契数 Tn的值

int tribonacci(int n) {
    if (n <= 1) return n;
    else if (n == 2) return 1;
    vector<int> mem = { 0,1,1 ,0 };
    int i = 3;
    while (i <= n) {
        mem[0] = mem[1] + mem[2] + mem[3];
        mem[3] = mem[2];
        mem[2] = mem[1];
        mem[1] = mem[0];
        ++i;
    }
    return mem[0];
}

题号:3 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯
请你计算并返回达到楼梯顶部的最低花费

楼梯，或者说斐波那契问题的关键就是，第k项只依赖于k-1和k-2项，爬到k阶的最小花费取决于k-1,k-2的最小花费+对应cost;而之前的楼梯问题相当于代价相等

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size(),i = 2;
    vector<int> mem = { 0,0,0 };
    while (i <= n) {
        mem[0] = min(mem[1] + cost[i - 1], mem[2] + cost[i - 2]);
        mem[2] = mem[1];
        mem[1] = mem[0];++i;
    }
    return mem[0];
}

题号:4 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额

假设我们已经偷到k家，如果之前偷了k-2,可以偷这家，否则和偷k-1家情况一致，也就是k家情况的最佳收益取决于money(k-2)+num[k]与money(k-1)的最大值

int rob(const vector<int>& nums) {
    int n = nums.size(), i = 2;
    if (n == 1) return nums[0];
    vector<int> mem = { max(nums[0], nums[1]),nums[0],max(nums[0], nums[1]) };
    while (i < n) {
        mem[0] = max(mem[1] + nums[i], mem[2]);
        mem[1] = mem[2];
        mem[2] = mem[0];
        ++i;
    }
    return mem[0];
}

题号:5 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数

乍一看无从下手，因为我们可以任意选择索引处的数x，但选择后x-1和x+1都清零了，现在必然选择所有x是最优的，因此每次我们选的是一个数而不是索引
对一个选择集，我们会发现其可以表示成一系列相差大于1的数如1,3,5,8，对其排序可得到一个升序序列，没错，可以视为打家劫舍的一个变种，但逻辑更复杂一点
先从简单的情形讨论，如果数组是个连续整数序列，那就纯粹是打家劫舍问题，对大小顺序里k的数，可以抢k-1或者抢k与k-2
但如果有2以上的间隔呢，如1,3,4,6,8,此时我们发现抢1对之后的选择没有任何影响，准确地说，抢到k时，如果k-1这个数不存在，即k-1情况等价于上一个存在的树对应情况，，例如我们抢到3时，发现2不存在，那么3的最优解就是抢了3加上之前的最好情况 这么分析后，假设我们有一个实际存在值的数组，那么策略是:

1. 遍历到某个数k,设j是k的上一个数
   1. 如果k-1==j，按打家劫舍做，k = max(k-1 ,money(k) +(k-2))
   2. 如果k-1不存在，k=j+money(k)

实现细节有不少麻烦之处，这里用空间换易读性，存储不重复值的升序数组和对应哈希表的出现次数，方便之后调用

int deleteAndEarn(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    sort(nums.begin(), nums.end(), less<int>());
    int n = nums.size(), i = 2;
    unordered_map<int, int> um;
    vector<int> keys = { nums[0] };
    for (auto i : nums) {
        if (!um.count(i)) um[i] = 1;
        else ++um[i];
        if (i != keys.back()) keys.emplace_back(i);
    }
    if (keys.size() == 1) return keys[0] * um[keys[0]];

    int temp;//偷到第二家
    temp = ((keys[1] - 1) != keys[0]) ? keys[0] * um[keys[0]] + keys[1] * um[keys[1]] : max(keys[1] * um[keys[1]], keys[0] * um[keys[0]]);
    vector<int> mem = { temp,temp,keys[0] * um[keys[0]] };//{结果，偷到第二家，偷到第一家}
    while (i < keys.size()) {//进入时已经偷了2家或1家
        if ((keys[i] - 1) != keys[i - 1]) mem[0] = mem[1] + keys[i] * um[keys[i]];
        else mem[0] = max(mem[1], mem[2] + keys[i] * um[keys[i]]);
        mem[2] = mem[1];
        mem[1] = mem[0];
        ++i;
    }
    return mem[0];
}

矩阵

怀疑不太可能考，先略过这部分

题号:1 不同路径
一个机器人位于一个 m x n 网格的左上角 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角 问总共有多少条不同的路径？

f(i,j)=f(i−1,j)+f(i,j−1)

int uniquePaths(int m, int n) {
    vector<vector<int>> f(m, vector<int>(n,0));
    for (int i = 0; i < m; ++i) f[i][0] = 1;
    for (int j = 0; j < n; ++j) f[0][j] = 1;
    for (int i = 1; i < m; ++i) for (int j = 1; j < n; ++j) f[i][j] = f[i - 1][j] + f[i][j - 1];
    return f[m - 1][n - 1];
}

题号:2 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小
说明：每次只能向下或者向右移动一步

dp[i][j]表示从左上角出发到 (i,j) 位置的最小路径和,从左上到右下更新dp即可

1. 当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]
2. 当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]
3. 当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]

int minPathSum(vector<vector<int>>& grid) {
    if (grid.size() == 0 || grid[0].size() == 0) return 0;
    int m = grid.size(), n = grid[0].size();
    auto dp = vector < vector <int> > (m, vector <int> (n));
    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    return dp[m - 1][n - 1];
}

字符串

可分为编辑问题和比较问题，编辑问题由于可能需要一个无任何编辑的初始情况，更适合用长度作为表示问题的方式，0表示空字符串，m表示m长度的字符串(但依旧从0索引，即尾字符索引是m-1)

题号:1 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串

从大往小遍历，并存储最大索引和长度

void find_symmetry_helper(const string& s, vector<vector<uint8_t>>& sym_word, int i, int j, int& m, int& st) {
    if (i >= j || sym_word[i][j] == 2) return;
    if (sym_word[i][j] == 1) { m = max(j - i + 1, m);if (m == j - i + 1) st = i; return; }
    else {
        if (j - i == 1) sym_word[i][j] = s[i] == s[j];
        else {
            find_symmetry_helper(s, sym_word, i + 1, j - 1, m, st);
            sym_word[i][j] = (s[i] == s[j] && sym_word[i + 1][j - 1] == 1) ? 1 : 2;
        }
        if (sym_word[i][j] == 1) { m = max(j - i + 1, m);if (m == j - i + 1) st = i; }
    }
}

string longestPalindrome(string s) {
    int n = s.size(), max_len = 1, max_start = 0;
    if (n < 2) return s;
    vector<vector<uint8_t>> dp(n, vector<uint8_t>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int i = 0; i < n;++i) {
        for (int j = n - 1;j > i;--j) {
            if (j - i + 1 > max_len) find_symmetry_helper(s, dp, i, j, max_len, max_start);
        }
    }
    return s.substr(max_start, max_len);
}

题号:2 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用

对0-i索引的字符串，如果能被表示，则对每个词word,其词长wl:
如果0-(i-wl)的字符串能被表示，且(i-wl) - i的字符串等于word，那么它可以被表示

bool wordBreak(string s, vector<string>& wordDict) {
    vector<bool> dp(s.size()+1, false);
    dp[0] = true;
    for (int i=0; i<s.size()+1; ++i){
        for (auto word : wordDict){
            if (dp[i] = true) break;
            int word_len = word.size();
            if (dp[i-word_len] && word_len <= i && s.substr(i-word_len, word_len) == word ) dp[i] = true;
        }
    }
    return dp[s.size()];
}

题号:3 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列

dp[i][j]表示字符串 s 的下标范围[i,j]内的最长回文子序列的长度

1. 如果 s[i]=s[j]，则 dp[i][j]=dp[i+1][j−1]+2
2. 如果 s[i]!=s[j]，则 s[i] 和 s[j] 不可能同时作为同一个回文子序列的首尾，因此 dp[i][j]=max(dp[i+1][j],dp[i][j−1])

由这个递推公式得出，需要从内向外遍历，而起始点和i,j扩张方向则可以随意 d 下方使用i向左，j向右的方式，当然相反也行，只需要保证外层调用时内层已经准备好
由于每次固定一个i，j从i+1开始往右走，因此，每次都是调用已经计算过的值

int longestPalindromeSubseq(string s) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(n,0));
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        char c1 = s[i];
        for (int j = i + 1; j < n; j++) {
            char c2 = s[j];
            if (c1 == c2) dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}

题号:4 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数
你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

注意到，别问怎么注意的，问题中缩短较长字符串等价于加长较短字符串，因此我们统一为两种操作:删除和替换 当我们获得D[i][j-1]，D[i-1][j] 和 D[i-1][j-1]的值之后就可以计算出D[i][j]。D[i][j]为 A 的前 i 个字符和 B 的前 j 个字符编辑距离的子问题
即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符，那么D[i][j]最小可以为 D[i][j-1] + 1； D[i-1][j]为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题
即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符，那么D[i][j]最小可以为D[i-1][j] + 1；D[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题
即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么D[i][j]最小可以为D[i-1][j-1] + 1
特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，D[i][j]最小可以为D[i-1][j-1]。 那么我们可以写出如下的状态转移方程：

1. 若 A 和 B 的最后一个字母相同： D[i][j]​=min(D[i][j−1]+1,D[i−1][j]+1,D[i−1][j−1])=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1]−1)​
2. 若 A 和 B 的最后一个字母不同： D[i][j]=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1])

int minDistance(string word1, string word2) {
    int n = word1.length();
    int m = word2.length();
    if (n * m == 0) return n + m;
    vector<vector<int>> dp(n + 1, vector<int>(m + 1,0));
    for (int i = 0; i < n + 1; i++) dp[i][0] = i;
    for (int j = 0; j < m + 1; j++) dp[0][j] = j;
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            int left = dp[i - 1][j] + 1;
            int down = dp[i][j - 1] + 1;
            int left_down = dp[i - 1][j - 1];
            if (word1[i - 1] != word2[j - 1]) left_down += 1;
            dp[i][j] = min(left, min(down, left_down));

        }
    }
    return dp[n][m];
}

题号:5 两个字符串的最小ASCII删除和
给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和

策略:需要删掉删除和最小的字符串，考虑什么情况是没必要删的，如果s1是s2的一个子序列，那么s2里s1的字符就不需要删，也就是说这个问题其实是寻找子序列配合一个删除和约束
如何寻找子序列呢？我们知道就是先比末尾字符，然后根据情况dp，此题加了一个删除和约束，那就往最小化删除和的方向dp
当然反过来想，也可以找字符和最大的公共子序列，然后用两个字符串的总字符和减去它的两倍

dp[i][j]表示s1直到i的子串和s2直到j的子串最小删除和

1. 初始条件如果另一方不存在，就等于存在一方字符值
2. 固定一个i增加j
   1. 如果对应两个字符相等，不用删除就等价于(i-1,j-1)子问题
   2. 否则删掉一个删除和最小的，等价于对应删掉字符的值加删掉后对应子问题的删除和

int minimumDeleteSum(string s1, string s2) {
    int m = s1.size(); int n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) dp[i][0] = dp[i - 1][0] + s1[i - 1];
    for (int j = 1; j <= n; ++j) dp[0][j] = dp[0][j - 1] + s2[j - 1];
    //上行结束后，所有有一方长度为0的子问题都解决了
    for (int i = 1; i <= m; i++) {
        char c1 = s1[i - 1];
        for (int j = 1; j <= n; j++) {
            char c2 = s2[j - 1];
            if (c1 == c2) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
        }
    }
    return dp[m][n];
}

最长递增子序列

题号:1 最长递增子序列
递增子序列有以下性质:

1. 递增，比序列尾部元素大就可以扩张子序列
2. 不知道具体有什么元素，或者说其尾部索引

因此可以dp[i]表示到i为止的最长子序列尾部，这样一来每次对j索引更新时就需要遍历查找之前的最长子序列，具体地说找尾部元素比j小的子序列中最长的一个
优化:考虑让每次可以新加的数尽可能小，这样至少不会是更差的选择:维护一个数组d[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]，d数组有递增性质

设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到nums[i]时：

1. 如果nums[i]>d[len] ，则直接加入到 d 数组末尾，并更新len=len+1
2. 否则，在 d 数组中二分查找，找到第一个比nums[i]小的数d[k]，并更新d[k+1]=nums[i]

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size(),max_num;
    if (n == 0) return 0;
    vector<int> dp(n, 0);
    for (int i = 0; i < n; ++i) {
        dp[i] = 1;
        for (int j = 0; j < i; ++j) if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
    }
    for (auto i: dp) max_num=max(i,max_num);
    return max_num;
}

int lengthOfLIS_bin(vector<int>& nums) {
    int len = 1, n = (int)nums.size();
    if (n == 0) return 0;
    vector<int> d(n + 1, 0);
    d[len] = nums[0];
    for (int i = 1; i < n; ++i) {
        if (nums[i] > d[len]) d[++len] = nums[i];
        else {
            int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (d[mid] < nums[i]) {
                    pos = mid;
                    l = mid + 1;
                } else r = mid - 1;
            }
            d[pos + 1] = nums[i];
        }
    }
    return len;
}

题号:2 最长递增子序列的个数
给定一个未排序的整数数组 nums， 返回最长递增子序列的个数
注意 这个数列必须是 严格 递增的

暴力法就是上题基础上加个计数，非暴力法，嗯，不提了

int findNumberOfLIS(vector<int> &nums) {
    int n = nums.size(), maxLen = 0, res = 0;
    vector<int> dp(n,0), cnt(n,0);
    for (int i = 0; i < n; ++i) {
        dp[i] = 1; cnt[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j]; // 重置计数
                } 
                else if (dp[j] + 1 == dp[i]) cnt[i] += cnt[j];
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            res = cnt[i]; // 重置计数
        } 
        else if (dp[i] == maxLen) res += cnt[i];
    }
    return res;
}

题号:3 最长数对链
给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链
找出并返回能够形成的 最长数对链的长度
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造

类似上题和上上题，定义dp[i]为以pairs[i]为结尾的最长数对链的长度。计算dp[i]时，遍历所有小于i的索引j，dp[i]赋值为索引处的pair可以添加数对的dp最大值+1。这种动态规划的思路要求计算dp[i]时，所有潜在的dp[j]已经计算完成，可以先将pairs进行排序来满足这一要求。初始化时，dp需要全部赋值为1

二分:用一个数组arr来记录当前最优情况，arr[i]就表示长度为 i+1 的数对链的末尾可以取得的最小值，遇到一个新数对时，先用二分查找得到这个数对可以放置的位置，再更新arr
贪心:要挑选最长数对链的第一个数对时，最优的选择是挑选右边界最小的，这样能给挑选后续的数对留下更多的空间。挑完第一个数对后，要挑第二个数对时，也是按照相同的思路，是在剩下的数对中，左边界满足题意的条件下，挑选右边界最小的。按照这样的思路，可以先将输入按照右边界排序，然后不停地判断左边界是否能满足大于前一个数对的右边界即可

int findLongestChain(vector<vector<int>>& pairs) {
    int n = pairs.size();
    sort(pairs.begin(), pairs.end());
    vector<int> dp(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (pairs[i][0] > pairs[j][1]) dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    return dp[n - 1];
}

int findLongestChain_binary(vector<vector<int>>& pairs) {
    sort(pairs.begin(), pairs.end());
    vector<int> arr;
    for (auto p : pairs) {
        int x = p[0], y = p[1];
        if (arr.size() == 0 || x > arr.back()) arr.emplace_back(y);
        else {
            int idx = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
            arr[idx] = min(arr[idx], y);
        }
    }
    return arr.size();
}

int findLongestChain_greed(vector<vector<int>>& pairs) {
    int curr = INT_MIN, res = 0;
    sort(pairs.begin(), pairs.end(), [](const vector<int> &a, const vector<int> &b) {
        return a[1] < b[1];
    });
    for (auto &p : pairs) {
        if (curr < p[0]) {
            curr = p[1];
            res++;
        }
    }
    return res;
}

题号:4 最长定差子序列
给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference
子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列

dp[i]表示以arr[i]为结尾的最长的等差子序列的长度，那么对任意v,其驱动元素如果存在必然是v-diff,如果存在v-difference元素，遍历到v时必然有个非0的d[v-diff]存在，其加一后就是dp[v]，由于哈希表默认值是0，因此不存在也不影响
结果就是dp数组最大值

int longestSubsequence(vector<int> &arr, int difference) {
    int res = 0;
    unordered_map<int, int> dp;
    for (int v: arr) {
        dp[v] = dp[v - difference] + 1;
        res = max(res, dp[v]);
    }
    return res;
}

题号:5 最长等差数列
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的

容易理解的方法:
dp[i][d]表示以nums[i]结尾且公差为d的数列长度，即dp[i]存储一个以i元素结尾可以存在的不同d等差数列的哈希表
对于nums[i]，可以枚举它的前一项nums[j]，0<= j < i，有了前一项nums[j]，其实公差就确定了d=nums[i]-nums[j]

1. 如果nums[j]可以是某个公差为d的数列的最后一项，nums[i]就可以接在后面形成更长的等差数列，状态转移方程为dp[i][d]=dp[j][d]+1
2. 否则它两就形成公差为d的等差数列前两项，状态转移方程为dp[i][d]=2

int longestArithSeqLength_best(vector<int>& nums) {
    auto [minit, maxit] = minmax_element(nums.begin(), nums.end());
    int diff = *maxit - *minit;
    int res = 1;
    for (int d = -diff; d <= diff; ++d) {
        vector<int> f(*maxit + 1, -1);
        for (int num: nums) {
            if (int prev = num - d; prev >= *minit && prev <= *maxit && f[prev] != -1) {
                f[num] = max(f[num], f[prev] + 1);
                res = max(res, f[num]);
            }
            f[num] = max(f[num], 1);
        }
    }
    return res;
}


int longestArithSeqLength(vector<int>& nums) {
    int n = nums.size();
    int res = 1;
    unordered_map<int, int> dp[n];
    for(int i = -500; i <= 500; i++) dp[0][i] = 1;//头元素可以视为任意差的数列开头
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {//对i之前的元素j
            int d = nums[i] - nums[j];//i与j的差
            if(dp[j].count(d)) dp[i][d] = dp[j][d] + 1;//如果j可以加在i的后面形成等差数列，其数列长度加一
            else dp[i][d] = 2;//否则生成一个新数列
            res = max(res, dp[i][d]);
        }
    }
    return res;
}

最长公共子序列

题号:1 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列

过于经典，不多说了

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; i++) {
        char c1 = text1.at(i - 1);
        for (int j = 1; j <= n; j++) {
            char c2 = text2.at(j - 1);
            if (c1 == c2) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

int longestCommonSubsequence_better(string text1, string text2) {//dp[j]等于text2中以text2[j]为末尾元素的子序列和text1的[0,i-1]子串的最长公共子序列的长度
    vector<int> dp(text2.size(), 0);
    for (int i = 0; i < text1.size(); ++i) {
        int maxlen = 0;
        for (int j = 0; j < text2.size(); ++j) {
            int newlen = max(maxlen, dp[j]);
            if (text1[i] == text2[j]) dp[j] = maxlen + 1;
            maxlen = newlen;
        }
    }
    return *max_element(dp.cbegin(), dp.cend());
}

题号:2 不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

• nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线
以这种方法绘制线条，并返回可以绘制的最大连线数

对每根线来说，两个索引都需要严格大于各自边的前方任意索引，并且对应元素要相等，这就是什么呢？每次，就是公共子序列，so……

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; i++) {
        int num1 = nums1[i - 1];
        for (int j = 1; j <= n; j++) {
            int num2 = nums2[j - 1];
            if (num1 == num2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

买卖股票

题号:1 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

因为最多只能卖一股，到第i天，我们的最优解是买入目前为止的最低价，到目前为止的最高价全卖出，因此遍历中记录迄今为止的最低价格，每次考虑此次卖出的利润是否比之前更好
如果用dp就是dp[i]= max(dp[i-1], prices[i]-minprices[i-1])，但我们

int maxProfit(vector<int>& prices) {
    int minprice = 0x7fffffff, maxprofit = 0;
    for (int price: prices) {
        maxprofit = max(maxprofit, price - minprice);
        minprice = min(price, minprice);
    }
    return maxprofit;
}

题号:2 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售
返回 你能获得的 最大 利润

定义状态dp[i][0]表示第 i 天交易完后手里没有股票的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0 开始）
可得:

1. dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]}
2. dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}

由于这个状态转移符合马尔科夫假设，因此只需要存储前一天状态dp[i−1][0]和dp[i−1][1]

贪心:我们只考虑利润，利润是什么？是一个子区间的右左差，由于每天可以随意买入卖出，因此i天买入，j天卖出的区间差等价于{i,i+1}……{j-1,j}的区间差之和，也就是说只要有赚头，我们当天买，第二天卖，加起来也是最优解
这样一来就简单了，我们沿着所有长度为2的区间滚过去，有利润就买入卖出，加起来就是最大利润，实际上这就是获取最大利润买入卖出次数最大的一种方式

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int dp[n][2];
    dp[0][0] = 0, dp[0][1] = -prices[0];
    for (int i = 1; i < n; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        /*
        int newDp0 = max(dp0, dp1 + prices[i]);
        int newDp1 = max(dp1, dp0 - prices[i]);
        dp0 = newDp0;
        dp1 = newDp1;
        */
    }
    return dp[n - 1][0];
}

int maxProfit_greed(vector<int>& prices) {   
    int res = 0;
    int n = prices.size();
    for (int i = 1; i < n; ++i) res += max(0, prices[i] - prices[i - 1]);
    return res;
}

动态规划树

题号:1 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数

定义:

• G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数
• F(i,n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数 (1≤i≤n)

则:$ G(n)=_{i=1}^{n}F(i,n) $
选定一个根节点后，其左右子树的结构相互独立互不影响，因此根为 i 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积
则
(其实这也是个卡特兰数问题)

具体来说，由于我们找的是个数，只要满足搜索树要求(中序遍历是升序数组)，值毫无影响，因此对任意i问题，可以随意划分根节点并转换成左右子树各自数量相乘，不同根节点的左右子树乘积就是目标值，例如我们找根为k(k<i)时左右积，左边是0-k,右边是k-i,值不影响形状数量，左边数量就是i'=k时的子问题，右边数量就是i'=i-k时的子问题

$ F(i,n)=G(i-1)G(n-i) $
$ G(n)=_{i=1}^{n}G(i-1)G(n-i) $

优化:鉴于一些乘积会重复取用，或许可以用一个乘积数组的空间换时间

int numTrees(int n) {
    vector<int> G(n + 1, 0);
    G[0] = 1; G[1] = 1;
    for (int i = 2; i <= n; ++i) 
        for (int j = 1; j <= i; ++j) G[i] += G[j - 1] * G[i - j];
    }
    return G[n];
}

题号:2 不同的二叉搜索树 II
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案

与上一题不同的是需要返回生成的树，也就是要把数组G换成树组，且需要考虑不同的值，因此对相同形状的不同取值也要重新生成数，没有存储子问题的必要了，每次要调用就先生成
如果想用空间表达这个问题，那么G[st][ed]表示st-ed自然数序列能生成的不同bst集合，其可以通过不断选取st-ed之间的一个值i作为根节点其左子树集合是G[st][i-1],右子树集合是G[i+1][end]，两者与i这个根节点的所有组合则是所求
优化:取值范围相同的二叉树集合也可以被复用,或许可以用两个索引值的哈希表存储这些树的集合

vector<TreeNode*> generateTrees(int start, int end) {
    if (start > end) return { nullptr };
    vector<TreeNode*> allTrees;
    // 枚举可行根节点
    for (int i = start; i <= end; i++) {
        // 获得所有可行的左子树集合
        vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
        // 获得所有可行的右子树集合
        vector<TreeNode*> rightTrees = generateTrees(i + 1, end);
        // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
        for (auto& left : leftTrees) for (auto& right : rightTrees) {
                TreeNode* currTree = new TreeNode(i);
                currTree->left = left;
                currTree->right = right;
                allTrees.emplace_back(currTree);
        }
    }
    return allTrees;
}

vector<TreeNode*> generateTrees(int n) {
    if (!n) return {};
    return generateTrees(1, n);
}

题号:3 打家劫舍 III
地区只有一个入口，我们称之为 root
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额

用 f(o) 表示选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和
g(o) 表示不选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和
l 和 r 代表 o 的左右孩子

抢了o就不能抢它的孩子，收益是不抢两个孩子的情况和;不抢o对左右孩子选取一个最好情况相加
优化:对于每个节点，我们只关心它的孩子节点们抢了和没抢的分别状况。设计一个结构，表示某个节点的 f 和 g 值，在每次递归返回的时候，都把这个点对应的 f 和 g 返回给上一级调用

unordered_map <TreeNode*, int> f, g;

void dfs1(TreeNode* node) {
    if (!node) return;
    dfs(node->left);
    dfs(node->right);
    f[node] = node->val + g[node->left] + g[node->right];
    g[node] = max(f[node->left], g[node->left]) + max(f[node->right], g[node->right]);
}

int rob1(TreeNode* root) {
    dfs(root);
    return max(f[root], g[root]);
}

struct SubtreeStatus {
    int selected;
    int notSelected;
};

SubtreeStatus dfs2(TreeNode* node) {
        if (!node) return {0, 0};
        auto l = dfs(node->left);
        auto r = dfs(node->right);
        int selected = node->val + l.notSelected + r.notSelected;
        int notSelected = max(l.selected, l.notSelected) + max(r.selected, r.notSelected);
        return {selected, notSelected};
    }

int rob2(TreeNode* root) {
        auto rootStatus = dfs(root);
        return max(rootStatus.selected, rootStatus.notSelected);
    }
}

背包问题

题号:1 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是

f[i]表示最少需要多少个数的平方来表示整数i，有两种可能:

1. i本身是完全平方数，返回1
2. 存在一个完全平方数k,存在非0的f[i-k]

如果第一种可能，就是k=i的特例,f[i]=f[0]+1=1，因此不需要额外判断
遍历i不断找最小的f[i-k]就行了，由于i-k+k=i,因此找到后+1就是i的最优解
极端情况下，由于1也是完全平方数,i超过一个可以表示数的部分总可以用1补上

int numSquares(int n) {
    vector<int> f(n + 1,0);
    for (int i = 1; i <= n; i++) {
        int min_num = INT_MAX;
        for (int j = 1; j * j <= i; j++) min_num = min(min_num, f[i - j * j]);
        f[i] = min_num + 1;
    }
    return f[n];
}

题号:2 零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0
假设每一种面额的硬币有无限个
题目数据保证结果符合 32 位带符号整数

dp[i]表示金额之和等于i的硬币组合数，目标是求dp[amount]，对每个i，如果存在一个硬币coin,dp[i-coin]不为0，那么就可以得到对应dp[i-coin]的组合数
为了避免重复计算同一个组合，我们用一个外层循环固定每次用的面值，例如面值有1,2,5，那么我们先用1解决所有找零问题，固定到2时我们已经知道只用1的找零方案数了，然后我们考虑增加一些用2找零的子情况，也就是用到两个1的方案都可以加个2的情况，固定到5时也类似
由于每次添加一个之前没有考虑的面值，因此不会重复

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1), valid(amount + 1);
    dp[0] = 1; valid[0] = 1;
    for (int& coin : coins) for (int i = coin; i <= amount; i++) valid[i] |= valid[i - coin];//如果存在一种方式使得 valid[i] 为 1，就将其标记为可行
    if (!valid[amount]) return 0;
    for (int& coin : coins) for (int i = coin; i <= amount; i++) dp[i] += dp[i - coin];  
    return dp[amount];
}

题号:3 组合总和 Ⅳ
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数
题目数据保证答案符合 32 位整数范围
请注意，顺序不同的序列被视作不同的组合

本题与上题不同的是，要计算排列数而不是组合数，我们需要严格从头到尾构造，对任意i，如果可以加num得到一个和为i的排列，就加进去
以及，这题闲的没事干又放一个超大用例，dp数组一定得用size_t(unsigned long long),无语

int combinationSum4(vector<int>& nums, int target) {
    vector<size_t> dp(target + 1);
    dp[0] = 1;
    for (int i = 1; i <= target; i++) 
        for (int& num : nums) 
            if (i >= num) dp[i] += dp[i - num];
    return dp[target];
}

一维问题

题号:1 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积
测试用例的答案是一个 32位 整数

维护一个 fmin​(i)，它表示以第 i 个元素结尾的乘积最小子数组的乘积，由于乘法要考虑正负性，我们需要考虑之前的最小负数和最大正数，由于还可能是0，因此有可能不乘是最优解

$\begin{array}{l}{{f_{\mathrm{max}}(i)=\operatorname*{{max}_{i=1}^n}\{f_{\mathrm{max}}(i-1)\times a_{i},\,f_{\mathrm{min}}(i-1)\times a_{i},\,a_{i}\}}}\\ {{{}}}\\ {{f_{\mathrm{min}}(i)=\operatorname*{min}_{i=1}^n\{f_{\mathrm{max}}(i-1)\times a_{i},\,f_{\mathrm{min}}(i-1)\times a_{i},\,a_{i}\}}}\end{array}$

也就是说，其实只要维护一个最小值和一个最大值

int maxProduct(vector<int>& nums) {
    long maxF = nums[0], minF = nums[0], ans = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        long mx = maxF, mn = minF;
        maxF = max(mx * nums[i], max((long)nums[i], mn * nums[i]));
        minF = min(mn * nums[i], min((long)nums[i], mx * nums[i]));
        if(minF<INT_MIN) minF=nums[i];
        ans = max(maxF, ans);
    }
    return ans;
}

题号:2 分割等和子集
给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

dp[i][j]表示从数组的[0,i]下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j。初始时，dp 中的全部元素都是 false

• dp[i][0]=true
• dp[0][nums[0]]=true

过程中规则:

• 如果j≥nums[i]，则对于当前的数字nums[i]，可以选取也可以不选取，两种情况只要有一个为 true，就有dp[i][j]=true
  • 如果不选取nums[i]，则 dp[i][j]=dp[i−1][j]
  • 如果选取nums[i]，则 dp[i][j]=dp[i−1][j−nums[i]]
• 如果j<nums[i]，则在选取的数字的和等于j的情况下无法选取当前的数字nums[i]，因此有dp[i][j]=dp[i−1][j]

在计算 dp 的过程中，每一行的 dp 值都只与上一行的 dp 值有关，因此只需要一个一维数组即可将空间复杂度降到 O(target)。此时的转移方程为：\(dp[j]=dp[j]\mid dp[j-n u m s[i]]\)
第二层的循环我们需要从大到小计算，因为如果我们从小到大更新 dp 值，那么在计算 dp[j] 值的时候，dp[j−nums[i]]已经是被更新过的状态，不再是上一行的 dp 值

bool canPartition(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return false;
    int sum = accumulate(nums.begin(), nums.end(), 0);
    int maxNum = *max_element(nums.begin(), nums.end());
    if (sum & 1) return false;
    int target = sum / 2;
    if (maxNum > target) return false;
    vector<vector<int>> dp(n, vector<int>(target + 1, 0));
    for (int i = 0; i < n; i++) dp[i][0] = true;
    dp[0][nums[0]] = true;
    for (int i = 1; i < n; i++) {
        int num = nums[i];
        for (int j = 1; j <= target; j++) {
            if (j >= num) dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
            else dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[n - 1][target];
}

bool canPartition_better(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return false;
    int sum = 0, maxNum = 0;
    for (auto& num : nums) {
        sum += num;
        maxNum = max(maxNum, num);
    }
    if (sum & 1) return false;
    int target = sum / 2;
    if (maxNum > target) return false;
    vector<int> dp(target + 1, 0);
    dp[0] = true;
    for (int i = 0; i < n; i++) {
        int num = nums[i];
        for (int j = target; j >= num; --j) dp[j] |= dp[j - num];
    }
    return dp[target];
}

题号:3 解决智力问题
给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri]
这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题0开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作

• 比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]]：
  • 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2
  • 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3

请你返回这场考试里你能获得的 最高 分数

从无后效性的角度考虑动态规划「状态」的定义。对于每一道题目，解决与否会影响到后面一定数量题目的结果，但不会影响到前面题目的解决。因此我们可以考虑从反方向定义「状态」，即考虑解决每道题本身及以后的题目可以获得的最高分数
用dp[i]来表示解决第 i 道题目及以后的题目可以获得的最高分数。同时，我们从后往前遍历题目，并更新 dp 数组

1. 不解决第 i 道题目，此时 dp[i]=dp[i+1]
2. 解决第 i 道题目，我们只能解决下标大于i+brainpower[i]的题目，而此时根据 dp 数组的定义，解决这些题目的最高分数为 dp[i+brainpower[i]+1]（当 i≥n 的情况下，我们认为 dp[i]=0）。因此，我们有：

\(d p[i]=\operatorname*{max}(d p[i+1],p o i n t{s[i]}+d p[\operatorname*{min}(n,i+b r a i n p o w e r[i]+1)]).\)

预留dp[n]=0用来表示没有做任何题目的分数，则:\(dp[i]=\operatorname*{max}(dp[i+1],p o i n t s[i]+dp[\operatorname*{min}(n,i+b r a i n p o w e r[i]+1)]).\)

long long mostPoints(vector<vector<int>>& questions) {
    int n = questions.size();
    vector<long long> dp(n + 1);   // 解决每道题及以后题目的最高分数
    for (int i = n - 1; i >= 0; --i) dp[i] = max(dp[i + 1], questions[i][0] + dp[min(n, i + questions[i][1] + 1)]);
    return dp[0];
}

题号:4 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1
你可以认为每种硬币的数量是无限的

令F(S)为组成金额 S 所需的最少硬币数量，如果存在一个硬盘面额c,f(s-c)存在，则f(s)=f(s-c)+1
那么通过递归不断从小到大遍历寻找就行了，此外还需要一个数组用于记忆化
迭代法的情况下，从1开始，每个s都是对所有硬币面额c找一个最优s-c的情况再加一

vector<int> count;
int dp(vector<int>& coins, int rem) {
    if (rem < 0) return -1;
    if (rem == 0) return 0;//说明找完了
    if (count[rem - 1] != 0) return count[rem - 1];
    int Min = INT_MAX;
    for (int coin:coins) {
        int res = dp(coins, rem - coin);//如果是-1则找不了，0及以上说明有解
        if (res >= 0 && res < Min) Min = res + 1;
    }
    count[rem - 1] = Min == INT_MAX ? -1 : Min;
    return count[rem - 1];
}

int coinChange(vector<int>& coins, int amount) {
    if (amount < 1) return 0;
    count.resize(amount);
    return dp(coins, amount);
}

int coinChange_dp(vector<int>& coins, int amount) {
    int Max = amount + 1;
    vector<int> dp(amount + 1, Max);
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) 
        for (int coin: coins) 
            if (coin <= i) dp[i] = min(dp[i], dp[i - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

题号:5 统计构造好字符串的方案数
给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

• 将 '0' 在字符串末尾添加 zero 次
• 将 '1' 在字符串末尾添加 one 次

以上操作可以执行任意次
如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串
请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 10 + 7 取余 后返回

int countGoodStrings(int low, int high, int zero, int one) {
    const int MOD = 1000000007;
    vector<int> memo(high + 1, -1); // -1 表示没有计算过
    auto dfs = [&](auto&& dfs, int i) -> int {
        if (i < 0) return 0;
        if (i == 0) return 1;
        int& res = memo[i]; // 注意这里是引用
        if (res != -1)  // 之前计算过
            return res;
        return res = (dfs(dfs, i - zero) + dfs(dfs, i - one)) % MOD;
    };
    int res = 0;
    for (int i = low; i <= high; i++) res = (res + dfs(dfs, i)) % MOD;
    return res;
}

题号:6 解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ："1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'
然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）
例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1, 1, 10, 6)
• "KJF" ，将消息分组为 (11, 10, 6)
• 消息不能分组为 (1, 11, 06) ，因为 "06" 不是一个合法编码（只有 "6" 是合法的）

注意，可能存在无法解码的字符串
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串，返回 0
题目数据保证答案肯定是一个 32 位 的整数

1. 当前字符为 0，和它前一个的组合编码不合法，则整个编码不可被解码，返回 0 即可，比如遇到了 00，60等
2. 当前字符为 0，和它前一个的组合编码合法，则只能将当前字符 0 和它的前一个字符“绑定”为“一个字符”，比如遇到了 10，20等（实际上只能是这两种情况）
3. 当前字符不为 0，和它前一个的组合编码不合法，则只能将当前字符看做一个单独的编码，比如遇到了 01，94等
4. 当前字符不为 0，和它前一个的组合编码合法，则可以将当前字符看做是一个单独的编码，也可以和它的前一个字符绑定，比如遇到了 11，24等，只有这种情况下有两种分叉

int numDecodings(string s) {
    if (s[0] == '0') return 0;
    int n = s.length();
    vector<int> dp(n + 1);
    dp[0] = dp[1] = 1;
    for (int i = 2, x = 0; i <= n; i++) {
        x = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
        if (s[i - 1] == '0') {
            if (x == 0 || x > 26) return 0;
            dp[i] = dp[i - 2];
        }
        else {
            if (x > 26 || x < 10) dp[i] = dp[i - 1];
            else dp[i] = dp[i - 1] + dp[i - 2];
        }
    }
    return dp[n];
}

题号:7 最低票价
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数
火车票有 三种不同的销售方式 ：

• 一张 为期一天 的通行证售价为 costs[0] 美元
• 一张 为期七天 的通行证售价为 costs[1] 美元
• 一张 为期三十天 的通行证售价为 costs[2] 美元

通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天
返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费

dp[i]表示第i天旅游的情况下，[1,i]这段日子的最小花费。在这个定义下，答案就应该是dp[days.back()]
首先没开始的时候肯定不花钱，dp[0]=0。令j=0指向数组days的首元素，如果第i天不旅游，状态转移方程即为dp[i]=dp[i−1]
如果i=days[j]，那为了保证第i天旅游，有三种选择策略。状态转移方程为dp[i]=min(dp[max(0,i−1)]+costs[0],dp[max(0,i−7)]+costs[1],dp[max(0,i−30)]+costs[2])，分别表示选择1、7、30天有效期的策略，选择最小的转移，转移完记得让j右移 事实上，当j≥n（n为days的长度）时就可以停止DP过程了，因为最后一个需要旅行的日子已经安排完了

int mincostTickets(vector<int>& days, vector<int>& costs) {
    vector<int> dp(366,0x3f);
    int n = days.size();
    dp[0] = 0;
    for(int i = 1, j = 0; i <= 365 && j < n; i++) {
        dp[i] = dp[i - 1];
        if(i == days[j]) {
            dp[i] = dp[max(0, i - 1)] + costs[0];
            dp[i] = min(dp[i], dp[max(0, i - 7)] + costs[1]);
            dp[i] = min(dp[i], dp[max(0, i - 30)] + costs[2]);
            j++;
        }
    }
    return dp[days.back()];
}

技巧

题号:1 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
如果不考虑时间复杂度和空间复杂度的限制，这道题有很多种解法:

• 使用集合存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字
• 使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字
• 使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字

但是常数空间线性时间的解法呢？注意到(别问怎么注意到的),任意偶数个相同的数异或运算都是0，而0和任意奇数个相同的数异或运算都是那个奇数的数，因此所有数异或就能得到答案

int singleNumber(vector<int>& nums) {
    int temp =0;
    for (int i: nums) temp ^=i;
    return temp;
}

cpp位运算:

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
|	或	两个位都为0时，结果才为0
^	异或	两个位相同为0，相异为1
~	取反	0变1，1变0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

题号:2 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素
你可以假设数组是非空的，并且给定的数组总是存在多数元素

1. 最简单的做法是哈希表，不赘述
   
2. 其次是排序，比较排序无法线性复杂度，但如果堆排可以常数空间
3. 如果将 nums 分成两部分，那么 a 必定是至少一部分的众数,可以使用分治法，向上合并时，如果两侧众数不同需要遍历算出正确的众数
4. Boyer-Moore 算法:
   1. 维护一个候选众数candidate和它出现的次数count初始时candidate可以为任意值，count为0；
   2. 遍历数组nums中的所有元素，对于每个元素x，在判断x之前，如果count的值为0，我们先将x的值赋予candidate，判断x：
      1. 如果x与candidate相等，那么计数器count的值增加1
      2. 如果x与candidate不等，那么计数器count的值减少1
   3. 在遍历完成后，candidate即为整个数组的众数

看起来很抽象？可以这么想，对真正的众数来说，其他数加在一起和众数相消，最后剩下的也只有众数；并且对任意对数的相消之后，这个性质都成立.为什么呢？设众数为x，非众数统称为y1-yk,不同的两个数能相消，假设y系数团结起来全部和众数想消，众数也会赢，如果y系数发生内斗相消，众数反而赢得更多，因此只要不断相消，众数就会赢到最后
在这个算法中，candidate就是下次相消操作的被挑战者，极端情况下candidate从始至终是众数，其count也会严格大于0，而对其他candidate，再怎么相消也赢不过众数
形象地说，可以称为相杀算法

int count_in_range(vector<int>& nums, int target, int lo, int hi) {
    int count = 0;
    for (int i = lo; i <= hi; ++i)
        if (nums[i] == target) ++count;
    return count;
}
int majority_element_rec(vector<int>& nums, int lo, int hi) {
    if (lo == hi) return nums[lo];
    int mid = (lo + hi) / 2;
    int left_majority = majority_element_rec(nums, lo, mid);
    int right_majority = majority_element_rec(nums, mid + 1, hi);
    if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2) return left_majority;
    if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2) return right_majority;
    return -1;
}
int majorityElement_div(vector<int>& nums) {
    return majority_element_rec(nums, 0, nums.size() - 1);
}


int majorityElement_vote(vector<int>& nums) {
    int candidate = -1;
    int count = 0;
    for (int num : nums) {
        if (num == candidate) ++count;
        else if (--count < 0) {
            candidate = num;
            count = 1;
        }
    }
    return candidate;
}

题号:3 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色
必须在不使用库内置的 sort 函数的情况下解决这个问题

本题是经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出
很容易想到可以像快排一样用一个枢纽(此题里存索引就可以)划分两个部分不断交换，但既然有三个颜色，那就需要两个分界点
这样一来有个问题，假设0-i是0部分，(i+1)-j是1部分，长度都不为0，那么0部分想拓展就需要挤占1部分，此时交换i+1(j部分开头)和当前索引v后，需要再把v和j+1交换
下方代码使用准确界限，即p0,p1指向0，1区最后一个元素，初始为-1,极端情况下全一数组，p1也会始终和i同步更新,p1+1<=i，因此不会越界

void sortColors(vector<int>& nums) {
    int n = nums.size();
    int p0 = -1, p1 = -1;
    for (int i = 0; i < n; ++i) {
        if (nums[i] == 1) swap(nums[i], nums[++p1]);
        else if (nums[i] == 0) {
            swap(nums[i], nums[1 + p0]);
            if (p0 < p1) swap(nums[i], nums[p1 + 1]);
            ++p1;++p0;
        }
    }
}

题号:4 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2]
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列

给你一个整数数组 nums ，找出 nums 的下一个排列
必须原地修改，只允许使用额外常数空间

下一个排列的性质:

1. 需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列
2. 同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小

具体地，我们这样描述该算法，对于长度为 n 的排列 a：

1. 首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i]<a[i+1](完全逆序就是最大序列了)。此时 [i+1,n) 必然是下降序列(从后往前找顺序对，说明找到的结果后没有这样的顺序对)
2. 如果找到了顺序对，那么在区间[i+1,n)中从后向前查找第一个元素 j 满足a[i]<a[j],即找一个比a[i]大的数中的最小数
3. 交换 a[i] 与 a[j]，此时可以证明区间[i+1,n)必为降序。我们可以直接使用双指针反转区间[i+1,n)使其变为升序，而无需对该区间进行排序

void nextPermutation(vector<int>& nums) {
    int i = nums.size() - 2;//保证i+1不越界
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = nums.size() - 1;
        while (j >= 0 && nums[i] >= nums[j]) j--;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}

题号:5 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数
假设 nums 只有 一个重复的整数 ，返回 这个重复的数
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间

此题的其他官解都很……难以理解，只看第三种做法
我们对nums数组建图，每个位置i视为一条 i→nums[i] 的边。由于存在且仅存在一个重复的数字target，因此target这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的target就是这个环的入口，那么整个问题就等价于环形链表
我们已经证明过如果慢指针从起点出发，快指针从相遇位置出发，快慢指针会在环的入口相遇，所以复刻就行了

int findDuplicate(vector<int>& nums) {
    int slow =nums[0] , fast = nums[nums[0]];
    while (slow != fast){
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}