• 关于

    二叉搜索树

    的搜索结果

问题

二叉搜索树和最优二叉搜索树的时间复杂度各是多少?

知与谁同 2019-12-01 20:16:09 809 浏览量 回答数 2

问题

关于二叉搜索树搜索的递归算法

知与谁同 2019-12-01 20:16:28 487 浏览量 回答数 2

问题

编写非递归算法求二叉搜索树中关键字最小的元素。

知与谁同 2019-12-01 20:16:34 374 浏览量 回答数 3

阿里云试用中心,为您提供0门槛上云实践机会!

0元试用32+款产品,最高免费12个月!拨打95187-1,咨询专业上云建议!

问题

给定一个二叉搜索树(BST),找到树中第 K 小的节点。

Runt 2020-04-14 16:42:27 0 浏览量 回答数 1

回答

二叉搜索树 最好:以2为底n的对数 最坏:n 最优二叉搜索树 最好/最坏:以2为底n的对数

boxti 2019-12-02 01:25:12 0 浏览量 回答数 0

问题

B树、B-树、B+树、B*树之间的关系

游客bnlxddh3fwntw 2020-04-25 14:23:57 12 浏览量 回答数 1

回答

二叉查找树(BST,Binary Search Tree) ,又名二叉搜索树或二叉检索树,是一颗满足如下条件的树: 1、每个节点包含一个键值 2、每个节点有最多两个孩子 3、对于任意两个节点x和y,它们满足下述搜索性质: a、如果y在x的左子树里,则key[y] <= key[x] b、如果y在x的右子树里,则key[y] >= key[x] 最优二叉查找树(Optimal BST,Optimal Binary Search Tree) 最优二叉查找树是使查找各节点平均代价最低的二叉查找树。具体来说就是:给定键值序列 K = <k1 , k2 , . . . , kn >,k1 < k2 <· · · < kn ,其中键值ki ,被查找的概率为pi ,要求以这些键值构建一颗二叉查找树T,使得查找的期望代价最低(查找代价为检查的节点数)。 下面是对于查找期望代价的解释: 对于键值ki , 如果其在构造的二叉查找树里的深度(离开树根的分支数)为depthT(ki ),则搜索该键值的代价= depthT(ki ) +1(需要加上深度为0的树根节点)。由于每个键值被查找的概率分别为pi ,i=1,2,3…,n。所以查找期望代价为: E[T的查找代价] = ∑i=1~n (depthT(ki ) +1) · pi 时间复杂度 1、穷举 穷举构造最优二叉查找树,其实就是这样的一个问题: 给一个拥有n个数的已排序的节点,可以将其构造成多少种不同的BST(用来找到一个最优的二叉查找树)。 设可以构造成T(n)个,那么枚举每一个元素作为根节点的情况,当第一个元素作为根节点时,其余n-1个构成右子树,无左子树,是n-1情况时的子问题, 共T(n-1)种;当第二个元素作为根节点时,左子树有1个元素,右子树有n-2个元素,根据乘法原理共有T(1)T(n-2)种情况……依此类推得 到:T(n) = T(0)T(n-1) + T(1)T(n-2) + T(2)T(n-3) + ...... + T(n-2)T(1) + T(n-1)T(0);此外,有T(0)=T(1)=1。 下面来求解T(n): 定义函数 f(x) = T(0) + T(1) · x + T(2) · x2 + ...... 那么有: f(x)2 = (T(0)2 ) + (T(0)T(1) + T(1)T(0)) · x + (T(0)T(2) + T(1)T(1) + T(2)T(0)) · x2 + ...... = T(1) + T(2) · x + T(3) · x2 + ...... = (f(x) - T(0)) / x = (f(x) - 1) / x 这样解方程得到 f(x) = [1 - (1 - 4x)1/2 ] / 2x 右边进行泰勒展开,再与定义式比较最终得到: T(n) = (2n)! / (n!(n+1)!) 然后根据Stirling公式:n! ~ (2πn)1/2 · (n/e)n 于是有(2n)! / n!(n+1)! ~ (4n1/2 · 2n2n ) / (2n1/2 · nn · (2(n+1))1/2 · (n+1)n ) ~ 4n · (n+1)-3/2 · (n/(n+1))n ~ 4n · n-3/2 因此最后得到穷举方法构造最优二叉查找树的时间复杂度: T(n) = O(4n · n-3/2 ) 2、递归 实际上左右子树是互不影响的,不需要穷举所有左右子树的组合,所以不需要用乘法原理,加法原理就可以了,这样式子变为: T(n) = T(0) + T(n-1) + T(1) + T(n-2) + T(2) + T(n-3) + ...... + T(n-2) + T(1) + T(n-1) + T(0) = 2(T(0) + T(1) + T(2) + ...... + T(n-1)) = 3T(n-1) 所以得到T(n) = O(3n ) ,还是指数级的一个算法 3、动态规划 上面得到指数级算法的原因在于,计算了很多重复的子树情况,一些子树的查找代价被计算了很多遍;而一棵树如果是最优二叉搜索树,那么要么它是空树,要么它 的左、右子树也是最优二叉搜索树,因此只需要将子树的查找代价记录下来,采用记忆化搜索或者是自底向上的动态规划的方法,虽然需要消耗一定的空间,但可以 把时间复杂度从指数级降到多项式级,这些空间消耗也是可以接受的。 以下是采用自底向上的解法: 输入:键值序列 K = <k1 , k2 , . . . , kn >,概率序列 P = <p1 , p2 , . . . , pn > 输出:两个二维数组,Price[i][j]表示ki 到kj 构成的最优子树的查找代价,Root[i][j]表示表示ki 到kj 构成的最优子树的根节点位置(用于重构最优二叉查找树) 算法1 : For 子树大小size = 1 to n For 子树的起点start = 1 to (n - size + 1) //这样子树的终点即为 end = start + size - 1,长度为size For 该子树的所有节点作为根节点root = start to end 对于每个root,根据之前计算过的Price数组得到左右最优子树的代价,可直接得到该子树的代价price为: 左右子树的最优子树代价之和 + 所有节点的访问概率之和(因为所有节点都下降了一层) 在内层循环中找到代价最小的price和root分别记录在Price[start][end]和Root[start][end]中 下面分析这个算法的时间复杂度: 由于除了计算出我们最后需要得到的Price和Root二维数组,还产生了部分冗余的子树,因此不能简单的将算法归结为O(n2 )的算法。 对于子树大小为1时,我们考察了n个子树; 对于子树大小为2时,一共产生了(n - 1)个最优子树,但是在我们的每次考察中,都将子树的所有节点作为根节点考虑过一次,因此每得到1个大小为2的子树,我们需要考察2个不同的子树来找到一 个代价最小的,因此最后我们实际上考察了2(n - 1)个子树; 对于子树大小为3时,类似的,我们考察了3(n - 2)个子树; …… 对于子树大小为n时,我们考察了n个子树。 最后,我们一共考察了T(n) = n + 2(n - 1) + 3(n - 2) + ...... + n个子树。 求解这个公式依然可以借用之前的方法,定义函数 f(x) = 1 + 2x + 3x2 + ...... = (1 - x)-2 这样一来 f(x)2 = T(1) + T(2) · x + T(3) · x2 + ...... 再借用泰勒展开得到 T(n) = (n + 2)(n + 1)n/6 = O(n3 ) 或者把所有项视为n2,则有 T(n) ≤ n2 + n2 + n2 + n2 + ...... = (n+1)n2 ≤ 2n3 把中间n/2项都视为n/4 · 3n/4的话,则有 T(n) ≥ n/2 · n/4 · 3n/4 = (3/32)n3 根据时间复杂度的定义有 T(n) = O(n3 ) 下面介绍一个定理,可以借此把动态规划算法的时间复杂度进一步降到O(n2 ),详细的证明参见参考文献: 定理1 :Root[i][j-1] ≤ Root[i][j] ≤ Root[i+1][j] (Root数组定义见算法1) 也就是说,算法1的第3个For就可以不用循环子树中的所有节点了,只要循环另两个子树的根节点之间的范围就可以了。算法如下,红色的为修改的部分: 算法2 : For 子树大小size = 1 to n For 子树的起点start = 1 to (n - size + 1) //这样子树的终点即为 end = start + size - 1,长度为size For 该子树的所有节点作为根节点root = Root[start][end-1] to Root[start+1][end] 对于每个root,根据之前计算过的Price数组得到左右最优子树的代价,可直接得到该子树的代价price为: 左右子树的最优子树代价之和 + 所有节点的访问概率之和(因为所有节点都下降了一层) 在内层循环中找到代价最小的price和root分别记录在Price[start][end]和Root[start][end]中 在分析该算法的时间复杂度时应注意,考察的子树是与考察的内层循环中root数量一一对应的,而当start递进时,前一个root的终点正好等于后一个root的起点(算法中的红色部分),也就是说对于固定的size来说,考察的root的范围加起来应当首位相接 而且至多刚好覆盖 所有节点,因此对于每个size,最多只考察2n个root(这里缩放了一下),因此总共最多考察了2n · n = 2n2 个子树;另一方面,Root数组中每一个值对应得到的一个最优二叉查找树,也即至少需要考察n2 个子树。因此根据定义得到 T(n) = O(n2 )

小旋风柴进 2019-12-02 01:25:12 0 浏览量 回答数 0

回答

楼主要复习还是怎么。 归一下类: 1.排序:插入,选择,冒泡,快排,桶排序,堆排序,基数排序,计数排序,top-k问题; 2.搜索:深搜,广搜,递归,递推,回溯; 3.图:拓扑排序,kruskal算法,prim算法,bellman-ford算法,dijkstra算法,最大流; 4.动态规划,贪心算法,hash表; 5.树;(二叉查找树,二叉平衡树。。。) 6.其他:不相交集合的路径压缩,kmp,数论(最大公约数,中国余数定理。。),随机算法。 暂时就想到这么多了。

美人迟暮 2019-12-02 01:26:15 0 浏览量 回答数 0

回答

首先,有一些实际场景中的数据,天然地就是树结构。凡是符合每个对象有一个上级,多个下级的性质,就可以用树建模。比如管理树(老板和员工),家族树(父亲和孩子),文件系统树(文件夹和文件)。 另外,二叉搜索树(BST)可以比较高效地对数据进行排序。如果需要维护动态增减且要保持顺序的一组数据,就可以用BST。

管理贝贝 2019-12-02 01:22:08 0 浏览量 回答数 0

回答

B 树 即二叉搜索树: 1. 所有非叶子结点至多拥有两个儿子( Left 和 Right ); 2. 所有结点存储一个关键字; 3. 非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树; B- 树 是一种多路搜索树(并不是二叉的): 1. 定义任意非叶子结点最多只有 M 个儿 子;且 M>2 ; 2. 根结点的儿子数为 [2, M] ; 3. 除根结点以外的非叶子结点的儿子数为 [M/2, M] ; 4. 每个结点存放至少 M/2-1 (取 上整)和至多 M-1 个关键字;(至少 2 个关键 字) 5. 非叶子结点的关键字个数 = 指向儿 子的指针个数 -1 ; 6. 非叶子结点的关键字: K[1], K[2], …, K[M-1] ;且 K[i] < K[i+1] ; 7. 非叶子结点的指针: P[1], P[2], …, P[M] ;其中 P[1] 指向关键字小于 K[1] 的子树, P[M] 指向关键字大于 K[M-1] 的子树,其它 P[i] 指 向关键字属于 (K[i-1], K[i]) 的子树; 8. 所有叶子结点位于同一层 B+ 树 B+ 树是 B- 树的变体,也是一种多路搜索 树: 1. 其定义基本与 B- 树 同,除了: 2. 非叶子结点的子树指针与关键字个数相同; 3. 非叶子结点的子树指针 P[i] , 指向关键字值属于 [K[i], K[i+1]) 的子树( B- 树是开区间); 5. 为所有叶子结点增加一个链指针; 6. 所有关键字都在叶子结点出现; 如:( M=3 ) B+ 的搜索与 B- 树也基本相同,区别是 B+ 树只有达到叶子结点才命中( B- 树可 以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找; B+ 的特性: 1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的; 2. 不可能在非叶子结点命中; 3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层; 4. 更适合文件索引系统; B 树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点; B- 树:多路搜索树,每个结点存储 M/2 到 M 个关键字,非叶子结点存储指向关键字范围的子结点; 所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中; B+ 树:在 B- 树基础上,为叶子结点增加链 表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引; B+ 树总 是到叶子结点才命中; B* 树:在 B+ 树基础上,为非叶子结点也增 加链表指针,将结点的最低利用率从 1/2 提高到 2/3 ;

程序员诗人 2019-12-02 00:24:59 0 浏览量 回答数 0

回答

请参考个人博客:https://blog.csdn.net/u010870518/article/details/79450295 在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出B树以及为什么MySQL数据库索引选择使用B+树! 学过数据结构的一般对最基础的树都有所认识,因此我们就从与我们主题更为相近的二叉查找树开始。 一、二叉查找树 (1)二叉树简介: 二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质: 1、任意节点左子树不为空,则左子树的值均小于根节点的值; 2、任意节点右子树不为空,则右子树的值均大于于根节点的值; 3、任意节点的左右子树也分别是二叉查找树; 4、没有键值相等的节点; 上图为一个普通的二叉查找树,按照中序遍历的方式可以从小到大的顺序排序输出:2、3、5、6、7、8。 对上述二叉树进行查找,如查键值为5的记录,先找到根,其键值是6,6大于5,因此查找6的左子树,找到3;而5大于3,再找其右子树;一共找了3次。如果按2、3、5、6、7、8的顺序来找同样需求3次。用同样的方法在查找键值为8的这个记录,这次用了3次查找,而顺序查找需要6次。计算平均查找次数得:顺序查找的平均查找次数为(1+2+3+4+5+6)/ 6 = 3.3次,二叉查找树的平均查找次数为(3+3+3+2+2+1)/6=2.3次。二叉查找树的平均查找速度比顺序查找来得更快。 (2)局限性及应用 一个二叉查找树是由n个节点随机构成,所以,对于某些情况,二叉查找树会退化成一个有n个节点的线性链。如下图: 大家看上图,如果我们的根节点选择是最小或者最大的数,那么二叉查找树就完全退化成了线性结构。上图中的平均查找次数为(1+2+3+4+5+5)/6=3.16次,和顺序查找差不多。显然这个二叉树的查询效率就很低,因此若想最大性能的构造一个二叉查找树,需要这个二叉树是平衡的(这里的平衡从一个显著的特点可以看出这一棵树的高度比上一个输的高度要大,在相同节点的情况下也就是不平衡),从而引出了一个新的定义-平衡二叉树AVL。 二、AVL树 (1)简介 AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1)。不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少,但查找多的情况。 从上面是一个普通的平衡二叉树,这张图我们可以看出,任意节点的左右子树的平衡因子差值都不会大于1。 (2)局限性 由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树。 (3)应用 1、Windows NT内核中广泛存在; 三、红黑树 (1)简介 一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是若平衡,可以推出,相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索、插入、删除操作多的情况下,我们就用红黑树。 (2)性质 1、每个节点非红即黑; 2、根节点是黑的; 3、每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的; 4、如果一个节点是红的,那么它的两儿子都是黑的; 5、对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节点; 6、每条路径都包含相同的黑节点; (3)应用 1、广泛用于C++的STL中,Map和Set都是用红黑树实现的; 2、著名的Linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间; 3、IO多路复用epoll的实现采用红黑树组织管理sockfd,以支持快速的增删改查; 4、Nginx中用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器; 5、Java中TreeMap的实现; 四、B/B+树 说了上述的三种树:二叉查找树、AVL和红黑树,似乎我们还没有摸到MySQL为什么要使用B+树作为索引的实现,不要急,接下来我们就先探讨一下什么是B树。 (1)简介 我们在MySQL中的数据一般是放在磁盘中的,读取数据的时候肯定会有访问磁盘的操作,磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。 为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。 总的来说,B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B树每个内节点有多个分支),与红黑树相比,在相同的的节点的情况下,一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成,而CPU的速度非常快,所以B树的操作效率取决于访问磁盘的次数,关键字总数相同的情况下B树的高度越小,磁盘I/O所花的时间越少。 注意B-树就是B树,-只是一个符号。 (2)B树的性质 1、定义任意非叶子结点最多只有M个儿子,且M>2; 2、根结点的儿子数为[2, M]; 3、除根结点以外的非叶子结点的儿子数为[M/2, M]; 4、每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字) 5、非叶子结点的关键字个数=指向儿子的指针个数-1; 6、非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1]; 7、非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树; 8、所有叶子结点位于同一层; 这里只是一个简单的B树,在实际中B树节点中关键字很多的,上面的图中比如35节点,35代表一个key(索引),而小黑块代表的是这个key所指向的内容在内存中实际的存储位置,是一个指针。 五、B+树 (1)简介 B+树是应文件系统所需而产生的一种B树的变形树(文件的目录一级一级索引,只有最底层的叶子节点(文件)保存数据)非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中,这不就是文件系统文件的查找吗? 我们就举个文件查找的例子:有3个文件夹a、b、c, a包含b,b包含c,一个文件yang.c,a、b、c就是索引(存储在非叶子节点), a、b、c只是要找到的yang.c的key,而实际的数据yang.c存储在叶子节点上。 所有的非叶子节点都可以看成索引部分! (2)B+树的性质(下面提到的都是和B树不相同的性质) 1、非叶子节点的子树指针与关键字个数相同; 2、非叶子节点的子树指针p[i],指向关键字值属于[k[i],k[i+1]]的子树.(B树是开区间,也就是说B树不允许关键字重复,B+树允许重复); 3、为所有叶子节点增加一个链指针; 4、所有关键字都在叶子节点出现(稠密索引). (且链表中的关键字恰好是有序的); 5、非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层; 6、更适合于文件系统; 非叶子节点(比如5,28,65)只是一个key(索引),实际的数据存在叶子节点上(5,8,9)才是真正的数据或指向真实数据的指针。 (3)应用 1、B和B+树主要用在文件系统以及数据库做索引,比如MySQL; 六、B/B+树性能分析 n个节点的平衡二叉树的高度为H(即logn),而n个节点的B/B+树的高度为logt((n+1)/2)+1;   若要作为内存中的查找表,B树却不一定比平衡二叉树好,尤其当m较大时更是如此。因为查找操作CPU的时间在B-树上是O(mlogtn)=O(lgn(m/lgt)),而m/lgt>1;所以m较大时O(mlogtn)比平衡二叉树的操作时间大得多。因此在内存中使用B树必须取较小的m。(通常取最小值m=3,此时B-树中每个内部结点可以有2或3个孩子,这种3阶的B-树称为2-3树)。 七、为什么说B+树比B树更适合数据库索引? 1、 B+树的磁盘读写代价更低:B+树的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对B树更小,如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对IO读写次数就降低了。 2、B+树的查询效率更加稳定:由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。 3、由于B+树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引。 PS:我在知乎上看到有人是这样说的,我感觉说的也挺有道理的: 他们认为数据库索引采用B+树的主要原因是:B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作或者说效率太低。 ———————————————— 版权声明:本文为CSDN博主「徐刘根」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/u010870518/java/article/details/79450295

AA大大官 2020-03-31 14:54:01 0 浏览量 回答数 0

问题

编写一个非递归算法求出二叉搜索树中的关键字最小的元素

知与谁同 2019-12-01 20:16:01 457 浏览量 回答数 1

回答

红黑树是一种二叉平衡树搜索树,相关背景知识此处不再叙述。 节点与关键值之间的关系与普通二叉树 一致,只是在插入时要保证红黑规则,如果插入过程中违反了红黑规则,树则会通过自我调整,改变树的结构和节点的颜色,使之满足红黑规则。满足红黑规则的树是平衡树。 红黑规则如下: 1. 每一个节点不是黑的就是红的 2. 根总是黑的 3. 红色节点的子节点必定是黑的,反之未必 4. 从根到叶节点或空子节点的每条路径中必然包含同样高度的黑色节点(从根到叶节点或空子节点的每条路径中必然有同样的高度) 为了保证红黑规则,程序按照如下方式工作: 新插入的节点(除了根以外)的是红的 插入过程中如果有一个黑色节点且它有两个红色节点,就需要颜色变化,如果该节点是根节点,则根节点不变化 右旋必须有一个左子节点,左旋必须有一个右子节点 旋转时,外侧子孙上升,内侧子孙断开其与父节点的连接,并成为其祖父节点的子节点 向下查找子节点的时候,发现一个黑色节点有两个红色节点时候,就执行一次颜色变化。 之后检查红黑冲突,发生冲突时 红色节点为X,红色节点的父节点为P,祖父节点为G, 旋转后继续向下查找 插入子节点X后 如果P为红色 如果X为G的外侧子孙,旋转一次 以G为顶点作一次旋转 如果X为G的内侧子孙,旋转两次 红黑树与Tree-2-3-4 原理非常相似,事实上可以相互转换。

小哇 2019-12-02 01:19:37 0 浏览量 回答数 0

回答

在使用 在线编程 过程中遇到的问题,可以先看这个帖子查看解决方式~产品使用有难题,进群来解答! 解题文章链接 没有思路的同学可以先去这里看看哦~ day1: 打怪兽 数组变换 day2: 超级区间 能量半径 day3: 找出二叉搜索树的第2大的数 字符配对 day4: 斐波那契字符串

被纵养的懒猫 2020-04-10 11:22:40 0 浏览量 回答数 0

问题

【算法】五分钟算法小知识:二叉堆详解实现优先级队列

游客ih62co2qqq5ww 2020-05-12 16:17:02 4 浏览量 回答数 1

问题

【今日算法】4月23日-如何调度考生的座位

游客ih62co2qqq5ww 2020-04-23 20:33:10 19 浏览量 回答数 1

问题

搜索引擎背后的经典数据结构和算法 6月10日 【今日算法】

游客ih62co2qqq5ww 2020-06-15 07:32:11 0 浏览量 回答数 0

问题

图解!24张图彻底弄懂九大常见数据结构! 7月22日 【今日算法】

游客ih62co2qqq5ww 2020-07-27 13:19:32 6 浏览量 回答数 1

问题

【算法】五分钟算法小知识:学习数据结构和算法的框架思维

游客ih62co2qqq5ww 2020-04-17 09:56:03 10 浏览量 回答数 1

问题

图解九大数据结构 6月13日 【今日算法】

游客ih62co2qqq5ww 2020-06-17 13:17:00 29 浏览量 回答数 1

问题

二叉搜索树的遍历问题

a123456678 2019-12-01 19:23:24 877 浏览量 回答数 1

回答

1.Python数据结构篇 数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录,当然,也结合了部分[算法导论](Introduction to Algorithms)中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。 **这一部分是下面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,我个人认为直接读算法设计篇比较好,因为大家时间也都比较宝贵,如果你会来读这些文章说明你肯定有一定基础了,后面的算法设计篇中更多的是思想,这里更多的是代码而已,嘿嘿。** (1)[搜索](Python Data Structures) 简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突) (2)[排序](Python Data Structures) 简述各种排序算法的思想以及它的图示和实现 (3)[数据结构](Python Data Structures) 简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆 (4)[树总结](Python Data Structures) 简述二叉树,详述二叉搜索树和AVL树的思想和实现 2.Python算法设计篇 算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**点击链接可进入Springer免费下载原书电子版**]之后写下的读书总结,原书大部分内容结合了经典书籍[算法导论](Introduction to Algorithms),内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但是我想我的介绍应该还算简单明了,因为我用的都是比较朴实的语言,并没有像算法导论一样列出一堆性质和定理,主要是对着某个问题一步步思考然后算法就出来了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩真的不容错过。 这里每篇文章都有实现代码,但是代码我一般都不会分析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。 本篇的顺序按照原书[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。 **1.你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等,采用问答式的方式让读者和我一起来想出某个问题的解,每篇文章之后都还有一两道小题练手哟** **2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂不更好些,当然,你如果想读算法导论的话我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科普的啦,没有多少人能够坚持读完的。但是码农与蛇的故事内容不多哟,呵呵呵** **3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,前面三节内容都是介绍基础知识,所以精彩内容从第4节开始哟,么么哒 O(∩_∩)O~** (1)[Python Algorithms - C1 Introduction](Python Algorithms) 本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。 (2)[Python Algorithms - C2 The basics](Python Algorithms) **本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。** (3)[Python Algorithms - C3 Counting 101](Python Algorithms) 原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法 (4)[Python Algorithms - C4 Induction and Recursion and Reduction](Python Algorithms) **本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分** (5)[Python Algorithms - C5 Traversal](Python Algorithms) **本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法** (6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms) **本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法** (7)[Python Algorithms - C7 Greedy](Python Algorithms) **本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树等等** (8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms) **本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比** (9)[Python Algorithms - C9 Graphs](Python Algorithms)

寒凝雪 2019-12-02 01:22:23 0 浏览量 回答数 0

回答

Python数据结构篇数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录,当然,也结合了部分[算法导论](Introduction to Algorithms)中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。**这一部分是下面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,我个人认为直接读算法设计篇比较好,因为大家时间也都比较宝贵,如果你会来读这些文章说明你肯定有一定基础了,后面的算法设计篇中更多的是思想,这里更多的是代码而已,嘿嘿。**(1)[搜索](Python Data Structures) 简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突)(2)[排序](Python Data Structures) 简述各种排序算法的思想以及它的图示和实现(3)[数据结构](Python Data Structures) 简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆(4)[树总结](Python Data Structures) 简述二叉树,详述二叉搜索树和AVL树的思想和实现2.Python算法设计篇算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**点击链接可进入Springer免费下载原书电子版**]之后写下的读书总结,原书大部分内容结合了经典书籍[算法导论](Introduction to Algorithms),内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但是我想我的介绍应该还算简单明了,因为我用的都是比较朴实的语言,并没有像算法导论一样列出一堆性质和定理,主要是对着某个问题一步步思考然后算法就出来了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩真的不容错过。这里每篇文章都有实现代码,但是代码我一般都不会分析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。本篇的顺序按照原书[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。 **1.你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等,采用问答式的方式让读者和我一起来想出某个问题的解,每篇文章之后都还有一两道小题练手哟****2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂不更好些,当然,你如果想读算法导论的话我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科普的啦,没有多少人能够坚持读完的。但是码农与蛇的故事内容不多哟,呵呵呵****3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,前面三节内容都是介绍基础知识,所以精彩内容从第4节开始哟,么么哒 O(∩_∩)O~**(1)[Python Algorithms - C1 Introduction](Python Algorithms) 本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。(2)[Python Algorithms - C2 The basics](Python Algorithms) **本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。**(3)[Python Algorithms - C3 Counting 101](Python Algorithms) 原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法(4)[Python Algorithms - C4 Induction and Recursion and Reduction](Python Algorithms) **本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分**(5)[Python Algorithms - C5 Traversal](Python Algorithms) **本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法**(6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms) **本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法**(7)[Python Algorithms - C7 Greedy](Python Algorithms) **本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树等等**(8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms) **本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比**(9)[Python Algorithms - C9 Graphs](Python Algorithms) /question/19889750/answer/27901020有哪些用 Python 语言讲算法和数据结构的书

琴瑟 2019-12-02 01:22:41 0 浏览量 回答数 0

回答

Python数据结构篇 数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录,当然,也结合了部分[算法导论](Introduction to Algorithms) 中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例 如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文 章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。 **这一部分是下 面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,我个人认为直接读算法设计篇比 较好,因为大家时间也都比较宝贵,如果你会来读这些文章说明你肯定有一定基础了,后面的算法设计篇中更多的是思想,这里更多的是代码而已,嘿嘿。** (1)[搜索](Python Data Structures) 简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突) (2)[排序](Python Data Structures) 简述各种排序算法的思想以及它的图示和实现 (3)[数据结构](Python Data Structures) 简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆 (4)[树总结](Python Data Structures) 简述二叉树,详述二叉搜索树和AVL树的思想和实现 2.Python算法设计篇 算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**点击链接可进入Springer免费下载原书电子版**]之后写下的读书总结,原书大部分内容结合了经典书籍[算法导论](Introduction to Algorithms), 内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排 序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并 没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但 是我想我的介绍应该还算简单明了,因为我用的都是比较朴实的语言,并没有像算法导论一样列出一堆性质和定理,主要是对着某个问题一步步思考然后算法就出来 了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩真的不容错过。 这里每篇文章都有实现代码,但是代码我一般都不会分 析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算 法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟 们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。 本篇的顺序按照原书[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。 **1. 你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这 个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等,采用问答式的方式让读者和我一起来想出某个问题的解,每篇 文章之后都还有一两道小题练手哟** **2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂 不更好些,当然,你如果想读算法导论的话我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科 普的啦,没有多少人能够坚持读完的。但是码农与蛇的故事内容不多哟,呵呵呵** **3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,前面三节内容都是介绍基础知识,所以精彩内容从第4节开始哟,么么哒 O(∩_∩)O~** (1)[Python Algorithms - C1 Introduction](Python Algorithms) 本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。 (2)[Python Algorithms - C2 The basics](Python Algorithms) **本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。** (3)[Python Algorithms - C3 Counting 101](Python Algorithms) 原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法 (4)[Python Algorithms - C4 Induction and Recursion and Reduction](Python Algorithms) **本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分** (5)[Python Algorithms - C5 Traversal](Python Algorithms) **本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法** (6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms) **本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法** (7)[Python Algorithms - C7 Greedy](Python Algorithms) **本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树等等** (8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms) **本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比** (9)[Python Algorithms - C9 Graphs](Python Algorithms) https://www.zhihu.com/question/19889750/answer/27901020

青衫无名 2019-12-02 01:23:20 0 浏览量 回答数 0

回答

1.Python数据结构篇 数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录,当然,也结合了部分[算法导论](Introduction to Algorithms)中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。 **这一部分是下面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,我个人认为直接读算法设计篇比较好,因为大家时间也都比较宝贵,如果你会来读这些文章说明你肯定有一定基础了,后面的算法设计篇中更多的是思想,这里更多的是代码而已,嘿嘿。** (1)[搜索](Python Data Structures) 简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突) (2)[排序](Python Data Structures) 简述各种排序算法的思想以及它的图示和实现 (3)[数据结构](Python Data Structures) 简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆 (4)[树总结](Python Data Structures) 简述二叉树,详述二叉搜索树和AVL树的思想和实现 2.Python算法设计篇 算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**点击链接可进入Springer免费下载原书电子版**]之后写下的读书总结,原书大部分内容结合了经典书籍[算法导论](Introduction to Algorithms),内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但是我想我的介绍应该还算简单明了,因为我用的都是比较朴实的语言,并没有像算法导论一样列出一堆性质和定理,主要是对着某个问题一步步思考然后算法就出来了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩真的不容错过。 这里每篇文章都有实现代码,但是代码我一般都不会分析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。 本篇的顺序按照原书[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。 **1.你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等,采用问答式的方式让读者和我一起来想出某个问题的解,每篇文章之后都还有一两道小题练手哟** **2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂不更好些,当然,你如果想读算法导论的话我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科普的啦,没有多少人能够坚持读完的。但是码农与蛇的故事内容不多哟,呵呵呵** **3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,前面三节内容都是介绍基础知识,所以精彩内容从第4节开始哟,么么哒 O(∩_∩)O~** (1)[Python Algorithms - C1 Introduction](Python Algorithms) 本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。 (2)[Python Algorithms - C2 The basics](Python Algorithms) **本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。** (3)[Python Algorithms - C3 Counting 101](Python Algorithms) 原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法 (4)[Python Algorithms - C4 Induction and Recursion and Reduction](Python Algorithms) **本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分** (5)[Python Algorithms - C5 Traversal](Python Algorithms) **本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法** (6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms) **本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法** (7)[Python Algorithms - C7 Greedy](Python Algorithms) **本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树等等** (8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms) **本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比** (9)[Python Algorithms - C9 Graphs](Python Algorithms) **本节主要介绍图算法中的各种最短路径算法,从不同的角度揭示它们的内核以及它们的异同**

一键天涯 2019-12-02 01:23:49 0 浏览量 回答数 0

问题

备战大厂每日挑战算法,坚持打卡更有社区定制周边奖品等你赢!

被纵养的懒猫 2020-04-07 11:41:45 5309 浏览量 回答数 5

回答

这是我们老师给我们写的二叉树最基本的.......追加、删除节点的程序,很简单,但是也不简单,如果你基础比较好,这个可以忽略,如果不好,看看也无妨,打酱油路过.......呵呵 #include <iostream> using namespace std; // 二叉搜索树 class BsTree { public: // 构造函数中初始化为空树 BsTree (void) : m_root (NULL), m_size (0) {} // 析构函数中释放剩余节点 ~BsTree (void) { Clear (); } // 插入数据 void Insert (int data) { Insert (new Node (data), m_root); m_size++; } // 删除数据,不存在返回false bool Remove (int data) { Node*& find = Find (data, m_root); if (find) { Insert (find -> m_left, find -> m_right); Node* node = find; find = find -> m_right; delete node; m_size--; return true; } return false; } // 删除所有值为data的数据 void RemoveAll (int data) { while (Remove (data)); } // 清空树 void Clear (void) { Clear (m_root); m_size = 0; } // 将全部old更新为_new void Update (int old, int _new) { while (Remove (old)) Insert (_new); } // 能否找到data bool Find (int data) { return Find (data, m_root) != NULL; } // 中序遍历 void Travel (void) { cout << '{'; Travel (m_root); cout << '}' << endl; } // 获取树的大小 size_t GetSize (void) { return m_size; } // 获取树的高度 size_t GetHeight (void) { return GetHeight (m_root); } private: // 节点 class Node { public: Node (int data) : m_data (data), m_left (NULL), m_right (NULL) {} int m_data; // 数据 Node* m_left; // 左树 Node* m_right; // 右树 }; void Insert (Node* node, Node*& tree) { if (! tree) tree = node; else if (node) { if (node -> m_data < tree -> m_data) Insert (node, tree -> m_left); else Insert (node, tree -> m_right); } } Node*& Find (int data, Node*& tree) { if (! tree) return tree; else if (data == tree -> m_data) return tree; else if (data < tree -> m_data) return Find (data, tree -> m_left); else return Find (data, tree -> m_right); } void Clear (Node*& tree) { if (tree) { Clear (tree -> m_left); Clear (tree -> m_right); delete tree; tree = NULL; } } void Travel (Node*& tree) { if (tree) { Travel (tree -> m_left); cout << ' ' << tree -> m_data << ' '; Travel (tree -> m_right); } } size_t GetHeight (Node*& tree) { if (tree) { size_t lh = GetHeight (tree -> m_left); size_t rh = GetHeight (tree -> m_right); return (lh > rh ? lh : rh) + 1; } return 0; } Node* m_root; // 树根 size_t m_size; // 树的大小 }; int main (void) { BsTree bs; bs.Insert (50); bs.Insert (70); bs.Insert (20); bs.Insert (60); bs.Insert (40); bs.Insert (30); bs.Insert (10); bs.Insert (90); bs.Insert (80); bs.Travel (); cout << bs.GetSize () << ", " << bs.GetHeight () << endl; cout << boolalpha << bs.Find (3) << endl; cout << boolalpha << bs.Find (10) << endl; bs.Remove (60); bs.Remove (30); bs.Travel (); bs.Insert (40); bs.Insert (40); bs.Travel (); bs.RemoveAll (40); bs.Travel (); bs.Insert (70); bs.Insert (70); bs.Travel (); bs.Update (70, 75); bs.Travel (); bs.Clear (); bs.Travel (); return 0; }

沉默术士 2019-12-02 01:24:22 0 浏览量 回答数 0

回答

参考答案: 考察点 1、基础数据结构的理解和编码能力 2、递归使用 示例 / \ 3 6 / \ 2 4 / 1 说明:保证输入的 K 满足 1<=K<=(节点数目) 解法1:树相关的题目,第一眼就想到递归求解,左右子树分别遍历。联想到二叉搜索树的性质,root 大于左子树,小于右子树,如果左子树的节点数目等于 K-1,那么 root 就是结果,否则如果左子树节点数目小于 K-1,那么结果必然在右子树,否则就在左子树。因此在搜索的时候同时返回节点数目,跟 K 做对比,就能得出结果了。 * Definition for a binary tree node. **/ public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } class Solution { private class ResultType { boolean found; // 是否找到 int val; // 节点数目 ResultType(boolean found, int val) { this.found = found; this.val = val; } } public int kthSmallest(TreeNode root, int k) { return kthSmallestHelper(root, k).val; } private ResultType kthSmallestHelper(TreeNode root, int k) { if (root == null) { return new ResultType(false, 0); } ResultType left = kthSmallestHelper(root.left, k); // 左子树找到,直接返回 if (left.found) { return new ResultType(true, left.val); } // 左子树的节点数目 = K-1,结果为 root 的值 if (k - left.val == 1) { return new ResultType(true, root.val); } // 右子树寻找 ResultType right = kthSmallestHelper(root.right, k - left.val - 1); if (right.found) { return new ResultType(true, right.val); } // 没找到,返回节点总数 return new ResultType(false, left.val + 1 + right.val); } } 解法2:基于二叉搜索树的特性,在中序遍历的结果中,第k个元素就是本题的解。 最差的情况是k节点是bst的最右叶子节点,不过每个节点的遍历次数最多是1次。 遍历并不是需要全部做完,使用计数的方式,找到第k个元素就可以退出。 下面是go的一个简单实现。 type BST struct { key, value int left, right *BST } func (bst *BST) setLeft(b *BST) { bst.left = b } func (bst *BST) setRight(b *BST) { bst.right = b } // count 查找bst第k个节点的值,未找到就返回0 func count(bst *BST, k int) int { if k < 1 { return 0 } c := 0 ok, value := countRecursive(bst, &c, k) if ok { return value } return 0 } // countRecurisive 对bst使用中序遍历 // 用计数方式控制退出遍历,参数c就是已遍历节点数 func countRecursive(bst *BST, c *int, k int) (bool, int) { if bst.left != nil { ok, value := countRecursive(bst.left, c, k) if ok { return ok, value } } if *c == k-1 { return true, bst.value } *c++ if bst.right != nil { ok, value := countRecursive(bst.right, c, k) if ok { return ok, value } } return false, 0 } // 下面是测试代码,覆盖了退化的情况和普通bst func createBST1() *BST { b1 := &BST{key: 1, value: 10} b2 := &BST{key: 2, value: 20} b3 := &BST{key: 3, value: 30} b4 := &BST{key: 4, value: 40} b5 := &BST{key: 5, value: 50} b6 := &BST{key: 6, value: 60} b7 := &BST{key: 7, value: 70} b8 := &BST{key: 8, value: 80} b9 := &BST{key: 9, value: 90} b9.setLeft(b8) b8.setLeft(b7) b7.setLeft(b6) b6.setLeft(b5) b5.setLeft(b4) b4.setLeft(b3) b3.setLeft(b2) b2.setLeft(b1) return b9 } func createBST2() *BST { b1 := &BST{key: 1, value: 10} b2 := &BST{key: 2, value: 20} b3 := &BST{key: 3, value: 30} b4 := &BST{key: 4, value: 40} b5 := &BST{key: 5, value: 50} b6 := &BST{key: 6, value: 60} b7 := &BST{key: 7, value: 70} b8 := &BST{key: 8, value: 80} b9 := &BST{key: 9, value: 90} b1.setRight(b2) b2.setRight(b3) b3.setRight(b4) b4.setRight(b5) b5.setRight(b6) b6.setRight(b7) b7.setRight(b8) b8.setRight(b9) return b1 } func createBST3() *BST { b1 := &BST{key: 1, value: 10} b2 := &BST{key: 2, value: 20} b3 := &BST{key: 3, value: 30} b4 := &BST{key: 4, value: 40} b5 := &BST{key: 5, value: 50} b6 := &BST{key: 6, value: 60} b7 := &BST{key: 7, value: 70} b8 := &BST{key: 8, value: 80} b9 := &BST{key: 9, value: 90} b5.setLeft(b3) b5.setRight(b7) b3.setLeft(b2) b3.setRight(b4) b2.setLeft(b1) b7.setLeft(b6) b7.setRight(b8) b8.setRight(b9) return b5 } func createBST4() *BST { b := &BST{key: 1, value: 10} last := b for i := 2; i < 100000; i++ { n := &BST{key: i, value: i * 10} last.setRight(n) last = n } return b } func createBST5() *BST { b := &BST{key: 99999, value: 999990} last := b for i := 99998; i > 0; i-- { n := &BST{key: i, value: i * 10} last.setLeft(n) last = n } return b } func createBST6() *BST { b := &BST{key: 50000, value: 500000} last := b for i := 49999; i > 0; i-- { n := &BST{key: i, value: i * 10} last.setLeft(n) last = n } last = b for i := 50001; i < 100000; i++ { n := &BST{key: i, value: i * 10} last.setRight(n) last = n } return b } func TestK(t *testing.T) { bst1 := createBST1() bst2 := createBST2() bst3 := createBST3() bst4 := createBST4() check(t, bst1, 1, 10) check(t, bst1, 2, 20) check(t, bst1, 3, 30) check(t, bst1, 4, 40) check(t, bst1, 5, 50) check(t, bst1, 6, 60) check(t, bst1, 7, 70) check(t, bst1, 8, 80) check(t, bst1, 9, 90) check(t, bst2, 1, 10) check(t, bst2, 2, 20) check(t, bst2, 3, 30) check(t, bst2, 4, 40) check(t, bst2, 5, 50) check(t, bst2, 6, 60) check(t, bst2, 7, 70) check(t, bst2, 8, 80) check(t, bst2, 9, 90) check(t, bst3, 1, 10) check(t, bst3, 2, 20) check(t, bst3, 3, 30) check(t, bst3, 4, 40) check(t, bst3, 5, 50) check(t, bst3, 6, 60) check(t, bst3, 7, 70) check(t, bst3, 8, 80) check(t, bst3, 9, 90) check(t, bst4, 1, 10) check(t, bst4, 2, 20) check(t, bst4, 3, 30) check(t, bst4, 4, 40) check(t, bst4, 5, 50) check(t, bst4, 6, 60) check(t, bst4, 7, 70) check(t, bst4, 8, 80) check(t, bst4, 9, 90) check(t, bst4, 99991, 999910) check(t, bst4, 99992, 999920) check(t, bst4, 99993, 999930) check(t, bst4, 99994, 999940) check(t, bst4, 99995, 999950) check(t, bst4, 99996, 999960) check(t, bst4, 99997, 999970) check(t, bst4, 99998, 999980) check(t, bst4, 99999, 999990) } func check(t *testing.T, b *BST, k, value int) { t.Helper() checkCall(t, b, k, value, count) // 此处可添加其他解法的实现 } func checkCall(t *testing.T, b *BST, k, value int, find func(bst *BST, kth int) int) { t.Helper() got := find(b, k) if got != value { t.Fatalf("want:%d, got:%d", value, got) } }

Runt 2020-04-14 16:43:57 0 浏览量 回答数 0

回答

摘要:面试也是一门学问,在面试之前做好充分的准备则是成功的必须条件,而程序员在代码面试时,常会遇到编写算法的相关问题,比如排序、二叉树遍历等等。 在程序员的职业生涯中,算法亦算是一门基础课程,尤其是在面试的时候,很多公司都会让程序员编写一些算法实例,例如快速排序、二叉树查找等等。 本文总结了程序员在代码面试中最常遇到的10大算法类型,想要真正了解这些算法的原理,还需程序员们花些功夫。 1.String/Array/Matrix 在Java中,String是一个包含char数组和其它字段、方法的类。如果没有IDE自动完成代码,下面这个方法大家应该记住: String/arrays很容易理解,但与它们有关的问题常常需要高级的算法去解决,例如动态编程、递归等。 下面列出一些需要高级算法才能解决的经典问题: Evaluate Reverse Polish Notation Longest Palindromic Substring 单词分割 字梯 Median of Two Sorted Arrays 正则表达式匹配 合并间隔 插入间隔 Two Sum 3Sum 4Sum 3Sum Closest String to Integer 合并排序数组 Valid Parentheses 实现strStr() Set Matrix Zeroes 搜索插入位置 Longest Consecutive Sequence Valid Palindrome 螺旋矩阵 搜索一个二维矩阵 旋转图像 三角形 Distinct Subsequences Total Maximum Subarray 删除重复的排序数组 删除重复的排序数组2 查找没有重复的最长子串 包含两个独特字符的最长子串 Palindrome Partitioning 2.链表 在Java中实现链表是非常简单的,每个节点都有一个值,然后把它链接到下一个节点。 class Node { int val; Node next; Node(int x) { val = x; next = null; } } 比较流行的两个链表例子就是栈和队列。 栈(Stack) class Stack{ Node top; public Node peek(){ if(top != null){ return top; } return null; } public Node pop(){ if(top == null){ return null; }else{ Node temp = new Node(top.val); top = top.next; return temp; } } public void push(Node n){ if(n != null){ n.next = top; top = n; } } } 队列(Queue) class Queue{ Node first, last;   public void enqueue(Node n){ if(first == null){ first = n; last = first; }else{ last.next = n; last = n; } }   public Node dequeue(){ if(first == null){ return null; }else{ Node temp = new Node(first.val); first = first.next; return temp; } } } 值得一提的是,Java标准库中已经包含一个叫做Stack的类,链表也可以作为一个队列使用(add()和remove())。(链表实现队列接口)如果你在面试过程中,需要用到栈或队列解决问题时,你可以直接使用它们。 在实际中,需要用到链表的算法有: 插入两个数字 重新排序列表 链表周期 Copy List with Random Pointer 合并两个有序列表 合并多个排序列表 从排序列表中删除重复的 分区列表 LRU缓存 3.树&堆 这里的树通常是指二叉树。 class TreeNode{ int value; TreeNode left; TreeNode right; } 下面是一些与二叉树有关的概念: 二叉树搜索:对于所有节点,顺序是:left children <= current node <= right children; 平衡vs.非平衡:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树; 满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点; 完美二叉树(Perfect Binary Tree):一个满二叉树,所有叶子都在同一个深度或同一级,并且每个父节点都有两个子节点; 完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。 堆(Heap)是一个基于树的数据结构,也可以称为优先队列( PriorityQueue),在队列中,调度程序反复提取队列中第一个作业并运行,因而实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。 下面列出一些基于二叉树和堆的算法: 二叉树前序遍历 二叉树中序遍历 二叉树后序遍历 字梯 验证二叉查找树 把二叉树变平放到链表里 二叉树路径和 从前序和后序构建二叉树 把有序数组转换为二叉查找树 把有序列表转为二叉查找树 最小深度二叉树 二叉树最大路径和 平衡二叉树 4.Graph 与Graph相关的问题主要集中在深度优先搜索和宽度优先搜索。深度优先搜索非常简单,你可以从根节点开始循环整个邻居节点。下面是一个非常简单的宽度优先搜索例子,核心是用队列去存储节点。 第一步,定义一个GraphNode class GraphNode{ int val; GraphNode next; GraphNode[] neighbors; boolean visited; GraphNode(int x) { val = x; } GraphNode(int x, GraphNode[] n){ val = x; neighbors = n; } public String toString(){ return "value: "+ this.val; } } 第二步,定义一个队列 class Queue{ GraphNode first, last; public void enqueue(GraphNode n){ if(first == null){ first = n; last = first; }else{ last.next = n; last = n; } } public GraphNode dequeue(){ if(first == null){ return null; }else{ GraphNode temp = new GraphNode(first.val, first.neighbors); first = first.next; return temp; } } } 第三步,使用队列进行宽度优先搜索 public class GraphTest { public static void main(String[] args) { GraphNode n1 = new GraphNode(1); GraphNode n2 = new GraphNode(2); GraphNode n3 = new GraphNode(3); GraphNode n4 = new GraphNode(4); GraphNode n5 = new GraphNode(5); n1.neighbors = new GraphNode[]{n2,n3,n5}; n2.neighbors = new GraphNode[]{n1,n4}; n3.neighbors = new GraphNode[]{n1,n4,n5}; n4.neighbors = new GraphNode[]{n2,n3,n5}; n5.neighbors = new GraphNode[]{n1,n3,n4}; breathFirstSearch(n1, 5); } public static void breathFirstSearch(GraphNode root, int x){ if(root.val == x) System.out.println("find in root"); Queue queue = new Queue(); root.visited = true; queue.enqueue(root); while(queue.first != null){ GraphNode c = (GraphNode) queue.dequeue(); for(GraphNode n: c.neighbors){ if(!n.visited){ System.out.print(n + " "); n.visited = true; if(n.val == x) System.out.println("Find "+n); queue.enqueue(n); } } } } } 输出结果: value: 2 value: 3 value: 5 Find value: 5 value: 4 实际中,基于Graph需要经常用到的算法: 克隆Graph 15 2014-04-24 18:55:03回复数 293 只看楼主 引用 举报 楼主 柔软的胖纸 Bbs1 5.排序 不同排序算法的时间复杂度,大家可以到wiki上查看它们的基本思想。 BinSort、Radix Sort和CountSort使用了不同的假设,所有,它们不是一般的排序方法。 下面是这些算法的具体实例,另外,你还可以阅读:Java开发者在实际操作中是如何排序的。 归并排序 快速排序 插入排序 6.递归和迭代 下面通过一个例子来说明什么是递归。 问题: 这里有n个台阶,每次能爬1或2节,请问有多少种爬法? 步骤1:查找n和n-1之间的关系 为了获得n,这里有两种方法:一个是从第一节台阶到n-1或者从2到n-2。如果f(n)种爬法刚好是爬到n节,那么f(n)=f(n-1)+f(n-2)。 步骤2:确保开始条件是正确的 f(0) = 0; f(1) = 1; public static int f(int n){ if(n <= 2) return n; int x = f(n-1) + f(n-2); return x; } 递归方法的时间复杂度指数为n,这里会有很多冗余计算。 f(5) f(4) + f(3) f(3) + f(2) + f(2) + f(1) f(2) + f(1) + f(2) + f(2) + f(1) 该递归可以很简单地转换为迭代。 public static int f(int n) { if (n <= 2){ return n; } int first = 1, second = 2; int third = 0; for (int i = 3; i <= n; i++) { third = first + second; first = second; second = third; } return third; } 在这个例子中,迭代花费的时间要少些。关于迭代和递归,你可以去 这里看看。 7.动态规划 动态规划主要用来解决如下技术问题: 通过较小的子例来解决一个实例; 对于一个较小的实例,可能需要许多个解决方案; 把较小实例的解决方案存储在一个表中,一旦遇上,就很容易解决; 附加空间用来节省时间。 上面所列的爬台阶问题完全符合这四个属性,因此,可以使用动态规划来解决: public static int[] A = new int[100]; public static int f3(int n) { if (n <= 2) A[n]= n; if(A[n] > 0) return A[n]; else A[n] = f3(n-1) + f3(n-2);//store results so only calculate once! return A[n]; } 一些基于动态规划的算法: 编辑距离 最长回文子串 单词分割 最大的子数组 8.位操作 位操作符: 从一个给定的数n中找位i(i从0开始,然后向右开始) public static boolean getBit(int num, int i){ int result = num & (1<<i); if(result == 0){ return false; }else{ return true; } } 例如,获取10的第二位: i=1, n=10 1<<1= 10 1010&10=10 10 is not 0, so return true; 典型的位算法: Find Single Number Maximum Binary Gap 9.概率 通常要解决概率相关问题,都需要很好地格式化问题,下面提供一个简单的例子: 有50个人在一个房间,那么有两个人是同一天生日的可能性有多大?(忽略闰年,即一年有365天) 算法: public static double caculateProbability(int n){ double x = 1; for(int i=0; i<n; i++){ x *= (365.0-i)/365.0; } double pro = Math.round((1-x) * 100); return pro/100; } 结果:calculateProbability(50) = 0.97 10.组合和排列 组合和排列的主要差别在于顺序是否重要。 例1: 1、2、3、4、5这5个数字,输出不同的顺序,其中4不可以排在第三位,3和5不能相邻,请问有多少种组合? 例2: 有5个香蕉、4个梨、3个苹果,假设每种水果都是一样的,请问有多少种不同的组合? 基于它们的一些常见算法 排列 排列2 排列顺序 来自: ProgramCreek 转载于:https://bbs.csdn.net/topics/390768965

养狐狸的猫 2019-12-02 02:11:29 0 浏览量 回答数 0

问题

【今日算法】4月30日-回溯算法详解

游客ih62co2qqq5ww 2020-04-30 14:13:51 9 浏览量 回答数 1
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 企业信息查询 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 2020阿里巴巴研发效能峰会 企业建站模板 云效成长地图 高端建站