题意整理  牛牛在锻炼，锻炼的项目有n个，a数组记录每个项目锻炼极限分数，b数组记录当前牛牛的得分，c数组记录每个项目多得一分需要得时间。 为了达到每个项目平均分大于等于d，牛牛至少还需要锻炼多长时间。  方法一（优先队列） 1.解题思路  可以定义一个int数组类型的优先队列，int数组长度为2，第一个元素存放每个项目多得一分所需时间，第二个元素存放每个项目还有多少分的上升空间，然后优先队列堆顶总是最小的第一个元素对应的数组。 每次取优先队列堆顶元素，如果当前得分总和加上堆顶元素对应的上升空间还小于目标分数，就加上对应的时间花费；如果大于等于目标分数，加上对应的时间花费，直接返回。  动图展...

题意整理  给定输入字符串，按规则打印出来。 如果不是'<'，正常打印，如果是'<'并且前面字符不为空，则删除上一次打印的字符。  方法一（栈） 1.解题思路 用栈记录每次打印的字符，如果当前字符是'<'，并且栈不为空，则弹出栈顶元素。最后将栈中所有元素返回。 动图展示：  2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ public Stri...

题意整理  给定一个大小为n的字符串数组。 找出字符串数组中原根的个数。 给定一个字符串，其他任何字符串都不是它的前缀，则称为原根。  方法一（暴力法） 1.解题思路 直接遍历整个字符串数组，然后将当前字符串，与所有其他字符串进行比较，只要其他字符串中有一个是它的前缀，就不是原根，原根标记置为false。每次都判断原根标记是否为true，如果为true，则计数加一。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 ...

题意整理  给定一个字符串数组。 求字符串数组中的字符串两两匹配的最长公共前缀之和。  方法一（暴力法） 1.解题思路 直接两层循环遍历所有的字符串组合，然后计算每个组合的最长公共前缀。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param s string字符串一维数组 * @return long长整型 */ public long solve (int n, String[] s) { //初始化...

题意整理  给定一个字符串S。 求S中有多少子序列等于"niuniu"。  方法一（动态规划） 1.解题思路 假设长度为i-1的字符串s包含N个长度为j的字符串t（"niuniu"）的子序列。如果s的第i个字符不等于t的第j个字符，那么当前状态必定等于前一个状态，即最多只能有N个对应的子序列；如果相等，说明除了这N个子序列，还多出了同时删除s的第i个字符以及t的第j个字符对应状态的子序列。  状态定义：表示长度为i的s包含多少个子序列是长度为j的t。 状态初始化：当t为空时，均包含1个对应的子序列。 状态转移：如果相等，说明既可以同时删除s、t的当前字符...

题意整理  牛牛准备出一套卷子，共n个多项选择题。 正确答案中，A和C出现次数差距不超过1，B和D出现次数差距不超过2。 问有多少种符合要求的正确答案。  方法一（动态规划） 1.解题思路 正确答案主要由两个因素决定它的种类数，一是A和C出现次数差距，二是B和D出现次数差距，可以通过这两个因素确定15种状态，每种状态的方案数累加，即是正确答案的数量。  A和C出现次数差距可以是-1，0，1，B和D出现次数差距可以是-2，-1，0，1，2，将参数对齐到大于等于0之后，分别对应j=0,1,2以及k=0,1,2,3,4  mask从1到15分别对应15种答案，其对应关系如下表所示:    mask ...

题意整理  有m辆货车，每辆货车能运送若干个鸡蛋。 总共要运送n个鸡蛋。 如果货车装不下，可以使用魔法将某辆货车容量翻倍，问最少需要使用多少次魔法，才能一次运完所有鸡蛋。  方法一（排序+贪心） 1.解题思路 首先对x数组进行排序，获得容量最大的货车。然后计算还剩多少鸡蛋运不走，每次选择容量最大的货车施加魔法，剩下的鸡蛋就会最大程度地减少，当没有鸡蛋剩下时，就不用施加魔法了。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n i...

题意整理  牛牛在一个3行n列的跑道上跑步。 牛牛的下一步只能在原来的那一行，或者由相邻行跳转过来（不能跨行或者越界）。 求牛牛从(1,1)到(3,n)有多少条不同的路径可走。  方法一（记忆化递归） 1.解题思路  递归终止条件：起点第1行第1列的位置肯定是可达的。 递归如何推进：总共有1，2，3三行跑道。当牛牛在第1行跑道上时，只能由上一列第1行或第2行的跑道跳转过来；当牛牛在第2行跑道上时，可以由上一列第1行、第2行或第3行的跑道跳转过来；当牛牛在第3行跑道上时，只能由上一列第2行或第3行的跑道跳转过来。 每一层递归返回什么：返回到达当前位置总共有多少条不同的路径。  由于递归会有很多重...

题意整理  总共有n层台阶，起初牛牛在第1层。 牛牛每次能跳奇数层台阶，问有多少种不同的跳法到达第n层台阶（不能踩到积水的台阶）。  方法一（记忆化递归） 1.解题思路  递归终止条件：只有0层或1层的时候，共1种方案，返回1。 递归如何推进：当前层的方案数，需要借助之前所有相隔奇数层的方案数来计算，即（i的范围在1到n，并且总是奇数）。 每一层递归返回什么：当前层的方案数。  由于递归会有很多重复的计算，可以通过记忆数组记录之前计算过的状态。 2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定...

题意整理  牛妹有一条由n个珠子组成的项链，每个珠子都有自己的颜色。 现在牛妹要截取一段尽可能长的珠子，但是截下的这一段不能有相同颜色的珠子。  方法一（暴力统计） 1.解题思路 简要分析：由于项链总共有n颗珠子，我们可以枚举所有的起始位置，然后从每个起始位置开始，最多截取n个珠子，每一个起始位置（记为start）对应的终点位置最多为start+n，如果超过n就对n取余。固定起始位置之后，就开始截取，可以用一个set集合存储之前截取过的珠子，一旦遇到颜色重复的珠子，直接终止循环，此时的set容量即为当前起点对应的最大珠子数。  首先定义结果变量，用于记录最终结果。 以每一个位置为起始点，往后截...

题意整理  给定由n个数字组成的一个序列。 求所有长度大于等于k的连续子段中，子段和的最大值。  方法一（枚举k长子段和） 1.解题思路  首先定义结果变量，用于记录最终结果。 固定子段和开始处索引，枚举所有长度的子段，并记录子段和。如果长度大于等于k，则与res比较，并记录最大值。  2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param k int整型 * @param a int整型一维数组 * @...

题意整理  给定两个字符串S1和S2。 求S2在S1的哪一个循环同构串中出现次数最多。 如果有多个这样的同构串，输出字典序最小的那一个。  方法一（kmp） 1.解题思路  首先初始化计数数组。 通过kmp算法，获取S2在同构串中出现的次数。 记录最大的出现次数。 通过最大出现次数定位到同构串起点索引，找到字典序最小的那一个。  通过kmp算法计算模式串在主串中出现次数，可参考我在牛客的另一篇题解：kmp题解入口 动图展示：  2.代码实现 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返...

题意整理  二维海面上有n只船，每只船有一个坐标，以及一个权值。 求最小的带权曼哈顿距离。  方法一（求极值） 1.解题思路 简要分析：首先考虑一个简化版的情况，一维横轴上有n个点，要从这个n个点中，找到一个点，使得其他点移动到这个点的距离之和最小。假设当前处于第x个点的位置（位置p），当前的最小移动距离是dist，如果把这个点向右移动一位（移到p'），则最小移动距离dist变为（位于p左边的所有点到p的距离加一，总共加x，位于p右边的所有点到p的距离减一，总共减）。如果dist是一个关于x的函数，那么dist关于x的一阶导等于，于是x小于时，dist递减，x大于时，dist递增，dist在x...

题意整理  给定N个城市，以及每个城市的开销。 一个前置城市数组，去y城市之前必须先去x城市。 牛妹手上有V元，她每次都会去开销最小的城市，如果开销相同，就选编号较小的城市，求牛妹最多能去几个城市。  方法一（优先队列+拓扑排序） 1.解题思路 首先明确一个事实，如果要去某个城市，那么他的前置城市一定都去过了，否则去不了这个城市。于是只要前置城市数目为0，就可以尝试访问这个城市，我们假设前置城市数为入度，记录在对应的Indeg入度数组。 由于每次都要选择花费最小的城市，如果花费相同，则选择编号最小的城市，所以可以将待去城市加入到优先队列（优先队列存放城市开销和城市编号组成的长度为2的数组），每...