第 70 场力扣夜喵双周赛
5971. 打折购买糖果的最小开销5972. 统计隐藏数组数目5973. 价格范围内最高排名的 K 样物品5974. 分隔长廊的方案数 第 277 场力扣周赛
5989. 元素计数5991. 按符号重排数组5990. 找出数组中的所有孤独数字5992. 基于陈述统计最多好人数
第 70 场力扣夜喵双周赛 5971. 打折购买糖果的最小开销
题目
一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。
免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。
比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。
给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得 所有 糖果的 最小 总开销。
示例 1：
输入：cost = [1,2,3]
输出：5
解释：我们购买价格为 2 和 3 的糖果，然后免费获得价格为 1 的糖果。
总开销为 2 + 3 = 5 。这是开销最小的 唯一 方案。
注意，我们不能购买价格为 1 和 3 的糖果，并免费获得价格为 2 的糖果。
这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。
示例 2：
输入：cost = [6,5,7,9,2,2]
输出：23
解释：最小总开销购买糖果方案为：
购买价格为 9 和 7 的糖果免费获得价格为 6 的糖果购买价格为 5 和 2 的糖果免费获得价格为 2 的最后一个糖果
因此，最小总开销为 9 + 7 + 5 + 2 = 23 。
示例 3：
输入：cost = [5,5]
输出：10
解释：由于只有 2 个糖果，我们需要将它们都购买，而且没有免费糖果。
所以总最小开销为 5 + 5 = 10 。
提示：
1 <= cost.length <= 100
1 <= cost[i] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-cost-of-buying-candies-with-discount
代码
class Solution {
public:
int minimumCost(vector& cost) {
sort(cost.begin(), cost.end());
int cnt=0;
int cur=0;
for(int i=cost.size()-1; i >= 0; i--){
cur++;
if(cur<=2){
cnt+= cost[i];
}else{
cur=0;
}
}
return cnt;
}
};
5972. 统计隐藏数组数目
题目
给你一个下标从 0 开始且长度为 n 的整数数组 differences ，它表示一个长度为 n + 1 的 隐藏 数组 相邻 元素之间的 差值 。更正式的表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。
同时给你两个整数 lower 和 upper ，它们表示隐藏数组中所有数字的值都在 闭 区间 [lower, upper] 之间。
比方说，differences = [1, -3, 4] ，lower = 1 ，upper = 6 ，那么隐藏数组是一个长度为 4 且所有值都在 1 和 6 （包含两者）之间的数组。
[3, 4, 1, 5] 和 [4, 5, 2, 6] 都是符合要求的隐藏数组。
[5, 6, 3, 7] 不符合要求，因为它包含大于 6 的元素。
[1, 2, 3, 4] 不符合要求，因为相邻元素的差值不符合给定数据。
请你返回 符合 要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0 。
示例 1：
输入：differences = [1,-3,4], lower = 1, upper = 6
输出：2
解释：符合要求的隐藏数组为：
[3, 4, 1, 5][4, 5, 2, 6]
所以返回 2 。
示例 2：
输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5
输出：4
解释：符合要求的隐藏数组为：
[-3, 0, -4, 1, 2, 0][-2, 1, -3, 2, 3, 1][-1, 2, -2, 3, 4, 2][0, 3, -1, 4, 5, 3]
所以返回 4 。
示例 3：
输入：differences = [4,-7,2], lower = 3, upper = 6
输出：0
解释：没有符合要求的隐藏数组，所以返回 0 。
提示：
n == differences.length
1 <= n <= 105
-105 <= differences[i] <= 105
-105 <= lower <= upper <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-the-hidden-sequences
代码
class Solution {
public:
int numberOfArrays(vector& differences, int lower, int upper) {
long long minn=0, maxn=0;
long long cnt=0;
for(int i=0; i < differences.size(); i++){
cnt+=differences[i];
minn = min(minn, cnt);
maxn = max(maxn, cnt);
}
int tmp=lower-minn;
cout< 0){
return upper-maxn+1;
}
return 0;
}
};
5973. 价格范围内最高排名的 K 样物品
题目
给你一个下标从 0 开始的二维整数数组 grid ，它的大小为 m x n ，表示一个商店中物品的分布图。数组中的整数含义为：
0 表示无法穿越的一堵墙。
1 表示可以自由通过的一个空格子。
所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。
从一个格子走到上下左右相邻格子花费 1 步。
同时给你一个整数数组 pricing 和 start ，其中 pricing = [low, high] 且 start = [row, col] ，表示你开始位置为 (row, col) ，同时你只对物品价格在 闭区间 [low, high] 之内的物品感兴趣。同时给你一个整数 k 。
你想知道给定范围 内 且 排名最高 的 k 件物品的 位置 。排名按照优先级从高到低的以下规则制定：
距离：定义为从 start 到一件物品的最短路径需要的步数（较近 距离的排名更高）。
价格：较低 价格的物品有更高优先级，但只考虑在给定范围之内的价格。
行坐标：较小 行坐标的有更高优先级。
列坐标：较小 列坐标的有更高优先级。
请你返回给定价格内排名最高的 k 件物品的坐标，将它们按照排名排序后返回。如果给定价格内少于 k 件物品，那么请将它们的坐标 全部 返回。
示例 1：
输入：grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
输出：[[0,1],[1,1],[2,1]]
解释：起点为 (0,0) 。
价格范围为 [2,5] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(2,1) 和 (2,2) 。
这些物品的排名为：
(0,1) 距离为 1(1,1) 距离为 2(2,1) 距离为 3(2,2) 距离为 4
所以，给定价格范围内排名最高的 3 件物品的坐标为 (0,1)，(1,1) 和 (2,1) 。
示例 2：
输入：grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
输出：[[2,1],[1,2]]
解释：起点为 (2,3) 。
价格范围为 [2,3] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(1,2) 和 (2,1) 。
这些物品的排名为：
(2,1) 距离为 2 ，价格为 2(1,2) 距离为 2 ，价格为 3(1,1) 距离为 3(0,1) 距离为 4
所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (1,2) 。
示例 3：
输入：grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
输出：[[2,1],[2,0]]
解释：起点为 (0,0) 。
价格范围为 [2,3] ，我们可以选择的物品坐标为 (2,0) 和 (2,1) 。
这些物品的排名为：
(2,1) 距离为 5(2,0) 距离为 6
所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (2,0) 。
注意，k = 3 但给定价格范围内只有 2 件物品。
提示：
m == grid.length n == grid[i].length 1 <= m, n <= 105 1 <= m * n <= 105 0 <= grid[i][j] <= 105 pricing.length == 2 2 <= low <= high <= 105 start.length == 2 0 <= row <= m - 1 0 <= col <= n - 1 grid[row][col] > 0 1 <= k <= m * n
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-highest-ranked-items-within-a-price-range
代码
struct Node{
int dist;
int price;
int x;
int y;
};
int xm[4] = {0,1,0,-1};
int ym[4] = {1,0,-1,0};
class Solution {
public:
vector> highestRankedKItems(vector>& grid, vector& pricing, vector& start, int k) {
queue q;
vector v;
Node p;
int m = grid.size(), n=grid[0].size();
p.dist=0;
p.price=grid[start[0]][start[1]];
p.x = start[0];
p.y = start[1];
grid[p.x][p.y] = 0;
q.push(p);
if(p.price >= pricing[0] && p.price <= pricing[1]){
v.push_back(p);
}
while(!q.empty()){
p = q.front();
q.pop();
for(int i=0; i < 4; i++){
int newx=p.x + xm[i], newy = p.y + ym[i];
if(newx < m && newx >= 0 && newy < n && newy >= 0 && grid[newx][newy] > 0){
Node tmp;
tmp.dist = p.dist+1;
tmp.price = grid[newx][newy];
tmp.x = newx;
tmp.y = newy;
if(tmp.price <= pricing[1] && tmp.price >= pricing[0] && tmp.price != 1){
v.push_back(tmp);
}
q.push(tmp);
grid[newx][newy] = 0;
}
}
}
int len = v.size();
sort(v.begin(),v.end(),[](auto &lhs,auto &rhs){
if(lhs.dist < rhs.dist)return true;
if(lhs.dist == rhs.dist){
if(lhs.price < rhs.price)return true;
if(lhs.price == rhs.price){
if(lhs.x < rhs.x)return true;
if(lhs.x == rhs.x)return lhs.y < rhs.y;
return false;
}
return false;
}
return false;
});
vector> ans;
for(int i=0; i < k && i < v.size(); i++){
vector tmp;
tmp.push_back(v[i].x);
tmp.push_back(v[i].y);
ans.push_back(tmp);
}
return ans;
}
};
5974. 分隔长廊的方案数
题目
在一个图书馆的长廊里，有一些座位和装饰植物排成一列。给你一个下标从 0 开始，长度为 n 的字符串 corridor ，它包含字母 ‘S’ 和 ‘P’ ，其中每个 ‘S’ 表示一个座位，每个 ‘P’ 表示一株植物。
在下标 0 的左边和下标 n - 1 的右边 已经 分别各放了一个屏风。你还需要额外放置一些屏风。每一个位置 i - 1 和 i 之间（1 <= i <= n - 1），至多能放一个屏风。
请你将走廊用屏风划分为若干段，且每一段内都 恰好有两个座位 ，而每一段内植物的数目没有要求。可能有多种划分方案，如果两个方案中有任何一个屏风的位置不同，那么它们被视为 不同 方案。
请你返回划分走廊的方案数。由于答案可能很大，请你返回它对 109 + 7 取余 的结果。如果没有任何方案，请返回 0 。
示例 1：
输入：corridor = “SSPPSPS”
输出：3
解释：总共有 3 种不同分隔走廊的方案。
上图中黑色的竖线表示已经放置好的屏风。
上图每种方案中，每一段都恰好有 两个 座位。
示例 2：
输入：corridor = “PPSPSP”
输出：1
解释：只有 1 种分隔走廊的方案，就是不放置任何屏风。
放置任何的屏风都会导致有一段无法恰好有 2 个座位。
示例 3：
输入：corridor = “S”
输出：0
解释：没有任何方案，因为总是有一段无法恰好有 2 个座位。
提示：
n == corridor.length
1 <= n <= 105
corridor[i] 要么是 ‘S’ ，要么是 ‘P’ 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-ways-to-divide-a-long-corridor
代码
class Solution {
public:
int numberOfWays(string corridor) {
int pre, cnt=0;
int ans = 1;
int mod = 1e9+7;
for(int i=0; i < corridor.size(); i++){
if(corridor[i] == 'S'){
cnt++;
if(cnt >= 3 && cnt % 2){
ans = (long)ans * (i - pre) % mod;
}
pre = i;
}
}
return cnt && cnt % 2==0 ? ans : 0;
}
};
第 277 场力扣周赛
5989. 元素计数
题目
给你一个整数数组 nums ，统计并返回在 nums 中同时具有一个严格较小元素和一个严格较大元素的元素数目。
示例 1：
输入：nums = [11,7,2,15]
输出：2
解释：元素 7 ：严格较小元素是元素 2 ，严格较大元素是元素 11 。
元素 11 ：严格较小元素是元素 7 ，严格较大元素是元素 15 。
总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。
示例 2：
输入：nums = [-3,3,3,90]
输出：2
解释：元素 3 ：严格较小元素是元素 -3 ，严格较大元素是元素 90 。
由于有两个元素的值为 3 ，总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。
提示：
1 <= nums.length <= 100
-105 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-elements-with-strictly-smaller-and-greater-elements
代码
class Solution {
public:
int countElements(vector& nums) {
sort(nums.begin(), nums.end());
int cnt=0;
for(int i=1; i < nums.size()-1; i++){
if(nums[i-1] nums[i+1]){
cnt++;
}
bool flag1=true, flag2=true;
if(nums[i-1]==nums[i]){
flag1=false;
for(int j=i-2; j >= 0; j--){
if(nums[j] < nums[i]){
flag1=true;
break;
}
}
}
//cout< nums[i]){
flag2=true;
break;
}
}
}
//cout<<2<<" "<
5991. 按符号重排数组
题目
给你一个下标从 0 开始的整数数组 nums ，数组长度为 偶数 ，由数目相等的正整数和负整数组成。
你需要 重排 nums 中的元素，使修改后的数组满足下述条件：
任意 连续 的两个整数 符号相反
对于符号相同的所有整数，保留 它们在 nums 中的 顺序 。
重排后数组以正整数开头。
重排元素满足上述条件后，返回修改后的数组。
示例 1：
输入：nums = [3,1,-2,-5,2,-4]
输出：[3,-2,1,-5,2,-4]
解释：
nums 中的正整数是 [3,1,2] ，负整数是 [-2,-5,-4] 。
重排的唯一可行方案是 [3,-2,1,-5,2,-4]，能满足所有条件。
像 [1,-2,2,-5,3,-4]、[3,1,2,-2,-5,-4]、[-2,3,-5,1,-4,2] 这样的其他方案是不正确的，因为不满足一个或者多个条件。
示例 2：
输入：nums = [-1,1]
输出：[1,-1]
解释：
1 是 nums 中唯一一个正整数，-1 是 nums 中唯一一个负整数。
所以 nums 重排为 [1,-1] 。
提示：
2 <= nums.length <= 2 * 105
nums.length 是 偶数
1 <= |nums[i]| <= 105
nums 由 相等 数量的正整数和负整数组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rearrange-array-elements-by-sign
代码
class Solution {
public:
vector rearrangeArray(vector& nums) {
vector a, b;
for(int i=0; i = 0){
a.push_back(nums[i]);
}else{
b.push_back(nums[i]);
}
}
int i;
vector ans;
for(i=0; i < a.size() && i < b.size(); i++){
ans.push_back(a[i]);
ans.push_back(b[i]);
}
for(int j=i; j < a.size(); j++){
ans.push_back(a[j]);
}
for(int j=i; j < b.size(); j++){
ans.push_back(b[j]);
}
return ans;
}
};
5990. 找出数组中的所有孤独数字
题目
给你一个整数数组 nums 。如果数字 x 在数组中仅出现 一次 ，且没有 相邻 数字（即，x + 1 和 x - 1）出现在数组中，则认为数字 x 是 孤独数字 。
返回 nums 中的 所有 孤独数字。你可以按 任何顺序 返回答案。
示例 1：
输入：nums = [10,6,5,8]
输出：[10,8]
解释：
10 是一个孤独数字，因为它只出现一次，并且 9 和 11 没有在 nums 中出现。8 是一个孤独数字，因为它只出现一次，并且 7 和 9 没有在 nums 中出现。5 不是一个孤独数字，因为 6 出现在 nums 中，反之亦然。
因此，nums 中的孤独数字是 [10, 8] 。
注意，也可以返回 [8, 10] 。
示例 2：
输入：nums = [1,3,5,3]
输出：[1,5]
解释：
1 是一个孤独数字，因为它只出现一次，并且 0 和 2 没有在 nums 中出现。5 是一个孤独数字，因为它只出现一次，并且 4 和 6 没有在 nums 中出现。3 不是一个孤独数字，因为它出现两次。
因此，nums 中的孤独数字是 [1, 5] 。
注意，也可以返回 [5, 1] 。
提示：
1 <= nums.length <= 105
0 <= nums[i] <= 106
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-lonely-numbers-in-the-array
代码
class Solution {
public:
vector findLonely(vector& nums) {
map m;
for(int i=0; i < nums.size(); i++){
m[nums[i]]++;
}
vector ans;
for(int i=0; i < nums.size(); i++){
if(m[nums[i]]==1 && m[nums[i]-1]==0 && m[nums[i]+1]==0){
ans.push_back(nums[i]);
}
}
return ans;
}
};
5992. 基于陈述统计最多好人数
题目
游戏中存在两种角色：
好人：该角色只说真话。
坏人：该角色可能说真话，也可能说假话。
给你一个下标从 0 开始的二维整数数组 statements ，大小为 n x n ，表示 n 个玩家对彼此角色的陈述。具体来说，statements[i][j] 可以是下述值之一：
0 表示 i 的陈述认为 j 是 坏人 。
1 表示 i 的陈述认为 j 是 好人 。
2 表示 i 没有对 j 作出陈述。
另外，玩家不会对自己进行陈述。形式上，对所有 0 <= i < n ，都有 statements[i][i] = 2 。
根据这 n 个玩家的陈述，返回可以认为是 好人 的 最大 数目。
示例 1：
输入：statements = [[2,1,2],[1,2,2],[2,0,2]]
输出：2
解释：每个人都做一条陈述。
0 认为 1 是好人。1 认为 0 是好人。2 认为 1 是坏人。
以 2 为突破点。假设 2 是一个好人：
基于 2 的陈述，1 是坏人。那么可以确认 1 是坏人，2 是好人。基于 1 的陈述，由于 1 是坏人，那么他在陈述时可能：
说真话。在这种情况下会出现矛盾，所以假设无效。说假话。在这种情况下，0 也是坏人并且在陈述时说假话。 在认为 2 是好人的情况下，这组玩家中只有一个好人。 假设 2 是一个坏人：
基于 2 的陈述，由于 2 是坏人，那么他在陈述时可能：
说真话。在这种情况下，0 和 1 都是坏人。
在认为 2 是坏人但说真话的情况下，这组玩家中没有一个好人。 说假话。在这种情况下，1 是好人。
由于 1 是好人，0 也是好人。在认为 2 是坏人且说假话的情况下，这组玩家中有两个好人。
在最佳情况下，至多有两个好人，所以返回 2 。
注意，能得到此结论的方法不止一种。
示例 2：
输入：statements = [[2,0],[0,2]]
输出：1
解释：每个人都做一条陈述。
0 认为 1 是坏人。1 认为 0 是坏人。
以 0 为突破点。假设 0 是一个好人：
基于与 0 的陈述，1 是坏人并说假话。在认为 0 是好人的情况下，这组玩家中只有一个好人。 假设 0 是一个坏人：
基于 0 的陈述，由于 0 是坏人，那么他在陈述时可能：
说真话。在这种情况下，0 和 1 都是坏人。
在认为 0 是坏人但说真话的情况下，这组玩家中没有一个好人。 说假话。在这种情况下，1 是好人。
在认为 0 是坏人且说假话的情况下，这组玩家中只有一个好人。
在最佳情况下，至多有一个好人，所以返回 1 。
注意，能得到此结论的方法不止一种。
提示：
n == statements.length == statements[i].length
2 <= n <= 15
statements[i][j] 的值为 0、1 或 2
statements[i][i] == 2
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-good-people-based-on-statements
代码
class Solution {
public:
int maximumGood(vector>& statements) {
int n = 1 << statements.size();
int ans = 0;
for(int i=1; i < n; i++){
int cnt=0;
for(int j=0; j < statements.size(); j++){
if((i>>j) & 1){
for(int k=0; k < statements.size(); k++){
if(statements[j][k] < 2 && statements[j][k] != ((i>>k)&1)){
goto next;
}
}
cnt++;
}
}
ans = max(ans, cnt);
next:;
}
return ans;
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）