xqxls

分类

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

/ 注册

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

297篇文章 4409人学习

全部文章（共297篇）

题解 | #牛牛的超市# 来自专栏

题意整理有n种不同的货币，给定每种货币的面值和个数。现在要将x元兑换为这些货币的组合，求总共有多少种方案。方法一（动态规划） 1.解题思路这是一个典型的背包问题，x元是背包容量，根据面值以及个数限制逐个推导出每种金额x对应的方案数。状态定义：表示i种币值下，j元的金额有多少换钱方案。...

java 动态规划状态压缩背包问题

2021-08-24

0 560

题解 | #车站建造问题# 来自专栏

题意整理数轴上有n个点，这n个点必须建立收集站。如果这n个点之间，相邻两个点间隔不是素数，则必须在中间修建对应数量的收集站，使得所有间隔是素数。求需要建设的收集站的最少数量。方法一（欧拉筛+动态规划） 1.解题思路首先计算给定n个特殊点的最大间隔距离，最大距离记为max。然后通过欧...

java 哥德巴赫猜想动态规划欧拉筛

2021-08-23

0 608

题解 | #牛牛港# 来自专栏

题意整理有n个工厂，提供了抵达时间和物资数量，由于每天只能装载一天，所以物资数量也相当于停留时间。按先抵达的工厂先装载的规则，通过k个码头最少多少天完成装载任务。方法一（排序+小顶堆） 1.解题思路首先将工厂按抵达时间排好。然后遍历所有工厂，如果某个工厂已经装载完毕，则从堆中移除。如...

java 堆小顶堆 TreeMap

2021-08-23

0 460

题解 | #苹果树# 来自专栏

题意整理有n颗苹果树，每棵树上有对应的果子存在数组a。数组b中存放着每天计划采摘的果子，如果某棵树上不足对应的果子，则全部摘完。求每天供应的苹果数。方法一（暴力法） 1.解题思路直接遍历每棵树上还剩下的果子数，如果有个，则直接摘个，如果没有，则摘剩下的对应果子数。然后每次都把所有树上摘...

java 小顶堆

2021-08-22

0 759

题解 | #牛牛排队# 来自专栏

题意整理 n个人在排队，它们的位置可能被打乱了，有一个数组记录了一些信息。数组中对应的那个人，记录着站在他左部分和站在他右部分的人的人数差的绝对值。根据上面的信息，求他们可能的站法有多少种。方法一（排序） 1.解题思路如果有两个人，a数组只能是[1,1]，如果有三个人a数组只能是[2，0...

java 排序快幂法

2021-08-22

0 523

题解 | #枪打出头鸟# 来自专栏

题意整理 n个人站成一列，如果某个人的前面有身高比他高的，则第一个比他高的会中枪。只要某个人中枪了，则荒唐度会增加对应那个人的编号，求最终的荒唐度。方法一（暴力法） 1.解题思路直接遍历所有的人，内层循环中找到第一个比他高的人，加上对应编号，如果找到，立即终止内层循环。 2.代码实现 im...

java 单调栈

2021-08-22

3 615

题解 | #牛牛锻炼# 来自专栏

题意整理牛牛在锻炼，锻炼的项目有n个，a数组记录每个项目锻炼极限分数，b数组记录当前牛牛的得分，c数组记录每个项目多得一分需要得时间。为了达到每个项目平均分大于等于d，牛牛至少还需要锻炼多长时间。方法一（优先队列） 1.解题思路可以定义一个int数组类型的优先队列，int数组长度为2，...

java 优先队列数组

2021-08-22

0 499

题解 | #打字# 来自专栏

题意整理给定输入字符串，按规则打印出来。如果不是'<'，正常打印，如果是'<'并且前面字符不为空，则删除上一次打印的字符。方法一（栈） 1.解题思路用栈记录每次打印的字符，如果当前字符是'<'，并且栈不为空，则弹出栈顶元素。最后将栈中所有元素返回。动图展示： 2.代...

java 模拟栈

2021-08-18

0 550

题解 | #原根# 来自专栏

题意整理给定一个大小为n的字符串数组。找出字符串数组中原根的个数。给定一个字符串，其他任何字符串都不是它的前缀，则称为原根。方法一（暴力法） 1.解题思路直接遍历整个字符串数组，然后将当前字符串，与所有其他字符串进行比较，只要其他字符串中有一个是它的前缀，就不是原根，原根标记置为fal...

java 字典树

2021-08-18

0 572

题解 | #相似和# 来自专栏

题意整理给定一个字符串数组。求字符串数组中的字符串两两匹配的最长公共前缀之和。方法一（暴力法） 1.解题思路直接两层循环遍历所有的字符串组合，然后计算每个组合的最长公共前缀。 2.代码实现 import java.util.*; public class Solution { ...

java 字符串字典树

2021-08-17

0 583