做个网站跳转链接怎么做,服饰网站建设,网页广告怎么拦截,给别人做网站用什么Leetcode Test
2731 移动机器人(10.10)
有一些机器人分布在一条无限长的数轴上#xff0c;他们初始坐标用一个下标从 0 开始的整数数组 nums 表示。当你给机器人下达命令时#xff0c;它们以每秒钟一单位的速度开始移动。
给你一个字符串 s #xff0c;每个字符按顺序分别…Leetcode Test
2731 移动机器人(10.10)
有一些机器人分布在一条无限长的数轴上他们初始坐标用一个下标从 0 开始的整数数组 nums 表示。当你给机器人下达命令时它们以每秒钟一单位的速度开始移动。
给你一个字符串 s 每个字符按顺序分别表示每个机器人移动的方向。L 表示机器人往左或者数轴的负方向移动R 表示机器人往右或者数轴的正方向移动。
当两个机器人相撞时它们开始沿着原本相反的方向移动。
请你返回指令重复执行 d 秒后所有机器人之间两两距离之和。由于答案可能很大请你将答案对 109 7 取余后返回。
注意
对于坐标在 i 和 j 的两个机器人(i,j) 和 (j,i) 视为相同的坐标对。也就是说机器人视为无差别的。当机器人相撞时它们 立即改变 它们的前进方向这个过程不消耗任何时间。当两个机器人在同一时刻占据相同的位置时就会相撞。 例如如果一个机器人位于位置 0 并往右移动另一个机器人位于位置 2 并往左移动下一秒它们都将占据位置 1并改变方向。再下一秒钟后第一个机器人位于位置 0 并往左移动而另一个机器人位于位置 2 并往右移动。例如如果一个机器人位于位置 0 并往右移动另一个机器人位于位置 1 并往左移动下一秒第一个机器人位于位置 0 并往左行驶而另一个机器人位于位置 1 并往右移动。
提示
2 nums.length 105-2 * 109 nums[i] 2 * 1090 d 109nums.length s.length s 只包含 L 和 R 。nums[i] 互不相同。
【排序】相撞等价于机器人互相穿过对方因为我们无法区分机器人。所以可以无视相撞的规则把每个机器人都看成是独立运动的。
const long long mod 1e9 7;static int cmp(const void *a, const void *b) {long long x *(long long *)a;long long y *(long long *)b;return x y ? -1 : 1;//这块如果改成基础的cmp最后一个案例会过不了。。
}int sumDistance(int* nums, int numsSize, char * s, int d) {int n numsSize;long long pos[n];for (int i 0; i n; i) {pos[i] s[i] L ? (long long) nums[i] - d : (long long) nums[i] d;}qsort(pos, n, sizeof(long long), cmp);long long res 0;for (int i 1; i n; i) {res 1ll * (pos[i] - pos[i - 1]) * i % mod * (n - i) % mod;res % mod;}return res;
}2512 奖励最顶尖的K名学生(10.11)
给你两个字符串数组 positive_feedback 和 negative_feedback 分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。
一开始每位学生分数为 0 。每个正面的单词会给学生的分数 加 3 分每个负面的词会给学生的分数 减 1 分。
给你 n 个学生的评语用一个下标从 0 开始的字符串数组 report 和一个下标从 0 开始的整数数组 student_id 表示其中 student_id[i] 表示这名学生的 ID 这名学生的评语是 report[i] 。每名学生的 ID 互不相同。
给你一个整数 k 请你返回按照得分 从高到低 最顶尖的 k 名学生。如果有多名学生分数相同ID 越小排名越前。
提示
1 positive_feedback.length, negative_feedback.length 1041 positive_feedback[i].length, negative_feedback[j].length 100positive_feedback[i] 和 negative_feedback[j] 都只包含小写英文字母。positive_feedback 和 negative_feedback 中不会有相同单词。n report.length student_id.length1 n 104report[i] 只包含小写英文字母和空格 。report[i] 中连续单词之间有单个空格隔开。1 report[i].length 1001 student_id[i] 109student_id[i] 的值 互不相同 。1 k n
【hash】
class Solution {
public:vectorint topStudents(vectorstring positive_feedback, vectorstring negative_feedback, vectorstring report, vectorint student_id, int k) {unordered_mapstd::string, int words;for(const auto word: positive_feedback){words[word]3;}for(const auto word: negative_feedback){words[word]-1;}vectorvectorint A;for(int i0;ireport.size();i){stringstream ss;//stream split words according to spacestring w;int score0;ssreport[i];while(ssw){if(words.count(w)){scorewords[w];}}A.push_back({-score,student_id[i]});}sort(A.begin(),A.end());vectorint top_k;for(int i0;ik;i){top_k.push_back(A[i][1]);}return top_k;}
};2562 找出数组的串联值(10.12)
给你一个下标从 0 开始的整数数组 nums 。
现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。
例如15 和 49 的串联是 1549 。
nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空
如果 nums 中存在不止一个数字分别选中 nums 中的第一个元素和最后一个元素将二者串联得到的值加到 nums 的 串联值 上然后从 nums 中删除第一个和最后一个元素。如果仅存在一个元素则将该元素的值加到 nums 的串联值上然后删除这个元素。
返回执行完所有操作后 nums 的串联值。
提示
1 nums.length 10001 nums[i] 104
【模拟 左右指针】
long long findTheArrayConcVal(int* nums, int numsSize){long long ans 0;char str[16];for (int i 0, j numsSize - 1; i j; i, j--) {if (i ! j) {sprintf(str, %d%d, nums[i], nums[j]);ans atoi(str);} else {ans nums[i];}}return ans;
}1488 避免洪水泛滥(10.13)
你的国家有无数个湖泊所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的那么它就会装满水。如果第 n 个湖泊下雨前是 满的 这个湖泊会发生 洪水 。你的目标是避免任意一个湖泊发生洪水。
给你一个整数数组 rains 其中
rains[i] 0 表示第 i 天时第 rains[i] 个湖泊会下雨。rains[i] 0 表示第 i 天没有湖泊会下雨你可以选择 一个 湖泊并 抽干 这个湖泊的水。
请返回一个数组 ans 满足
ans.length rains.length如果 rains[i] 0 那么ans[i] -1 。如果 rains[i] 0 ans[i] 是你第 i 天选择抽干的湖泊。
如果有多种可行解请返回它们中的 任意一个 。如果没办法阻止洪水请返回一个 空的数组 。
请注意如果你选择抽干一个装满水的湖泊它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊那么将无事发生。
提示
1 rains.length 1050 rains[i] 109
【贪心 二分】
class Solution {
public:vectorint avoidFlood(vectorint rains) {vectorint ans(rains.size(),1);setint st;unordered_mapint,int mp;for(int i0;irains.size();i){if(rains[i]0){ //如果rain【i】0则将i加入有序集合stst.insert(i);}else{ //如果rain【i】0说明第rain【i】湖泊下雨ans[i]-1; //表示不可抽干if(mp.count(rains[i])0){ //如果rain【i】湖泊有积水auto itst.lower_bound(mp[rains[i]]); //二分法找到第一个大于等于rain【i】上一次下雨天数的最小索引itif(itst.end()){return {}; //会洪水}ans[*it]rains[i]; //在第it天抽干rain【i】st.erase(it); //抹除}mp[rains[i]]i; //如果rain【i】没有积水则mp中rain【i】湖泊为i}}return ans;}
};136 只出现一次的数字(10.14)
给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。
提示
1 nums.length 3 * 104-3 * 104 nums[i] 3 * 104除了某个元素只出现一次以外其余每个元素均出现两次。
【异或】
int singleNumber(int* nums, int numsSize){int nnumsSize;int ans0;for(int i0;in;i){ans ^ nums[i]; //异或符合为^}return ans;
}137 只出现一次的数字Ⅱ(10.15)
给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
提示
1 nums.length 3 * 104-231 nums[i] 231 - 1nums 中除某个元素仅出现 一次 外其余每个元素都恰出现 三次
【hash】
class Solution {
public:int singleNumber(vectorint nums) {unordered_mapint,int cnt;for(int num: nums){cnt[num];}int ret0;for(auto [num, count]: cnt){if(count1){retnum;break;}}return ret;}
};【灵神】位运算137. 只出现一次的数字 II - 力扣LeetCode
class Solution {
public:int singleNumber(vectorint nums) {int ans 0;for (int i 0; i 32; i) {int cnt1 0;for (int x: nums) {cnt1 x i 1;}ans | cnt1 % 3 i;}return ans;}
};260 只出现一次的数字Ⅲ(10.16)
给你一个整数数组 nums其中恰好有两个元素只出现一次其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
2 nums.length 3 * 104-231 nums[i] 231 - 1除两个只出现一次的整数外nums 中的其他数字都出现两次
【hash】
class Solution {
public:vectorint singleNumber(vectorint nums) {unordered_mapint,int cnt;for(int x:nums){cnt[x];}vectorint ret;int count0;for(auto [x,c]:cnt){if(count2){break;}if(c1){ret.push_back(x);}}return ret;}
};
