做网彩网站,drupal网站建设,家居设计,外链屏蔽逐步解除文章目录 2828.判别首字母缩略词完整版 2829.k-avoiding数组的最小总和#xff08;贪心解法#xff09;思路完整版 类似题#xff1a;2834.找出美丽数组的最小和思路完整版 2830.销售利润最大化⭐⭐思路DP数组含义递推公式 完整版 2828.判别首字母缩略词
给你一个字符串数组… 文章目录 2828.判别首字母缩略词完整版 2829.k-avoiding数组的最小总和贪心解法思路完整版 类似题2834.找出美丽数组的最小和思路完整版 2830.销售利润最大化⭐⭐思路DP数组含义递推公式 完整版 2828.判别首字母缩略词
给你一个字符串数组 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 words.length 1001 words[i].length 101 s.length 100words[i] 和 s 由小写英文字母组成
完整版
class Solution {
public:bool isAcronym(vectorstring words, string s) {string result ;for(string word:words){result.push_back(word[0]);}if(results) return true;return false;}
};2829.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
思路
本题思路是贪心解法。不同正整数组成的数组且需要选择可能的最小总和因此需要从小到大开始取值。
我们可以使用一个set集合存储已经选择过的数字使用 curr 来代表当前尝试选择的数字。开始时curr 被设置为 1。
检查curr 是否已经在 used 中或者 k-curr是否在 used 中 如果 curr 已经被选择过或者 k-curr 也被选择过这意味着如果我们选择 curr 会有一个和为 k 的对存在那么我们应该跳过这个 curr 并使 curr 加1。否则我们选择 curr 增加总和并将 curr 加入到 used 中。 最后返回总和。
完整版
因为是找最小和所以并不适合用组合总和那一套回溯的方法解决
class Solution {
public:int minimumSum(int n, int k) {setintused;int sum0;for(int i1;in;i){int cur1;//从1开始尝试//只要不满足条件就一直cur一直到满足条件为止while(used.count(cur)||used.count(k-cur)){cur;}sumcur;used.insert(cur);}return sum;}
};举一个简单的例子来解释这个算法。考虑 n 5 和 k 4。
首先选择数字 1sum 1used {1}。下一个数字是 2但是我们不能选择2因为 22 4即 k。因此我们跳过2。接着选择数字 3sum 4used {1,3}。选择数字 4sum 8used {1,3,4}。选择数字 5sum 13used {1,3,4,5}。最后选择数字 6sum 18used {1,3,4,5,6}。
因此输出为 18。
类似题2834.找出美丽数组的最小和
给你两个正整数n 和 target 。
如果数组 nums 满足下述条件则称其为 美丽数组 。
nums.length n.nums 由两两互不相同的正整数组成。在范围 [0, n-1] 内不存在 两个 不同 下标 i 和 j 使得 nums[i] nums[j] target 。
返回符合条件的美丽数组所可能具备的 最小 和。
示例 1
输入n 2, target 3
输出4
解释nums [1,3] 是美丽数组。
- nums 的长度为 n 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j 使得 nums[i] nums[j] 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。示例 2
输入n 3, target 3
输出8
解释
nums [1,3,4] 是美丽数组。
- nums 的长度为 n 3 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j 使得 nums[i] nums[j] 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。示例 3
输入n 1, target 1
输出1
解释nums [1] 是美丽数组。提示
1 n 1051 target 105
思路
本题就和上面的贪心很像了求得也是可能的最小和所以需要从最小的数字开始取
完整版
本题代码就和上面几乎一模一样了。因为求解的是可能的最小和所以都是贪心来做。
class Solution {
public:long long minimumPossibleSum(int n, int target) {setlong longused;int cur 1;long long sum0;for(int i1;in;i){while(used.count(cur)||used.count(target-cur)){cur;}used.insert(cur);sumcur;}return sum;}
};2830.销售利润最大化⭐⭐
给你一个整数 n 表示数轴上的房屋数量编号从 0 到 n - 1 。
另给你一个二维整数数组 offers 其中 offers[i] [starti, endi, goldi] 表示第 i 个买家想要以 goldi 枚金币的价格购买从 starti 到 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 10^51 offers.length 10^5offers[i].length 30 starti endi n - 11 goldi 10^3
思路
题解2830. 销售利润最大化 - 力扣LeetCode
DP数组含义
dp[i]的含义是dp[i1]表示销售编号不超过i的房屋的最大盈利。因为还要考虑房屋为0的情况。
如果用 dp[i] 而不是 dp[i 1]来表示的话那 dp[0]的意思就是不超过编号为0的。但是我们还需要考虑 编号不超过-1的有点抽象意思就是一个房屋都不考虑但是下标不能是-1所以就要把 dp 数组的下标移一下 让它别越界。
递推公式
考虑编号为i的房屋卖或者不卖
不卖dp[i1]dp[i]卖遍历所有终点房屋是房屋i的方案找收益最大的方案。
完整版
class Solution {
public:int maximizeTheProfit(int n, vectorvectorint offers) {vectorintdp(n1,0);sort(offers.begin(),offers.end(),[](vectorinta,vectorintb){return a[1]b[1];//按照下标1位置升序排序也就是对购买请求按照房屋终点值从小到大排序});int index0;//方案编号//dp[i1]表示从前往后卖到编号下标是i的房子时总的最大获利for(int i0;in;i){//不卖i房子dp[i1]dp[i];//卖i房子while(indexoffers.size()ioffers[index][1]){dp[i1]max(dp[i1],dp[offers[index][0]]offers[index][2]);index;}}return dp[n];//dp[n]就对应着卖到下标n-1的房子也就是最后一栋房子的最大获益}
};注意不能像下面这么写因为while循环可能根本进不去也就是说可能根本不存在ioffers[index][1]即根本不存在以房屋i为结尾的方案但是dp[i1]最少也要dp[i]
class Solution {
public://错误写法while循环可能根本进不去int maximizeTheProfit(int n, vectorvectorint offers) {vectorintdp(n1,0);sort(offers.begin(),offers.end(),[](vectorinta,vectorintb){return a[1]b[1];//按照下标1位置升序排序});int index0;//方案编号//dp[i1]表示从前往后卖到编号下标是i的房子时总的最大获利for(int i0;in;i){//不卖i房子//dp[i1]dp[i];//卖i房子while(indexoffers.size()ioffers[index][1]){dp[i1]max(dp[i],max(dp[i1],dp[offers[index][0]]offers[index][2]));index;}}return dp[n];//dp[n]就对应着卖到下标n-1的房子也就是最后一栋房子的最大获益}
};
