Month: June 2024

今天向大家介绍一道二叉树的题目，题目问题比较新颖，我自己在做题的过程中也碰到了些问题，花了些时间才通过测试题的。在这里向大家介绍一下思路。 题目如下：二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。具体题目描述可以参考引文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

树结构是数据结构中常常出现的，且用到非常多的一种数据结构。树结构中常见的有二叉树，二叉搜索树，AVL树以及B树等。树结构一般可以用递归去求解，如二叉树的遍历算法中，有先序，中序和后续遍历，一般的树结构的遍历中，有DFS（深度优先遍历）和BFS（宽度优先遍历）等都是用递归来实现。今天的实例中，有用递归直接实现的，也有用递归间接实现的。具体问题要具体分析，下面将要介绍几种具体的方法。 实例1：判断一颗二叉树是否是一个有效的二叉搜索树？ 浅析：根据二叉搜索树的递归定义，其每个节点的左子树都要比当前节点小，其右子树都要比当前节点大。一个直观的想法是：1、首先判断根节点是否满足要求，如果不满足，直接返回false，程序停止；2、再递归判断左子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算；3、再递归判断右子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算。但仔细分析发现这个思路有缺陷，不能保证右子树的最小节点比根节点要大，或者左子树的最大节点比根节点要小。这道题可以先用中序遍历（可以用递归）的方式将结果存起来，因为二叉搜索树的中序遍历结果是有序的。通过检查中序遍历结果的有序性即可判断是否为二叉搜索树。 实例2：二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。 浅析：首先判断当前节点的值，如果比low要小，说明左子树都要比low小，直接递归调用右子树即可。反之如果比high值要大，则递归调用左子树。如果在low和hight之间（假设其值为val），则，左子树上，递归调用trim[low,val]或trim[low,high],右子树上递归调用trim[low,high],或trim[val, high]。 实例3：给定二叉树的根节点root ，返回所有左叶子之和。 浅析：比较容易判断是否为叶子节点，当为叶子节点时，还需要考虑其父节点指向的左孩子是否为当前的叶子节点。递归实现的示例代码如下： 实例4：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 浅析：通过递归可以找到要删除的节点，如果节点是叶子节点，则好办。如果不是叶子节点呢，这个时候需要找到该节点的后继节点（successor）进行替换，然后递归调用后继节点的删除操作。由于后继节点一般是右子树的最左边的节点（可能是叶子节点，可能是含有右子树的节点），删除相对比较容易，不会再次出现递归调用。这道题的具体分析可以参考引文中的说明，比较详细。 后续将继续分析更多的树类型的数据结构的不同的问题场景和解题思路。 Reference

动态规划(dynamic programming)是数据结构与算法中常用到的策略算法，一般是通过状态转移方程和初始状态来一起定义问题，从而将更大的问题转换为前面已经计算出结果的动态的更新的过程。动态规划的难点在于状态转移方程的定义，有得问题比较显而易见，而有的问题可能就比较难以定义，需要多从实际问题中总结相关的经验。 今天向大家介绍动态规划的三个示例，具体一一向大家进行介绍。 实例1：爬楼梯问题，也是经典的动态规划问题，描述如下：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 分析及解答，假设爬到n阶有methods[n]种方法，则有两种可能，先爬到n-2阶，然后跨2个台阶到达n阶，或者先爬到n-1阶，然后跨1个台阶达到n阶。因此状态转移方程为：dp[n]=dp[n-1]+dp[n-2]。初始状态为dp[0]=0,dp[1]=1,dp[2]=2。然后就可以用递推来进行循环计算了。 实例2：找零钱问题，给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。 分析及解答：假设所需最少的硬币个数为f[amount]，则状态转移方程可以表示为f[amount]=min(f[amount-conins[j]+1)，其中要求满足amount-conins[j]>0的所有的j。在递推求解的过程中，可以用双重循环来实现，外层从1到amount，内层j从0到硬币的个数-1，然后循环有个条件，及当前amount-coins[j]要大于零。 实例3：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。 分析和解答：这是和第二个问题相似但思路差别较大的问题，这里不做详细分析，直接先给出状态转移方程并作出一定的解释。状态转移方程为：problem(k,i) = problem(k-1, i) + problem(k, i-k)。其中problem(k,i) 为一个二维的状态，其中第一个维度表示用到了前面的k个硬币，i表示当前的凑的金额。problem(k-1, i)表示只用到了前面k-1个硬币就已经凑到了i，不需要第k个硬币，problem(k, i-k)表示用到了前面k个硬币凑到了i-k，已经用到了第k个硬币。 关于代码实现，后续有机会再向大家进行分享，也希望自己后面有机会向大家逐步整理关于数据结构和算法的较为系统全面的介绍，欢迎大家提出意见和建议。