Category: Data Structure and Algorithms

今天向大家介绍另一个图的宽度优先遍历示例-最小基因变化，具体题目的内容请见引文1。这里描述一下问题的分析思路，并给出一个实现仅供参考，期待能看到更多更优秀的代码实现，从中学习以不断进步。 首先我们可以将每一个基因建模为一个图节点，如果两个节点之间只有一个基因变化，则可以认为两个节点相邻，距离为1。距离大于1的两个节点可以不考虑其距离特性（默认为-1，表示为不直接相连）。关于图的表示问题，这里可以用矩阵进行表示，而且由于对称性，我们可以只利用上矩阵来进行图的搜索。 关于起始节点，如果在gene bank里边，则以起始节点开始进行图的宽度优先搜索，如果不再gene bank里边，则需要从gene bank里边去寻找与该节点的距离为1的所有节点作为候选起始节点，然后对所有可能的起始节点，依次调用图的宽度优先遍历搜索找到最短路径。因为每次都只改变一个基因，而且从起始节点到目标节点的距离已经定下来了（按顺序计算不同字母的个数），因此如果找到，我们可以从目标节点逆序看过来，就知道这个最小路径数就是距离（当然要通过搜索才能找到这样的路径），比如起始点和终点的距离为2，有可能搜索的时候，第一个后继节点和第二个后继节点与起始节点的距离都为1，但是第一个后继节点可能与重点的距离为3（又加了一个不同的基因），因此在最短路径搜索的时候会选择基于第二个后继节点。基于此我们可以得出结论，要么没有路径（返回-1），要么就等于起始节点和目标节点的不同基因数（也可能有多个路径，只要有一个路径找到即可返回，基于这点可以对搜索进行优化）。 具体实现代码可以参看引文2，欢迎读者提出优化建议，由于撰写匆忙加以思考过程可能不够全面深入，以及针对上述的问题分析中有任何问题也欢迎提出意见建议。 References

图（graph）相关的数据结构在解决实际问题时也会常用到，这里向读者介绍几个相关应用题目并给出解决思路分析和代码实现，欢迎读者朋友们针对相关问题提出意见和建议，用更好的思路和更加高效的方法去解决。 问题1：参考引文1的描述（这里就不再花文字描述问题本身），理解题目确实要花点时间，这里用图示辅以简单的文字重复描述一下，如下图所示，方格编号从左下角开始连续交错方向按数字递增进行编码，下图的示例对应着如下的输入数据：输入：board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]。可以看出从最后一行开始，第二个格子的数字为15，意思是从2到15(第四行第三列)安排了一个梯子或蛇，可以直接传送不算挪动的步骤，这样到达目标所在地分别是从1->2,15->17,13->14,35->36,四步即可到达。 首先，我们来分析一下题目的含义和根据场景用合适的数据结构建模相关问题，首先根据board去解析数据，构造合理的数据结构和算法解决问题。我们可以看到目标方格 next的编号符合范围是[curr + 1, min(curr + 6, n2)]，可以理解为从curr（当前方格的位置索引）到这些范围内的任何一个值都存在着一条边（等值边，边长为1，没有长短优先级），比如1到2-7这些格子都可以直接到达，因此我们可以将这个问题构建为一颗动态的搜索图。从根节点位置1开始，如存在着节点有梯子和蛇，则同时添加一条curr到梯子或蛇的终点位置编号的边（不需要满足next节点的1-6step的约束，而且这里特别注意一下，规则中说明梯子或蛇不能连续跳，如不能梯子跳过一些格子再连续梯子跳过一些格子），按照上述逻辑该问题为一颗有向图（如13到17存在着边，17到13也存在着边，13到17存在边时board[13]=17,17到13存在边时，即可以从位置17直接跳到13位置时board[17]=13）。 因此上述的问题就转化为了用基于图的深度优先遍历或宽度优先遍历去查找最短路径问题，搜索最短路径用宽度搜索更加合适，因为宽度搜索的过程中第一个达到目标位置的即为路径长度，而深度优先遍历算法需要遍历整个图（也存在着一些剪枝优化的行为）才能找到最短路径问题。 参考引文2提供了两个代码实现，其中第一个提供了深度优先遍历算法的实现，而且可以将搜索可能的路径都列出来，其实现主要采用了回溯递归的方法，特别需要注意的是递归过程中由于子递归返回后状态恢复的问题，由于基于深度优先遍历性能不够够，在某些测试题目上达不到时间要求，因此这道题的更为合理的方法是宽度优先遍历，采用队列结构来实现，将同一宽度的节点先后依次入队列，然后依次pop并将下一个层级的依次入栈，保证每一个访问的节点都是访问的深度最浅的某一个节点。(Solution类为基于深度优先遍历的实现，Solution2为参考的宽度优先遍历的代码，其中深度优先遍历方法做了一定的扩充，可以支持将所有可能的路径都输出出来保存到文件中）。欢迎读者对代码实现提出问题意见和建议，以便更好的去进步。 References

今天向大家介绍一种特殊的属性结构的应用，主要是介绍几个相关的题目的分析思路及相关实现。 题目1的描述见参考引文1，为了实现方便起见，Trie树中的单词都是小写英文中的26个字母。参考引文1的网页右边同时提供了一种基于递归的实现，同时求字符字串使用的是std::string类的substr函数（需要注意一下这个函数的参数的含义，第一个参数表示字串起始位置，第二个参数表示字串长度，而不是字串终止位置）。但是这个问题的推荐解法请参考引文2，相对第一种实现有两个地方的明显改进，第一个地方在于通过“for (char ch : word)”访问字符串的每一个单词，而且通过for方式避免了递归调用函数，节省了系统的执行资源。 题目2的要求是添加和搜索单词，具体描述参考引文3，这道题目在上述的基础上做了一定的扩展，支持通配符，需要注意一些边界条件，稍不注意就容易在某些情况出现bug。同时为了应对通配符的情况，代码中某些地方用到了递归调用。总体上也是一种扩展的前缀树应用，具体实现可以参考引文3网页的右边的代码。 题目3的详细描述请见参考引文4，这道题目的要求是已经有词汇表，根据矩形单词盘板的字母排列规则去核实词汇表中的哪些单词可以从矩形单词盘板中排列（字母之间只能和上下左右相连）得出。这里给出我的思路（欢迎读者给出更加高效的解决方案），首先通过按照题目1或2的方法根据词汇表去构建前缀树（一种特殊构造的词汇表），然后根据从矩形框中的每一个位置进行上下左右四个方向的搜索（需要考虑矩形的边界情况进行剪枝），可以理解为对一颗四叉树进行深度优先搜索，参考引文6提供了一个实现，这里也是一种回溯算法，在代码实现的过程中需要考虑回溯状态的复位。 引文5提供了上述三个问题的各一种解决方法，在前面的部分代码没有充分的从效率上进行优化，不过也可以从三个题目中去互相借鉴更优的写法。 References

LRU缓存机制在操作系统和其他缓存系统中常会用到，这里的题目要求是：1、以整数key，value键值对的形式进行存取；2、以一定的容量进行初始化；3、实现get和put操作，如果get传入的key有对应的value值则返回value，否则返回-1，put如果已经有key对应的cache，则更新value值，如果put时容量超限，则逐出最久未使用的关键字。并要求这些实现在O(1)的复杂度里完成。有名的缓存系统redis就是基于LRU的缓存机制实现的。 这道题如果读者没有较为系统的学习和刷题数据结构和算法，也许想不到用哈希表和双向链表相结合去实现，这道题目是数据结构的一道综合题在实际场景下的应用，主要考察两个点，1、哈希函数的即时O(1)时间复杂度寻址能力及其实现（哈希函数功能可以直接用unordered_map数据结构来实现）；2、双向链表的实现，双向链表支持从中间任何位置挪出节点并放置到表头，双向链表的表头和表尾的节点都可以作为哨兵节点（用变量存储head和tail），这样双向链表就方便实现O(1)时间内移动节点。这里补充下hash函数和双向链表的的相关知识细节供大家参考，欢迎读者关于这些内容提出问题和意见建议。 首先哈希函数可以将整数或字符串进行映射为特定范围内的整数值(取模运算，字符串作为输入的哈希函数有多种，如简单的将每个字符的ascii相加等），这样就可能存在着不同的输入值映射为相同结果的可能（如15%10和25%10都等于5）。这样不同的输入映射到同一个结果就需要解决冲突问题（hash collision)，解决hash冲突的方法有链式地址法(chaining)和开放寻址法（open addressing）。链式地址法的思想是相同结果的输入(key)所对应的value（基础树类型外也支持任何可扩展的灵活自定义的类型）值存放到该hash函数结果对应的链表中（hash函数的结果值表示的含义是以链表的节点指针类型申请的数组对应的位置的下标索引，hash值所对应的数组位置存放链表的表头）。开放寻址法的思想是通过探查（probe）去按一定的规则继续寻找可能的空闲位置，常见的探查方法有一次探查（linear probing，即索引逐渐加1直至找到），二次探查（quadratic probing，逐渐加2的次方直至找到空闲位置）以及双重哈希（两个哈希函数，第一个用来计算初始映射位置，如出现冲突，则第二函数用来计算索引的搜索步长）。在标准模板库中提供了hash函数std:hash。unordered_map提供了灵活的使用哈希函数的方式，既可以用标准提供的，也可以用自定义的。 双向链表的实现也在这里做一下简要说明，双向链表的每一个节点都会保存两个临近节点的指针，即前驱节点和后继节点（头节点的前驱节点为空，尾节点的后续节点为空，如果是双向循环链表，则首尾相连，头节点的前驱节点为尾节点，尾节点的后继节点为头节点）。在本题中，双向链表的表尾节点为记录最久未访问的key（可以理解为双向链表从表头到表尾按时间先后顺序记录着这些key的访问记录），如果缓存已满，则需要将表尾节点更新为表头节点（key和value值用最近访问的值去更新），表尾的前置节点更新为表尾节点。这里为了直接能访问表尾节点，需要在程序中将表尾节点也作为哨兵节点。如果get的key为中间某个节点，则可以通过hash函数首先找到该节点，并将该节点挪动到表头更新为表头节点，同时也说明当前的key是最近访问的。实现了LRU的按时间排序访问节点的功能，并且由于hash函数的O(1)复杂度特性，也保证了LRU的O(1)访问效率要求。 References

动态规划的题目需求各异，想法也差别比较大，有时候找出状态转移方程并不是那么容易的事情，需要具体问题具体分析。今天这篇文章将要下大家介绍一种新的基于动态规划解决的题目，并辅以自己的分析思路的阐述过程，欢迎读者基于此提出问题意见和建议。 题目的内容如下：给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。返回一个表示可访问单元格最大数量的整数。 下面简要阐述一下我的思路分析以及一个不错的参考答案： 可能的思路1：我们先只针对问题本身，而不是提示解决的具体方法去尝试分析问题，我们可以针对矩阵的每个位置(i,j)去找到它的该行和列的可能路径(row[i][j]，为矩阵当前行中比当前单元格mat[i][j]值要大的元素的集合，同理可以找出col[i][j]),矩阵中每个元素找出之后，就可以通过树搜索的方式，找出mat[i][j]所有可能路径中最大的(搜索树中从根节点到叶子节点的最大路径数字，经过简单验证可以得出当前位置在同一行和同一列的candidate中，必然要经过同行或者同列中比它大的最小的值，因为其他大的值可以通过这个值去抵达，因此同行和同列中的大的元素可以增序进行排列，而且可以以一颗二叉树来进行构建搜索树，按行行走为左子树，按列行走为右子树）。但是问题是要针对每个元素去找这样的最大路径，所需要的时间复杂度肯定就比较高。当然也可以不用每个元素都要调用这样的搜索树，可以基于已经搜索出来的和相邻节点的大小关系算出附近节点所能访问的单元格的最大数量。还有基于当前节点去遍历的这颗最大路径和上的路径上的每一个节点的最大值也是确定的（不仅如此，每一个路径节点的值都是最大值）。这样也可以基于此去优化搜索过程。 可能的思路2（参考答案）：基于思路1，可以进行进一步的优化，基于整个矩阵可以建立一颗有向无环图（不一定是树），同一行（列）中按节点顺序构造有向边(如果存在同一行或列有相同值的时候，可以加入一个dummy节点)，然后基于有向无环图（不一定联通，可能有多个分量组成）去找到最长的路径，具体可以用动态规划的算法，后面有时间再介绍详细动态规划实现上的细节。 可能的思路3：基于初始值的多次迭代更新后收敛，比如每个元素位置的初始值可以设为其行和列中比它大的数字的个数的最大值。然后更新的规则是当前行和列中比它大的值的位置对应值里边的最大值加1，不断这个过程直至每个位置对应的结果值不再发生变化。 以上主要从解决思路上分别做了阐述，欢迎读者点评，如有逻辑问题欢迎读者批评指正，或者分享新的解题思路，谢谢。 References

今天向大家介绍一道二叉树的题目，题目问题比较新颖，我自己在做题的过程中也碰到了些问题，花了些时间才通过测试题的。在这里向大家介绍一下思路。 题目如下：二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。具体题目描述可以参考引文1。 这道题目的具有最大路径和的路径的特点为：1、是任意的二叉树，二叉树的节点的值没有规律；2、最大的路径除了根节点允许同时拥有左右子孩子外，其它节点只允许只有一个孩子(左孩子或右孩子，因为每对相邻节点之间都存在一条边，如果非根节点同时有左孩子和右孩子，则不满足相邻节点之间有边的情况）。3，最大路径有可能只有一个节点，也有可能这条路径的节点都属于树的非叶子节点。 总体思路采用类似于树的后序遍历算法，算法逻辑可以描述大体如下：1、如果为叶子节点，直接返回该节点的值；2、如果该节点只有左孩子，则递归调用左孩子返回最大的路径和max_left，这个路径和放入最大路径和的candidates里边，同时该节点值本身也放入candidates里边（是否冗余可能需要再确认一下），如果max_left大于0，则返回max_left + root->val;否则返回root->val。类似的情况是节点只有右孩子，不做过多阐述；3、节点同时具有左孩子和右孩子，则分别递归调用左孩子和右孩子的最大路径和函数返回值max_left,max_right。并将max_left,max_right中的大者max_left_right放入candidates，同时将max_left + root->val+max_right作为candidates，以及如果max_left_right大于0，则返回max_left_right+root->val的值作为root的调用函数以root节点作为参数的返回值。否则如果max_left_right小于0，则直接返回root->val的值作为以root的参数的调用函数的返回值。具体代码请参考引文2的实现 References

今天介绍一种特殊的数据结构-树状数组(binary index tree)，其巧妙利用了二进制的数学特性，对数组的索引下标的含义进行了特殊的定义，以方便对数组的任意区间内的元素进行求和。下面将简要向大家介绍一下其基本的原理。 为了求得一个数组中任意区间的元素的和，可以采用不同的方法，比较直接和朴素的方法是给出范围的区间，通过for循环去累加求和。但是这种方法求解的效率不高，如果数组的元素比较多，会影响程序的执行时间。树状数组通过巧妙的构造数组特定位置（下标）下的元素值的含义（通常为下标所映射的一定范围的元素的和），由于这种下标的巧妙映射，数组范围内任意区间的元素和都可以通过对应的较为少数的下标的元素的和去组成。而这种下标所对应数组元素范围的解析就是基于整数二进制编码的基本原理。下面将详细的通过示例进行介绍。 比如一个示例，求数组元素前15项的和。一般的数组每个索引下存放对应该位置的值，这样就需要做15次加法运算去求得所需的值。而这里我们的15的二进制表示为1111。如果不断的从右往左消除1，则可以分别由四个区间来组成，分别为（1110->1111]，(1100->1110],(1000,1100],(0000,1000]。而这几个区间可以分别看成是(14,15],(12,14],(8,12],(0,8]这几个区间的和，每个区间没有重叠（注意开闭区间的区别），假设数组的名称为treeindexarray，则treeindexarray[15]（1111）只表示15这个位置本身的值，treeindexarray[14](1110)表示13到14位置的和的值，treeindexarray[12]（1100）表示9到12位置的和的值，treeindexarray[8]代表1到8位置的和的值，这个对应范围和上述的区间是一致的。因此treeindexarray[8]+treeindexarray[12]+treeindexarray[14]+treeindexarray[15]这四个值相加的结果即为该数组的前15个元素之和，只需求4次加法即可。 更新数组中某个位置，其逻辑为该索引值为基础不断加上当前值的lowbit迭代直到索引越界。如数组中某个位置加或减去某个值，根据树状数组的定义，该索引之前的位置的值并不受影响。我们以简单的一个示例来进行说明，比如想把数组的第10个位置的值加上5（假设数组长度为31，32个元素但第索引为0处没有用到），则第10（二进制为1010）个位置本身要加上5，下一个加上5的位置为12（二进制为1100，根据上面的示例，其包含了9到12位置的值，因为10在内，所以也要加上5），再下一个需要加上5的位置的值为16（1100+lowbit(1100)，二进制为10000，该位置索引表示的是数组从1到16索引位置的和。由于16+lowbit(16)=32,查出了数组的边界，因此更新结束。比如求前面17（二进制为10001）个元素的和，则可以表示为（10000，10001],(00000,10000]两个区间的和。即为treeindexarray[17]+treeindexarray[16]，由于更新的第10个元素的位置已经在treeindexarray[16]中体现，所以最终的编码更新满足树状数组的逻辑定义。 在此进一步对lowbit的计算方式做一下说明。二进制编码的基本原理的基础上，求二进制数字最后一个为1的编码的位置的值得函数lowbit(x)，其计算方法利用到了计算机的二进制编码特性，在计算机中整数x的相反数-x的编码通常采用二进制补位方法（2’s Complement Representation，关于information encoding读者可以去了解更多的细节）。基于二进制补位表示法的机制，-x的二进制和x的二进制只在最右边编码为1的位置相同（其他位置均互补）。因此lowbit(x)= x&(-x)。 树状数组的应用场合可以参考引文中的开始的一个场景描述。后面有机会碰到更多的场景再在这里进行更新。 References

上一篇文章介绍了01背包问题及分析，这篇短文主要介绍一个有点不同的题目：完全背包问题。具体题目内容如下：有N种物品和一个容量是V的背包，每种物品都有无限件可用。第 𝑖 种物品的体积是𝑣𝑖，价值是𝑤𝑖。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。其中输入格式和样例等和上一篇文章一样，具体可以参考引文1链接。 问题分析：和01背包不同的是，每一种物体可以放多个（具体个数上限为V/v[i]）,从另一个角度灵活考虑，可以认为该问题可以转换为01背包问题。及一种物体可以看成是V/v[i]种不同的物体，但其价值相同。通过这样转换后完全背包问题就可以转化为01背包问题。转换的代码如下所示。其中dp_solver的递推计算和01背包中国的代码段是一样的。 下面的思路提供一种更简洁的实现，具体的状态转移方程有一定的变化，即当j>v[i]的时候，可以放入1到j/v[i]个物体，因此状态转移方程写为： dp[i][j] = max(dp[i-1][j-m*v[i]]+m*w[i], dp[i-1][j])（其中m=1,2,…j/v[i]） 具体代码如下(dp[1][j]的定义也有变化)： References

从这篇短文开始将准备陆续介绍一下动态规划中的背包问题，这次主要介绍01背包问题的求解方法及分析。所谓01背包问题，就是N个物体中每一个物体要么不放入背包（0状态），要么一个物体要完整的放入背包（1状态）。具体问题描述如下。 有 N件物品和一个容量是 V的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。输出格式输出一个整数，表示最大价值。数据范围0<N,V≤1000，0<vi,wi≤1000输入样例4 51 22 43 44 5输出样例：8 分析：我们可以看出，每个物体要么放入（状态为1），要么不放（状态为0）有两种状态，N种物体会有2的N次幂种状态（当然有些状态会不满足条件，如总容量超标），用这种组合枚举的方式计算量会比较大（算法复杂度）。下面就用深度优先搜索的方式去向大家介绍此种方法的实现。首先我们贴上代码如下： 上述代码的浅析过程如下：第一个参数idx表示已经从第一个物体搜索到第idx的物体的放置状态，spV表示当前idx个物品放置状态下还有spV剩余的容量。初始调用时的参数状态为dfs_solver(1, V)，这里为了方便，物体索引从1开始，根据c/c++以及python的语言规范，下表0的相关数据为冗余空间。在这里我们以上述的输入样例来说明深度优先遍历的搜索过程。如下图所示： 上述的基于深度优先遍历的递归实现方式是物品组合方式的一种实现，效率不是很高，因为有上述的递归搜索树的实现，在程序调用上，递归函数实现过程会涉及函数及其参数的多次入栈和退栈（寄存器的一些操作，可以参考引文），这也是影响效率的主要原因（基于递归也可以有一定的优化，如有的调用参数状态会重复，这样的状态调用可以将结果暂存起来）。 而动态规划是一种基于递推的实现，计算的中间过程不断朝着目标状态演进。动态规划的实现主要是要合理的定义状态矩阵和写出状态转移方程，这里我们用二维数组dp[i][j]来描述01背包的状态，其中第一个维度的i表示已经处理到第i个物体，第二个维度的j表示容量为j时背包所装下的所有可能物体的价值总和的最大值，因此问题下的最优结果为dp[N][V](为了表示方便，下标从1开始，在c/c++和python中会引起一定的空间浪费)。基于此状态矩阵表示，这里01背包的状态方程可以写成如下的等式： dp[i][j] = max(dp[i-1][j-v[i]]+w[i], dp[i-1][j])。 也就是遍历到第i个物体总容量为j的背包所能容下物体的总价值的最大值为下面两种状态下的较大的值： 第一种：dp[i-1][j-v[i]]+w[i]，为前i-1种物体在容量为j-v[i]的状态的最大值下再放入物体i后形成的值；第二种：dp[i-1][j]为前i-1种物体在容量为j的状态的最大值下不放入第i个物体的最大值。当然也要满足容量的约束条件，而且在i为1时，j只要大于v[1], 所有的后面的d[1][>v[1]]的值均为w[1]，dp[1][<v[1]]的值均为0，这个可以认为是作为初始化条件。因此，整个动态规划的逻辑代码可以表示为如下： 后续将继续向大家介绍关于背包相关问题的解决方案。 References