xqxls

题解

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

/ 注册

全部文章 / 题解（共292篇）

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

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

java 模拟贪心排序

2021-08-31

0 602

题解 | #Tree I# 来自专栏

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

java 完全二叉树异或模拟

2021-08-30

1 557

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

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

java 小顶堆数学组合

2021-08-30

1 699

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

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

java 枚举二分

2021-08-30

0 633

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

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

java 动态规划数学

2021-08-29

0 649

题解 | #牛牛的函数2# 来自专栏

题意整理给定函数以及a、b的值。求，结果对10000000033取余。方法一（模拟） 1.解题思路首先当n为0时，直接返回0。然后模拟题目给的函数进行计算，为了防止溢出，乘方运算需要使用大数快幂法。由于测试数据较大，这种方法运行超时。 2.代码实现 import java.util.*;...

java 快幂法大数运算等比数列费马小定理

2021-08-29

0 600

题解 | #牛牛的函数# 来自专栏

题意整理给定函数以及a、b的值。求，结果对10000000033取余。方法一（模拟） 1.解题思路首先当n为0时，直接返回0。然后模拟题目给的函数进行计算，为了防止溢出，乘方运算需要使用快幂法，乘法运算使用快乘法。由于测试数据较大，这种方法运行超时。 2.代码实现 import java...

java 模拟快幂法快乘法等比数列费马小定理

2021-08-29

0 640

题解 | #牛妹的春游# 来自专栏

题意整理给定x，y，以及若干数对[ai,bi,ci]。从中选出部分数对，使得ai数对的和不小于x，bi数对的和不小于y，求最小的ci数对的和。方法一（动态规划） 1.解题思路状态定义：dp[i][j][k]表示选择包装数为i，面包数为j，饮料数为k的情况下，最小的花费。状态初始化：不...

java 动态规划空间压缩

2021-08-28

0 598

题解 | #权值最大的路径# 来自专栏

题意整理给定一个有向无环图，每个节点都有一个权值。求所有路径中，节点权值和最大的路径。方法一（记忆化递归） 1.解题思路递归终止条件：跟新完所有的节点。递归如何推进：每跟新完一个后置节点，就将当前后置节点作为新的起点进行递归。 2.代码实现 import java.util.*; ...

java 动态规划记忆化递归

2021-08-28

0 1386

题解 | #破译密码# 来自专栏

题意整理给定字符串s1和s2，均由4个字母组成。求s1变换到s2，至少要变换多少次。变换的规则是，固定其中一位，其他三位从左到右依次加上2、3和5，如果超过'z'，重新从'a'开始。方法一（BFS） 1.解题思路初始化一个队列和set，队列用于存储每次变化的字符串和当前变换的次数，s...

java BFS 枚举

2021-08-27

0 535