首页
精选文章回溯法查看全文回溯法是一种选优搜索法，在回溯过程中按选优条件向前搜索或者试探，以达到目标结果。但当探索到某一步时，发现之前的选择路径不能达成目标或者不是最优的方案，就沿着已经选择的路径进行回退重新选择，这种按照一定规则试探，并且试探失败就回退到一定状态重新试探的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法解决的典型问题一般分为三类，分别是子集问题，组合问题，以及排列问题。 解决一个回溯问题，实际上就是一个决策树的遍历过程。一般情况下分为三步： 确定试探路径，也就是之前试探中的选择集合。 确定当前的选择条件，当前可以进行选择的选择列表。 结束条件是值到达决策树底层，可以结束本次回溯的条件。 回溯法流程的通用模版可以抽象如下： 回溯(路径, 选择列表){ 如果到达终止条件： 将该路径加入结果列表； 循环选择列表: #将该选择添加到选择路径 路径.添加(选择) 回溯(路径, 选择列表) # 撤销选择 路径.删除(选择） } 子集问题 给定一个数组，返回它所有的子集。如nums=[1, 2, 3] 返回的是[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]。 集合中有有三个数组，每次从集合中可能选择的有4个值，分别是1、2、3和空。 返回4个可选值集合所有的子集，试探路径最长为4。 所以当路径长度为4时，则将该路径存入结果集中。二叉树遍历查看全文二叉树的遍历，从和根节点的关系来看，可以分为前序遍历，中序遍历，后序遍历三种方式，这三种遍历形式在部分场景也被称之为先根遍历，中根遍历，后根遍历。从遍历的方式来看，可以分为广度优先遍历和深度优先遍历。先序遍历 前序遍历二叉树是先遍历根节点，然后遍历左子树，最后遍历右子树。可以想象是绕着二叉树外围转一圈的路径。 非递归算法： 中序遍历 中序遍历是把先遍历左子树，然后遍历根节点，最后遍历右子树，所以中序遍历是从左到右遍历的，二叉树在平面上的投影就是中序遍历的结果。 非递归算法： 后序遍历 后序遍历是先遍历左子树，然后遍历右子树，最后遍历根节点，可以认为是和摘葡萄的过程类似，先从左到右把下面的葡萄摘了，然后再摘上面的葡萄。 递归算法： 非递归算法：两阶段提交查看全文两阶段提交（2PC）是分布式事务的一种实现方案。两阶段提交协议把分布式事务分成两个过程，分别是准备阶段和提交阶段，准备阶段和提交阶段都是由事务管理器（协调者）发起，资管管理器（事务参与者）接收协调者的指令完成事务的执行动作。 两阶段具体分工如下： 准备阶段：协调者向参与者发起指令，参与者评估自己的状态，如果参与者评估指令可以完成，参与者会写redo或者undo日志（这也是前面提起的Write-Ahead Log的一种），然后锁定资源，执行操作，但是并不提交。 提交阶段：如果每个参与者明确返回准备成功，也就是预留资源和执行操作成功，协调者向参与者发起提交指令，参与者提交资源变更的事务，释放锁定的资源；如果任何一个参与者明确返回准备失败，也就是预留资源或者执行操作失败，协调者向参与者发起中止指令，参与者取消已经变更的事务，执行undo日志，释放锁定的资源。 普通事务的提交也包括写数据阶段和提交阶段，例如Mysql的InnoDB引擎在提交之前，会写入undolog，修改BufferPool，在事务提交的时候会写入redolog。两阶段提交会将提交操作再分为两部分，例如准备提交的阶段会先准备写入redolog，之后写入binlog，再进行提交redolog。 准备阶段 两阶段事务的准备阶段，协调者会对所有的参与者发起准备的指令。 参与者接收到准备指令之后，进行事务操作，本环节的事务操作一般包括资源锁定，记录回滚日志（Undolog），执行成功会给协调者发送成功的返回，否则返回失败。 协调者收到所有参与者的返回都是成功时，而阶段提交会进入提交阶段。 协调者如果收到部分参与者的返回是失败的时候，则将成功的参与者进行回滚。… |
热门分类开源Golang消息队列JavaJavascriptLinuxMysqlNLPPHP事务内存管理分布式理论分类存储常用存储开源软件操作系统画图网络编程数据库算法虚拟化前端存储理论常用算法微服务数据结构算法应用计算机原理中间件共识算法分布式分治动态规划容器并发排序架构组件绘图工具网络协议编程语言理论算法思想树缓存架构C++字符串算法工程思想搜索
算法题库精选内容 |
