网站制作的合同,wordpress小工具用不,制作电子商务网站,南阳企业网站排名优化LeetCode第359场周赛 判别首字母缩略词k-avoiding 数组的最小总和销售利润最大化找出最长等值子数组 判别首字母缩略词
给你一个字符串数组 words 和一个字符串 s #xff0c;请你判断 s 是不是 words 的 首字母缩略词 。 如果可以按顺序串联 words 中每个字符串的第一个字符… LeetCode第359场周赛 判别首字母缩略词k-avoiding 数组的最小总和销售利润最大化找出最长等值子数组 判别首字母缩略词
给你一个字符串数组 words 和一个字符串 s 请你判断 s 是不是 words 的 首字母缩略词 。 如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s 则认为 s 是 words 的首字母缩略词。例如“ab” 可以由 [“apple”, “banana”] 形成但是无法从 [“bear”, “aardvark”] 形成。 如果 s 是 words 的首字母缩略词返回 true 否则返回 false 。
示例 1 输入words [“alice”,“bob”,“charlie”], s “abc” 输出true 解释words 中alice、“bob” 和 “charlie” 的第一个字符分别是 ‘a’、‘b’ 和 ‘c’。因此s abc是首字母缩略词。 示例 2 输入words [“an”,“apple”], s “a” 输出false 解释words 中 “an” 和 apple的第一个字符分别是 ‘a’ 和 ‘a’。 串联这些字符形成的首字母缩略词是 “aa” 。 因此s “a” 不是首字母缩略词。 示例 3 输入words [“never”,“gonna”,“give”,“up”,“on”,“you”], s “ngguoy” 输出true 解释串联数组 words 中每个字符串的第一个字符得到字符串 “ngguoy” 。 因此s ngguoy是首字母缩略词。 提示 1 w o r d s . l e n g t h 100 1 words.length 100 1words.length100 1 w o r d s [ i ] . l e n g t h 10 1 words[i].length 10 1words[i].length10 1 s . l e n g t h 100 1 s.length 100 1s.length100 words[i] 和 s 由小写英文字母组成 思路 简单模拟题直接按照题意取出每个单词的首字母拼接起来判断和字符串s是否相等即可。 代码
class Solution {
public:bool isAcronym(vectorstring words, string s) {string res;for(auto word:words){resword[0];}return ress;}
};k-avoiding 数组的最小总和
给你两个整数 n 和 k 。 对于一个由不同正整数组成的数组如果其中不存在任何求和等于 k 的不同元素对则称其为 k-avoiding 数组。 返回长度为 n 的 k-avoiding 数组的可能的最小总和。 示例 1 输入n 5, k 4 输出18 解释设若 k-avoiding 数组为 [1,2,4,5,6] 其元素总和为 18 。可以证明不存在总和小于 18 的 k-avoiding 数组。 示例 2 输入n 2, k 6 输出3 解释可以构造数组 [1,2] 其元素总和为 3 。 可以证明不存在总和小于 3 的k-avoiding 数组。 提示 1 n , k 50 1 n, k 50 1n,k50 思路 简单模拟题需要构造一个长度为n的数组满足不存在求和等于k的两个元素。数据范围很小那么直接从1开始枚举将每个数插入数组之前判断该数字插入是否会和之前的数字相加等于k不会等于k才能插入数组中。 代码
class Solution {
public:bool Find(vectorintp,int x,int k){for(auto a:p){if(ak-x)return 1;}return 0;}int minimumSum(int n, int k) {int x1,sum0;vectorintp;while(p.size()n){if(!Find(p,x,k)){sumx;p.push_back(x);}else x;}return sum;}
};销售利润最大化
给你一个整数 n 表示数轴上的房屋数量编号从 0 到 n - 1 。 另给你一个二维整数数组 offers 其中 o f f e r s [ i ] [ s t a r t i , e n d i , g o l d i ] offers[i] [start_i, end_i, gold_i] offers[i][starti,endi,goldi] 表示第 i i i 个买家想要以 g o l d i gold_i goldi 枚金币的价格购买从 s t a r t i start_i starti 到 e n d i end_i endi 的所有房屋。 作为一名销售你需要有策略地选择并销售房屋使自己的收入最大化。 返回你可以赚取的金币的最大数目。 注意 同一所房屋不能卖给不同的买家并且允许保留一些房屋不进行出售。
示例 1 输入n 5, offers [[0,0,1],[0,2,2],[1,3,2]] 输出3 解释有 5 所房屋编号从 0 到4 共有 3 个购买要约。 将位于 [0,0] 范围内的房屋以 1 金币的价格出售给第 1 位买家并将位于 [1,3] 范围内的房屋以2 金币的价格出售给第 3 位买家。 可以证明我们最多只能获得 3 枚金币。 示例 2 输入n 5, offers [[0,0,1],[0,2,10],[1,3,2]] 输出10 解释有 5 所房屋编号从 0 到4 共有 3 个购买要约。 将位于 [0,2] 范围内的房屋以 10 金币的价格出售给第 2 位买家。 可以证明我们最多只能获得 10枚金币。 提示 1 n 1 0 5 1 n 10^5 1n105 o f f e r s [ i ] . l e n g t h 3 offers[i].length 3 offers[i].length3 0 s t a r t i e n d i n − 1 0 starti endi n - 1 0startiendin−1 1 g o l d i 1 0 3 1 goldi 10^3 1goldi103
思路 动态规划dp[i1]表示购买编号不超过i的房屋所能获得的最大利益。
若不购买 d p [ i 1 ] d p [ i ] dp[i1]dp[i] dp[i1]dp[i]若购买那么遍历所有 e n d j i end_ji endji的买家请求 d p [ i 1 ] m a x ( d p [ i 1 ] , d p [ s t a r t j ] g o l d j ) dp[i1]max(dp[i1],dp[start_j]gold_j) dp[i1]max(dp[i1],dp[startj]goldj) 可以先将所有相同房屋结尾的购买请求通过结尾房屋编号存储起来。 d p [ i 1 ] m a x { d p [ i ] 不购买 i 房屋 d p [ i 1 ] d p [ s t a r t j ] g o l d j 购买 i 房屋 dp[i1]max\begin{cases} dp[i] 不购买i房屋 \\ dp[i1]dp[start_j]gold_j 购买i房屋 \\ \end{cases} dp[i1]max{dp[i]dp[i1]dp[startj]goldj不购买i房屋购买i房屋
代码
class Solution {
public:int maximizeTheProfit(int n, vectorvectorint offers){//dp[i]维护的是只卖到第i个房子的收益vectorvectorpairint, inttmp(n);for(auto offer:offers){tmp[offer[1]].push_back({offer[0],offer[2]});}int dp[n1];//dp[i1]维护的就是买到第i个房子的收益memset(dp,0,sizeof(dp));for(int i0;in;i){dp[i1]dp[i];//不买第i个房子,那么其收益最大就是dp[i]for(auto pii:tmp[i]){int startpii.first,goldpii.second;//买第i个房子dp[i1]max(dp[i1],dp[start]gold);}}return dp[n];}
};找出最长等值子数组
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 如果子数组中所有元素都相等则认为子数组是一个 等值子数组 。注意空数组是 等值子数组 。 从 nums 中删除最多 k 个元素后返回可能的最长等值子数组的长度。 子数组 是数组中一个连续且可能为空的元素序列。
示例 1 输入nums [1,3,2,3,1,3], k 3 输出3 解释最优的方案是删除下标 2 和下标 4 的元素。删除后nums 等于 [1, 3, 3, 3] 。 最长等值子数组从 i 1 开始到 j 3 结束长度等于 3 。可以证明无法创建更长的等值子数组。 示例 2 输入nums [1,1,2,2,1,1], k 2 输出4 解释最优的方案是删除下标 2 和下标 3 的元素。 删除后nums 等于 [1, 1, 1, 1] 。 数组自身就是等值子数组长度等于 4 。 可以证明无法创建更长的等值子数组。 提示 1 n u m s . l e n g t h 1 0 5 1 nums.length 10^5 1nums.length105 1 n u m s [ i ] n u m s . l e n g t h 1 nums[i] nums.length 1nums[i]nums.length 0 k n u m s . l e n g t h 0 k nums.length 0knums.length
分析 分析题意得知题目的目的就是需要删除每两个相同的数字之间不同的数在删除k次的情况下使得连续的相同的数字最多。那么我们可以存储每一个数字出现的位置。对于每一个数字因为我们找到删除后连续的该数字最多比如说对数字1我们可以先维护出每两个1之间的距离那么我们的目的就是要找到一串距离使得距离和小于k且距离的个数最多。显然可以用滑动窗口的方法获得满足条件的答案。 代码
class Solution {
public:const int MAXN 1e55;int longestEqualSubarray(vectorint nums, int k) {if(nums.size()1)return 1;vectorintp[MAXN];for(int i0;inums.size();i){p[nums[i]].push_back(i);//先维护一下每个数字的位置}int res1;for(int i1;inums.size();i){int cnt0,ans0;vectorintq;for(int j1;jp[i].size();j){//维护每个数字两两之间的距离q.push_back(p[i][j]-p[i][j-1]-1);}for(int l0,r0;rq.size();){//双指针得到最多的距离cntq[r];while(cntk)cnt-q[l];ansmax(ans,r-l1);}resmax(res,ans);}return res;}
};
