思路： 题目的主要信息：  长度为n为队伍，人员编号1-n cutIn数组中是要插队的编号，依次进行插队，即加入到最前面 求最后有多少人不在原来的位置  方法一：哈希表具体做法：对于最后的队列，没有插过队的人肯定都排在后面，最大插队元素是其分界线，最大插队元素之前的位置都可能有改变，之后的就不会有变化，如果没有重复，它就是严格分界线。因为我们只要最大插队元素，然后减掉重复的元素，即可得到位置改变的人数。去重可以用哈希表。 class Solution { public: int countDislocation(int n, vector<int>& cutIn) { in...

思路： 题目的主要信息：  给一串数组，每次找到一个位置进行一次操作：将该位置前后一个数及本身改为三者中的最大值 一共进行n次操作，每次操作需要找到改变后使数组和最大那个位置来改变  方法一：暴力解法（超时）具体做法：利用二进制掩码的特性，枚举所有位置选择或是不选择的组合（相当于n次操作，选择的位置进行排列足组合），按照顺序模拟改变的值，最后更新较大值即可。 class Solution { public: vector<int> solve(int n, vector<int>& a) { vector<int> res(n, 0); for(in...

思路： 题目的主要信息：  数组a是初始时水桶里的水 数组p是每次询问后，要求水桶中水相同的水桶数量 一共是q次查询，每次需要找到使水桶中拥有相同水量的水桶数量达到p中要求的最少花费，即每次加水量最少  方法一：动态规划+前缀和具体做法：我们用（下标1开始）表示前i个数的和。对于某一次查询，我们要求需要有个相同水量的水桶，那我们知道经过第次查询，前面的已经相同了，所以我们后续找要添加到的标杆水桶就从下标为开始，于是利用前面求到的前缀和，我们可以得到总花费，即标杆水桶的水量乘上需要相同的个数，减去前面已经有的水量（这个通过前缀和相减得到），遍历后续数组找到这个花费的最小值即可。找到之后，我们需要...

思路： 题目的主要信息：  从一个一维数组中任选4个数，组成四边形，求能组成的四边形的最大面积 返回结果与正确答案的误差应小于0.00001  性质1：能够组成四边形的四条边必然满足，三边之和大于第四边性质2：四条边已知（a,b,c,d)的四边形，最大面积（形状不确定，因为四边形有不稳定性，只能求最大面积）为，其中因为我们要求的是最大面积，因此用上述公式计算面积也没错。 方法一：暴力法具体做法：四次遍历数组，找到所有四个数的组合，用性质1验证其是否是四边形，用性质2计算其最大面积。 class Solution { public: double square(int a, int b, int...

思路： 题目的主要信息：  每天吃掉蛋糕总数的1/3，再额外吃1个 吃到第n天还剩下1个蛋糕，问最开始总共有多少蛋糕  这是一个数学问题，可以用递归、动态规划、迭代处理。 方法一：递归具体做法：第n天还剩下1一个蛋糕，那么总蛋糕数就是n-1的子问题+1的3/2，可以写出如下递归： class Solution { public: int cakeNumber(int n) { if(n == 1) //1和2单独讨论 return 1; if(n == 2) return 3; return 3 * (cakeNumber(n - 1) + 1) / 2; //返回子问题+1的3/2 } };...

思路： 题目的主要信息：  从一个六边形的01矩阵中找到全1的三角形，且要找边长最大的一个 其中六边形矩阵的数据以vector数组的形式给出因为给出的数据是一维的，现在首要的难题的是将一维数组表示的六边形矩阵装入二维矩阵。仔细观察边长为的六边形矩阵，一共是行，最长是列。因此我们建立一个这样的矩阵保存数据。因为六边形上下形状的特殊性，对于上半个矩阵的列（下标0开始），元素分布在矩形矩阵的，下半个矩阵因为与上面是对称的，所以可以类似的推断。至此，将一维数组记录的六边形矩阵放入一个二维矩阵中，二维数组中空出来的格子用0填充，反正我们后续只计算有1的格子。  方法一：动态规划具体做法：有了记录六边形的...

思路： 题目的主要信息：  两个长度相同的数组a与b，长度都为n 统计数对出现的次数，其中：     相当于是相同的下标，a数组中的区间求和等于b数组中两端相加。 方法一：暴力法具体做法：一个慢指针遍历a数组中的每个元素，另一个快指针遍历a数组中后面的所有元素，并累加快慢指针之间的和，并每次与快慢指针下标在b数组中对应两个元素的和作比较，若是相等则计数加一。 class Solution { public: int countLR(vector<int>& a, vector<int>& b) { int count = 0; //计数 for(int ...

思路： 题目的主要信息：  对一个数组，每次选1个元素进行操作，两次操作后使数组和最小 操作为：任选一个元素x，将数组中所有大于等于x的数减去x  方法一：暴力法具体做法：首先对数组进行排序，使之成为递增顺序。求一个数组的和sum，然后就是找到sum要减去的最大值。这个最大值就是进行两次操作的时候要减去的数的总和。因为数组是递增次数，因此我们如果要减去的元素是，那么从下标到全部都可以减去，减去的部分就是，因此我们可以遍历每个元素，减去1个之后，再对其排序再遍历减去第二个元素，找到能够减去的最大值。最后sum减去最大值就是所求结果。 class Solution { public: long l...

思路： 题目的主要信息：  求给定数组的一个子序列，该子序列修改一个元素后可以变成完全递增序列，可以不用修改 要求返回子序列的最长长度  基本思路就是遍历数组中的所有元素，检查如果该元素后一个元素大于前一个元素，我们可以找到以它前一个元素结尾的最长递增序列加上以它后一个元素开始的最长递增序列，二者相加再加上自己就是可修改的最长递增序列。 方法一：递归具体做法：我们可以递归得到以结束的最长递增序列长度：对于，如果，则返回子问题的基础上加1，否则直接返回1.同理可得到以开始的最长递增序列长度。遍历数组，一旦，就可以尝试连接左右两边的最长递增子序列长度。 class Solution { publi...

思路： 题目的主要信息：  找到给定串中的最长回文子序列的长度 子序列不同于字串，不要求字符全部相邻 回文序列是指这个序列无论从左读还是从右读都是一样的  方法一：递归（超时）性质：一个字符串的最长回文子序列等于该字符串与其逆序的最长公共子序列。具体做法：我们可以利用上述性质，构造字符串s的逆序字符串rs，然后递归寻找两个字符串的最长公共子序列。对于下标为n-1的s与rs，若是此时两个字符相等，那么子问题就是n-2了，若是不相等，任意一个往前移一个下标作为子问题，找二者的最大值。 class Solution { public: int recursion(int i, int j, stri...

思路： 题目的主要信息：  vector中是每个信封的长度和宽度，当一个信封长度和宽度都大于另一个信封时，便可以嵌套 题目要求最大嵌套数量，且长宽不能颠倒  方法一：动态规划具体做法：我们可以用动态规划来解决。首先对数组进行排序，将较长的信封放在前面，使之成为一个信封长度递减的序列。维护一个辅助数组dp，表示仅使用信封下标为时的最大嵌套度。我们遍历整个数组维护dp，对于，我们遍历其前面所有的信封，找到能放下它的最大嵌套度，并更新 class Solution { public: int maxLetters(vector<vector<int> >& lette...

思路： 题目的主要信息：写一个atoi函数，将字符串转变成int型数字，输入没有任何限制，需要注意以下几点：  前导0与前导空格要全部去掉 第一个符号是正负号的情况 输入了非数字要直接跳出 输入达到了int型表示边界 空串返回0  方法一：遍历法具体做法：用一个index全程记录字符串下标。按照上面提到的点，先排除前导空格，再检查符号，最后转换数字，注意边界等情况。一个遍历可以解决。 class Solution { public: int atoi(const char *str) { string s = str; //转换为string类型 int n = s.length(); // ...

思路： 题目的主要信息：  从数组num找出所有加起来等于target的组合 每个组合num中每个元素只能用1次 返回的值必须是非递减次序，组合不能重复  方法一：递归+枝剪具体做法：对于排序后的num数组中第一个元素，我们可以考虑如果它比target大，那么后续都会比target大，没有加起来等于target的组合；但是如果它比target，我们可以考虑要不要将其加入待选路径（待选组合）中，如果没有加入（重复了），考虑下一个元素，target不变，如果加入了待选路径，考虑下一个元素的时就需要，由此转化成了一个子问题，递归结束的点就是或者数组遍历结束。因此，我们可以遍历数组，对于每个数使用递归...

思路： 题目的主要信息：  在S字符串中找到包含T字符串所有字符的最小字串 要求时间复杂度 如果S中没有包含T中所有字符的子串，返回空字符串""，若有有则存在唯一最短  方法一：滑动窗口+哈希表+双指针具体做法：  维护一个哈希表，里面是字符串T的字符为key值，初始时当字符在T中出现一次则减一。 依次遍历字符串S，如果匹配则将哈希表中的内容加一。 在遍历过程维护一个窗口，如果哈希表中所有元素都大于0，则窗口收缩向左移动，如果不满足这个条件则窗口右移继续匹配。 窗口移动的时候需要更新最小窗口，以取得最短。 如果匹配到最后，窗口left（初始为-1）也没有右移，说明没有找到，...