目录
252. 会议室
给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。
示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：false
示例 2：
输入：intervals = [[7,10],[2,4]]
输出：true
提示：
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti < endi <= 106
bool cmp(vector<int> x, vector<int> y)
{
return x[0] < y[0];
}
class Solution {
public:
bool canAttendMeetings(vector<vector<int>>& v) {
sort(v.begin(), v.end(), cmp);
for (int i = 1; i < v.size(); i++)if (v[i - 1][1] > v[i][0])return false;
return true;
}
};253. 会议室 II
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。
示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2
示例 2：
输入：intervals = [[7,10],[2,4]]
输出：1
提示：
1 <= intervals.length <= 104
0 <= starti < endi <= 106
struct Node {
int t;
int flag;
};
bool cmp(Node n1, Node n2)
{
if (n1.t == n2.t)return n1.flag > n2.flag;
return n1.t < n2.t;
}
class Solution {
public:
int minMeetingRooms(vector<vector<int>>& v) {
vector<Node>ns;
for (auto &vi : v)ns.push_back({ vi[0],0 }), ns.push_back({ vi[1],1 });
sort(ns.begin(), ns.end(), cmp);
int ans = 0, k = 0;
for (auto &ni : ns) {
if (ni.flag == 0)k++;
else k--;
ans = max(ans, k);
}
return ans;
}
};263. 丑数
题目：
编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例 1:
输入: 6
输出: true
解释: 6 = 2 × 3
示例 2:
输入: 8
输出: true
解释: 8 = 2 × 2 × 2
示例 3:
输入: 14
输出: false
解释: 14 不是丑数，因为它包含了另外一个质因数 7。
说明：
1 是丑数。
输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。
代码：
class Solution {
public:
bool isUgly(int num) {
if(num<=0)return false;
while(num%2==0)num/=2;
while(num%3==0)num/=3;
while(num%5==0)num/=5;
return (num==1);
}
};274. H 指数
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。
示例 1：
输入：citations = [3,0,6,1,5]输出：3 解释：给定数组表示研究者总共有5篇论文，每篇论文相应的被引用了3, 0, 6, 1, 5次。 由于研究者有3篇论文每篇 至少 被引用了3次，其余两篇论文每篇被引用 不多于3次，所以她的 h 指数是3。
示例 2：
输入：citations = [1,3,1] 输出：1
提示：
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(),citations.end());
for(int i=0;i<citations.size();i++){
if(citations[i]>=citations.size()-i)return citations.size()-i;
}
return 0;
}
};319. 灯泡开关
题目：
初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。
示例:
输入: 3
输出: 1
解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].
你应该返回 1，因为只有一个灯泡还亮着。
代码：
class Solution {
public:
int bulbSwitch(int n) {
return int(sqrt(n));
}
};672. 灯泡开关 Ⅱ
房间中有 n 只已经打开的灯泡，编号从 1 到 n 。墙上挂着 4 个开关 。
这 4 个开关各自都具有不同的功能，其中：
开关 1 ：反转当前所有灯的状态（即开变为关，关变为开）
开关 2 ：反转编号为偶数的灯的状态（即 0, 2, 4, ...）
开关 3 ：反转编号为奇数的灯的状态（即 1, 3, ...）
开关 4 ：反转编号为 j = 3k + 1 的灯的状态，其中 k = 0, 1, 2, ...（即 1, 4, 7, 10, ...）
你必须 恰好 按压开关 presses 次。每次按压，你都需要从 4 个开关中选出一个来执行按压操作。
给你两个整数 n 和 presses ，执行完所有按压之后，返回 不同可能状态 的数量。
示例 1：
输入：n = 1, presses = 1
输出：2
解释：状态可以是：
- 按压开关 1 ，[关]
- 按压开关 2 ，[开]
示例 2：
输入：n = 2, presses = 1
输出：3
解释：状态可以是：
- 按压开关 1 ，[关, 关]
- 按压开关 2 ，[开, 关]
- 按压开关 3 ，[关, 开]
示例 3：
输入：n = 3, presses = 1
输出：4
解释：状态可以是：
- 按压开关 1 ，[关, 关, 关]
- 按压开关 2 ，[关, 开, 关]
- 按压开关 3 ，[开, 关, 开]
- 按压开关 4 ，[关, 开, 开]
提示：
1 <= n <= 1000
0 <= presses <= 1000
class Solution {
public:
int flipLights(int n, int presses) {
if (presses == 0)return 1;
if (n ==1)return 2;
if (n == 2)return 4 - presses % 2;
if (presses ==1)return 4;
if (presses == 2)return 7;
return 8;
}
};769. 最多能完成排序的块
给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
返回数组能分成的最多块数量。
示例 1:
输入: arr = [4,3,2,1,0] 输出: 1 解释: 将数组分成2块或者更多块，都无法得到所需的结果。 例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
示例 2:
输入: arr = [1,0,2,3,4] 输出: 4 解释: 我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。 然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。 对每个块单独排序后，结果为 [0, 1], [2], [3], [4]
提示:
n == arr.length1 <= n <= 100 <= arr[i] < narr中每个元素都 不同
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int m=0,ans=0;
for(int i=0;i<arr.size();i++){
m=max(m,arr[i]);
if(m<=i)ans++;
}
return ans;
}
};1060. 有序数组中的缺失元素
现有一个按 升序 排列的整数数组 nums ，其中每个数字都 互不相同 。
给你一个整数 k ，请你找出并返回从数组最左边开始的第 k 个缺失数字。
示例 1：
输入：nums = [4,7,9,10], k = 1 输出：5 解释：第一个缺失数字为 5 。
示例 2：
输入：nums = [4,7,9,10], k = 3 输出：8 解释：缺失数字有 [5,6,8,...]，因此第三个缺失数字为 8 。
示例 3：
输入：nums = [1,2,4], k = 3 输出：6 解释：缺失数字有 [3,5,6,7,...]，因此第三个缺失数字为 6 。
提示：
1 <= nums.length <= 5 * 1041 <= nums[i] <= 107nums按 升序 排列，其中所有元素 互不相同 。1 <= k <= 108
进阶：你可以设计一个对数时间复杂度（即，O(log(n))）的解决方案吗？
class Solution {
public:
int missingElement(vector<int>& nums, int k) {
for(int i=1;i<nums.size();i++){
if(k<=nums[i]-nums[i-1]-1)return nums[i-1]+k;
k-=nums[i]-nums[i-1]-1;
}
return nums[nums.size()-1]+k;
}
};1085. 最小元素各数位之和
给你一个正整数的数组 A。
然后计算 S，使其等于数组 A 当中最小的那个元素各个数位上数字之和。
最后，假如 S 所得计算结果是 奇数 ，返回 0 ；否则请返回 1。
示例 1:
输入：[34,23,1,24,75,33,54,8] 输出：0 解释： 最小元素为 1 ，该元素各个数位上的数字之和 S = 1 ，是奇数所以答案为 0 。
示例 2：
输入：[99,77,33,66,55] 输出：1 解释： 最小元素为 33 ，该元素各个数位上的数字之和 S = 3 + 3 = 6 ，是偶数所以答案为 1 。
提示：
1 <= A.length <= 1001 <= A[i] <= 100
class Solution {
public:
int sumOfDigits(vector<int>& nums) {
int x=nums[0];
for(int i=1;i<nums.size();i++)x=min(x,nums[i]);
int s=0;
while(x)s+=x%10,x/=10;
return 1-s%2;
}
};1093. 大样本统计
我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 在样本中出现的次数。
计算以下统计数据:
minimum：样本中的最小元素。maximum：样品中的最大元素。mean：样本的平均值，计算为所有元素的总和除以元素总数。median：- 如果样本的元素个数是奇数，那么一旦样本排序后，中位数
median就是中间的元素。 - 如果样本中有偶数个元素，那么中位数
median就是样本排序后中间两个元素的平均值。
- 如果样本的元素个数是奇数，那么一旦样本排序后，中位数
mode：样本中出现次数最多的数字。保众数是 唯一 的。
以浮点数数组的形式返回样本的统计信息 [minimum, maximum, mean, median, mode] 。与真实答案误差在 10-5 内的答案都可以通过。
示例 1：
输入：count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 输出：[1.00000,3.00000,2.37500,2.50000,3.00000] 解释：用count表示的样本为[1,2,2,2,3,3,3,3]。 最小值和最大值分别为1和3。 均值是(1+2+2+2+3+3+3+3) / 8 = 19 / 8 = 2.375。 因为样本的大小是偶数，所以中位数是中间两个元素2和3的平均值，也就是2.5。 众数为3，因为它在样本中出现的次数最多。
示例 2：
输入：count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 输出：[1.00000,4.00000,2.18182,2.00000,1.00000] 解释：用count表示的样本为[1,1,1,1,2,2,3,3,3,4,4]。 最小值为1，最大值为4。 平均数是(1+1+1+1+2+2+2+3+3+4+4)/ 11 = 24 / 11 = 2.18181818…(为了显示，输出显示了整数2.18182)。 因为样本的大小是奇数，所以中值是中间元素2。 众数为1，因为它在样本中出现的次数最多。
提示：
count.length == 2560 <= count[i] <= 1091 <= sum(count) <= 109-
count的众数是 唯一 的
class Solution {
public:
vector<double> sampleStats(vector<int>& count) {
int minid = 0, maxid = 0, num = 0;
double s = 0;
for (int i = 0; i <= 255; i++) {
if (count[i] == 0)continue;
if (count[minid]==0)minid = i;
maxid = i;
num += count[i], s += i * 1.0 * count[i];
}
vector<double>ans{ minid * 1.0,maxid * 1.0 ,s / num };
int num2 = 0, median = 0, mode = 0;
for (int i = 0; i <= 255; i++) {
if (count[i] == 0)continue;
if (num2 < (num + 1) / 2 && num2 + count[i] >= (num + 1) / 2)median+= i;
if (num2 < num / 2 + 1 && num2 + count[i] >= num / 2 + 1)median += i;
num2 += count[i];
if (count[mode] < count[i])mode = i;
}
ans.push_back(median / 2.0);
ans.push_back(mode);
return ans;
}
};1133. 最大唯一数
给你一个整数数组 A，请找出并返回在该数组中仅出现一次的最大整数。
如果不存在这个只出现一次的整数，则返回 -1。
示例 1：
输入：[5,7,3,9,4,9,8,3,1] 输出：8 解释： 数组中最大的整数是 9，但它在数组中重复出现了。而第二大的整数是 8，它只出现了一次，所以答案是 8。
示例 2：
输入：[9,9,8,8] 输出：-1 解释： 数组中不存在仅出现一次的整数。
提示：
1 <= A.length <= 20000 <= A[i] <= 1000
class Solution {
public:
int largestUniqueNumber(vector<int>& nums) {
map<int,int>m;
for(auto x:nums)m[x]++;
int ans=-1;
for(auto p:m)if(p.second==1)ans=p.first;
return ans;
}
};1150. 检查一个数是否在数组中占绝大多数
给出一个按 非递减 顺序排列的数组 nums，和一个目标数值 target。假如数组 nums 中绝大多数元素的数值都等于 target，则返回 True，否则请返回 False。
所谓占绝大多数，是指在长度为 N 的数组中出现必须 超过 N/2 次。
示例 1：
输入：nums = [2,4,5,5,5,5,5,6,6], target = 5 输出：true 解释： 数字 5 出现了 5 次，而数组的长度为 9。 所以，5 在数组中占绝大多数，因为 5 次 > 9/2。
示例 2：
输入：nums = [10,100,101,101], target = 101 输出：false 解释： 数字 101 出现了 2 次，而数组的长度是 4。 所以，101 不是 数组占绝大多数的元素，因为 2 次 = 4/2。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 10^91 <= target <= 10^9
class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
int n=0;
for(auto x:nums)n+=(x==target);
return n*2>nums.size();
}
};1151. 最少交换次数来组合所有的 1
给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。
示例 1:
输入: data = [1,0,1,0,1] 输出: 1 解释: 有三种可能的方法可以把所有的 1 组合在一起： [1,1,1,0,0]，交换 1 次； [0,1,1,1,0]，交换 2 次； [0,0,1,1,1]，交换 1 次。 所以最少的交换次数为 1。
示例 2:
输入：data = [0,0,0,1,0] 输出：0 解释： 由于数组中只有一个 1，所以不需要交换。
示例 3:
输入：data = [1,0,1,0,1,0,0,1,1,0,1] 输出：3 解释： 交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。
示例 4:
输入: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1] 输出: 8
提示:
1 <= data.length <= 105data[i]==0or1.
class Solution {
public:
int minSwaps(vector<int>& data) {
int num=0,s=0,ans=data.size();
for(auto x:data)num+=(x==1);
for(int i=0;i<data.size();i++){
s+=data[i];
if(i>=num)s-=data[i-num];
ans=min(ans,num-s);
}
return ans;
}
};1196. 最多可以买到的苹果数量
你有一些苹果和一个可以承载 5000 单位重量的篮子。
给定一个整数数组 weight ，其中 weight[i] 是第 i 个苹果的重量，返回 你可以放入篮子的最大苹果数量 。
示例 1：
输入：weight = [100,200,150,1000] 输出：4 解释：所有 4 个苹果都可以装进去，因为它们的重量之和为 1450。
示例 2：
输入：weight = [900,950,800,1000,700,800] 输出：5 解释：6 个苹果的总重量超过了 5000，所以我们只能从中任选 5 个。
提示：
1 <= weight.length <= 1031 <= weight[i] <= 103
class Solution {
public:
int maxNumberOfApples(vector<int>& weight) {
sort(weight.begin(),weight.end());
int s=5000;
for(int i=0;i<weight.size();i++){
s-=weight[i];
if(s<0)return i;
}
return weight.size();
}
};1213. 三个有序数组的交集
给出三个均为 严格递增排列 的整数数组 arr1，arr2 和 arr3。返回一个由 仅 在这三个数组中 同时出现 的整数所构成的有序数组。
示例 1：
输入: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8] 输出: [1,5] 解释: 只有 1 和 5 同时在这三个数组中出现.
示例 2:
输入: arr1 = [197,418,523,876,1356], arr2 = [501,880,1593,1710,1870], arr3 = [521,682,1337,1395,1764] 输出: []
提示：
1 <= arr1.length, arr2.length, arr3.length <= 10001 <= arr1[i], arr2[i], arr3[i] <= 2000
class Solution {
public:
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
arr1=GetSameData(arr1,arr2);
return GetSameData(arr1,arr3);
}
};1228. 等差数列中缺失的数字
在某个数组 arr 中，值符合等差数列的数值规律：在 0 <= i < arr.length - 1 的前提下，arr[i+1] - arr[i] 的值都相等。
我们会从该数组中删除一个 既不是第一个 也 不是最后一个的值，得到一个新的数组 arr。
给你这个缺值的数组 arr，返回 被删除的那个数 。
示例 1：
输入：arr = [5,7,11,13] 输出：9 解释：原来的数组是 [5,7,9,11,13]。
示例 2：
输入：arr = [15,13,12] 输出：14 解释：原来的数组是 [15,14,13,12]。
提示：
3 <= arr.length <= 10000 <= arr[i] <= 105- 给定的数组 保证 是一个有效的数组。
class Solution {
public:
int missingNumber(vector<int>& arr) {
int dif = (arr[arr.size() - 1] - arr[0]) / int(arr.size());
for (int i = 1; i < arr.size(); i++)if (arr[i] != arr[i - 1] + dif)return arr[i - 1] + dif;
return arr[0];
}
};1491. 去掉最低工资和最高工资后的工资平均值
给你一个整数数组 salary ，数组里每个数都是 唯一 的，其中 salary[i] 是第 i 个员工的工资。
请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。
示例 1：
输入：salary = [4000,3000,1000,2000] 输出：2500.00000 解释：最低工资和最高工资分别是 1000 和 4000 。 去掉最低工资和最高工资以后的平均工资是 (2000+3000)/2= 2500
示例 2：
输入：salary = [1000,2000,3000] 输出：2000.00000 解释：最低工资和最高工资分别是 1000 和 3000 。 去掉最低工资和最高工资以后的平均工资是 (2000)/1= 2000
示例 3：
输入：salary = [6000,5000,4000,3000,2000,1000] 输出：3500.00000
示例 4：
输入：salary = [8000,9000,2000,3000,6000,1000] 输出：4750.00000
提示：
3 <= salary.length <= 10010^3 <= salary[i] <= 10^6salary[i]是唯一的。- 与真实值误差在
10^-5以内的结果都将视为正确答案。
class Solution {
public:
double average(vector<int>& v) {
int mins=v[0],maxs=v[0],s=0;
for(auto x:v)s+=x,mins=min(mins,x),maxs=max(maxs,x);
return (s-mins-maxs)*1.0/(v.size()-2);
}
};1599. 经营摩天轮的最大利润
你正在经营一座摩天轮，该摩天轮共有 4 个座舱 ，每个座舱 最多可以容纳 4 位游客 。你可以 逆时针 轮转座舱，但每次轮转都需要支付一定的运行成本 runningCost 。摩天轮每次轮转都恰好转动 1 / 4 周。
给你一个长度为 n 的数组 customers ， customers[i] 是在第 i 次轮转（下标从 0 开始）之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转 i 次。每位游客在登上离地面最近的座舱前都会支付登舱成本 boardingCost ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。
你可以随时停下摩天轮，即便是 在服务所有游客之前 。如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转 。注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。
返回最大化利润所需执行的 最小轮转次数 。 如果不存在利润为正的方案，则返回 -1 。
示例 1：
输入：customers = [8,3], boardingCost = 5, runningCost = 6 输出：3 解释：座舱上标注的数字是该座舱的当前游客数。 1. 8 位游客抵达，4 位登舱，4 位等待下一舱，摩天轮轮转。当前利润为 4 * $5 - 1 * $6 = $14 。 2. 3 位游客抵达，4 位在等待的游客登舱，其他 3 位等待，摩天轮轮转。当前利润为 8 * $5 - 2 * $6 = $28 。 3. 最后 3 位游客登舱，摩天轮轮转。当前利润为 11 * $5 - 3 * $6 = $37 。 轮转 3 次得到最大利润，最大利润为 $37 。
示例 2：
输入：customers = [10,9,6], boardingCost = 6, runningCost = 4 输出：7 解释： 1. 10 位游客抵达，4 位登舱，6 位等待下一舱，摩天轮轮转。当前利润为 4 * $6 - 1 * $4 = $20 。 2. 9 位游客抵达，4 位登舱，11 位等待（2 位是先前就在等待的，9 位新加入等待的），摩天轮轮转。当前利润为 8 * $6 - 2 * $4 = $40 。 3. 最后 6 位游客抵达，4 位登舱，13 位等待，摩天轮轮转。当前利润为 12 * $6 - 3 * $4 = $60 。 4. 4 位登舱，9 位等待，摩天轮轮转。当前利润为 * $6 - 4 * $4 = $80 。 5. 4 位登舱，5 位等待，摩天轮轮转。当前利润为 20 * $6 - 5 * $4 = $100 。 6. 4 位登舱，1 位等待，摩天轮轮转。当前利润为 24 * $6 - 6 * $4 = $120 。 7. 1 位登舱，摩天轮轮转。当前利润为 25 * $6 - 7 * $4 = $122 。 轮转 7 次得到最大利润，最大利润为$122 。
示例 3：
输入：customers = [3,4,0,5,1], boardingCost = 1, runningCost = 92 输出：-1 解释： 1. 3 位游客抵达，3 位登舱，0 位等待，摩天轮轮转。当前利润为 3 * $1 - 1 * $92 = -$89 。 2. 4 位游客抵达，4 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 2 * $92 = -$177 。 3. 0 位游客抵达，0 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 3 * $92 = -$269 。 4. 5 位游客抵达，4 位登舱，1 位等待，摩天轮轮转。当前利润为 11 * $1 - 4 * $92 = -$357 。 5. 1 位游客抵达，2 位登舱，0 位等待，摩天轮轮转。当前利润为 13 * $1 - 5 * $92 = -$447 。 利润永不为正，所以返回 -1 。
提示：
n == customers.length1 <= n <= 1050 <= customers[i] <= 501 <= boardingCost, runningCost <= 100
class Solution {
public:
int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {
int ans=0,s=0;
int maxAns=0,ret=-1;
for(int i=0;;i++){
if(i>=customers.size() && s==0)break;
if(i<customers.size())s+=customers[i];
int a=min(s,4);
s-=a;
ans += a*boardingCost - runningCost;
if(maxAns<ans){
maxAns=ans;
ret=i+1;
}
}
return ret;
}
};1663. 具有给定数值的最小字符串
小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。
字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。
给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。
注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：
x 是 y 的一个前缀；
如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。
示例 1：
输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。
示例 2：
输入：n = 5, k = 73
输出："aaszz"
提示：
1 <= n <= 105
n <= k <= 26 * n
class Solution {
public:
string getSmallestString(int n, int k) {
int x=n-1-(k-n)/25;
k-=x;
string ans(n,'a');
for(int i=x+1;i<ans.length();i++)ans[i]='z',k-=26;
if(x<ans.length())ans[x]=k-1+'a';
return ans;
}
};1664. 生成平衡数组的方案数
给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。
比方说，如果 nums = [6,1,7,4,1] ，那么：
选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。
选择删除下标 2 ，剩下的数组为 nums = [6,1,4,1] 。
选择删除下标 4 ，剩下的数组为 nums = [6,1,7,4] 。
如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。
请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。
示例 1：
输入：nums = [2,1,6,4]
输出：1
解释：
删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。
示例 2：
输入：nums = [1,1,1]
输出：3
解释：你可以删除任意元素，剩余数组都是平衡数组。
示例 3：
输入：nums = [1,2,3]
输出：0
解释：不管删除哪个元素，剩下数组都不是平衡数组。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 104
class Solution {
public:
int waysToMakeFair(vector<int>& nums) {
if (nums.size() < 2)return 1;
vector<int> v1 = dif(nums);
vector<int> v2 = dif(Frev(nums));
int x = nums.size() % 2 ? -1 : 1, ans = 0;
for (int i = 0; i <= nums.size()-3; i++)if (v1[i] + v2[nums.size()-i-3] * x == 0)ans++;
if (v1[nums.size()-2] == 0)ans++;
if (v2[nums.size() - 2] == 0)ans++;
return ans;
}
vector<int> dif(const vector<int> &v)
{
vector<int>ans = v;
for (int i = 1; i < v.size(); i++)ans[i] = i % 2 ? ans[i - 1] - ans[i] : ans[i - 1] + ans[i];
return ans;
}
};1732. 找到最高海拔
有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。
给你一个长度为 n 的整数数组 gain ，其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔 。
示例 1：
输入：gain = [-5,1,5,0,-7] 输出：1 解释：海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。
示例 2：
输入：gain = [-4,-3,-2,-1,4,3,2] 输出：0 解释：海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。
提示：
n == gain.length1 <= n <= 100-100 <= gain[i] <= 100
class Solution {
public:
int largestAltitude(vector<int>& gain) {
int ans=0,s=0;
for(auto g:gain)s+=g,ans=max(ans,s);
return ans;
}
};1742. 盒子中小球的最大数量
你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。
你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。
给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。
示例 1：
输入：lowLimit = 1, highLimit = 10 输出：2 解释： 盒子编号：1 2 3 4 5 6 7 8 9 10 11 ... 小球数量：2 1 1 1 1 1 1 1 1 0 0 ... 编号 1 的盒子放有最多小球，小球数量为 2 。
示例 2：
输入：lowLimit = 5, highLimit = 15 输出：2 解释： 盒子编号：1 2 3 4 5 6 7 8 9 10 11 ... 小球数量：1 1 1 1 2 2 1 1 1 0 0 ... 编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。
示例 3：
输入：lowLimit = 19, highLimit = 28 输出：2 解释： 盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ... 小球数量：0 1 1 1 1 1 1 1 1 2 0 0 ... 编号 10 的盒子放有最多小球，小球数量为 2 。
提示：
1 <= lowLimit <= highLimit <= 105
class Solution {
public:
int countBalls(int lowLimit, int highLimit) {
map<int,int>m;
int ans=0;
for(int x=lowLimit;x<=highLimit;x++)ans=max(ans,++m[id(x)]);
return ans;
}
int id(int x)
{
int ans=0;
while(x)ans+=x%10,x/=10;
return ans;
}
};1752. 检查数组是否经排序和轮转得到
给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。
如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。
源数组中可能存在 重复项 。
注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。
示例 1：
输入：nums = [3,4,5,1,2] 输出：true 解释：[1,2,3,4,5] 为有序的源数组。 可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。
示例 2：
输入：nums = [2,1,3,4] 输出：false 解释：源数组无法经轮转得到 nums 。
示例 3：
输入：nums = [1,2,3] 输出：true 解释：[1,2,3] 为有序的源数组。 可以轮转 x = 0 个位置（即不轮转）得到 nums 。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100
class Solution {
public:
bool check(vector<int>& nums) {
int x=1;
for(int i=1;i<=nums.size();i++)if(nums[i%nums.size()]<nums[i-1]){
x--;
if(x<0)return false;
}
return true;
}
};1828. 统计一个圆中点的数目
给你一个数组 points ，其中 points[i] = [xi, yi] ，表示第 i 个点在二维平面上的坐标。多个点可能会有 相同 的坐标。
同时给你一个数组 queries ，其中 queries[j] = [xj, yj, rj] ，表示一个圆心在 (xj, yj) 且半径为 rj 的圆。
对于每一个查询 queries[j] ，计算在第 j 个圆 内 点的数目。如果一个点在圆的 边界上 ，我们同样认为它在圆 内 。
请你返回一个数组 answer ，其中 answer[j]是第 j 个查询的答案。
示例 1：
输入：points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
输出：[3,2,2]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆。
示例 2：
输入：points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
输出：[2,3,2,4]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆，queries[3] 是紫色的圆。
提示：
1 <= points.length <= 500
points[i].length == 2
0 <= xi, yi <= 500
1 <= queries.length <= 500
queries[j].length == 3
0 <= xj, yj <= 500
1 <= rj <= 500
所有的坐标都是整数。
class Solution {
public:
vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
vector<int>ret;
for(auto q:queries){
int ans=0;
for(auto p:points){
if((p[0]-q[0])*(p[0]-q[0])+(p[1]-q[1])*(p[1]-q[1])<=q[2]*q[2])ans++;
}
ret.push_back(ans);
}
return ret;
}
};1954. 收集足够苹果的最小花园周长
给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 (i, j) 处的苹果树有 |i| + |j| 个苹果。
你将会买下正中心坐标是 (0, 0) 的一块 正方形土地 ，且每条边都与两条坐标轴之一平行。
给你一个整数 neededApples ，请你返回土地的 最小周长 ，使得 至少 有 neededApples 个苹果在土地 里面或者边缘上。
|x| 的值定义为：
- 如果
x >= 0，那么值为x - 如果
x < 0，那么值为-x
示例 1：
输入：neededApples = 1 输出：8 解释：边长长度为 1 的正方形不包含任何苹果。 但是边长为 2 的正方形包含 12 个苹果（如上图所示）。 周长为 2 * 4 = 8 。
示例 2：
输入：neededApples = 13 输出：16
示例 3：
输入：neededApples = 1000000000 输出：5040
提示：
1 <= neededApples <= 1015
class Solution {
public:
long long minimumPerimeter(long long neededApples) {
long long x = pow(neededApples/4,1/3.0)-5;
while(x*(x+1)*(x*2+1)*2<neededApples)x++;
cout<<x;
return x*8;
}
};2103. 环和杆
总计有 n 个环，环的颜色可以是红、绿、蓝中的一种。这些环分别穿在 10 根编号为 0 到 9 的杆上。
给你一个长度为 2n 的字符串 rings ，表示这 n 个环在杆上的分布。rings 中每两个字符形成一个 颜色位置对 ，用于描述每个环：
- 第
i对中的 第一个 字符表示第i个环的 颜色（'R'、'G'、'B'）。 - 第
i对中的 第二个 字符表示第i个环的 位置，也就是位于哪根杆上（'0'到'9'）。
例如，"R3G2B1" 表示：共有 n == 3 个环，红色的环在编号为 3 的杆上，绿色的环在编号为 2 的杆上，蓝色的环在编号为 1 的杆上。
找出所有集齐 全部三种颜色 环的杆，并返回这种杆的数量。
示例 1：
输入：rings = "B0B6G0R6R0R6G9" 输出：1 解释： - 编号 0 的杆上有 3 个环，集齐全部颜色：红、绿、蓝。 - 编号 6 的杆上有 3 个环，但只有红、蓝两种颜色。 - 编号 9 的杆上只有 1 个绿色环。 因此，集齐全部三种颜色环的杆的数目为 1 。
示例 2：
输入：rings = "B0R0G0R9R0B0G0" 输出：1 解释： - 编号 0 的杆上有 6 个环，集齐全部颜色：红、绿、蓝。 - 编号 9 的杆上只有 1 个红色环。 因此，集齐全部三种颜色环的杆的数目为 1 。
示例 3：
输入：rings = "G4" 输出：0 解释： 只给了一个环，因此，不存在集齐全部三种颜色环的杆。
提示：
rings.length == 2 * n1 <= n <= 100- 如
i是 偶数 ，则rings[i]的值可以取'R'、'G'或'B'（下标从 0 开始计数） - 如
i是 奇数 ，则rings[i]的值可以取'0'到'9'中的一个数字（下标从 0 开始计数）
class Solution {
public:
int countPoints(string rings) {
map<char,set<char>>m;
for(int i=0;i<rings.length();i+=2){
m[rings[i+1]].insert(rings[i]);
}
int ans=0;
for(auto &mi:m){
if(mi.second.size()==3)ans++;
}
return ans;
}
};2180. 统计各位数字之和为偶数的整数个数
给你一个正整数 num ，请你统计并返回 小于或等于 num 且各位数字之和为 偶数 的正整数的数目。
正整数的 各位数字之和 是其所有位上的对应数字相加的结果。
示例 1：
输入：num = 4
输出：2
解释：
只有 2 和 4 满足小于等于 4 且各位数字之和为偶数。
示例 2：
输入：num = 30
输出：14
解释：
只有 14 个整数满足小于等于 30 且各位数字之和为偶数，分别是：
2、4、6、8、11、13、15、17、19、20、22、24、26 和 28 。
提示：
1 <= num <= 1000
class Solution {
public:
int countEven(int num) {
int x=0,a=num-num%10;
while(a)x+=a%10,a/=10;
return num/2-(x%2==1 && num%2==0);
}
};2303. 计算应缴税款总额
给你一个下标从 0 开始的二维整数数组 brackets ，其中 brackets[i] = [upperi, percenti] ，表示第 i 个税级的上限是 upperi ，征收的税率为 percenti 。税级按上限 从低到高排序（在满足 0 < i < brackets.length 的前提下，upperi-1 < upperi）。
税款计算方式如下：
不超过 upper0 的收入按税率 percent0 缴纳
接着 upper1 - upper0 的部分按税率 percent1 缴纳
然后 upper2 - upper1 的部分按税率 percent2 缴纳
以此类推
给你一个整数 income 表示你的总收入。返回你需要缴纳的税款总额。与标准答案误差不超 10-5 的结果将被视作正确答案。
示例 1：
输入：brackets = [[3,50],[7,10],[12,25]], income = 10
输出：2.65000
解释：
前 $3 的税率为 50% 。需要支付税款 $3 * 50% = $1.50 。
接下来 $7 - $3 = $4 的税率为 10% 。需要支付税款 $4 * 10% = $0.40 。
最后 $10 - $7 = $3 的税率为 25% 。需要支付税款 $3 * 25% = $0.75 。
需要支付的税款总计 $1.50 + $0.40 + $0.75 = $2.65 。
示例 2：
输入：brackets = [[1,0],[4,25],[5,50]], income = 2
输出：0.25000
解释：
前 $1 的税率为 0% 。需要支付税款 $1 * 0% = $0 。
剩下 $1 的税率为 25% 。需要支付税款 $1 * 25% = $0.25 。
需要支付的税款总计 $0 + $0.25 = $0.25 。
示例 3：
输入：brackets = [[2,50]], income = 0
输出：0.00000
解释：
没有收入，无需纳税，需要支付的税款总计 $0 。
提示：
1 <= brackets.length <= 100
1 <= upperi <= 1000
0 <= percenti <= 100
0 <= income <= 1000
upperi 按递增顺序排列
upperi 中的所有值 互不相同
最后一个税级的上限大于等于 income
class Solution {
public:
double calculateTax(vector<vector<int>>& brackets, int income) {
int ans=0,bf=0;
for(auto v:brackets){
ans+=min(v[0]-bf,income)*v[1];
income=max(income-v[0]+bf,0);
bf=v[0];
}
return ans*0.01;
}
};2319. 判断矩阵是否是一个 X 矩阵
如果一个正方形矩阵满足下述 全部 条件，则称之为一个 X 矩阵 ：
矩阵对角线上的所有元素都 不是 0
矩阵中所有其他元素都是 0
给你一个大小为 n x n 的二维整数数组 grid ，表示一个正方形矩阵。如果 grid 是一个 X 矩阵 ，返回 true ；否则，返回 false 。
示例 1：
输入：grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
输出：true
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 是一个 X 矩阵。
示例 2：
输入：grid = [[5,7,0],[0,3,1],[0,5,0]]
输出：false
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 不是一个 X 矩阵。
提示：
n == grid.length == grid[i].length
3 <= n <= 100
0 <= grid[i][j] <= 105
class Solution {
public:
bool checkXMatrix(vector<vector<int>>& grid) {
for(int i=0;i<grid.size();i++)for(int j=0;j<grid.size();j++){
if(i==j||i+j==grid.size()-1){
if(grid[i][j]==0)return false;
}else{
if(grid[i][j]!=0)return false;
}
}
return true;
}
};2481. 分割圆的最少切割次数
圆内一个 有效切割 ，符合以下二者之一：
该切割是两个端点在圆上的线段，且该线段经过圆心。
该切割是一端在圆心另一端在圆上的线段。
一些有效和无效的切割如下图所示。
给你一个整数 n ，请你返回将圆切割成相等的 n 等分的 最少 切割次数。
示例 1：
输入：n = 4
输出：2
解释：
上图展示了切割圆 2 次，得到四等分。
示例 2：
输入：n = 3
输出：3
解释：
最少需要切割 3 次，将圆切成三等分。
少于 3 次切割无法将圆切成大小相等面积相同的 3 等分。
同时可以观察到，第一次切割无法将圆切割开。
提示：
1 <= n <= 100
class Solution {
public:
int numberOfCuts(int n) {
return n>1?(n%2?n:n/2):0;
}
};2525. 根据规则将箱子分类
给你四个整数 length ，width ，height 和 mass ，分别表示一个箱子的三个维度和质量，请你返回一个表示箱子 类别 的字符串。
- 如果满足以下条件，那么箱子是
"Bulky"的：- 箱子 至少有一个 维度大于等于
104。 - 或者箱子的 体积 大于等于
109。
- 箱子 至少有一个 维度大于等于
- 如果箱子的质量大于等于
100，那么箱子是"Heavy"的。 - 如果箱子同时是
"Bulky"和"Heavy"，那么返回类别为"Both"。 - 如果箱子既不是
"Bulky"，也不是"Heavy"，那么返回类别为"Neither"。 - 如果箱子是
"Bulky"但不是"Heavy"，那么返回类别为"Bulky"。 - 如果箱子是
"Heavy"但不是"Bulky"，那么返回类别为"Heavy"。
注意，箱子的体积等于箱子的长度、宽度和高度的乘积。
示例 1：
输入：length = 1000, width = 35, height = 700, mass = 300 输出："Heavy" 解释： 箱子没有任何维度大于等于 104 。 体积为 24500000 <= 109 。所以不能归类为 "Bulky" 。 但是质量 >= 100 ，所以箱子是 "Heavy" 的。 由于箱子不是 "Bulky" 但是是 "Heavy" ，所以我们返回 "Heavy" 。
示例 2：
输入：length = 200, width = 50, height = 800, mass = 50 输出："Neither" 解释： 箱子没有任何维度大于等于 104 。 体积为 8 * 106 <= 109 。所以不能归类为 "Bulky" 。 质量小于 100 ，所以不能归类为 "Heavy" 。 由于不属于上述两者任何一类，所以我们返回 "Neither" 。
提示：
1 <= length, width, height <= 1051 <= mass <= 103
class Solution {
public:
string categorizeBox(long long length, int width, int height, int mass) {
bool flag1=(length>=10000 ||width>=10000|| height>=10000||length*width*height>=1000000000);
bool flag2= mass>=100;
if(flag1&&flag2)return "Both";
if(flag1)return "Bulky";
if(flag2)return "Heavy";
return "Neither";
}
};2544. 交替数字和
给你一个正整数 n 。n 中的每一位数字都会按下述规则分配一个符号：
- 最高有效位 上的数字分配到 正 号。
- 剩余每位上数字的符号都与其相邻数字相反。
返回所有数字及其对应符号的和。
示例 1：
输入：n = 521 输出：4 解释：(+5) + (-2) + (+1) = 4
示例 2：
输入：n = 111 输出：1 解释：(+1) + (-1) + (+1) = 1
示例 3：
输入：n = 886996 输出：0 解释：(+8) + (-8) + (+6) + (-9) + (+9) + (-6) = 0
提示：
1 <= n <= 109
class Solution {
public:
int alternateDigitSum(int n) {
int ans=0,num=0;
while(n){
ans+=num%2?-(n%10):(n%10);
n/=10,num++;
}
return num%2?ans:-ans;
}
};2582. 递枕头
n 个人站成一排，按从 1 到 n 编号。
最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。
- 例如，当枕头到达第
n个人时，TA 会将枕头传递给第n - 1个人，然后传递给第n - 2个人，依此类推。
给你两个正整数 n 和 time ，返回 time 秒后拿着枕头的人的编号。
示例 1：
输入：n = 4, time = 5 输出：2 解释：队伍中枕头的传递情况为：1 -> 2 -> 3 -> 4 -> 3 -> 2 。 5 秒后，枕头传递到第 2 个人手中。
示例 2：
输入：n = 3, time = 2 输出：3 解释：队伍中枕头的传递情况为：1 -> 2 -> 3 。 2 秒后，枕头传递到第 3 个人手中。
提示：
2 <= n <= 10001 <= time <= 1000
class Solution {
public:
int passThePillow(int n, int time) {
time %= (n * 2 - 2);
if (time < n - 1)return time + 1;
return n * 2 - 1 - time;
}
};2600. K 件物品的最大和
袋子中装有一些物品，每个物品上都标记着数字 1 、0 或 -1 。
给你四个非负整数 numOnes 、numZeros 、numNegOnes 和 k 。
袋子最初包含：
numOnes件标记为1的物品。numZeroes件标记为0的物品。numNegOnes件标记为-1的物品。
现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中，物品上所标记数字之和的最大值。
示例 1：
输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
输出：2
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 2 件标记为 1 的物品，得到的数字之和为 2 。
可以证明 2 是所有可行方案中的最大值。
示例 2：
输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
输出：3
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 3 件标记为 1 的物品，1 件标记为 0 的物品，得到的数字之和为 3 。
可以证明 3 是所有可行方案中的最大值。
提示：
0 <= numOnes, numZeros, numNegOnes <= 500 <= k <= numOnes + numZeros + numNegOnes
class Solution {
public:
int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
if(k<numOnes+numZeros)return min(k,numOnes);
return numOnes*2+numZeros-k;
}
};2639. 查询网格图中每一列的宽度
给你一个下标从 0 开始的 m x n 整数矩阵 grid 。矩阵中某一列的宽度是这一列数字的最大 字符串长度 。
- 比方说，如果
grid = [[-10], [3], [12]]，那么唯一一列的宽度是3，因为-10的字符串长度为3。
请你返回一个大小为 n 的整数数组 ans ，其中 ans[i] 是第 i 列的宽度。
一个有 len 个数位的整数 x ，如果是非负数，那么 字符串长度 为 len ，否则为 len + 1 。
示例 1：
输入：grid = [[1],[22],[333]] 输出：[3] 解释：第 0 列中，333 字符串长度为 3 。
示例 2：
输入：grid = [[-15,1,3],[15,7,12],[5,6,-2]] 输出：[3,1,2] 解释： 第 0 列中，只有 -15 字符串长度为 3 。 第 1 列中，所有整数的字符串长度都是 1 。 第 2 列中，12 和 -2 的字符串长度都为 2 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 100-109 <= grid[r][c] <= 109
class Solution {
public:
vector<int> findColumnWidth(vector<vector<int>>& grid) {
vector<int>ans(grid[0].size());
for(auto &v:grid){
for(int i=0;i<v.size();i++){
ans[i]=max(ans[i],getLen(v[i]));
}
}
return ans;
}
int getLen(int x){
if(x<0)return getLen(-x)+1;
if(x==0)return 1;
int s=0;
while(x)s++,x/=10;
return s;
}
};2660. 保龄球游戏的获胜者
给你两个下标从 0 开始的整数数组 player1 和 player2 ，分别表示玩家 1 和玩家 2 击中的瓶数。
保龄球比赛由 n 轮组成，每轮的瓶数恰好为 10 。
假设玩家在第 i 轮中击中 xi 个瓶子。玩家第 i 轮的价值为：
- 如果玩家在该轮的前两轮的任何一轮中击中了
10个瓶子，则为2xi。 - 否则，为
xi。
玩家的得分是其 n 轮价值的总和。
返回
- 如果玩家 1 的得分高于玩家 2 的得分，则为
1； - 如果玩家 2 的得分高于玩家 1 的得分，则为
2； - 如果平局，则为
0。
示例 1：
输入：player1 = [4,10,7,9], player2 = [6,5,2,3] 输出：1 解释：player1 的得分是 4 + 10 + 2*7 + 2*9 = 46 。 player2 的得分是 6 + 5 + 2 + 3 = 16 。 player1 的得分高于 player2 的得分，所以 play1 在比赛中获胜，答案为 1 。
示例 2：
输入：player1 = [3,5,7,6], player2 = [8,10,10,2] 输出：2 解释：player1 的得分是 3 + 5 + 7 + 6 = 21 。 player2 的得分是 8 + 10 + 2*10 + 2*2 = 42 。 player2 的得分高于 player1 的得分，所以 play2 在比赛中获胜，答案为 2 。
示例 3：
输入：player1 = [2,3], player2 = [4,1] 输出：0 解释：player1 的得分是 2 + 3 = 5 。 player2 的得分是 4 + 1 = 5 。 player1 的得分等于 player2 的得分，所以这一场比赛平局，答案为 0 。
提示：
n == player1.length == player2.length1 <= n <= 10000 <= player1[i], player2[i] <= 10
class Solution {
public:
int isWinner(vector<int>& player1, vector<int>& player2) {
int s1=s(player1);
int s2=s(player2);
if(s1>s2)return 1;
if(s1<s2)return 2;
return 0;
}
int s(vector<int>& v){
int ans=0;
for(int i=0;i<v.size();i++){
ans+=v[i];
if((i>=1 && v[i-1]==10)||(i>=2&&v[i-2]==10))ans+=v[i];
}
return ans;
}
};2679. 矩阵中的和
给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空：
- 矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
- 在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的 分数 中。
请你返回最后的 分数 。
示例 1：
输入：nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]] 输出：15 解释：第一步操作中，我们删除 7 ，6 ，6 和 3 ，将分数增加 7 。下一步操作中，删除 2 ，4 ，5 和 2 ，将分数增加 5 。最后删除 1 ，2 ，3 和 1 ，将分数增加 3 。所以总得分为 7 + 5 + 3 = 15 。
示例 2：
输入：nums = [[1]] 输出：1 解释：我们删除 1 并将分数增加 1 ，所以返回 1 。
提示：
1 <= nums.length <= 3001 <= nums[i].length <= 5000 <= nums[i][j] <= 103
class Solution {
public:
int matrixSum(vector<vector<int>>& nums) {
for(int i=0;i<nums.size();i++)sort(nums[i].begin(),nums[i].end());
int ans=0;
for(int j=0;j<nums[0].size();j++){
int m=0;
for(int i=0;i<nums.size();i++)m=max(m,nums[i][j]);
ans+=m;
}
return ans;
}
};2729. 判断一个数是否迷人
给你一个三位数整数 n 。
如果经过以下修改得到的数字 恰好 包含数字 1 到 9 各一次且不包含任何 0 ，那么我们称数字 n 是 迷人的 ：
- 将
n与数字2 * n和3 * n连接 。
如果 n 是迷人的，返回 true，否则返回 false 。
连接 两个数字表示把它们首尾相接连在一起。比方说 121 和 371 连接得到 121371 。
示例 1：
输入：n = 192 输出：true 解释：我们将数字 n = 192 ，2 * n = 384 和 3 * n = 576 连接，得到 192384576 。这个数字包含 1 到 9 恰好各一次。
示例 2：
输入：n = 100 输出：false 解释：我们将数字 n = 100 ，2 * n = 200 和 3 * n = 300 连接，得到 100200300 。这个数字不符合上述条件。
提示：
100 <= n <= 999
class Solution {
public:
bool isFascinating(int n) {
set<int>s;
s.insert(n/100);
s.insert(n/10%10);
s.insert(n%10);
n*=2;
s.insert(n/100);
s.insert(n/10%10);
s.insert(n%10);
n=n/2*3;
s.insert(n/100);
s.insert(n/10%10);
s.insert(n%10);
if(s.size()!=9)return false;
s.insert(0);
return n<=999 && s.size()==10;
}
};2739. 总行驶距离
卡车有两个油箱。给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。
该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。
返回卡车可以行驶的最大距离。
注意：从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。
示例 1：
输入：mainTank = 5, additionalTank = 10 输出：60 解释： 在用掉 5 升燃料后，主油箱中燃料还剩下 (5 - 5 + 1) = 1 升，行驶距离为 50km 。 在用掉剩下的 1 升燃料后，没有新的燃料注入到主油箱中，主油箱变为空。 总行驶距离为 60km 。
示例 2：
输入：mainTank = 1, additionalTank = 2 输出：10 解释： 在用掉 1 升燃料后，主油箱变为空。 总行驶距离为 10km 。
提示：
1 <= mainTank, additionalTank <= 100
class Solution {
public:
int distanceTraveled(int mainTank, int additionalTank) {
int s=0;
while(mainTank>=5){
int mt = mainTank / 5 * 5;
s+=mt;
int t = min(mt/5,additionalTank);
mainTank+=t-mt,additionalTank-=t;
}
s+=mainTank;
return s*10;
}
};2769. 找出最大的可达成数字
给你两个整数 num 和 t 。
如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等，则称其为 可达成数字 ：
- 每次操作将
x的值增加或减少1，同时可以选择将num的值增加或减少1。
返回所有可达成数字中的最大值。可以证明至少存在一个可达成数字。
示例 1：
输入：num = 4, t = 1 输出：6 解释：最大可达成数字是 x = 6 ，执行下述操作可以使其等于 num ： - x 减少 1 ，同时 num 增加 1 。此时，x = 5 且 num = 5 。 可以证明不存在大于 6 的可达成数字。
示例 2：
输入：num = 3, t = 2 输出：7 解释：最大的可达成数字是 x = 7 ，执行下述操作可以使其等于 num ： - x 减少 1 ，同时 num 增加 1 。此时，x = 6 且 num = 4 。 - x 减少 1 ，同时 num 增加 1 。此时，x = 5 且 num = 5 。 可以证明不存在大于 7 的可达成数字。
提示：
1 <= num, t <= 50
class Solution {
public:
int theMaximumAchievableX(int num, int t) {
return num+t+t;
}
};2951. 找出峰值
给你一个下标从 0 开始的数组 mountain 。你的任务是找出数组 mountain 中的所有 峰值。
以数组形式返回给定数组中 峰值 的下标，顺序不限 。
注意：
- 峰值 是指一个严格大于其相邻元素的元素。
- 数组的第一个和最后一个元素 不 是峰值。
示例 1：
输入：mountain = [2,4,4] 输出：[] 解释：mountain[0] 和 mountain[2] 不可能是峰值，因为它们是数组的第一个和最后一个元素。 mountain[1] 也不可能是峰值，因为它不严格大于 mountain[2] 。 因此，答案为 [] 。
示例 2：
输入：mountain = [1,4,3,8,5] 输出：[1,3] 解释：mountain[0] 和 mountain[4] 不可能是峰值，因为它们是数组的第一个和最后一个元素。 mountain[2] 也不可能是峰值，因为它不严格大于 mountain[3] 和 mountain[1] 。 但是 mountain[1] 和 mountain[3] 严格大于它们的相邻元素。 因此，答案是 [1,3] 。
提示：
3 <= mountain.length <= 1001 <= mountain[i] <= 100
class Solution {
public:
vector<int> findPeaks(vector<int>& mountain) {
vector<int>ans;
for(int i=1;i<mountain.size()-1;i++){
if(mountain[i]>mountain[i-1]&&mountain[i]>mountain[i+1])ans.push_back(i);
}
return ans;
}
};
扫一扫
222
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
