思路： 题目的主要信息：  字符串的相似度定义为两个字符串的相同字符前缀长度 对于n个字符串，求任意两个字符串的相似度，并求总和 只出现小写字母a-z  方法一：暴力法具体做法： class Solution { public: int similarity(string& s1, string& s2){ //计算两个字符串相似度的函数 int len1 = s1.length(); int len2 = s2.length(); int n = min(len1, len2); //遍历较小的 int res = 0; for(int i = 0; i < n; i+...

思路： 题目的主要信息：  顺序输入字符，存在字符串s中 如果输入的是'<'，则回退一格，相当于删除当前输入的最末尾字符，如果当前输入为空不操作 输入只包含小写字母和'<'，问最后的结果是什么  方法一：数组过程模拟具体做法：使用数组临时存储所有字符，遍历字符串s，如果遇到'<'且数组为空，则不操作，遍历下一个；如果遇到'<'且数组不为空，则删除末尾元素；否则，字符加入数组的末尾。最后将数组中的元素存入string。 class Solution { public: string Typing(string s) { vector<char> temp; /...

思路： 题目的主要信息：  从字符串s的子序列中找到等于"niuniu"的子序列数 子序列即原串的删去任意个字符（包括0和全部） 字符串s长度默认不小于10，结果需取模1e9+7  方法一：动态规划具体做法：我们用表示以i-1为结尾的s子序列中出现以j-1为结尾的字符串t的个数，对于某一个字符，我们比较，如果其相等，我们选择匹配或者不匹配（不匹配就是删去这个，另外匹配的意思），二者相加即可；如果不相等，那只能选不匹配，于是转移方程就是这两个:  字符相等： 字符不相等：class Solution { public: int solve(string s) { int mo...

思路： 题目的主要信息：  选择题答案有15种情况：A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCDA,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD 对于每道题，要使前道题，A与C的相差不超过1，B与D想抄不超过2 问总共有多少种答案布局方式，结果需取模1e9+7  方法一：动态规划具体做法：我们给每个答案编号为0-14（对应上述15种情况），用表示前道题以编号结尾的题目的方案种类有多少。对于15种情况，我们遍历的15种情况，，一一比较，可以事先算出AC的差值和BD的差值，如果符合条件则将的对应的加入中。因...

思路： 题目的主要信息：  的跑道，要从到 每次下一步列号必须加1，行号可以是本行或者邻近的一行，比如1行可以到1行或者2行，2行可以到1行或者2行或者3行，3行可以到2行或者3行 数组x，y分别是路障的行列坐标，有路障的位置不能经过 问路径种类有多少，取模1e+7  方法一：动态规划具体做法：用辅助数组dp，表示起点到第行第列的方案数。那么如果，它就可以从第列第1行或者第2行走过来，因此方案数就是这二者相加。另外两种情况类似，转移方程如下：需要注意的是路障位置，我们一开始将dp数组中路障位置设置为-1，再后续如果遇到-1则路障位置的方案数设置为0，省去了额外表达路障的空间。 class So...

思路： 题目的主要信息：  跳上n级台阶，每次只能跳奇数级 a数组中存放着不能跳上的台阶序号 达不到n级就返回0 求跳上n级的方案数，结果需要取模1e9+7  方法一：动态规划具体做法：我们可以用动态规划，辅助数组dp，其中表示i级台阶方法数，有如下情况：  如果i级台阶有积水， 如果i为奇数，那它肯定由偶数级台阶跳来，于是，对于每个偶数级台阶跳一个相差的奇数即可 如果i为偶数，那它肯定由奇数级台阶挑来，于是，理由同上  按照上述说法，我们可以计算前缀奇数和与前缀偶数和来辅助dp数组。  class Solution { public: int solve(int n, int m, vect...

思路： 题目的主要信息：  用数组a表示项链的不同颜色，即不同数字表示不同颜色，且首尾相接 从数组中取出一段数字都不同的连续子序列，求子序列最长长度，需要注意首尾相接的情况  方法一：动态规划具体做法：我们可以将数组首尾相接，组成一个的新数组，就不需要再处理循环了。我们用表示以第个珠子结尾的最长连续不相同颜色的长度，遍历新数组，每次判断判断前个珠子是否和第个珠子同色,同色则停下，然后记录下最长长度。  class Solution { public: int solve(int n, vector<int>& a) { int res = 0; for(int i = 0;...

思路： 题目的主要信息：  x和y是位置坐标数组（位置可能会重复），a为其对应的金币数，k为钥匙数量 从(0，0)开始，每次行动时进入下一步行号列号都要至少加1，到达一个地方，需要用一把钥匙开启宝藏，获得金币 钥匙有限，求能够获得的最大金币数，同一个一个地方只能访问一次  可以利用贪心思想，用矩阵记录每个位置的最大金币数，每次开启宝藏的时候肯定选择开启那个地方的最大金币数的宝藏才能保证最多。 方法一：动态规划具体做法：后续对于每个位置，可以用动态规划。设表示范围内，剩余把钥匙时所能获得的最大收益，初始状态肯定是0.我们可以看到图中，对于固定的钥匙，处的值可以等于其上或者其左的值，因为每次行列都...

思路： 题目的主要信息：  从~中挑选,作为区间，其中，即边界点可以重合 如果存在至少个不同的质数，每个质数都可以整除~之间的每一个数 我们要找到第k长的这样的区间，返回其长度即  方法一：暴力法具体做法：根据题意，首先我们准备了2到数组最大值中的所有质数，记录到primes中。然后我们暴力遍历每一个数对，每次对于数对区间中的元素，对每一个primes中的质数，查看是否能整除区间中所有的元素，如果可以计数加1，当计数不小于时，我们就可以记录这对数对。然后我们重载sort函数的比较，使其排序时按照的大小来排序，这样我们就可以直接在排好序的数组中找到第大的数对了。  class Solution ...

思路： 题目的主要信息：  给出一个序列a，从中选出长度大于等于k的连续子序列，使子序列和最大 k一定不大于序列长度 连续子段指的是序列中一段连续的数字  方法一：暴力解法具体做法：首先长度的种类包含k到n这些长度，我们要遍历所有的长度选项。然后，对于每一个选项，遍历数组找到每一个可以起点的元素，向后相加长度那么多个单位即可得到一次的结果，我们比较每次的结果，取最大值即可。 class Solution { public: long long solve(int n, int k, vector<int>& a) { long long res = LONG_LONG_MI...

思路： 题目的主要信息：  一共辆货车，每辆容量为，需要运送n个鸡蛋 如果装满货车后，还剩有鸡蛋，则选择一辆货车容量翻倍，继续装，如此循环 同一辆车可以多次翻倍，求需要翻倍多少次  方法一：贪心+排序+差值运算具体做法：使用sort函数对数组排序，找到最大值。遍历数组x，对于每个，用减去容量，如果剩余鸡蛋数小于等于0，则不需要魔法返回0.如果最后还是大于0，我们选择增大容量最大的车，直到小于等于0. class Solution { public: int Holy(int n, int m, vector<int>& x) { int res = 0; sort(x.be...

思路： 题目的主要信息：  行列的矩阵，起始位置第一列任意行 每到一个矩阵一格时会获得该格子的金币 当位于第行第列时，他下一步最多可能有三种选择： 不花费金币跑到第i行第j+1列 花费的金币跑到第行第列（如果则不可以这么跑） 花费的金币跑到第行第列（如果则不可以这么跑）  初始金币无限，求能够获得的最多金币，即获得减去消耗  方法一：动态规划具体做法：可以用动态规划解决这类问题，首先假设就是第行第列能够获得最大金币数，其中，于是对于第行，它的前一个可以来自于第行的列或者是第行的列，如果是第行需要减去它在列时换行的花费。因此有如下转移方程：  class Solution { public: i...

思路： 题目的主要信息（直接看题意，背景不重要）：  对于数组mSet，每次以前个元素为一个集合，如果集合中出现了最小数到最大数中的所有元素，则返回true，否则返回false 需要判断每一个前缀是否为true，第一个元素一定是true  方法一：排序+暴力解法具体做法：遍历数组mSet，每次将新元素加入辅助数组，然后对辅助数组进行排序，排成递增序。然后遍历辅助数组，如果出现前后两个数相差大于1，则一定为false，遇到相差为1的元素，计数器加一，最后如果计数器等于尾元素减首元素说明填满了这其中所有的元素，是返回true。 class Solution { public: vector<...

思路： 题目的主要信息：  1红球+1黄球+1蓝球=1彩票 1红球=2黄球+1蓝球 1黄球=2蓝球+1红球 1蓝球=2红球+1黄球  球的相互兑换是循环的，要求最多可兑换的彩票数 方法一：过程模拟+贪心具体做法：采用贪心思想，因为球换球不划算，所以先把能兑换彩票的球换完，再考虑球换球。在abc不为0的情况下，每个参数减1，彩票数加1。一旦有一个数（假设是a)为0，用另外两个数来换球，这种时候需要3个b球+2个c球才能换一张彩票，最后换到只剩一种颜色的球为止。。因为是一个循环，所以不管是哪个球先被耗尽，另外两个球都能表示。  class Solution { public: int two_co...