LeetCode刷题笔记
【摘要】 目录 2748.美丽下标对的数目 思路：模拟代码： 2749.得到整数零需要执行的最少操作数 思路：枚举代码： 2750.将数组划分成若干好子数组的方式 思路：代码： 2751.机器人碰撞 思路：栈模拟代码: 编辑 2748.美丽下标对的数目 思路：模拟设 x=nums[i]。遍历 nums，同时维护 x 的最高位的出现次数 cnt。枚举 [1,9] 内的数字y，如果与 x ...
目录
2748.美丽下标对的数目
思路：模拟
设 x=nums[i]。
遍历 nums，同时维护 x 的最高位的出现次数 cnt。枚举 [1,9] 内的数字y，如果与 x mod 10 互质则答案加上cnt[y]。
代码：
class Solution {
public:
int countBeautifulPairs(vector<int> &nums) {
int ans = 0, cnt[10]{};
for (int x: nums) {
for (int y = 1; y < 10; y++)
if (cnt[y] && gcd(x % 10, y) == 1)
ans += cnt[y];
while (x >= 10) x /= 10;
cnt[x]++;
}
return ans;
}
};
2749.得到整数零需要执行的最少操作数
思路：枚举
(1)从小到大枚举答案。
(2)假设操作了 k 次，那么操作后 num1变成num 1 −num 2⋅k 再减去 k 个 2的i次方。此时问题变成：num1 −num2⋅k 能否拆分成 k 个 2的i次方之和？
(3)设 x=num1−num2⋅k。
- 如果 x<0，无解。
- 否则如果 x<k，那么即使每次操作取 i=0，也至少要把 x 拆分成 k 个 1 之和，这是不可能的。
- 否则如果 x 中二进制 1 的个数大于 k，也无法拆分成 k 个 2的i次方 之和，无解。
- 否则分解方案一定存在，返回 k。（因为可以把一个 2的j次方 分解成两个 2的j−1次方，所以分解出的 2的i次方 的个数可以从「x 中二进制 1 的个数」一直到 x，k 只要属于这个范围，分解方案就是存在的。)
代码：
class Solution {
public:
int makeTheIntegerZero(int num1, int num2) {
for (long long k = 1; k <= num1 - num2 * k; k++)
if (k >= __builtin_popcountll(num1 - num2 * k))
return k;
return -1;
}
};
2750.将数组划分成若干好子数组的方式
思路：
根据题意，需要在每两个 1 之间画一条分割线，有 x 个 0 就可以画 x+1 条分割线。根据乘法原理，答案为所有分割线的方案数的乘积。特别地，如果数组中没有 1，那么答案为 0。如果数组只有一个 1，那么答案为 1。
代码：
class Solution {
public:
const int quyu=1e9+7;
int numberOfGoodSubarraySplits(vector<int>& nums) {
int len=nums.size();
vector<int> m;
int count=0;
for(int i=0;i<len;i++){
if(nums[i]==1){
count++;
m.push_back(i);
}
}
if(count==1) return 1;
if(count==0) return 0;
long long res=1;
int len2=m.size();
for(int i=0;i<len2-1;i++){
res=(res*((m[i+1]-m[i])%quyu))%quyu;
}
res%=quyu;
return (int)res;
}
};2751.机器人碰撞
思路：栈模拟
用列表维护向左的机器人，用栈维护向右的机器人。
按照positions[i] 从小到大排序。遍历机器人，如果遇到一个向左的机器人 p，分类讨论：
- 如果 p 的健康度小于栈顶，那么栈顶的健康度减一。
- 如果 p 的健康度等于栈顶，那么移除栈顶。
- 如果 p 的健康度大于栈顶，那么移除栈顶，将 �p 的健康度减一后加入 有toLeft。
- 请注意，如果健康度减一，那么在减一之前，健康度一定是大于 1 的，不存在健康度减为 0 的情况。
最后剩余的就是 toLefttoLeft 和 stst 中的机器人，合并，按照编号排序后，返回健康度列表。
代码:
class Solution {
public:
vector<int> survivedRobotsHealths(vector<int> &positions, vector<int> &healths, string directions) {
int n = positions.size(), id[n];
iota(id, id + n, 0);
sort(id, id + n, [&](const int i, const int j) {
return positions[i] < positions[j];
});
stack<int> st;
for (int i: id) {
if (directions[i] == 'R') { // 向右，存入栈中
st.push(i);
continue;
}
// 向左，与栈中向右的机器人碰撞
while (!st.empty()) {
int top = st.top();
if (healths[top] > healths[i]) { // 栈顶的健康度大
healths[top]--;
healths[i] = 0;
break;
}
if (healths[top] == healths[i]) { // 健康度一样大
healths[top] = 0;
st.pop(); // 移除栈顶
healths[i] = 0;
break;
}
healths[top] = 0;
st.pop(); // 移除栈顶
healths[i]--; // 当前机器人的健康度大
}
}
// 去掉 0
healths.erase(remove(healths.begin(), healths.end(), 0), healths.end());
return healths;
}
};
作
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）