题目描述有n个水桶，第i个水桶里面水的体积为Ai，你可以用1秒时间向一个桶里添加1体积的水。有q次询问，每次询问一个整数pi,你需要求出使其中pi个桶中水的体积相同所花费的最少时间。对于一次询问如果有多种方案，则采用使最终pi个桶中水的体积最小的方案。 方法一：动态规划的思想 求解思路对于求解本题目，我们可以使用动态规划的思想，我们用dp[i]表示前i个数的和。对于题目所提到的每次询问，我们看成第i次查询的说法。我们要求需要有p[i]个相同水量的水桶，根据前面的叙述，我们可以得到花费的公式为：sum=a[j-1]*p[i]-(dp[j]-dp[j-p[i]]).然后我们遍历后续数组找到花费的最...

题目描述给定大小为n的整数集合A，代表n根木棍的长度。从A中任选4根木棍组成一个四边形，求其面积最大为多少。数据保证有解。程序返回结果与正确答案的误差应小于0.00001 方法一：暴力方法 求解思路对于求解本题目，我们应首先知道构成四边形的充要条件为三边之和大于第四边，并且在四边已知的情况下四边形的最大面积为 ，其中sum=(a+b+c+d)/2.根据以上条件，我们将题目所给的数组进行遍历，首先判断是否否成四边形，若构成四边形则计算其最大面积，最后输出结果即可。   解题代码 class Solution { public: double square(int a, int b, int c,...

题目描述给你一个边长为 a 的六边形 01 矩阵，请找到一个最大的全1子三角形，输出三角形的边长b。 方法一：动态规划方法 求解思路对于本题目要求解最大的全1子三角形，因为题目给出的数据，为了方便题目的求解，我们将一维数组表示的六边形矩阵装入二维矩阵。根据边长为a的六边形矩阵，共有2a行，最长4a-1列。我们将其元素放在矩形矩阵的[a-i-1,3a+i-1]中，并且我们根据正六边形的对称性，我们选定其一个朝向，并且用dp[i][j]记录以矩形矩阵中某一个点为顶点的三角形边长的最大值。根据图形的特点我们有状态转移方程：dp[i][j]=min{dp[i+1][j-1],dp[i+1][j+1]}...

题目描述牛牛有两个长度为n的数组a,b,牛牛希望统计有多少数对(l,r)满足：1、0<=l<=r<=n-12、  方法一：暴力方法 求解思路对于求解本题目，我们使用内外层指针来进行暴力循环求解。让外层指针遍历数组a中的每个元素，内层指针遍历外层指针以后的在数组a中的元素并且累加。同时将累加和与内外层指针在数组b中对应位置元素之和作比较，若相等，则计数+1.   解题代码 class Solution { public: int countLR(vector<int>& a, vector<int>& b) { int hycount =...

题目描述给定一个数组 nums，其中有 n 个非负整数。你的目的是进行两次操作，使得数组的元素之和最小。每次操作形如：任选一个整数 x ，将数组中所有大于等于 x 的数减去 x 。 方法一：暴力方法 求解思路对于题目给出的操作规则，我们首先对数组进行排序，使其按照递增的顺序排列。题目要求的数组和，即是原数组进行两次操作以后，减去数的总和。因此我们可以遍历每个元素，进行第一步操作以后再对其进行排序和第二部操作，最终找到能够减去的最大值，即是题目所要求的结果。   解题代码 class Solution { public: long long minimumValueAfterDispel(vec...

题目描述将整数n分成k份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5;1，5，1;5，1，1;问有多少种不同的分法。输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 )输出：一个整数，即不同的分法。 方法一：递归求解 求解思路对于本题目要求将整数n分成k份的个数，我们使用递归的思想进行解答。首先我们明确递归的终止条件为分成了k份。然后递归进行推进，当份数加1时，我们设置rest和use两个变量，其中rest减去已经分配的数字，use则是当前尝试分配的数字，根据上述描述，最终求出题目的答案即可。   解题代码...

题目描述已知一棵节点个数为n的二叉树的中序遍历单调递增，求该二叉树能能有多少种树形,输出答案取模10^9+7 方法一：递归求解 求解思路对于本题目，因为题目给出一颗节点个数为n的二叉树的中序遍历单挑递增的条件，我们任意取一个节点为根节点，然后左子树的树形数目加上右子树的树形数目即为题目所要求的总的树形数目。但是由于普通递归会有很多重复情况，我们声明一个用来记录重复情况的数组，当数组的值不为0时，递归直接返回。   解题代码 import java.util.*; public class Solution { int mod=1000000007; // 常数 long[] mymemo; /...

题目描述给你一个非空模板串S，一个文本串T，问S在T中出现了多少次 方法一：暴力求解 求解思路对于本题目要求出模板串S在文本串T中出现的次数，我们想到直接从文本串T的第一个位置往后寻找模板串S长度的子串，然后拿出来和S比较即可，并且我们设置res变量来记录相同的个数。   解题代码 class Solution { public: int kmp(string S, string T) { if(S.empty() || S.size() > T.size()) return 0; // 边界 int hyres = 0, next[S.size() + 1]; next[0] = -1...

题目描述给你一个长度为n的数组A。A[i]表示从i这个位置开始最多能往后跳多少格。求从1开始最少需要跳几次就能到达第n个格子。 方法一：暴力求解 求解思路对于本题目要求从1开始最少需要跳几次就能到达第n个格子。我们设置三个变量分别记录当前位置、最远跳跃位置和跳跃次数。每当当前位置和索引i相等时，将最远跳跃位置赋值给当前位置，跳跃次数加1，如果索引中没找到当前位置，则说明已经跳出数组A了。然后我们从第一个到最后n-1依次进行遍历，每经过之处都要求出最大可达到的位置。   解题代码 import java.util.*; public class Solution { public int Jum...

题目描述有n个活动即将举办，每个活动都有活动的开始时间与活动的结束时间，第i个活动的开始时间是starti,第i个活动的结束时间是endi,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，活动主持人参与了第i个活动，那么该主持人在[starti,endi]这个时间段不能参与其他任何活动。求为了成功举办这n个活动，最少需要多少名主持人。 方法一：队列思想求解 求解思路对于本题目关于主持人个数的求解，我们首先将start和end按时间的早晚进行排序。如果开始时间相同，则按结束时间进行排序。然后我们使用队列，如果当前开...

题目描述已知一个背包最多能容纳物体的体积为V现有n个物品第i个物品的体积为vi，第i个物品的重量为wi。求当前背包最多能装多大重量的物品 方法一：动态规划 求解思路对于求解01背包问题，我们想到使用动态规划进行求解，可以发现，对于一个物体，我们有两种选择，放或者不放进背包。这样便将问题划分成了更小的子问题。我们使用表示当前第i个物品，背包体积为V时能够得到的最大重量和。表示题目所给的物体的体积和重量。因此根据第i-1个物品的放或者不放进背包的情况对第i个物品进行讨论，我们即可得到转移方程为：，最终我们得出题目要求的答案。   解题代码 class Solution { public: int ...

题目描述给你一个n（1≤n≤10^5），和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，求该序列的最大子序列和（挑选出的子序列可以为空）。 方法一：动态规划 求解思路对于本题目要求在不相邻的位置时求解最大子序列的和。这道题目是一个01背包问题，即根据前边计算好的i个节点的结果判断是否选择当前节点，我们假定dp[i]为i位置最大子序列的和，其状态转移方程为： ，其中array[i]表示题目所给的数组在第i位置上的数，根据以上描述即可求解出相应的结果。   解题代码 import java.util.*; public class Solution { public long subse...

题目描述一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。给定一个字符串，请编写一个函数，返回其最长的重复字符子串。若不存在任何重复字符子串，则返回0。 方法一：暴力解法 求解思路对于本题目，我们直到这个重复的子串是小于原字符串的一半的。然后我们对子串进行一一列举，从长度为1的子串一直到长度为原字符串一半长度的子串。继而将列举出来的字符串进行重复判断，即可得到题目的答案 。   解题代码 class Solution { public: //对具体的起点与长度，确认字符串是否为重复拼接形式 bool check(str...

题目描述给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。 方法一：暴力解法--直接反转字符串，判断是否相等 求解思路对于本题目，判断是否是回文，我们用最直接的方法，将字符串直接翻转过来，然后判断是否相等即可。   解题代码 import java.util.*; public class Solution { public boolean judge (String str) { String hyres = new StringBuffer(str).reverse().toString(); // 反转字符串 return str.equal...