查网站备案名称,成都购物网站建设,自己建的网站百度查找不到,网页设计代码模板在哪找题目列表 2828. 判别首字母缩略词
2829. k-avoiding 数组的最小总和
2830. 销售利润最大化
2831. 找出最长等值子数组
一、判断首字母缩略词 纯模拟#xff0c;代码如下
class Solution {
public:bool isAcronym(vectorstring words, string s) {string tmp…题目列表 2828. 判别首字母缩略词
2829. k-avoiding 数组的最小总和
2830. 销售利润最大化
2831. 找出最长等值子数组
一、判断首字母缩略词 纯模拟代码如下
class Solution {
public:bool isAcronym(vectorstring words, string s) {string tmp;for(auto x:words)tmpx[0];return tmps;}
};
二、k-avoiding数组的最小和 根据题目所给的数据范围我们甚至可以将和为k的数据对全部求出来然后一个个筛选但是没必要我们只要从小到大枚举元素将枚举过的元素记录起来当遇到能匹配的元素时跳过就行直到选满n个元素有点贪心的意思在里面
class Solution {
public:int minimumSum(int n, int k) {setint s;int sum0;for(int i1;n;i){if(s.find(k-i)s.end()){s.insert(i);sumi;n--;}}return sum;}
};
或者直接推导出数学公式代码如下(利用等差数列求和公式)
class Solution {
public:int minimumSum(int n, int k) {int mmin(k/2,n);return m*(m1)/2(kk(n-m-1))*(n-m)/2;}
};
三、销售利润最大化 这题相信有人一看到最大化就直接去想贪心了但是这题的贪心策略是不确定的因为它是由区间和价格共同影响决定的好既然贪心不行我们就要去想想动态规划 1.dp数组有几个维度含义是什么(最重要的一步后面几个问题都是围绕这个问题展开的) 根据题目要求我们定义dp[i]代表前i个房子能获取的最大利润 2.dp数组的递推公式 1)如果不选i这个位置的房子那么相当于只考虑前i-1个房子即dp[ i ]dp[ i - 1 ] 2)如果选i这个位置的房子那么我们只能选以i为右端点区间的买家所以前i个房子的最大利润以i为右端点区间的买家价格该买家买的左端点之前的房屋最大利润 即dp[i]offers[j][2]dp[offer[j][0] - 1] j是代表以i为有端点的买家下标 上诉两种情况取最大值得到dp[i] 3.dp数组的初始化 dp[0]0即前0个房子的最大利润是0前0个房子也就是没有房子可以选故利润为0 动态规划问题总结关键是将上面三个问题搞明白尤其是第一个问题它将直接关乎另外两个问题的思考难度和方法的正确性 代码如下
class Solution {
public:int maximizeTheProfit(int n, vectorvectorint offers) {//将右端点相同的买家分类记录vectorvectorint v(n);for(int i0;ioffers.size();i)v[offers[i][1]].push_back(i);int dp[n1];dp[0]0;//数组初始化for(int i1;in;i){dp[i]dp[i-1];//不选第i个房子i和房子下标差1for(auto x:v[i-1]){//选第i个房子下标为i-1dp[i]max(dp[i],dp[offers[x][0]]offers[x][2]);//这里的offers中记录的左端点是下标不用-1}}return dp[n];}
};
四、找到最长等值子数组 这题找最长等值子数组即将不同数字为等值的最大值都算出来取最大值即可
不同数字的最大值计算用双指针滑动窗口
代码如下
class Solution {
public:int longestEqualSubarray(vectorint nums, int k) {int nnums.size();vectorvectorint v(n1);for(int i0;in;i)v[nums[i]].push_back(i);int ans1;for(int i1;in;i){for(int left0,right0;rightv[i].size();right){while(v[i][right]-v[i][left]-(right-left)k)left;ansmax(ans,right-left1);}}return ans;}
};
