目录
2601. 质数减法运算
2604. 吃掉所有谷子的最短时间
一条线上有
n
只母鸡和
m
颗谷子。给定两个整数数组
hens
和
grains
，它们的大小分别为
n
和
m
，表示母鸡和谷子的初始位置。
如果一只母鸡和一颗谷子在同一个位置，那么这只母鸡可以吃掉这颗谷子。吃掉一颗谷子的时间可以忽略不计。一只母鸡也可以吃掉多颗谷子。
在
1
秒钟内，一只母鸡可以向左或向右移动
1
个单位。母鸡可以同时且独立地移动。
如果母鸡行动得当，返回吃掉所有谷子的
最短
时间。
示例 1 ：
输入：hens = [3,6,7], grains = [2,4,7,9] 输出：2 解释： 母鸡吃掉所有谷子的一种方法如下： - 第一只母鸡在 1 秒钟内吃掉位置 2 处的谷子。 - 第二只母鸡在 2 秒钟内吃掉位置 4 处的谷子。 - 第三只母鸡在 2 秒钟内吃掉位置 7 和 9 处的谷子。 所以，需要的最长时间为2秒。 可以证明，在2秒钟之前，母鸡不能吃掉所有谷子。
示例 2 ：
输入：hens = [4,6,109,111,213,215], grains = [5,110,214] 输出：1 解释： 母鸡吃掉所有谷子的一种方法如下： - 第一只母鸡在 1 秒钟内吃掉位置 5 处的谷子。 - 第四只母鸡在 1 秒钟内吃掉位置 110 处的谷子。 - 第六只母鸡在 1 秒钟内吃掉位置 214 处的谷子。 - 其他母鸡不动。 所以，需要的最长时间为 1 秒。
提示：
-
1 <= hens.length, grains.length <= 2*104
-
0 <= hens[i], grains[j] <= 109
class TimeOk:public Bsearch<int> {
public:
bool timeok(const vector<int> &hens, const vector<int>& grains, int t) {
int id = 0;
this->grains = grains;
for (int i = 0; i < hens.size(); i++) {
int t2 = t - abs(hens[i] - grains[id]);
if (t2 < 0)continue;
s = hens[i] <= grains[id] ? hens[i] + t : max(hens[i] + t2 / 2, grains[id] + t2);
id = find(id, int(grains.size())-1);
if (id >= grains.size())return true;
}
return false;
}
virtual bool isOk(int x) const //若isOk(x)且!isOk(y)则必有y<x
{
return grains[x] > s;
}
vector<int> grains;
int s;
};
class Solution :public Bsearch<int> {
public:
int minimumTime(vector<int>& hens, vector<int>& grains) {
sort(hens.begin(), hens.end());
sort(grains.begin(), grains.end());
this->hens = hens;
this->grains = grains;
return find(0,1000000000);
}
virtual bool isOk(int x) const //若isOk(x)且!isOk(y)则必有y<x
{
return TimeOk().timeok(hens, grains, x);
}
vector<int> hens;
vector<int> grains;
};
2605. 从两个数字数组里生成最小数字
给你两个只包含 1 到 9 之间数字的数组
nums1
和
nums2
，每个数组中的元素
互不相同
，请你返回
最小
的数字，两个数组都
至少
包含这个数字的某个数位。
示例 1：
输入：nums1 = [4,1,3], nums2 = [5,7] 输出：15 解释：数字 15 的数位 1 在 nums1 中出现，数位 5 在 nums2 中出现。15 是我们能得到的最小数字。
示例 2：
输入：nums1 = [3,5,2,6], nums2 = [3,1,7] 输出：3 解释：数字 3 的数位 3 在两个数组中都出现了。
提示：
-
1 <= nums1.length, nums2.length <= 9
-
1 <= nums1[i], nums2[i] <= 9
-
每个数组中，元素
互不相同
。
class Solution {
public:
int minNumber(vector<int>& nums1, vector<int>& nums2) {
map<int, int>m;
int min1=123, min2=123;
for (auto x : nums1)min1 = min(min1, x), m[x]++;
for (auto x : nums2)min2 = min(min2, x), m[x]++;
for (auto mi : m)if (mi.second == 2)return mi.first;
if (min1 > min2)min1 ^= min2 ^= min1 ^= min2;
return min1 * 10 + min2;
}
};
2607. 使子数组元素和相等
2611. 老鼠和奶酪
有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。
下标为 i 处的奶酪被吃掉的得分为：
如果第一只老鼠吃掉，则得分为 reward1[i] 。
如果第二只老鼠吃掉，则得分为 reward2[i] 。
给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。
请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。
示例 1：
输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出：15
解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15 。
15 是最高得分。
示例 2：
输入：reward1 = [1,1], reward2 = [1,1], k = 2
输出：2
解释：这个例子中，第一只老鼠吃掉第 0 和 1 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 2 。
2 是最高得分。
提示：
1 <= n == reward1.length == reward2.length <= 105
1 <= reward1[i], reward2[i] <= 1000
0 <= k <= n
class Solution {
public:
int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
Fcheng(reward1,-1);
reward1=VecAdd(reward1,reward2);
Fcheng(reward1,-1);
int s=0;
for(auto x:reward2)s+=x;
cout<<reward1.size()<<endl;
sort(reward1.begin(),reward1.end());
for(int i=reward1.size()-1;i>=int(reward1.size())-k;i--)s+=reward1[i];
return s;
}
};
2614. 对角线上的质数
2652. 倍数求和
2654. 使数组所有元素变成 1 的最少操作次数
2679. 矩阵中的和
2680. 最大或值
2681. 英雄的力量
2682. 找出转圈游戏输家
n
个朋友在玩游戏。这些朋友坐成一个圈，按
顺时针方向
从
1
到
n
编号。从第
i
个朋友的位置开始顺时针移动
1
步会到达第
(i + 1)
个朋友的位置（
1 <= i < n
），而从第
n
个朋友的位置开始顺时针移动
1
步会回到第
1
个朋友的位置。
游戏规则如下：
第
1
个朋友接球。
-
接着，第
1
个朋友将球传给距离他顺时针方向
k
步的朋友。 -
然后，接球的朋友应该把球传给距离他顺时针方向
2 * k
步的朋友。 -
接着，接球的朋友应该把球传给距离他顺时针方向
3 * k
步的朋友，以此类推。
换句话说，在第
i
轮中持有球的那位朋友需要将球传递给距离他顺时针方向
i * k
步的朋友。
当某个朋友第 2 次接到球时，游戏结束。
在整场游戏中没有接到过球的朋友是
输家
。
给你参与游戏的朋友数量
n
和一个整数
k
，请按升序排列返回包含所有输家编号的数组
answer
作为答案。
示例 1：
输入：n = 5, k = 2
输出：[4,5]
解释：以下为游戏进行情况：
1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 2 步的玩家 —— 第 3 个朋友。
2）第 3 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 2 个朋友。
3）第 2 个朋友将球传给距离他顺时针方向 6 步的玩家 —— 第 3 个朋友。
4）第 3 个朋友接到两次球，游戏结束。
示例 2：
输入：n = 4, k = 4
输出：[2,3,4]
解释：以下为游戏进行情况：
1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 1 个朋友。
2）第 1 个朋友接到两次球，游戏结束。
提示：
-
1 <= k <= n <= 50
class Solution {
public:
vector<int> circularGameLosers(int n, int k) {
map<int, int>m;
for (int i = 0;; i++)
{
int a = ((i*i + i) / 2 * k + 1) % n;
if (m[a])break;
m[a] = 1;
}
vector<int>ans;
for (int i = 1; i < n; i++) {
if (m[i] == 0)ans.push_back(i);
}
if (m[0] == 0)ans.push_back(n);
return ans;
}
};
2703. 返回传递的参数的长度
2708. 一个小组的最大实力值
2709. 最大公约数遍历
2710. 移除字符串中的尾随零
2717. 半有序排列
给你一个下标从
0
开始、长度为
n
的整数排列
nums
。
如果排列的第一个数字等于
1
且最后一个数字等于
n
，则称其为
半有序排列
。你可以执行多次下述操作，直到将
nums
变成一个
半有序排列
：
-
选择
nums
中相邻的两个元素，然后交换它们。
返回使
nums
变成
半有序排列
所需的最小操作次数。
排列
是一个长度为
n
的整数序列，其中包含从
1
到
n
的每个数字恰好一次。
示例 1：
输入：nums = [2,1,4,3] 输出：2 解释：可以依次执行下述操作得到半有序排列： 1 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。 2 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。 可以证明，要让 nums 成为半有序排列，不存在执行操作少于 2 次的方案。
示例 2：
输入：nums = [2,4,1,3] 输出：3 解释： 可以依次执行下述操作得到半有序排列： 1 - 交换下标 1 和下标 2 对应元素。排列变为 [2,1,4,3] 。 2 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。 3 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。 可以证明，要让 nums 成为半有序排列，不存在执行操作少于 3 次的方案。
示例 3：
输入：nums = [1,3,4,2,5] 输出：0 解释：这个排列已经是一个半有序排列，无需执行任何操作。
提示：
-
2 <= nums.length == n <= 50
-
1 <= nums[i] <= 50
-
nums
是一个
排列
class Solution {
public:
int semiOrderedPermutation(vector<int>& nums) {
int a = 0, b = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 1)a = i;
if (nums[i] == nums.size())b = i;
}
return a + nums.size() - 1 - b - (a > b);
}
};
2731. 移动机器人
2748. 美丽下标对的数目
2761. 和等于目标值的质数对
2778. 特殊元素平方和
2806. 取整购买后的账户余额
一开始，你的银行账户里有
100
块钱。
给你一个整数
purchaseAmount
，它表示你在一次购买中愿意支出的金额。
在一个商店里，你进行一次购买，实际支出的金额会向
最近
的
10
的
倍数
取整。换句话说，你实际会支付一个
非负
金额
roundedAmount
，满足
roundedAmount
是
10
的倍数且
abs(roundedAmount - purchaseAmount)
的值
最小
。
如果存在多于一个最接近的
10
的倍数，
较大的倍数
是你的实际支出金额。
请你返回一个整数，表示你在愿意支出金额为
purchaseAmount
块钱的前提下，购买之后剩下的余额。
注意：
0
也是
10
的倍数。
示例 1：
输入：purchaseAmount = 9 输出：90 解释：这个例子中，最接近 9 的 10 的倍数是 10 。所以你的账户余额为 100 - 10 = 90 。
示例 2：
输入：purchaseAmount = 15 输出：80 解释：这个例子中，有 2 个最接近 15 的 10 的倍数：10 和 20，较大的数 20 是你的实际开销。 所以你的账户余额为 100 - 20 = 80 。
提示：
-
0 <= purchaseAmount <= 100
class Solution {
public:
int accountBalanceAfterPurchase(int x) {
return 100-(x+5)/10*10;
}
};
2807. 在链表中插入最大公约数
2809. 使数组和小于等于 x 的最少时间
2815. 数组中的最大数对和
2818. 操作使得分最大
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
class Solution {
public:
int minimumSum(int n, int k) {
if (n <= k / 2)return n * (n + 1) / 2;
return k / 2 * (k / 2 + 1) / 2 + (n - k / 2)*(n + k * 2 - k / 2 - 1) / 2;
}
};