算法中文手册
[toc]
正则
规则
abcdefghijklmnopqurtuvwxyz
ABCDEFGHIJKLMNOPQRSTUVWXYZa
abced
abd
A[A-Z]{24}Z
abbabbbc
abbc
abc
ac
ab{5}c
ab((ce)?d)?
10^6ml
10^9ML
10E9 ML
10[^E][369] ?(ml|ML)
ad
1234567890
[^\s]
Ha HaHa
.转义
[abc]
[^abc]
[a-z]
[^a-z]
[a-zA-Z]
.
\s\S space
\w\W word
\d\D digit
(a|b)
a? 0-1次
a* 0-任意次
a+ 1-任意次
a{3} 3次
a{3,6} 三到六次
a{,6} 至多6次
a{3,} 至少三次
(a{3}|a{6}) 3次或6次
^ 开头
$ 结尾
MetaCharacters (Need to be escaped):
.[{()^$|?*+
coreyms.com
[-a-zA-Z0-9./]+.[a-zA-Z]+/?
\d{3}[.-]\d{3}[.-]\d{4}
192.168.0.1
255.255.255.255
[1-9]?\d|1\d{2}|2([0-4]\d|5[0-5])
(([1-9]?\d|1\d{2}|2([0-4]\d|5[0-5])).){3}([1-9]?\d|1\d{2}|2([0-4]\d|5[0-5])))
321-555-4321
123.555.1234
Mr. Schafer
Mr Smith
Ms Davis
Mrs. Robinson
Mr. T
Mr. t
M(s|r|rs).? [A-Z][a-z]*
https://deerchao.net/tutorials/regex/regex.htm
https://regex101.com/
https://www.regular-expressions.info/
练习
Dave Martin
615-555-7164
173 Main St., Springfield RI 55924
davemartin@bogusemail.com
Charles Harris
800-555-5669
969 High St., Atlantis VA 34075
charlesharris@bogusemail.com
Eric Williams
560-555-5153
806 1st St., Faketown AK 86847
laurawilliams@bogusemail.com
Corey Jefferson
900-555-9340
826 Elm St., Epicburg NE 10671
coreyjefferson@bogusemail.com
Jennifer Martin-White
714-555-7405
212 Cedar St., Sunnydale CT 74983
jenniferwhite@bogusemail.com
Erick Davis
800-555-6771
519 Washington St., Olympus TN 32425
tomdavis@bogusemail.com
Neil Patterson
783-555-4799
625 Oak St., Dawnstar IL 61914
neilpatterson@bogusemail.com
Laura Jefferson
516-555-4615
890 Main St., Pythonville LA 29947
laurajefferson@bogusemail.com
Maria Johnson
127-555-1867
884 High St., Braavos ME 43597
mariajohnson@bogusemail.com
Michael Arnold
608-555-4938
249 Elm St., Quahog OR 90938
michaelarnold@bogusemail.com
Michael Smith
568-555-6051
619 Park St., Winterfell VA 99000
michaelsmith@bogusemail.com
Erik Stuart
292-555-1875
220 Cedar St., Lakeview NY 87282
robertstuart@bogusemail.com
Laura Martin
900-555-3205
391 High St., Smalltown WY 28362
lauramartin@bogusemail.com
Barbara Martin
614-555-1166
121 Hill St., Braavos UT 92474
barbaramartin@bogusemail.com
Linda Jackson
530-555-2676
433 Elm St., Westworld TX 61967
lindajackson@bogusemail.com
Eric Miller
470-555-2750
838 Main St., Balmora MT 56526
stevemiller@bogusemail.com
Dave Arnold
800-555-6089
732 High St., Valyria KY 97152
davearnold@bogusemail.com
Jennifer Jacobs
880-555-8319
217 High St., Old-town IA 82767
jenniferjacobs@bogusemail.com
Neil Wilson
777-555-8378
191 Main St., Mordor IL 72160
neilwilson@bogusemail.com
Kurt Jackson
998-555-7385
607 Washington St., Blackwater NH 97183
kurtjackson@bogusemail.com
Mary Jacobs
800-555-7100
478 Oak St., Bedrock IA 58176
maryjacobs@bogusemail.com
Michael White
903-555-8277
906 Elm St., Mordor TX 89212
michaelwhite@bogusemail.com
Jennifer Jenkins
196-555-5674
949 Main St., Smalltown SC 96962
jenniferjenkins@bogusemail.com
Sam Wright
900-555-5118
835 Pearl St., Smalltown ND 77737
samwright@bogusemail.com
John Davis
905-555-1630
451 Lake St., Bedrock GA 34615
johndavis@bogusemail.com
Eric Davis
203-555-3475
419 Lake St., Balmora OR 30826
neildavis@bogusemail.com
Laura Jackson
884-555-8444
443 Maple St., Quahog MS 29348
laurajackson@bogusemail.com
John Williams
904-555-8559
756 Hill St., Valyria KY 94854
johnwilliams@bogusemail.com
Michael Martin
889-555-7393
216 High St., Olympus NV 21888
michaelmartin@bogusemail.com
Maggie Brown
195-555-2405
806 Lake St., Lakeview MD 59348
maggiebrown@bogusemail.com
Erik Wilson
321-555-9053
354 Hill St., Mordor FL 74122
kurtwilson@bogusemail.com
Elizabeth Arnold
133-555-1711
805 Maple St., Winterfell NV 99431
elizabetharnold@bogusemail.com
Jane Martin
900-555-5428
418 Park St., Metropolis ID 16576
janemartin@bogusemail.com
Travis Johnson
760-555-7147
749 Washington St., Braavos SD 25668
travisjohnson@bogusemail.com
Laura Jefferson
391-555-6621
122 High St., Metropolis ME 29540
laurajefferson@bogusemail.com
Tom Williams
932-555-7724
610 High St., Old-town FL 60758
tomwilliams@bogusemail.com
Jennifer Taylor
609-555-7908
332 Main St., Pythonville OH 78172
jennifertaylor@bogusemail.com
Erick Wright
800-555-8810
858 Hill St., Blackwater NC 79714
jenniferwright@bogusemail.com
Steve Doe
149-555-7657
441 Elm St., Atlantis MS 87195
stevedoe@bogusemail.com
Kurt Davis
130-555-9709
404 Oak St., Atlantis ND 85386
kurtdavis@bogusemail.com
Corey Harris
143-555-9295
286 Pearl St., Vice City TX 57112
coreyharris@bogusemail.com
Nicole Taylor
903-555-9878
465 Hill St., Old-town LA 64102
nicoletaylor@bogusemail.com
Elizabeth Davis
574-555-3194
151 Lake St., Eerie SD 17880
elizabethdavis@bogusemail.com
Maggie Jenkins
496-555-7533
504 Lake St., Gotham PA 46692
maggiejenkins@bogusemail.com
Linda Davis
210-555-3757
201 Pine St., Vice City AR 78455
lindadavis@bogusemail.com
Dave Moore
900-555-9598
251 Pine St., Old-town OK 29087
davemoore@bogusemail.com
Linda Jenkins
866-555-9844
117 High St., Bedrock NE 11899
lindajenkins@bogusemail.com
Eric White
669-555-7159
650 Oak St., Smalltown TN 43281
samwhite@bogusemail.com
Laura Robinson
152-555-7417
377 Pine St., Valyria NC 78036
laurarobinson@bogusemail.com
Charles Patterson
893-555-9832
416 Pearl St., Valyria AK 62260
charlespatterson@bogusemail.com
Joe Jackson
217-555-7123
683 Cedar St., South Park KS 66724
joejackson@bogusemail.com
Michael Johnson
786-555-6544
288 Hill St., Smalltown AZ 18586
michaeljohnson@bogusemail.com
Corey Miller
780-555-2574
286 High St., Springfield IA 16272
coreymiller@bogusemail.com
James Moore
926-555-8735
278 Main St., Gotham KY 89569
jamesmoore@bogusemail.com
Jennifer Stuart
895-555-3539
766 Hill St., King’s Landing GA 54999
jenniferstuart@bogusemail.com
Charles Martin
874-555-3949
775 High St., Faketown PA 89260
charlesmartin@bogusemail.com
Eric Wilks
800-555-2420
885 Main St., Blackwater OH 61275
joewilks@bogusemail.com
Elizabeth Arnold
936-555-6340
528 Hill St., Atlantis NH 88289
elizabetharnold@bogusemail.com
John Miller
372-555-9809
117 Cedar St., Thundera NM 75205
johnmiller@bogusemail.com
Corey Jackson
890-555-5618
115 Oak St., Gotham UT 36433
coreyjackson@bogusemail.com
Sam Thomas
670-555-3005
743 Lake St., Springfield MS 25473
samthomas@bogusemail.com
Patricia Thomas
509-555-5997
381 Hill St., Blackwater CT 30958
patriciathomas@bogusemail.com
Jennifer Davis
721-555-5632
125 Main St., Smalltown MT 62155
jenniferdavis@bogusemail.com
Patricia Brown
900-555-3567
292 Hill St., Gotham WV 57680
patriciabrown@bogusemail.com
Barbara Williams
147-555-6830
514 Park St., Balmora NV 55462
barbarawilliams@bogusemail.com
James Taylor
582-555-3426
776 Hill St., Dawnstar MA 51312
jamestaylor@bogusemail.com
Eric Harris
400-555-1706
421 Elm St., Smalltown NV 72025
barbaraharris@bogusemail.com
Travis Anderson
525-555-1793
937 Cedar St., Thundera WA 78862
travisanderson@bogusemail.com
Sam Robinson
317-555-6700
417 Pine St., Lakeview MD 13147
samrobinson@bogusemail.com
Steve Robinson
974-555-8301
478 Park St., Springfield NM 92369
steverobinson@bogusemail.com
Mary Wilson
800-555-3216
708 Maple St., Braavos UT 29551
marywilson@bogusemail.com
Sam Wilson
746-555-4094
557 Pearl St., Westworld KS 23225
samwilson@bogusemail.com
Charles Jones
922-555-1773
855 Hill St., Olympus HI 81427
charlesjones@bogusemail.com
Laura Brown
711-555-4427
980 Maple St., Smalltown MO 96421
laurabrown@bogusemail.com
Tom Harris
355-555-1872
676 Hill St., Blackwater AR 96698
tomharris@bogusemail.com
Patricia Taylor
852-555-6521
588 Pine St., Olympus FL 98412
patriciataylor@bogusemail.com
Barbara Williams
691-555-5773
351 Elm St., Sunnydale GA 26245
barbarawilliams@bogusemail.com
Maggie Johnson
332-555-5441
948 Cedar St., Quahog DE 56449
maggiejohnson@bogusemail.com
Kurt Miller
900-555-7755
381 Hill St., Quahog AL 97503
kurtmiller@bogusemail.com
Neil Stuart
379-555-3685
496 Cedar St., Sunnydale RI 49113
neilstuart@bogusemail.com
Linda Patterson
127-555-9682
736 Cedar St., Lakeview KY 47472
lindapatterson@bogusemail.com
Charles Davis
789-555-7032
678 Lake St., Mordor MN 11845
charlesdavis@bogusemail.com
Jennifer Jefferson
783-555-5135
289 Park St., Sunnydale WA 74526
jenniferjefferson@bogusemail.com
Erick Taylor
315-555-6507
245 Washington St., Bedrock IL 26941
coreytaylor@bogusemail.com
Robert Wilks
481-555-5835
573 Elm St., Sunnydale IL 47182
robertwilks@bogusemail.com
Travis Jackson
365-555-8287
851 Lake St., Metropolis PA 22772
travisjackson@bogusemail.com
Travis Jackson
911-555-7535
489 Oak St., Atlantis HI 73725
travisjackson@bogusemail.com
Laura Wilks
681-555-2460
371 Pearl St., Smalltown SC 47466
laurawilks@bogusemail.com
Neil Arnold
274-555-9800
504 Oak St., Faketown PA 73860
neilarnold@bogusemail.com
Linda Johnson
800-555-1372
667 High St., Balmora IN 82473
lindajohnson@bogusemail.com
Jennifer Wilson
300-555-7821
266 Pine St., Westworld DC 58720
jenniferwilson@bogusemail.com
Nicole White
133-555-3889
276 High St., Braavos IL 57764
nicolewhite@bogusemail.com
Maria Arnold
705-555-6863
491 Elm St., Metropolis PA 31836
mariaarnold@bogusemail.com
Jennifer Davis
215-555-9449
859 Cedar St., Old-town MT 31169
jenniferdavis@bogusemail.com
Mary Patterson
988-555-6112
956 Park St., Valyria CT 81541
marypatterson@bogusemail.com
Jane Stuart
623-555-3006
983 Oak St., Old-town RI 15445
janestuart@bogusemail.com
Robert Davis
192-555-4977
789 Maple St., Mordor IN 22215
robertdavis@bogusemail.com
James Taylor
178-555-4899
439 Hill St., Olympus NV 39308
jamestaylor@bogusemail.com
Eric Stuart
952-555-3089
777 High St., King’s Landing AZ 16547
johnstuart@bogusemail.com
Charles Miller
900-555-6426
207 Washington St., Blackwater MA 24886
charlesmiller@bogusemail.com
- ip正则：
(((\d{1,2})|(1\d{2})|(2[0-4]\d)|(25[0-5])).){3}((\d{1,2})|(1\d{2})|(2[0-4]\d)|(25[0-5]))
设计模式2
设计模式2
1.观察者模式
- 定义：在对象之间定义了一对多的依赖，这样的话，当一个对象改变状态，依赖他的对象会受到通知并自动更新。（其实就是发布订阅模式：发布者发布信息，订阅者获取信息，订阅了就能收到消息，没订阅的就收不到消息）
2.访问者模式
- 定义：封装作用于某种数据结构中各元素的操作，它可在不改变数据结构的前提下定义作用于这些元素的新的操作。
3.命令模式
- 定义：发送者和接收者之间引入了一个命令对象，将发送者的请求封装在命令对象中，再通过命令对象来调用接受者的方法。
- spring框架：spring是怎么做的，view、controller、service是怎么连在一起的：spring是控制反转、依赖注入，解决了数据数据初始化一些问题，能够吧代码写得很简洁，然后脱颖而出，核心是怎么做的，数据初始化是怎么做的。面向切面的编程可以用在什么地方，spring的一般框架是mvc
：层是controller、中间层是service、底层是dao。为什么这么分？他比其他的区别是什么？对一些request包装了
找spring一两点深入研究：我不仅仅是用了spring，我还研究了他某一个组件，他是怎么实现的？讲讲(闪光点） - velocity（模板语言）
我用了velocity，我发现了velocity里的很多东西和我学的java、c++都是一样的，他这个框架他把一些公用的都提取出来，前面的spring boot是个java框架，为什么要用velocity，因为我要前后端分离，view和后面的数据要分离，data是怎么传过来的，怎么解析的，他支持什么东西？（不仅仅用了这个东西，还有思想，解耦）3.mybatis
- 怎么把数据库的一些前后的读取给做了，怎么把xml里的多重条件，怎么做文法的解析，然后把这些条件给处理掉。
4.登录/注册
- 网站安全（salt）：密码为什么加了一个salt就变得安全？
- 通过拦截器来实现的：拦截器的思想、框架，留好接口;拦截器实现登录注册：我在cookie里放了一个token，token怎么处理用户登录注册的：在用户登录注册的时候，会下发一个token，把token与用户信息关联起来，关联起来之后我为了优化token信息，把token放到数据库里（redis），设计一个分布式的统一登录系统，现在的互联网产品都是统一登录的，比如，登录qq之后，登录网页就不需要登录了，qq登录过的token直接注入到网页上去。这是个ssension共享问题：、
- 保证数据安全：验证（邮件激活）
5.前缀树
- 构造一个前缀树，通过一个有限状态机来实现一传文本是不是包含敏感词，繁杂度是多少 很重要：优点有哪些？为什么不用kmp，文本查找算法：
可以很快的加一些词汇过来；有扩展性，以及性能更提高6.redis
- 数据结构：跳列表，哈希，优先队列，list：我了解redis底层是怎么实现的，为什么他的效率很高，他的字符串是怎么保存的，做这个工程的时候我用在的异步队列上、排序上、异步框架
7.异步框架
*思路：我这个网站附带的每一步操作可能附带的操作都非常多，为了更快的吧结果返回给用户，所以采用异步框架，自己写的，数据结构：使用redis的队列，因为redis能够保证线程同步；除了用队列，我还想过用有优先队列，这样我的异步框架能够把紧急的任务线处理掉。我这个异步框架：有消息的发射，消息的处理，事件的模型定义以及具体执行的eventhandle，我定义了一些公共接口把这些实现了。
8.邮件（smtp协议）
- 做了一个简单邮件，怎么连接上服务器，我当时做这个的时候，ssl问题
，ssl理解，服务器需要ssl链接，为了安全服务器是怎么做的；java sdk 1.7 1.8的问题，1.8是需要换一个jar包的 - 豆瓣电影排序：好的问题能挑选出来，互动越多，时间越新，评分越高。
9.timeline（时间轴）
- 肯定会问：为什么用推拉模式，用推实时性高能让好友快速得到消息，用拉能节省僵尸号、不是活跃用户的存储空间。怎么区分？最后把timeline组合起来‘timeline模板系统，每个新鲜事展向不一样，和velocity结合起来，后台存储的都是核心数据，每个数据对应的是一个模板，我把模板结合起来，我就能快速的把时间轴展示出来。
10.爬虫
11.solr搜索
- 搜索去重：对比相似度，敏感哈希算法，哈希算法：两个字符串稍微有一点点不一样，结构就是不一样的。可能头尾是不一样的，内容一样：采用敏感哈希算法把相似度求出来，区别：敏感哈希算法两个文档相似度很高，他生成的哈希值的比例是很相似的。
12.单元测试/部署
- 部署：运维，llinux nigix反向代理，与正向对比。负载均衡：为什么要负载均衡。
设计模式
常用设计模式
1.观察者模式
- 定义：在对象之间定义了一对多的依赖，这样的话，当一个对象改变状态，依赖他的对象会受到通知并自动更新。（其实就是发布订阅模式：发布者发布信息，订阅者获取信息，订阅了就能收到消息，没订阅的就收不到消息）
2.访问者模式
- 定义：封装作用于某种数据结构中各元素的操作，它可在不改变数据结构的前提下定义作用于这些元素的新的操作。
3.命令模式
- 定义：发送者和接收者之间引入了一个命令对象，将发送者的请求封装在命令对象中，再通过命令对象来调用接受者的方法。
- spring框架：spring是怎么做的，view、controller、service是怎么连在一起的：spring是控制反转、依赖注入，解决了数据数据初始化一些问题，能够吧代码写得很简洁，然后脱颖而出，核心是怎么做的，数据初始化是怎么做的。面向切面的编程可以用在什么地方，spring的一般框架是mvc
：层是controller、中间层是service、底层是dao。为什么这么分？他比其他的区别是什么？对一些request包装了
找spring一两点深入研究：我不仅仅是用了spring，我还研究了他某一个组件，他是怎么实现的？讲讲(闪光点） - velocity（模板语言）
我用了velocity，我发现了velocity里的很多东西和我学的java、c++都是一样的，他这个框架他把一些公用的都提取出来，前面的spring boot是个java框架，为什么要用velocity，因为我要前后端分离，view和后面的数据要分离，data是怎么传过来的，怎么解析的，他支持什么东西？（不仅仅用了这个东西，还有思想，解耦）
3.mybatis
- 怎么把数据库的一些前后的读取给做了，怎么把xml里的多重条件，怎么做文法的解析，然后把这些条件给处理掉。
4.登录/注册
- 网站安全（salt）：密码为什么加了一个salt就变得安全？
- 通过拦截器来实现的：拦截器的思想、框架，留好接口;拦截器实现登录注册：我在cookie里放了一个token，token怎么处理用户登录注册的：在用户登录注册的时候，会下发一个token，把token与用户信息关联起来，关联起来之后我为了优化token信息，把token放到数据库里（redis），设计一个分布式的统一登录系统，现在的互联网产品都是统一登录的，比如，登录qq之后，登录网页就不需要登录了，qq登录过的token直接注入到网页上去。这是个ssension共享问题：、
- 保证数据安全：验证（邮件激活）
5.前缀树
- 构造一个前缀树，通过一个有限状态机来实现一传文本是不是包含敏感词，繁杂度是多少 很重要：优点有哪些？为什么不用kmp，文本查找算法：
可以很快的加一些词汇过来；有扩展性，以及性能更提高
6.redis
- 数据结构：跳列表，哈希，优先队列，list：我了解redis底层是怎么实现的，为什么他的效率很高，他的字符串是怎么保存的，做这个工程的时候我用在的异步队列上、排序上、异步框架
7.异步框架
*思路：我这个网站附带的每一步操作可能附带的操作都非常多，为了更快的吧结果返回给用户，所以采用异步框架，自己写的，数据结构：使用redis的队列，因为redis能够保证线程同步；除了用队列，我还想过用有优先队列，这样我的异步框架能够把紧急的任务线处理掉。我这个异步框架：有消息的发射，消息的处理，事件的模型定义以及具体执行的eventhandle，我定义了一些公共接口把这些实现了。
8.邮件（smtp协议）
- 做了一个简单邮件，怎么连接上服务器，我当时做这个的时候，ssl问题
，ssl理解，服务器需要ssl链接，为了安全服务器是怎么做的；java sdk 1.7 1.8的问题，1.8是需要换一个jar包的 - 豆瓣电影排序：好的问题能挑选出来，互动越多，时间越新，评分越高。
9.timeline（时间轴）
- 肯定会问：为什么用推拉模式，用推实时性高能让好友快速得到消息，用拉能节省僵尸号、不是活跃用户的存储空间。怎么区分？最后把timeline组合起来‘timeline模板系统，每个新鲜事展向不一样，和velocity结合起来，后台存储的都是核心数据，每个数据对应的是一个模板，我把模板结合起来，我就能快速的把时间轴展示出来。
10.爬虫
11.solr搜索
- 搜索去重：对比相似度，敏感哈希算法，哈希算法：两个字符串稍微有一点点不一样，结构就是不一样的。可能头尾是不一样的，内容一样：采用敏感哈希算法把相似度求出来，区别：敏感哈希算法两个文档相似度很高，他生成的哈希值的比例是很相似的。
12.单元测试/部署
- 部署：运维，llinux nigix反向代理，与正向对比。负载均衡：为什么要负载均衡。
NAS上搭建SS客户端
群辉NAS上搭建SS客户端来连接远程并提供本地HTTP/Socks5代理
**Contents** [hide](https://1024.ee/index.php/2020/04/06/群辉nas上搭建ss客户端来连接远程并提供本地http-socks5代理/#)
下载docker – ss-privoxy
高级设置
注意是文件，不是文件夹。而且，文件名就是config, 不是config.conf之类。
1 | #配置文件 |
设置端口
- 7070 For Socks5 – All Traffic
- 8118 for Http/Https – 部分域名翻墙，改conf文件即可
最后查一查
开启后查查日志，一切正常即可
群辉自己的使用，开这里就行。
指令
1 | docker run -d --restart=always \ |
动态规划答疑篇
动态规划答疑篇
预计阅读时间：7 分钟
这篇文章就给你讲明白两个读者问得最多的问题：
1、到底什么才叫「最优子结构」，和动态规划什么关系。
2、为什么动态规划遍历dp数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历，有的无论咋遍历都是对的。
一、最优子结构详解
「最优子结构」是某些问题的一种特定性质，并不是动态规划问题专有的。也就是说，很多问题其实都具有最优子结构，只是其中大部分不具有重叠子问题，所以我们不把它们归为动态规划系列问题而已。
我先举个很容易理解的例子：假设你们学校有 10 个班，你已经计算出了每个班的最高考试成绩。那么现在我要求你计算全校最高的成绩，你会不会算？当然会，而且你不用重新遍历全校学生的分数进行比较，而是只要在这 10 个最高成绩中取最大的就是全校的最高成绩。
我给你提出的这个问题就符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。
你看，这么简单的问题都有最优子结构性质，只是因为显然没有重叠子问题，所以我们简单地求最值肯定用不出动态规划。
再举个例子：假设你们学校有 10 个班，你已知每个班的最大分数差（最高分和最低分的差值）。那么现在我让你计算全校学生中的最大分数差，你会不会算？可以想办法算，但是肯定不能通过已知的这 10 个班的最大分数差推到出来。因为这 10 个班的最大分数差不一定就包含全校学生的最大分数差，比如全校的最大分数差可能是 3 班的最高分和 6 班的最低分之差。
这次我给你提出的问题就不符合最优子结构，因为你没办通过每个班的最优值推出全校的最优值，没办法通过子问题的最优值推出规模更大的问题的最优值。前文 动态规划详解 说过，想满足最优子结，子问题之间必须互相独立。全校的最大分数差可能出现在两个班之间，显然子问题不独立，所以这个问题本身不符合最优子结构。
那么遇到这种最优子结构失效情况，怎么办？策略是：改造问题。对于最大分数差这个问题，我们不是没办法利用已知的每个班的分数差吗，那我只能这样写一段暴力代码：
1 | int result = 0; |
改造问题，也就是把问题等价转化：最大分数差，不就等价于最高分数和最低分数的差么，那不就是要求最高和最低分数么，不就是我们讨论的第一个问题么，不就具有最优子结构了么？那现在改变思路，借助最优子结构解决最值问题，再回过头解决最大分数差问题，是不是就高效多了？
当然，上面这个例子太简单了，不过请读者回顾一下，我们做动态规划问题，是不是一直在求各种最值，本质跟我们举的例子没啥区别，无非需要处理一下重叠子问题。
前文 动态规划：不同的定义产生不同的解法 和 经典动态规划：高楼扔鸡蛋（进阶篇） 就展示了如何改造问题，不同的最优子结构，可能导致不同的解法和效率。
再举个常见但也十分简单的例子，求一棵二叉树的最大值，不难吧（简单起见，假设节点中的值都是非负数）：
1 | int maxVal(TreeNode root) { |
你看这个问题也符合最优子结构，以root为根的树的最大值，可以通过两边子树（子问题）的最大值推导出来，结合刚才学校和班级的例子，很容易理解吧。
当然这也不是动态规划问题，旨在说明，最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质；但反过来，最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的，以后碰到那种恶心人的最值题，思路往动态规划想就对了，这就是套路。
动态规划不就是从最简单的 base case 往后推导吗，可以想象成一个链式反应，不断以小博大。但只有符合最优子结构的问题，才有发生这种链式反应的性质。
找最优子结构的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。这也是套路，经常刷题的朋友应该能体会。
这里就不举那些正宗动态规划的例子了，读者可以翻翻历史文章，看看状态转移是如何遵循最优子结构的，这个话题就聊到这，下面再来看另外个动态规划迷惑行为。
二、dp 数组的遍历方向
我相信读者做动态规划问题时，肯定会对dp数组的遍历顺序有些头疼。我们拿二维dp数组来举例，有时候我们是正向遍历：
1 | int[][] dp = new int[m][n]; |
有时候我们反向遍历：
1 | for (int i = m - 1; i >= 0; i--) |
有时候可能会斜向遍历：
1 | // 斜着遍历数组 |
甚至更让人迷惑的是，有时候发现正向反向遍历都可以得到正确答案，比如我们在 团灭 LeetCode 股票买卖问题 中有的地方就正反皆可。
那么，如果仔细观察的话可以发现其中的原因的。你只要把住两点就行了：
1、遍历的过程中，所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置。
下面来具体解释上面两个原则是什么意思。
比如编辑距离这个经典的问题，详解见前文 经典动态规划：编辑距离，我们通过对dp数组的定义，确定了 base case 是dp[..][0]和dp[0][..]，最终答案是dp[m][n]；而且我们通过状态转移方程知道dp[i][j]需要从dp[i-1][j],dp[i][j-1],dp[i-1][j-1]转移而来，如下图：
那么，参考刚才说的两条原则，你该怎么遍历dp数组？肯定是正向遍历：
1 | for (int i = 1; i < m; i++) |
因为，这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的，而且最终结束在我们想要的答案dp[m][n]。
再举一例，回文子序列问题，详见前文 子序列解题模板：最长回文子序列，我们通过过对dp数组的定义，确定了 base case 处在中间的对角线，dp[i][j]需要从dp[i+1][j],dp[i][j-1],dp[i+1][j-1]转移而来，想要求的最终答案是dp[0][n-1]，如下图：
这种情况根据刚才的两个原则，就可以有两种正确的遍历方式：
要么从左至右斜着遍历，要么从下向上从左到右遍历，这样才能保证每次dp[i][j]的左边、下边、左下边已经计算完毕，最终得到正确结果。
现在，你应该理解了这两个原则，主要就是看 base case 和最终结果的存储位置，保证遍历过程中使用的数据都是计算完毕的就行，有时候确实存在多种方法可以得到正确答案，可根据个人口味自行选择。
动态规划设计之最长递增子序列
动态规划设计之最长递增子序列
预计阅读时间： 9 分钟
很多读者反应，就算看了前文 动态规划详解，了解了动态规划的套路，也不会写状态转移方程，没有思路，怎么办？本文就借助「最长递增子序列」来讲一种设计动态规划的通用技巧：数学归纳思想。
最长递增子序列（Longest Increasing Subsequence，简写 LIS）是比较经典的一个问题，比较容易想到的是动态规划解法，时间复杂度 O(N^2)，我们借这个问题来由浅入深讲解如何写动态规划。
比较难想到的是利用二分查找，时间复杂度是 O(NlogN)，我们通过一种简单的纸牌游戏来辅助理解这种巧妙的解法。
先看一下题目，很容易理解：
注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的。下面先来一步一步设计动态规划算法解决这个问题。
一、动态规划解法
动态规划的核心设计思想是数学归纳法。
相信大家对数学归纳法都不陌生，高中就学过，而且思路很简单。比如我们想证明一个数学结论，那么我们先假设这个结论在 k<n 时成立，然后想办法证明 k=n 的时候此结论也成立。如果能够证明出来，那么就说明这个结论对于 k 等于任何数都成立。
类似的，我们设计动态规划算法，不是需要一个 dp 数组吗？我们可以假设 dp[0…i−1] 都已经被算出来了，然后问自己：怎么通过这些结果算出dp[i] ?
直接拿最长递增子序列这个问题举例你就明白了。不过，首先要定义清楚 dp 数组的含义，即 dp[i] 的值到底代表着什么？
我们的定义是这样的：****dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
举个例子：
算法演进的过程是这样的：
根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值。
1 | int res = 0; |
读者也许会问，刚才这个过程中每个 dp[i] 的结果是我们肉眼看出来的，我们应该怎么设计算法逻辑来正确计算每个 dp[i] 呢？
这就是动态规划的重头戏了，要思考如何进行状态转移，这里就可以使用数学归纳的思想：
我们已经知道了 d**p[0…4] 的所有结果，我们如何通过这些已知结果推出 d**p[5] 呢？
根据刚才我们对 dp 数组的定义，现在想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。
nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。
当然，可能形成很多种新的子序列，但是我们只要最长的，把最长子序列的长度作为 dp[5] 的值即可。
_20210715223303.gif)
这段代码的逻辑就可以算出 dp[5]。到这里，这道算法题我们就基本做完了。读者也许会问，我们刚才只是算了 dp[5] 呀，dp[4], dp[3] 这些怎么算呢？
类似数学归纳法，你已经可以通过 dp[0…4] 算出 dp[5] 了，那么任意 dp[i] 你肯定都可以算出来：
还有一个细节问题，就是 base case。dp 数组应该全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1。下面我们看一下完整代码：
至此，这道题就解决了，时间复杂度 O(N^2)。总结一下动态规划的设计流程：
首先明确 dp 数组所存数据的含义。这步很重要，如果不得当或者不够清晰，会阻碍之后的步骤。
然后根据 dp 数组的定义，运用数学归纳法的思想，假设 d**p[0…i−1] 都已知，想办法求出 d**p[i]，一旦这一步完成，整个题目基本就解决了。
但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。
二、二分查找解法
这个解法的时间复杂度会将为 O(NlogN)，但是说实话，正常人基本想不到这种解法（也许玩过某些纸牌游戏的人可以想出来）。所以如果大家了解一下就好，正常情况下能够给出动态规划解法就已经很不错了。
根据题目的意思，我都很难想象这个问题竟然能和二分查找扯上关系。其实最长递增子序列和一种叫做 patience game 的纸牌游戏有关，甚至有一种排序方法就叫做 patience sorting（耐心排序）。
为了简单起见，后文跳过所有数学证明，通过一个简化的例子来理解一下思路。
首先，给你一排扑克牌，我们像遍历数组那样从左到右一张一张处理这些扑克牌，最终要把这些牌分成若干堆。
处理这些扑克牌要遵循以下规则：
只能把点数小的牌压到点数比它大的牌上。如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去。如果当前牌有多个堆可供选择，则选择最左边的堆放置。
比如说上述的扑克牌最终会被分成这样 5 堆（我们认为 A 的值是最大的，而不是 1）。
为什么遇到多个可选择堆的时候要放到最左边的堆上呢？因为这样可以保证牌堆顶的牌有序（2, 4, 7, 8, Q），证明略。
按照上述规则执行，可以算出最长递增子序列，牌的堆数就是我们想求的最长递增子序列的长度，证明略。
我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗，牌堆顶的牌不是有序吗，这就能用到二分查找了：用二分查找来搜索当前牌应放置的位置。
PS：旧文 二分查找算法详解 详细介绍了二分查找的细节及变体，这里就完美应用上了。如果没读过强烈建议阅读。
至此，二分查找的解法也讲解完毕。
这个解法确实很难想到。首先涉及数学证明，谁能想到按照这些规则执行，就能得到最长递增子序列呢？其次还有二分查找的运用，要是对二分查找的细节不清楚，给了思路也很难写对。
所以，这个方法作为思维拓展好了。但动态规划的设计方法应该完全理解：假设之前的答案已知，利用数学归纳的思想正确进行状态的推演转移，最终得到答案。
回溯算法和动态规划，到底谁是谁爹
回溯算法和动态规划，到底谁是谁爹？
我们前文经常说回溯算法和递归算法有点类似，有的问题如果实在想不出状态转移方程，尝试用回溯算法暴力解决也是一个聪明的策略，总比写不出来解法强。
那么，回溯算法和动态规划到底是啥关系？它俩都涉及递归，算法模板看起来还挺像的，都涉及做「选择」，真的酷似父与子。
那么，它俩具体有啥区别呢？回溯算法和动态规划之间，是否可能互相转化呢？
今天就用力扣第 494 题「目标和」来详细对比一下回溯算法和动态规划，真可谓群魔乱舞：
注意，给出的例子 nums 全是 1，但实际上可以是任意正整数哦。
一、回溯思路
其实我第一眼看到这个题目，花了两分钟就写出了一个回溯解法。
任何算法的核心都是穷举，回溯算法就是一个暴力穷举算法，前文 回溯算法解题框架 就写了回溯算法框架：
1 | def backtrack(路径, 选择列表): |
关键就是搞清楚什么是「选择」，而对于这道题，「选择」不是明摆着的吗？
**对于每个数字 nums[i]，我们可以选择给一个正号 + 或者一个负号 -**，然后利用回溯模板穷举出来所有可能的结果，数一数到底有几种组合能够凑出 target 不就行了嘛？
伪码思路如下：
1 | def backtrack(nums, i): |
如果看过我们之前的几篇回溯算法文章，这个代码可以说是比较简单的了：
1 | int result = 0; |
有的读者可能问，选择 - 的时候，为什么是 rest += nums[i]，选择 + 的时候，为什么是 rest -= nums[i] 呢，是不是写反了？
不是的，「如何凑出 target」和「如何把 target 减到 0」其实是一样的。我们这里选择后者，因为前者必须给 backtrack 函数多加一个参数，我觉得不美观：
1 | void backtrack(int[] nums, int i, int sum, int target) { |
因此，如果我们给 nums[i] 选择 + 号，就要让 rest - nums[i]，反之亦然。
以上回溯算法可以解决这个问题，时间复杂度为 O(2^N)，N 为 nums 的大小。这个复杂度怎么算的？回忆前文 学习数据结构和算法的框架思维，发现这个回溯算法就是个二叉树的遍历问题：
1 | void backtrack(int[] nums, int i, int rest) { |
树的高度就是 nums 的长度嘛，所以说时间复杂度就是这棵二叉树的节点数，为 O(2^N)，其实是非常低效的。
那么，这个问题如何用动态规划思想进行优化呢？
二、消除重叠子问题
动态规划之所以比暴力算法快，是因为动态规划技巧消除了重叠子问题。
如何发现重叠子问题？看是否可能出现重复的「状态」。对于递归函数来说，函数参数中会变的参数就是「状态」，对于 backtrack 函数来说，会变的参数为 i 和 rest。
前文 动态规划之编辑距离 说了一种一眼看出重叠子问题的方法，先抽象出递归框架：
1 | void backtrack(int i, int rest) { |
举个简单的例子，如果 nums[i] = 0，会发生什么？
1 | void backtrack(int i, int rest) { |
你看，这样就出现了两个「状态」完全相同的递归函数，无疑这样的递归计算就是重复的。这就是重叠子问题，而且只要我们能够找到一个重叠子问题，那一定还存在很多的重叠子问题。
因此，状态 (i, rest) 是可以用备忘录技巧进行优化的：
1 | int findTargetSumWays(int[] nums, int target) { |
以前我们都是用 Python 的元组配合哈希表 dict 来做备忘录的，其他语言没有元组，可以用把「状态」转化为字符串作为哈希表的键，这是一个常用的小技巧。
这个解法通过备忘录消除了很多重叠子问题，效率有一定的提升，但是这就结束了吗？
三、动态规划
事情没有这么简单，先来算一算，消除重叠子问题之后，算法的时间复杂度是多少？其实最坏情况下依然是 O(2^N)。
为什么呢？因为我们只不过恰好发现了重叠子问题，顺手用备忘录技巧给优化了，但是底层思路没有变，依然是暴力穷举的回溯算法，依然在遍历一棵二叉树。这只能叫对回溯算法进行了「剪枝」，提升了算法在某些情况下的效率，但算不上质的飞跃。
其实，这个问题可以转化为一个子集划分问题，而子集划分问题又是一个典型的背包问题。动态规划总是这么玄学，让人摸不着头脑……
首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：
1 | sum(A) - sum(B) = target |
综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：**nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2**？
类似的子集划分问题我们前文 经典背包问题：子集划分 讲过，现在实现这么一个函数：
1 | /* 计算 nums 中有几个子集的和为 sum */ |
然后，可以这样调用这个函数：
1 | int findTargetSumWays(int[] nums, int target) { |
好的，变成背包问题的标准形式：
有一个背包，容量为 sum，现在给你 N 个物品，第 i 个物品的重量为 nums[i - 1]（注意 1 <= i <= N），每个物品只有一个，请问你有几种不同的方法能够恰好装满这个背包？
现在，这就是一个正宗的动态规划问题了，下面按照我们一直强调的动态规划套路走流程：
第一步要明确两点，「状态」和「选择」。
对于背包问题，这个都是一样的，状态就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。
第二步要明确 dp 数组的定义。
按照背包问题的套路，可以给出如下定义：
dp[i][j] = x 表示，若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包。
翻译成我们探讨的子集问题就是，若只在 nums 的前 i 个元素中选择，若目标和为 j，则最多有 x 种方法划分子集。
根据这个定义，显然 dp[0][..] = 0，因为没有物品的话，根本没办法装背包；dp[..][0] = 1，因为如果背包的最大载重为 0，「什么都不装」就是唯一的一种装法。
我们所求的答案就是 dp[N][sum]，即使用所有 N 个物品，有几种方法可以装满容量为 sum 的背包。
第三步，根据「选择」，思考状态转移的逻辑。
回想刚才的 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么恰好装满背包的方法数就取决于上一个状态 dp[i-1][j]，继承之前的结果。
如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么只要看前 i - 1 个物品有几种方法可以装满 j - nums[i-1] 的重量就行了，所以取决于状态 dp[i-1][j-nums[i-1]]。
PS：注意我们说的 i 是从 1 开始算的，而数组 nums 的索引时从 0 开始算的，所以 nums[i-1] 代表的是第 i 个物品的重量，j - nums[i-1] 就是背包装入物品 i 之后还剩下的容量。
由于 dp[i][j] 为装满背包的总方法数，所以应该以上两种选择的结果求和，得到状态转移方程：
1 | dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]; |
然后，根据状态转移方程写出动态规划算法：
1 | /* 计算 nums 中有几个子集的和为 sum */ |
然后，发现这个 dp[i][j] 只和前一行 dp[i-1][..] 有关，那么肯定可以优化成一维 dp：
1 | /* 计算 nums 中有几个子集的和为 sum */ |
对照二维 dp，只要把 dp 数组的第一个维度全都去掉就行了，唯一的区别就是这里的 j 要从后往前遍历，原因如下：
因为二维压缩到一维的根本原理是，dp[j] 和 dp[j-nums[i-1]] 还没被新结果覆盖的时候，相当于二维 dp 中的 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]。
那么，我们就要做到：在计算新的 dp[j] 的时候，dp[j] 和 dp[j-nums[i-1]] 还是上一轮外层 for 循环的结果。
如果你从前往后遍历一维 dp 数组，dp[j] 显然是没问题的，但是 dp[j-nums[i-1]] 已经不是上一轮外层 for 循环的结果了，这里就会使用错误的状态，当然得不到正确的答案。
现在，这道题算是彻底解决了。
总结一下，回溯算法虽好，但是复杂度高，即便消除一些冗余计算，也只是「剪枝」，没有本质的改进。而动态规划就比较玄学了，经过各种改造，从一个加减法问题变成子集问题，又变成背包问题，经过各种套路写出解法，又搞出状态压缩，还得反向遍历。
现在搞得我都忘了自己是来干嘛的了。嗯，这也许就是动态规划的魅力吧。
回溯算法团灭排列组合子集问题
回溯算法团灭排列/组合/子集问题
回溯算法团灭排列/组合/子集问题
预计阅读时间：7 分钟
今天就来聊三道考察频率高，而且容易让人搞混的算法问题，分别是求子集（subset），求排列（permutation），求组合（combination）。这几个问题都可以用回溯算法解决。
一、子集
问题很简单，输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集。
1 | vector<vector<int>> subsets(vector<int>& nums); |
比如输入 nums = [1,2,3]，你的算法应输出 8 个子集，包含空集和本身，顺序可以不同：
[ [],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3] ]
第一个解法是利用数学归纳的思想：假设我现在知道了规模更小的子问题的结果，如何推导出当前问题的结果呢？
具体来说就是，现在让你求 [1,2,3] 的子集，如果你知道了 [1,2] 的子集，是否可以推导出 [1,2,3] 的子集呢？先把 [1,2] 的子集写出来瞅瞅：
[ [],[1],[2],[1,2] ]
你会发现这样一个规律：
subset([1,2,3]) - subset([1,2])
= [3],[1,3],[2,3],[1,2,3]
而这个结果，就是把 sebset([1,2]) 的结果中每个集合再添加上 3。
换句话说，如果 A = subset([1,2]) ，那么：
subset([1,2,3])
= A + [A[i].add(3) for i = 1..len(A)]
这就是一个典型的递归结构嘛，[1,2,3] 的子集可以由 [1,2] 追加得出，[1,2] 的子集可以由 [1] 追加得出，base case 显然就是当输入集合为空集时，输出子集也就是一个空集。
翻译成代码就很容易理解了：
1 | vector<vector<int>> subsets(vector<int>& nums) { |
这个问题的时间复杂度计算比较容易坑人。我们之前说的计算递归算法时间复杂度的方法，是找到递归深度，然后乘以每次递归中迭代的次数。对于这个问题，递归深度显然是 N，但我们发现每次递归 for 循环的迭代次数取决于 res 的长度，并不是固定的。
根据刚才的思路，res 的长度应该是每次递归都翻倍，所以说总的迭代次数应该是 2^N。或者不用这么麻烦，你想想一个大小为 N 的集合的子集总共有几个？2^N 个对吧，所以说至少要对 res 添加 2^N 次元素。
那么算法的时间复杂度就是 O(2^N) 吗？还是不对，2^N 个子集是 push_back 添加进 res 的，所以要考虑 push_back 这个操作的效率：
1 | vector<vector<int>> res = ... |
因为 res[i] 也是一个数组呀，push_back 是把 res[i] copy 一份然后添加到数组的最后，所以一次操作的时间是 O(N)。
综上，总的时间复杂度就是 O(N*2^N)，还是比较耗时的。
空间复杂度的话，如果不计算储存返回结果所用的空间的，只需要 O(N) 的递归堆栈空间。如果计算 res 所需的空间，应该是 O(N*2^N)。
第二种通用方法就是回溯算法。旧文「回溯算法详解」写过回溯算法的模板：
1 | result = [] |
只要改造回溯算法的模板就行了：
1 | vector<vector<int>> res; |
可以看见，对 res 的更新是一个前序遍历，也就是说，res 就是树上的所有节点：
二、组合
输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合。
1 | vector<vector<int>> combine(int n, int k); |
比如输入 n = 4, k = 2，输出如下结果，顺序无所谓，但是不能包含重复（按照组合的定义，[1,2] 和 [2,1] 也算重复）：
[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4]
]
这就是典型的回溯算法，k 限制了树的高度，n 限制了树的宽度，直接套我们以前讲过的回溯算法模板框架就行了：
1 | vector<vector<int>>res; |
backtrack 函数和计算子集的差不多，区别在于，更新 res 的地方是树的底端。
三、排列
输入一个不包含重复数字的数组 nums，返回这些数字的全部排列。
1 | vector<vector<int>> permute(vector<int>& nums); |
比如说输入数组 [1,2,3]，输出结果应该如下，顺序无所谓，不能有重复：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
回溯算法详解 中就是拿这个问题来解释回溯模板的。这里又列出这个问题，是将「排列」和「组合」这两个回溯算法的代码拿出来对比。
首先画出回溯树来看一看：
我们当时使用 Java 代码写的解法：
1 | List<List<Integer>> res = new LinkedList<>(); |
回溯模板依然没有变，但是根据排列问题和组合问题画出的树来看，排列问题的树比较对称，而组合问题的树越靠右节点越少。
在代码中的体现就是，排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字；而组合问题通过传入一个 start 参数，来排除 start 索引之前的数字。
以上，就是排列组合和子集三个问题的解法，总结一下：
子集问题可以利用数学归纳思想，假设已知一个规模较小的问题的结果，思考如何推导出原问题的结果。也可以用回溯算法，要用 start 参数排除已选择的数字。
组合问题利用的是回溯思想，结果可以表示成树结构，我们只要套用回溯算法模板即可，关键点在于要用一个 start 排除已经选择过的数字。
排列问题是回溯思想，也可以表示成树结构套用算法模板，不同之处在于使用 contains 方法排除已经选择的数字，前文有详细分析，这里主要是和组合问题作对比。
对于这三个问题，关键区别在于回溯树的结构，不妨多观察递归树的结构，很自然就可以理解代码的含义了。
如何拆解复杂问题：实现一个计算器
如何拆解复杂问题：实现一个计算器
我记得很多大学数据结构的教材上，在讲栈这种数据结构的时候，应该都会用计算器举例，但是有一说一，讲的真的垃圾，我只感受到被数据结构支配的恐惧，丝毫没有支配数据结构的快感。
不知道多少未来的计算机科学家就被这种简单的数据结构劝退了。
1、输入一个字符串，可以包含+ - * / ()``、数字、空格，你的算法返回运算结果。
2、要符合运算法则，括号的优先级最高，先乘除后加减。
3、除号是整数除法，无论正负都向 0 取整（5/2=2，-5/2=-2）。
4、可以假定输入的算式一定合法，且计算过程不会出现整型溢出，不会出现除数为 0 的意外情况。
比如输入如下字符串，算法会返回 9：
1 | 3 * (2-6 /(3 -7)) |
可以看到，这就已经非常接近我们实际生活中使用的计算器了，虽然我们以前肯定都用过计算器，但是如果简单思考一下其算法实现，就会大惊失色：
1、按照常理处理括号，要先计算最内层的括号，然后向外慢慢化简。这个过程我们手算都容易出错，何况写成算法呢！
2、要做到先乘除，后加减，这一点教会小朋友还不算难，但教给计算机恐怕有点困难。
3、要处理空格。我们为了美观，习惯性在数字和运算符之间打个空格，但是计算之中得想办法忽略这些空格。
那么本文就来聊聊怎么实现上述一个功能完备的计算器功能，关键在于层层拆解问题，化整为零，逐个击破，相信这种思维方式能帮大家解决各种复杂问题。
下面就来拆解，从最简单的一个问题开始。
一、字符串转整数
是的，就是这么一个简单的问题，首先告诉我，怎么把一个字符串形式的正整数，转化成 int 型？
1 | string s = "458"; |
这个还是很简单的吧，老套路了。但是即便这么简单，依然有坑：**(c - '0')的这个括号不能省略，否则可能造成整型溢出**。
因为变量c是一个 ASCII 码，如果不加括号就会先加后减，想象一下n如果接近 INT_MAX，就会溢出。所以用括号保证先减后加才行。
二、处理加减法
现在进一步，如果输入的这个算式只包含加减法，而且不存在空格，你怎么计算结果？我们拿字符串算式1-12+3为例，来说一个很简单的思路：
1、先给第一个数字加一个默认符号+，变成+1-12+3。
2、把一个运算符和数字组合成一对儿，也就是三对儿+1，-12，+3，把它们转化成数字，然后放到一个栈中。
3、将栈中所有的数字求和，就是原算式的结果。
我们直接看代码，结合一张图就看明白了：
1 | int calculate(string s) { |
我估计就是中间带switch语句的部分有点不好理解吧，**i就是从左到右扫描，sign和num跟在它身后。**当s[i]遇到一个运算符时，情况是这样的：
所以说，此时要根据sign的 case 不同选择nums的正负号，存入栈中，然后更新sign并清零nums记录下一对儿符合和数字的组合。
另外注意，不只是遇到新的符号会触发入栈，当i走到了算式的尽头（i == s.size() - 1），也应该将前面的数字入栈，方便后续计算最终结果。
至此，仅处理紧凑加减法字符串的算法就完成了，请确保理解以上内容，后续的内容就基于这个框架修修改改就完事儿了。
三、处理乘除法
其实思路跟仅处理加减法没啥区别，拿字符串2-3*4+5举例，核心思路依然是把字符串分解成符号和数字的组合。
比如上述例子就可以分解为+2，-3，*4，+5几对儿，我们刚才不是没有处理乘除号吗，很简单，其他部分都不用变，在switch部分加上对应的 case 就行了：
1 | for (int i = 0; i < s.size(); i++) { |
乘除法优先于加减法体现在，乘除法可以和栈顶的数结合，而加减法只能把自己放入栈。
现在我们思考一下****如何处理字符串中可能出现的空格字符。其实也非常简单，想想空格字符的出现，会影响我们现有代码的哪一部分？
1 | // 如果 c 非数字 |
显然空格会进入这个 if 语句，但是我们并不想让空格的情况进入这个 if，因为这里会更新sign并清零nums，空格根本就不是运算符，应该被忽略。
那么只要多加一个条件即可：
1 | if ((!isdigit(c) && c != ' ') || i == s.size() - 1) { |
好了，现在我们的算法已经可以按照正确的法则计算加减乘除，并且自动忽略空格符，剩下的就是如何让算法正确识别括号了。
四、处理括号
处理算式中的括号看起来应该是最难的，但真没有看起来那么难。
为了规避编程语言的繁琐细节，我把前面解法的代码翻译成 Python 版本：
1 | def calculate(s: str) -> int: |
这段代码跟刚才 C++ 代码完全相同，唯一的区别是，不是从左到右遍历字符串，而是不断从左边pop出字符，本质还是一样的。
那么，为什么说处理括号没有看起来那么难呢，因为括号具有递归性质。我们拿字符串3*(4-5/2)-6举例：
1 | calculate(`3*(4-5/2)-6`) |
可以脑补一下，无论多少层括号嵌套，通过 calculate 函数递归调用自己，都可以将括号中的算式化简成一个数字。换句话说，括号包含的算式，我们直接视为一个数字就行了。
现在的问题是，递归的开始条件和结束条件是什么？遇到(开始递归，遇到)结束递归：
1 | def calculate(s: str) -> int: |
你看，加了两三行代码，就可以处理括号了，这就是递归的魅力。至此，计算器的全部功能就实现了，通过对问题的层层拆解化整为零，再回头看，这个问题似乎也没那么复杂嘛。
五、最后总结
本文借实现计算器的问题，主要想表达的是一种处理复杂问题的思路。
我们首先从字符串转数字这个简单问题开始，进而处理只包含加减法的算式，进而处理包含加减乘除四则运算的算式，进而处理空格字符，进而处理包含括号的算式。
可见，对于一些比较困难的问题，其解法并不是一蹴而就的，而是步步推进，螺旋上升的。如果一开始给你原题，你不会做，甚至看不懂答案，都很正常，关键在于我们自己如何简化问题，如何以退为进。
退而求其次是一种很聪明策略。你想想啊，假设这是一道考试题，你不会实现这个计算器，但是你写了字符串转整数的算法并指出了容易溢出的陷阱，那起码可以得 20 分吧；如果你能够处理加减法，那可以得 40 分吧；如果你能处理加减乘除四则运算，那起码够 70 分了；再加上处理空格字符，80 有了吧。我就是不会处理括号，那就算了，80 已经很 OK 了好不好。
我们要支配算法，而不是被算法支配。如果这种思维方式对大家有些启发，希望点个在看分享。