有了BFS，困难的谜题也不过如此，一个模板就够了
模板BFS，其英文全称是Breadth First Search，中文叫广度优先搜索，从根节点开始遍历，然后遍历根节点的子节点，所有子节点访问到后再遍历子节点的子节点，也就是根据深度每一层每一层的遍历。一般会用到队列和字典这两种数据结构。队列用于存储枚举的节点集合，字典用于记录节点是否访问过，用于排重。
对于一般的迷宫类谜题来说，该算法可以枚举所有的路径，由于它是按层序遍历的，所以当到达终点时，它得到的路径一定是最短的，这也是该算法奏效的原因。
现在的问题的关键就是如何将节点的子节点抽象出来，也就是说从一个状态可以衍生出的所有状态。我们用children函数来表示这个过程，这个函数接收一个输入，得到一个集合。从数据结构上看，是指返回某个节点的所有子节点集合，从现实问题来看，是指从一个状态，只进行最简化（不可拆分）的一步操作能到达的所有状态。
12345678910111213141516171819def children(status): ...def solution(): start = ... end = ... queue = [(start,0)] ...
一个模板搞定各种背包问题
前言背包问题实际上是动态规划的一种经典应用，本文想通过介绍一种模板用于解决各种背包问题。
模板统一采用二维数组来表示动态规划的状态，其中行表示物品的价值（或体积、大小、重量等），列表示背包的容量（或目标值）。
行和列都增加了一位，即从1开始计数，一来可以避免边界检查，二来dp[...][target]变得有意义，而非dp[...][target-1]，具体值和数组索引能够对上。根据不同题意来初始化dp，需要注意的是只要涉及到取物品的值，我们需要对索引减1，因为我们是从1开始计数的。
接下来分三种情况考虑动态规划中的状态转移表达式：
完全背包（每件物品可以无限使用）：dp[i][j]=OPERATE(dp[i-1][j],dp[i][j-objs[i-1]])。这里的OPERATE可以是sum、max、or视具体的问题而定。第二个表达式的索引是i。
1234567891011def bag_problem(self, bag: int, objs: List[int]) -> int: n=len(objs)+1 #将物品数量增加1，避免边界检查 #以下两行初 ...
装饰模式(Decorator)
意图装饰模式是一种结构型模式，允许你通过将对象放入包含行为的特殊封装对象中来为原对象绑定新的行为。
问题假设你正在开发一个提供通知功能的库，其他程序可使用它向用户发送关于重要事件的通知。
库的最初版本基于通知器Notifier类，其中只有很少的几个成员变量，一个构造函数和一个send发送方法。该方法可以接收来自客户端的消息参数，并将该消息发送给一系列的邮箱，邮箱列表则是通过构造函数传递给通知器的。作为客户端的第三方程序仅会创建和配置通知器对象一次，然后在有重要事件发生时对其进行调用。
此后某个时刻，你会发现库的用户希望使用除邮件通知之外的功能。许多用户会希望接收关于紧急事件的手机短信，还有些用户希望在微信上接收消息，而公司用户则希望在 QQ 上接收消息。
这有什么难的呢？首先扩展通知器类，然后在新的子类中加入额外的通知方法。现在客户端要对所需通知形式的对应类进行初始化，然后使用该类发送后续所有的通知消息。
但是很快有人会问：“为什么不同时使用多种通知形式呢？如果房子着火了，你大概会想在所有渠道中都收到相同的消息吧。”
你可以尝试创建一个特殊子类来将多种通知方法组合在一起以解决该 ...
组合模式(Composite)
意图组合模式是一种结构型模式，你可以使用它将对象组合成树状结构，并且能像使用独立对象一样使用它们。
问题如果应用的核心模型能用树状结构表示，在应用中使用组合模式才有价值。
例如，你有两类对象：产品和盒子。一个盒子中可以包含多个产品或者几个较小的盒子。这些小盒子中同样可以包含一些产品或更小的盒子，以此类推。
假设你希望在这些类的基础上开发一个定购系统。订单中可以包含无包装的简单产品，也可以包含装满产品的盒子……以及其他盒子。此时你会如何计算每张订单的总价格呢？
你可以尝试直接计算：打开所有盒子，找到每件产品，然后计算总价。这在真实世界中或许可行，但在程序中，你并不能简单地使用循环语句来完成该工作。你必须事先知道所有产品和盒子的类别，所有盒子的嵌套层数以及其他繁杂的细节信息。因此，直接计算极不方便，甚至完全不可行。
解决方案组合模式建议使用一个通用接口来与产品和盒子进行交互，并且在该接口中声明一个计算总价的方法。
那么方法该如何设计呢？对于一个产品，该方法直接返回其价格；对于一个盒子，该方法遍历盒子中的所有项目，询问每个项目的价格，然后返回该盒子的总价格。如果其中某个项目是小一号的盒子 ...
责任链模式(ChainOfResponsibility)
意图责任链模式是一种行为型模式，允许你将请求沿着处理者链进行发送。收到请求后，每个处理者均可对请求进行处理，或将其传递给链上的下个处理者。
问题假如你正在开发一个在线订购系统。你希望对系统访问进行限制，只允许认证用户创建订单。此外，拥有管理权限的用户也拥有所有订单的完全访问权限。
简单规划后，你会意识到这些检查必须依次进行。只要接收到包含用户凭据的请求，应用程序就可尝试对进入系统的用户进行认证。但如果由于用户凭据不正确而导致认证失败，那就没有必要进行后续检查了。
在接下来的几个月里，你实现了后续的几个检查步骤。
一位同事认为直接将原始数据传递给订购系统存在安全隐患。因此你新增了额外的验证步骤来清理请求中的数据。
过了一段时间，有人注意到系统无法抵御暴力密码破解方式的攻击。为了防范这种情况，你立刻添加了一个检查步骤来过滤来自同一 IP 地址的重复错误请求。
又有人提议你可以对包含同样数据的重复请求返回缓存中的结果，从而提高系统响应速度。因此，你新增了一个检查步骤，确保只有没有满足条件的缓存结果时请求才能通过并被发送给系统。
检查代码本来就已经混乱不堪，而每次新增功能都会使其更加 ...
享元模式(Flyweight)
意图享元模式是一种结构型模式，它摒弃了在每个对象中保存所有数据的方式，通过共享多个对象所共有的相同状态，让你能在有限的内存容量中载入更多对象。
问题假如你希望在长时间工作后放松一下，所以开发了一款简单的游戏：玩家们在地图上移动并相互射击。你决定实现一个真实的粒子系统，并将其作为游戏的特色。大量的子弹、导弹和爆炸弹片会在整个地图上穿行，为玩家提供紧张刺激的游戏体验。
开发完成后，你推送提交了最新版本的程序，并在编译游戏后将其发送给了一个朋友进行测试。尽管该游戏在你的电脑上完美运行，但是你的朋友却无法长时间进行游戏：游戏总是会在他的电脑上运行几分钟后崩溃。在研究了几个小时的调试消息记录后，你发现导致游戏崩溃的原因是内存容量不足。朋友的设备性能远比不上你的电脑，因此游戏运行在他的电脑上时很快就会出现问题。
真正的问题与粒子系统有关。每个粒子（一颗子弹、一枚导弹或一块弹片）都由包含完整数据的独立对象来表示。当玩家在游戏中鏖战进入高潮后的某一时刻，游戏将无法在剩余内存中载入新建粒子，于是程序就崩溃了。
解决方案仔细观察粒子Particle类，你可能会注意到颜色（color）和精灵图（spri ...
中介者模式(Mediator)
意图中介者模式是一种行为型模式，能让你减少对象之间混乱无序的依赖关系。该模式会限制对象之间的直接交互，迫使它们通过一个中介者对象进行合作。
问题假如你有一个创建和修改客户资料的对话框，它由各种控件组成，例如文本框（TextField）、复选框（Checkbox）和按钮（Button）等。
某些表单元素可能会直接进行互动。例如，选中“我有一只狗”复选框后可能会显示一个隐藏文本框用于输入狗狗的名字。另一个例子是提交按钮必须在保存数据前校验所有输入内容。
如果直接在表单元素代码中实现业务逻辑，你将很难在程序其他表单中复用这些元素类。例如，由于复选框类与狗狗的文本框相耦合，所以将无法在其他表单中使用它。你要么使用渲染资料表单时用到的所有类，要么一个都不用。
解决方案中介者模式建议你停止组件之间的直接交流并使其相互独立。这些组件必须调用特殊的中介者对象，通过中介者对象重定向调用行为，以间接的方式进行合作。最终，组件仅依赖于一个中介者类，无需与多个其他组件相耦合。
在资料编辑表单的例子中，对话框（Dialog）类本身将作为中介者，其很可能已知自己所有的子元素，因此你甚至无需在该类中引入新的依 ...
备忘录模式(Memento)
意图备忘录模式是一种行为型模式，允许在不暴露对象实现细节的情况下保存和恢复对象之前的状态。
问题假如你正在开发一款文字编辑器应用程序。除了简单的文字编辑功能外，编辑器中还要有设置文本格式和插入内嵌图片等功能。
后来，你决定让用户能撤销施加在文本上的任何操作。这项功能在过去几年里变得十分普遍，因此用户期待任何程序都有这项功能。你选择采用直接的方式来实现该功能：程序在执行任何操作前会记录所有的对象状态，并将其保存下来。当用户此后需要撤销某个操作时，程序将从历史记录中获取最近的快照，然后使用它来恢复所有对象的状态。
让我们来思考一下这些状态快照。首先，到底该如何生成一个快照呢？很可能你会需要遍历对象的所有成员变量并将其数值复制保存。但只有当对象对其内容没有严格访问权限限制的情况下，你才能使用该方式。不过很遗憾，绝大部分对象会使用私有成员变量来存储重要数据，这样别人就无法轻易查看其中的内容。
现在我们暂时忽略这个问题，假设对象都像嬉皮士一样：喜欢开放式的关系并会公开其所有状态。尽管这种方式能够解决当前问题，让你可随时生成对象的状态快照，但这种方式仍存在一些严重问题。未来你可能会添加或删除一 ...
模板方法模式(TemplateMethod)
意图模板方法模式是一种行为型模式，它在超类中定义了一个算法的框架，允许子类在不修改结构的情况下重写算法的特定步骤。
问题假如你正在开发一款分析公司文档的数据挖掘程序。用户需要向程序输入各种格式（PDF、DOC 或 CSV）的文档，程序则会试图从这些文件中抽取有意义的数据，并以统一的格式将其返回给用户。
该程序的首个版本仅支持 DOC 文件。在接下来的一个版本中，程序能够支持 CSV 文件。一个月后，你“教会”了程序从 PDF 文件中抽取数据。
一段时间后，你发现这三个类中包含许多相似代码。尽管这些类处理不同数据格式的代码完全不同，但数据处理和分析的代码却几乎完全一样。如果能在保持算法结构完整的情况下去除重复代码，这难道不是一件很棒的事情吗？
还有另一个与使用这些类的客户端代码相关的问题：客户端代码中包含许多条件语句，以根据不同的处理对象类型选择合适的处理过程。如果所有处理数据的类都拥有相同的接口或基类，那么你就可以去除客户端代码中的条件语句，转而使用多态机制来在处理对象上调用函数。
解决方案模板方法模式建议将算法分解为一系列步骤，然后将这些步骤改写为方法，最后在“模板方法”中依次调 ...
外观模式(Facade)
意图外观模式是一种结构型模式，能为程序库、框架或其他复杂类提供一个简单的接口。
问题假设你必须在代码中使用某个复杂的库或框架中的众多对象。正常情况下，你需要负责所有对象的初始化工作、管理其依赖关系并按正确的顺序执行方法等。
最终，程序中类的业务逻辑将与第三方类的实现细节紧密耦合，使得理解和维护代码的工作很难进行。
解决方案外观类为包含许多活动部件的复杂子系统提供一个简单的接口。与直接调用子系统相比，外观提供的功能可能比较有限，但它却包含了客户端真正关心的功能。
如果你的程序需要与包含几十种功能的复杂库整合，但只需使用其中非常少的功能，那么使用外观模式会非常方便，
例如，上传猫咪搞笑短视频到社交媒体网站的应用可能会用到专业的视频转换库，但它只需使用一个包含encode(filename, format)方法（以文件名与文件格式为参数进行编码的方法）的类即可。在创建这个类并将其连接到视频转换库后，你就拥有了自己的第一个外观。
结构
外观（Facade）提供了一种访问特定子系统功能的便捷方式，其了解如何重定向客户端请求，知晓如何操作一切活动部件。
创建附加外观（Additional Fa ...