xqxls

题解

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

/ 注册

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

题解 | #牛妹的项链# 来自专栏

题意整理牛妹有一条由n个珠子组成的项链，每个珠子都有自己的颜色。现在牛妹要截取一段尽可能长的珠子，但是截下的这一段不能有相同颜色的珠子。方法一（暴力统计） 1.解题思路简要分析：由于项链总共有n颗珠子，我们可以枚举所有的起始位置，然后从每个起始位置开始，最多截取n个珠子，每一个起始位置（...

java 哈希表滑动窗口

2021-08-11

0 643

题解 | #k长连续子段和# 来自专栏

题意整理给定由n个数字组成的一个序列。求所有长度大于等于k的连续子段中，子段和的最大值。方法一（枚举k长子段和） 1.解题思路首先定义结果变量，用于记录最终结果。固定子段和开始处索引，枚举所有长度的子段，并记录子段和。如果长度大于等于k，则与res比较，并记录最大值。 2.代码实现...

java 动态规划

2021-08-11

0 762

题解 | #MagicString# 来自专栏

题意整理给定两个字符串S1和S2。求S2在S1的哪一个循环同构串中出现次数最多。如果有多个这样的同构串，输出字典序最小的那一个。方法一（kmp） 1.解题思路首先初始化计数数组。通过kmp算法，获取S2在同构串中出现的次数。记录最大的出现次数。通过最大出现次数定位到同构串起点索...

java kmp 哈希字符串

2021-08-10

0 670

题解 | #航海# 来自专栏

题意整理二维海面上有n只船，每只船有一个坐标，以及一个权值。求最小的带权曼哈顿距离。方法一（求极值） 1.解题思路简要分析：首先考虑一个简化版的情况，一维横轴上有n个点，要从这个n个点中，找到一个点，使得其他点移动到这个点的距离之和最小。假设当前处于第x个点的位置（位置p），当前的最小移...

java 中位数极值

2021-08-09

0 665

题解 | #旅行Ⅰ# 来自专栏

题意整理给定N个城市，以及每个城市的开销。一个前置城市数组，去y城市之前必须先去x城市。牛妹手上有V元，她每次都会去开销最小的城市，如果开销相同，就选编号较小的城市，求牛妹最多能去几个城市。方法一（优先队列+拓扑排序） 1.解题思路首先明确一个事实，如果要去某个城市，那么他的前置城市一...

java 优先队列拓扑排序

2021-08-08

0 717

题解 | #旅行Ⅱ# 来自专栏

题意整理给定N个城市，以及每个城市的开销。一个前置城市数组，即去y城市之前必须先去x城市。求牛妹用V元最多能去多少个城市旅游。方法一（记忆化递归） 1.解题思路前置知识：假设有N个城市，每个城市的编号是，牛妹去了哪几个城市可以用一个N位二进制编码mask来表示，mask中对应位是1，则...

java 记忆化递归动态规划状压dp

2021-08-07

0 626

题解 | #单双难全# 来自专栏

题意整理给定个字符串组成的字符串数组，以及个字符串组成的字符串数组。对于中的每一个字符串，如果s数组中存在某个字符串的前缀与单匹配，但不满足双匹配，求这样的字符串有多少个。方法一（暴力匹配） 1.解题思路首先固定t数组的某一个字符串，然后遍历s数组，将s数组中的每一个字符串与t数组固定...

java 字典树字符串

2021-08-06

0 508

题解 | #扔骰子# 来自专栏

题意整理牛妹和牛牛在玩掷骰子游戏，看谁能够获胜。得分规则为，给定每一次所掷的骰子点数，这些点数可以随意组合相加得到一些数，从1开始计算，如果某个数不在这些组合得到的数中，则这个数就是他的得分。方法一（有序哈希） 1.解题思路首先定义一个TreeSet，用于存放所有可能的累加和，并保证累...

java 哈希表贪心排序

2021-08-04

0 601

题解 | #生产口罩# 来自专栏

题意整理牛妹要安排m名员工到n条生产线生产口罩。每条生产线有一个策略数组，对于这条生产线，牛妹要么一个员工也不给安排，要么按策略数组的某条策略进行安排。求怎么样安排每天生产的口罩最多，最多是多少。方法一（动态规划） 1.解题思路状态定义：表示i条生产线，j名员工每天产多少口罩。状...

java 动态规划状态压缩 01背包

2021-08-03

0 545

题解 | #下象棋# 来自专栏

题意整理只要牛妹的炮，将，车，兵的任意一个能吃到牛牛的将，则牛妹获胜。将、兵只有在相邻的时候才能吃。炮、车在同行和同列都可以吃，炮需要隔一个棋子，车不能有棋子挡在中间。方法一（模拟搜索） 1.解题思路首先找到牛牛的将在什么位置。以牛牛将的位置为起点，沿着四个方向进行搜索，当与起点位...

java 数组模拟

2021-08-02

0 649