邮箱域名和网站域名,浙江手机版建站系统哪个好,怎么选择顺德网站建设,徐州网站开发哪个好薇文章目录1. 比赛结果2. 题目1. LeetCode LCP 17. 速算机器人 easy2. LeetCode LCP 18. 早餐组合 easy3. LeetCode LCP 19. 秋叶收藏集 medium4. LeetCode LCP 20. 快速公交 hard5. LeetCode LCP 21. 追逐游戏 hard1. 比赛结果
做出来2题#xff0c;第三题写了好长时间无果。还…
文章目录1. 比赛结果2. 题目1. LeetCode LCP 17. 速算机器人 easy2. LeetCode LCP 18. 早餐组合 easy3. LeetCode LCP 19. 秋叶收藏集 medium4. LeetCode LCP 20. 快速公交 hard5. LeetCode LCP 21. 追逐游戏 hard1. 比赛结果
做出来2题第三题写了好长时间无果。还是实力太差了继续加油
有提交成功的选手 3244 人排 656 名 前几名大佬太强了 2. 题目
1. LeetCode LCP 17. 速算机器人 easy
题目链接
小扣在秋日市集发现了一款速算机器人。店家对机器人说出两个数字记作 x 和 y请小扣说出计算指令
“A” 运算使 x 2 * x y “B” 运算使 y 2 * y x。 在本次游戏中店家说出的数字为 x 1 和 y 0小扣说出的计算指令记作仅由大写字母 A、B 组成的字符串 s字符串中字符的顺序表示计算顺序请返回最终 x 与 y 的和为多少。
示例 1
输入s AB
输出4
解释
经过一次 A 运算后x 2, y 0。
再经过一次 B 运算x 2, y 2。
最终 x 与 y 之和为 4。提示
0 s.length 10
s 由 A 和 B 组成解题
按题意模拟
class Solution {
public:int calculate(string s) {int x 1, y 0;for(char c : s) {if(c A)x x*2y;elsey y*2x;}return xy;}
};2. LeetCode LCP 18. 早餐组合 easy
题目链接
小扣在秋日市集选择了一家早餐摊位一维整型数组 staple 中记录了每种主食的价格一维整型数组 drinks 中记录了每种饮料的价格。 小扣的计划选择一份主食和一款饮料且花费不超过 x 元。 请返回小扣共有多少种购买方案。
注意答案需要以 1e9 7 (1000000007) 为底取模 如计算初始结果为1000000008请返回 1
示例 1
输入staple [10,20,5], drinks [5,5,2], x 15
输出6
解释小扣有 6 种购买方案所选主食与所选饮料在数组中对应的下标分别是
第 1 种方案staple[0] drinks[0] 10 5 15
第 2 种方案staple[0] drinks[1] 10 5 15
第 3 种方案staple[0] drinks[2] 10 2 12
第 4 种方案staple[2] drinks[0] 5 5 10
第 5 种方案staple[2] drinks[1] 5 5 10
第 6 种方案staple[2] drinks[2] 5 2 7。示例 2
输入staple [2,1,1], drinks [8,9,5,1], x 9
输出8
解释小扣有 8 种购买方案所选主食与所选饮料在数组中对应的下标分别是
第 1 种方案staple[0] drinks[2] 2 5 7
第 2 种方案staple[0] drinks[3] 2 1 3
第 3 种方案staple[1] drinks[0] 1 8 9
第 4 种方案staple[1] drinks[2] 1 5 6
第 5 种方案staple[1] drinks[3] 1 1 2
第 6 种方案staple[2] drinks[0] 1 8 9
第 7 种方案staple[2] drinks[2] 1 5 6
第 8 种方案staple[2] drinks[3] 1 1 2提示
1 staple.length 10^5
1 drinks.length 10^5
1 staple[i],drinks[i] 10^5
1 x 2*10^5解题
对一个数组A排序遍历另一个数组B在A中二分查找
class Solution {
public:int breakfastNumber(vectorint staple, vectorint drinks, int x) {sort(drinks.begin(), drinks.end());long long ans 0, mod 1e97;for(int stp : staple) {if(stp x)continue;int target x - stp;int pos bs(drinks, target);if(pos ! -1){ans (anspos1)%mod;}}return ans;}int bs(vectorint arr, int target){int l 0, r arr.size()-1, n arr.size(), mid;while(l r) //查找小于等于 target的最后一个数{mid (l r) / 2;if(arr[mid] target){r mid-1;}else{if(mid n-1 || arr[mid1] target)return mid;elsel mid1;}}return -1;}
};1164 ms 146.5 MB
或者对两个数组都排序 双指针进行遍历
class Solution {
public:int breakfastNumber(vectorint staple, vectorint drinks, int x) {sort(staple.begin(), staple.end());sort(drinks.begin(), drinks.end());long long ans 0, mod 1e97;int m staple.size(), n drinks.size(), i, j;i 0, j n-1;while(i m j 0){if(staple[i]drinks[j] x){ans (ansj1)%mod;i;}elsej--;}return ans;}
};1368 ms 146.4 MB
3. LeetCode LCP 19. 秋叶收藏集 medium
题目链接
小扣出去秋游途中收集了一些红叶和黄叶他利用这些叶子初步整理了一份秋叶收藏集 leaves 字符串 leaves 仅包含小写字符 r 和 y 其中字符 r 表示一片红叶字符 y 表示一片黄叶。 出于美观整齐的考虑小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等但均需大于等于 1。 每次调整操作小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。 请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
示例 1
输入leaves rrryyyrryyyrr
输出2
解释调整两次将中间的两片红叶替换成黄叶得到 rrryyyyyyyyrr示例 2
输入leaves ryr
输出0
解释已符合要求不需要额外操作提示
3 leaves.length 10^5
leaves 中只包含字符 r 和字符 y解题 参考IK大佬的DP dp[i][0] 是表示到 i 结束时全是 红色R的最少操作次数 dp[i][1] 是表示到 i 结束时形成 RY 的最少操作次数 dp[i][2] 是表示到 i 结束时形成 RYR 的最少操作次数
class Solution {
public:int minimumOperations(string leaves) {int n leaves.size(), i;vectorvectorint dp(n, vectorint(3, INT_MAX));if(leaves[0]r)dp[0][0] 0;elsedp[0][0] 1;//黄的改成红的if(leaves[1]y){dp[1][0] dp[0][0]1;//全红 前面全红 y改rdp[1][1] dp[0][0];// RY 前面全红 当前y}else{dp[1][0] dp[0][0];//全红 前面全红 当前也是红dp[1][1] dp[0][0]1;//RY 前面全红当前r改y}if(leaves[2]r){dp[2][0] dp[1][0];dp[2][1] min(dp[1][0]1, dp[1][1]1);dp[2][2] dp[1][1];}else{dp[2][0] dp[1][0]1;dp[2][1] min(dp[1][0], dp[1][1]);dp[2][2] dp[1][1]1;}for(i 3; i n; i) {if(leaves[i] r){dp[i][0] dp[i-1][0];dp[i][1] min(dp[i-1][0]1, dp[i-1][1]1);dp[i][2] min(dp[i-1][1], dp[i-1][2]);}else{dp[i][0] dp[i-1][0]1;dp[i][1] min(dp[i-1][1],dp[i-1][0]);dp[i][2] min(dp[i-1][1]1, dp[i-1][2]1);}}return dp[n-1][2];}
};704 ms 114.4 MB
4. LeetCode LCP 20. 快速公交 hard
题目链接 解题
5. LeetCode LCP 21. 追逐游戏 hard
题目链接 解题 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
