链接：LeetCode
[Leetcode]5475. 统计好三元组
给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。
如果三元组 ((arr[i], arr[j], arr[k])) 满足下列全部条件，则认为它是一个 好三元组 。
- 0 <= i < j < k < arr.length
- (|arr[i] - arr[j]| <= a)
- (|arr[j] - arr[k]| <= b)
- (|arr[i] - arr[k]| <= c)
其中 (|x|) 表示 x 的绝对值。
返回 好三元组的数量 。
根据题意暴力即可。
class Solution {
public:
int abs(int x){
return x>0?x:-x;
}
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
int n = arr.size();
int i,j,k,res=0;
for(j=1;j<n-1;++j){
for(i=0;i<j;++i){
for(k=j+1;k<n;++k){
if(abs(arr[i]-arr[j])<=a && abs(arr[j]-arr[k])<=b && abs(arr[i]-arr[k])<=c)
res ++;
}
}
}
return res;
}
};
[Leetcode]5476. 找出数组游戏的赢家
给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。
每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。
返回赢得比赛的整数。
题目数据 保证 游戏存在赢家。
遍历数组维护一个最大值，并且统计他几次会被下一个最大值替换掉。也就相当于题目中的比较操作。如果有其中一个最大值替换次数 >= k 那么直接返回这个最大值。若遍历完成后无返回，由于数据保证游戏存在赢家，此时只要返回整个数组最大值就好。
# include <cmath>
class Solution {
public:
int getWinner(vector<int>& arr, int k) {
int n = arr.size();
int pre = arr[0],cur = 0;
int max_num;
for(int i=1;i<n;++i){
max_num = max(pre,arr[i]);
if(max_num==pre){
cur ++ ;
}
else{
cur = 1;
pre = max_num;
}
if(cur>=k){
return max_num;
}
}
return max_num;
}
};
[Leetcode]5477. 排布二进制网格的最少交换次数
给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换。
一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。
请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。
主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。
要想实现对角线以上格子全是0，那么我们只需要记录，每一行从后往前遍历，连续0的个数。根据贪心思想，从第一行开始，如果该行的后缀0满足条件，那么直接跳过进入下一行（因为需要的后缀0个数是从大到小的顺序，所以不必担心前面的会抢后面的）；如果该行后缀0个数不满足条件，那么就往下遍历找到最先（贪心，这是最小次数）满足条件的行，一行一行换上来，记录交换的次数。如果找不到满足条件的后缀0，那么就返回-1.
class Solution {
public:
int minSwaps(vector<vector<int>>& grid) {
vector<int> inds;
int n = grid.size();
for(int i=0;i<n;++i){
int cur = 0;
for(int j=n-1;j>=0;--j){
if(grid[i][j]==0) cur ++;
else break;
}
inds.push_back(cur);
}
int res = 0;
for(int i=0;i<n-1;++i){
int wants = n-1-i,j;
bool flag = false;
for (j=0;j<inds.size();++j){
if(inds[j]>=wants){
flag = true;
res += j;
break;
}
}
if(!flag) return -1;
inds.erase(inds.begin()+j);
}
return res;
}
};
[Leetcode]5478. 最大得分
你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。
一条 合法路径 定义如下：
选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
从左到右遍历当前数组。
如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。
得分定义为合法路径中不同数字的和。
请你返回所有可能合法路径中的最大得分。
由于答案可能很大，请你将它对 10^9 + 7 取余后返回。
双指针遍历即可。
class Solution {
typedef long long ll;
const int P=1000000007;
public:
int maxSum(vector<int>& nums1, vector<int>& nums2) {
int i=0,j=0;
ll sum1=0,sum2=0,res = 0;
while(i<nums1.size() && j<nums2.size()){
if(nums1[i]<nums2[j]){
sum1 += nums1[i];
i++;
}
else if(nums1[i]> nums2[j]){
sum2 += nums2[j];
j++;
}
else{
res += max(sum1,sum2)+nums1[i];
sum1 = sum2 =0;
i++;
j++;
}
}
for(;i<nums1.size();++i){
sum1 += nums1[i];
}
for(;j<nums2.size();++j){
sum2 += nums2[j];
}
res += max(sum1,sum2);
return res%P;
}
};
参考：
Leetcode