Leetcode---359周赛

题目列表

2828. 判别首字母缩略词

2829. k-avoiding 数组的最小总和

2830. 销售利润最大化

2831. 找出最长等值子数组

一、判断首字母缩略词

 纯模拟，代码如下

class Solution {
public:bool isAcronym(vector<string>& words, string s) {string tmp;for(auto & x:words)tmp+=x[0];return tmp==s;}
};

二、k-avoiding数组的最小和

 

根据题目所给的数据范围，我们甚至可以将和为k的数据对全部求出来，然后一个个筛选，但是没必要，我们只要从小到大枚举元素，将枚举过的元素记录起来，当遇到能匹配的元素时跳过就行，直到选满n个元素（有点贪心的意思在里面）

class Solution {
public:int minimumSum(int n, int k) {set<int> s;int sum=0;for(int i=1;n;i++){if(s.find(k-i)==s.end()){s.insert(i);sum+=i;n--;}}return sum;}
};

或者直接推导出数学公式，代码如下(利用等差数列求和公式)

class Solution {
public:int minimumSum(int n, int k) {int m=min(k/2,n);return m*(m+1)/2+(k+k+(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, vector<vector<int>>& offers) {//将右端点相同的买家分类记录vector<vector<int>> v(n);for(int i=0;i<offers.size();i++)v[offers[i][1]].push_back(i);int dp[n+1];dp[0]=0;//数组初始化for(int i=1;i<=n;i++){dp[i]=dp[i-1];//不选第i个房子（i和房子下标差1）for(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(vector<int>& nums, int k) {int n=nums.size();vector<vector<int>> v(n+1);for(int i=0;i<n;i++)v[nums[i]].push_back(i);int ans=1;for(int i=1;i<=n;i++){for(int left=0,right=0;right<v[i].size();right++){while(v[i][right]-v[i][left]-(right-left)>k)left++;ans=max(ans,right-left+1);}}return ans;}
};