题目描述给定n个数字的序列a0,a1,…an−1，对位置i进行一次操作将使得ai−1,ai,ai+1都变成max(ai−1,ai,ai+1)特别的，对位置0进行操作将使得a0和a1都变成max(a0,a1)对位置n-1进行操作将使得an−2和an−1都变成max(an−2,an−1)并且操作过位置i之后，位置0到i都不能再操作设最多可以操作k(k≤n)次，最后得到的整个序列的总和最大可以是mk你需要求出m1,m2,...mn  方法一：动态规划解法 求解思路对于本题要求的最大值等于数组的元素和加上每次操作后增加最多的大小。因此可以一开始就求出数组的元素和，然后用辅助数组dp[n][n]来进行相...

题目描述给定两个n * n的矩阵 A和 B，求A * B。 方法一：暴力解法 求解思路求解矩阵A和B相乘，我们直接根据矩阵乘法的定义，行列元素对应相乘后相加，即可得到本题的答案。   解题代码 class Solution { public: vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) { int n = a.size(); // 存储矩阵大小 vector<vector<int>...

题目描述牛牛刚刚得知牛牛所在的街道上有一个人得了新型冠状病毒！！！由于新型冠状病毒传染力很强，所以，只要在被传染的人的活动范围内活动都有可能被感染！现根据大数据可以得知，初始患病人在整个街道人群中的序号Pid和每个人在街道上的活动区域Pos。因为情况紧急，所以牛牛想请你帮忙快速计算下究竟最坏情况下会有多少人感染上冠状病毒？ 方法一：贪心解法 求解思路对于求解本题，我们要找多少人感染上病毒，就是找每个人活动范围的交集，然后取交点最多的那个区间并输出结果。对于如果求解交集，我们可以用贪心的思想去寻找，按照左端点从大到小排序，维护右端点的最大值，这样我们就可以知道每一个区间中有多少交点，这样即可得到...

题目描述城市 A 新建了 n 个座房子，城市规划处用 n−1 条双向街道将房子连在一起，使得任意两座房子之间有且仅有一条道路可达。牛牛和牛妹将被随机分到两个房子，现在牛牛想知道，他和牛妹房子的最长路径是多少。 方法一：暴力解法 求解思路对于求解本题，我们可以将房子看作节点，双向街道看作边，即n个节点，n-1条边，可以构成树。我们对每个叶节点做一次dfs，求出到其它叶节点的距离，然后我们保留最大值即可。   解题代码 class Solution { #define pii pair<int, int> private: long long myans; vector<pii&...

题目描述牛牛最近搬到了一座新的城镇，这个城镇可以看成是一个一维的坐标系。城镇上有n个居民，第i个居民的位置为ai。现在牛牛有m个搬家方案，在第i个方案中他会搬到位置xi。 俗话说的好，远亲不如近邻。现在牛牛想知道，对于每个搬家方案，搬家后与最近的居民的距离为多少。 方法一：暴力解法 求解思路对于求解本题，我们对每个方案的位置，求出所有居民位置，即可得到本题目的答案。   解题代码 class Solution { public: vector<int> solve(int n, int m, vector<int> a, vector<int> x) { v...

题目描述牛牛是励志成为世界第一宝可梦大师的宝可梦训练家。现在他遇到了一个强劲的野生宝皮卡丘，野生宝皮卡丘的生命值是HP，攻击力是ACK，牛牛召唤的宝可梦是杰尼龟。杰尼龟的生命值是HP2，攻击力是ACK2，除此之外身为训练家还可以给宝可梦吃药让他满血复活(吃药发生在双方发动攻击之前，并且吃药一方不得在本回合发动攻击)。牛牛想知道他最少多少回合才能能打败野生宝皮卡丘？因为皮卡丘会电光一闪，所以皮卡丘总是比杰尼龟先发动攻击。若能成功击败野生皮卡丘则返回最少回合数，否则返回-1。 方法一：暴力解法 求解思路对于本题求解最少多少次可以击败野生皮卡丘，我们对所有的情况进行模拟枚举即可，即只要牛牛的宝可梦这...

题目描述现在给定一个正整数N，牛牛希望知道N最少表示成多少个素数的和。素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 提示哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。 方法一：暴力解法 求解思路对于本题求解N最少能表示成多少个素数的和，想到使用DFS枚举素数累加，我们可以先判断N本身是不是素数，然后暴力判断N是否可以分解成两个素数的和，如果不能分解，则答案自然就是3.据此我们根据上述思路进行求解。   解题代码 class Solution { public: bool IsPrime(int N) // 判断是否为素...

题目描述牛妹有有两个字符串S1与S2，她想知道S2在S1中的哪一个循环同构串中的出现次数最多，如果有多个，请输出字典序最小的一个。循环同构串的定义：不断地将si...sn的部分提前到s1...si−1之前,得到一个新的字符串，这些新的字符串称为循环同构串。例：abcc的循环同构串为：abcc,bcca,ccab,cabc。 如果S2没有在S1的任意一个循环同构串中出现则返回IMPOSSIBLE否则返回字符串代表答案。 方法一：暴力解法 求解思路对于本题求解循环同构串，我们自然想到将所有的情况进行枚举，并且用S2与枚举出来的字符串进行一一对比，这样即可求解出题目所要求的字符串。   解题代码 c...

题目描述牛妹在和牛牛下牛客象棋。现在轮到牛妹了，牛妹想知道她在这一回合能否战胜牛牛。 棋盘chessboard上只可能包含：炮，将，车，兵 牛客象棋的规则解释：炮：炮在不吃子的时候，走动与车完全相同，但炮在吃棋子时，必须跳过一个棋子，我方的和敌方的都可以兵：可以上下左右移动，每次只能移动一格车：上下左右均可走，只要无棋子阻拦，步数不受限制。将：可以上下左右移动，每次只能移动一格接下来给出一个棋盘，牛妹的棋子用大写字母表示，牛牛的棋子用小写字母表示。将用J,jJ,j表示，炮用P,pP,p表示，车用C,cC,c表示，兵用B,bB,b表示，没有棋子的格子用..表示保证棋盘上一定同时包含JJ与jj各一...

题目描述众所周知，牛牛不喜欢6这个数字（因为牛牛和66发音相近）所以他想知道，不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的）输入只包含一个正整数n（1<=n<20） 方法一：递归的思想 求解思路对于本题目所要求解的答案，因为要求出不连续的6，因此我们自然想到第i位数字是否为6与i-1和i-2这两位是否为6有关，因此我们可以用递归的方法求出相应的答案。   解题代码 import java.util.*; public class Solution { long[] memory; // 辅助数组 public String calculate (int n) { m...

题目描述实现函数 atoi 。函数的功能为将字符串转化为整数提示：仔细思考所有可能的输入情况。这个问题没有给出输入的限制，你需要自己考虑所有可能的情况。 方法一：遍历的方法 求解思路对于本题目所给出的条件，由于对输入没有任何限制，因此参考部分作者的思路，写出如下需要注意的几点。1、前缀0和空格要全部去掉2、判断第一个符号为正号or负号的情况3、输入非数字的处理4、输入的数字超过了int类型的范围5、空串的情况然后我们根据上述情况，用index记录字符串的下表，按照上述的情况进行逐个字符的判断，然后求得结果。   解题代码 class Solution { public: int atoi(co...

题目描述众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。地板是N×M的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。地板的坐标是左上角(1,1) 右下角（N, M）。牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步每次走过一个格子，拿起（并且必须拿上）这个格子上的礼物。牛妹想知道，她能走到最后拿起的所有礼物体积最小和是多少？ 方法一：动态规划的方法 求解思路对于本题目的求解，我们使用动态规划的思想进行求解，当下一步只能往右边走时，则此时数据只跟左边的数据有关。当下一步只能往下走时，则此时数据只跟上边的数据有...

题目描述众所周知，牛能和牛可乐经常收到小粉丝们送来的礼物，每个礼物有特定的价值，他俩想要尽可能按照自己所得价值来平均分配所有礼物。那么问题来了，在最优的情况下，他俩手中得到的礼物价值和的最小差值是多少呢？p.s 礼物都很珍贵，所以不可以拆开算哦 方法一：动态规划的方法 求解思路对于本题目的求解，我们可以将此题目看成背包容量为总和的一半的01背包问题。我们要装两部分，并且这两部分之间的差值要尽可能的小。我们依次遍历数组，利用动态规划的思想尽力将背包填满，对于背包中剩余余量，我们可虑装或者不装，因此状态转移公式为：dp[j]=max{dp[j],dp[j-present[i]]+present[i...

题目描述给定两个长度相等的，由小写字母组成的字符串S1和S2，定义S1和S2的距离为两个字符串有多少个位置上的字母不相等。现在牛牛可以选定两个字母X1和X2，将S1中的所有字母X1均替换成X2。（X1和X2可以相同）牛牛希望知道执行一次替换之后，两个字符串的距离最少为多少。 方法一：暴力方法 求解思路对于本题目，给出的条件中，因为全是小写字母，我们替换的X1和X2也都是小写字母，因此我们可以暴力枚举所有的小写字母作为被替换和替换的情况，然后分别计算每种情况的距离，然后从中求出最小值即可。   解题代码 class Solution { public: int GetMinDistance(st...