xqxls

分类

二叉树技巧总结(2) 未归档(3) 题解(292)

/ 注册

TA的专栏 297篇文章 4人订阅

297篇文章 4409人学习

全部文章（共297篇）

题解 | #找出重复的数# 来自专栏

题意整理给定一个长度为n+1的序列，包含1到n之间的数。有一个数重复了，找出重复的数。方法一（数学） 1.解题思路先计算出序列中所有数字的和。然后计算1到n所有数字的和。由于序列中有一个重复了，所以序列和中多算了一次，从序列和中减去1到n所有数的和，即时那个重复的数字。动图展示...

java 数学异或

2021-09-03

1 595

题解 | #中序序列# 来自专栏

题意整理给定一颗二叉树的先序遍历序列和后序遍历序列。求中序遍历序列（如果某个节点只有一个子节点，则必是左子节点）。方法一（递归+重建二叉树） 1.解题思路在每次递归中，可以确定当前根节点在先序遍历开头处，后续遍历结尾处。在后续遍历中找到当前节点的第一个左子节点，则后续遍历中，该节点之前...

java 递归哈希表

2021-09-03

4 933

题解 | #序列取反问题# 来自专栏

题意整理给定一个序列，序列中每个下标对应一个值，选定一个下标i，则从i到的区间所有数都做一个标记。最后的目标是将所有的数都打上标记，问所有可能的方案中期望步数是多少。方法一（排列+费马小定理+快幂法） 1.解题思路对于任意均满足条件：若，则这两个条件一定满足其中1个。所以，如果，要么，...

java 排列费马小定理快幂法差分数组前缀和

2021-09-02

0 513

题解 | #最大最小# 来自专栏

题意整理给定一个数组。求所有的区间中，满足区间最大值大于等于最小值对应的区间个数。方法一（暴力） 1.解题思路先确定左端点，然后遍历所有的右端点。每次记录最大值和最小值，只要最大值大于等于最小值，则结束内循环。将满足条件的区间数加入到结果变量。直到确定完所有的左端点。动图展示：...

java 单调栈二分

2021-09-01

0 429

题解 | #消息压缩# 来自专栏

题意整理有一段长度为n的消息，要将消息分成若干组，每组2个消息。第一个消息长度必须是4，第二个消息长度不能为0。求有多少种分割方法。方法一（递归） 1.解题思路递归终止条件：如果剩下的长度为0，说明正好完成分割，返回一种方案。递归如何推进：首先减去4，表示第一个消息的长度，然后第二...

java 递归动态规划

2021-09-01

0 547

题解 | #牛牛凑数字# 来自专栏

题意整理给定1-9共9个数字，a数组记录了每个数字的价格。牛牛手上有n元钱，为了凑出最大的数字带回家，问牛牛应该怎么买，并返回最大的数字。方法一（贪心） 1.解题思路首先计算最便宜的数字是多少。然后根据最便宜的数字，得到最多买多少个数字，以及买了之后，剩余多少钱。因为要凑出最大的数字...

java 模拟贪心排序

2021-08-31

0 579

题解 | #Tree I# 来自专栏

题意整理给定完全二叉树的层序遍历序列。还原二叉树，并计算树中所有边的节点间异或值的累加和。方法一（重建二叉树） 1.解题思路首先根据层序遍历序列，重建二叉树，找到根节点。利用重建的二叉树，遍历所有边，将对应异或和累加到结果变量。返回结果变量res。 2.代码实现 import j...

java 完全二叉树异或模拟

2021-08-30

1 529

题解 | #组合数第k小# 来自专栏

题意整理在所有组合数中，找到第k小的，并返回其值。方法一（小顶堆） 1.解题思路枚举从k个数中取若干个数的所有组合数，然后依次添加到堆，如果已经在堆，则不再添加。然后从堆里弹出k-1个数，此时的堆顶元素一定是第k小的组合数，直接返回。由于数据量大，运行超时。动图展示： 2.代码实现 i...

java 小顶堆数学组合

2021-08-30

1 679

题解 | #牛牛分蛋糕# 来自专栏

题意整理给定n个盘子以及a、b两种蛋糕，蛋糕各有一定数量。要求每个盘子都有蛋糕，且只有一种蛋糕。求蛋糕数最少的盘子最多能分多少蛋糕。方法一（枚举） 1.解题思路由于a、b两种蛋糕的盘子数之和固定为n，只要枚举出a蛋糕的盘子数，b蛋糕盘子数也确定了。然后计算最少a蛋糕数量的最大值，以...

java 枚举二分

2021-08-30

0 614

题解 | #牛牛的棋盘# 来自专栏

题意整理给定的矩阵以及个点。现在要将这个点放在矩阵里，并且保证第一行，第一列，最后一行，最后一列都有点。求总共有多少种方案。方法一（动态规划） 1.解题思路初始化一个组合数组，表示在i个格子里取j个点的组合数，即。根据组合递归公式，可得：。计算出所有的组合数之后，首先取对应的所有...

java 动态规划数学

2021-08-29

0 625