东莞市新冠最新消息,龙岩优化公司,网页制作基础教程我的足球网,一亩地开发多少钱Leetcode Test
2586 统计范围内的元音字符串数(11.7)
给你一个下标从 0 开始的字符串数组 words 和两个整数#xff1a;left 和 right 。
如果字符串以元音字母开头并以元音字母结尾#xff0c;那么该字符串就是一个 元音字符串 #xff0c;其中元音字母是 a、e、i、o、u…Leetcode Test
2586 统计范围内的元音字符串数(11.7)
给你一个下标从 0 开始的字符串数组 words 和两个整数left 和 right 。
如果字符串以元音字母开头并以元音字母结尾那么该字符串就是一个 元音字符串 其中元音字母是 a、e、i、o、u 。
返回 words[i] 是元音字符串的数目其中 i 在闭区间 [left, right] 内。
提示
1 words.length 10001 words[i].length 10words[i] 仅由小写英文字母组成0 left right words.length
【模拟】
bool check(char t){if(ta || te || ti || to || tu){return 1;}return 0;
}int vowelStrings(char** words, int wordsSize, int left, int right) {int cnt0;for(int ileft;iright;i){char t1words[i][0];char t2words[i][strlen(words[i])-1];if(check(t1) check(t2)){cnt;}}return cnt;
}2609 最长平衡子字符串(11.8)
给你一个仅由 0 和 1 组成的二进制字符串 s 。
如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量则认为 s 的这个子字符串是平衡子字符串。请注意空子字符串也视作平衡子字符串。
返回 s 中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。
提示
1 s.length 500 s[i] 1
【模拟 遍历】
int findTheLongestBalancedSubstring(char * s){int nstrlen(s),cnt10,cnt20,cnt0;for(int i0;in;i){//s[i]1if(s[i]1){cnt2;cntfmax(cnt,2*fmin(cnt1,cnt2));}//s[i]0i0初始化上一个是1也初始化else if(i0 || s[i-1]1){cnt11;cnt20;}//s[i]0上一个也是0else{cnt1;}}return cnt;
}2258 逃离火灾(11.9)
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid 它表示一个网格图。每个格子为下面 3 个值之一
0 表示草地。1 表示着火的格子。2 表示一座墙你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) 你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟你可以移动到 相邻 的草地格子。每次你移动 之后 着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数且停留完这段时间后你还能安全到达安全屋。如果无法实现请你返回 -1 。如果不管你在初始位置停留多久你 总是 能到达安全屋请你返回 109 。
注意如果你到达安全屋后火马上到了安全屋这视为你能够安全到达安全屋。
如果两个格子有共同边那么它们为 相邻 格子。
提示
m grid.lengthn grid[i].length2 m, n 3004 m * n 2 * 104grid[i][j] 是 0 1 或者 2 。grid[0][0] grid[m - 1][n - 1] 0
【二分】2258. 逃离火灾 - 力扣LeetCode
class Solution {const int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 返回能否在初始位置停留 t 分钟并安全到达安全屋bool check(vectorvectorint grid, int t) {int m grid.size(), n grid[0].size();vectorvectorint on_fire(m, vectorint(n));vectorpairint, int f;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {on_fire[i][j] true; // 标记着火的位置f.emplace_back(i, j);}}}// 火的 BFSauto spread_fire []() {vectorpairint, int nf;for (auto [i, j]: f) {for (auto [dx, dy]: dirs) { // 枚举上下左右四个方向int x i dx, y j dy;if (0 x x m 0 y y n !on_fire[x][y] grid[x][y] 0) {on_fire[x][y] true; // 标记着火的位置nf.emplace_back(x, y);}}}f move(nf);};while (t-- !f.empty()) { // 如果火无法扩散就提前退出spread_fire(); // 火扩散}if (on_fire[0][0]) {return false; // 起点着火寄}// 人的 BFSvectorvectorint vis(m, vectorint(n));vis[0][0] true;vectorpairint, int q{{0, 0}};while (!q.empty()) {vectorpairint, int nq;for (auto [i, j]: q) {if (on_fire[i][j]) continue; // 人走到这个位置后火也扩散到了这个位置for (auto [dx, dy]: dirs) { // 枚举上下左右四个方向int x i dx, y j dy;if (0 x x m 0 y y n !on_fire[x][y] !vis[x][y] grid[x][y] 0) {if (x m - 1 y n - 1) {return true; // 我们安全了…暂时。}vis[x][y] true; // 避免反复访问同一个位置nq.emplace_back(x, y);}}}q move(nq);spread_fire(); // 火扩散}return false; // 人被火烧到或者没有可以到达安全屋的路}public:int maximumMinutes(vectorvectorint grid) {int m grid.size(), n grid[0].size();// 这里我用开区间二分其它写法也可以int left -1, right m * n 1;while (left 1 right) {int mid (left right) / 2;(check(grid, mid) ? left : right) mid;}return left m * n ? left : 1000000000;}
};2300 咒语和药水的成功对数(11.10)
给你两个正整数数组 spells 和 potions 长度分别为 n 和 m 其中 spells[i] 表示第 i 个咒语的能量强度potions[j] 表示第 j 瓶药水的能量强度。
同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success 那么它们视为一对 成功 的组合。
请你返回一个长度为 n 的整数数组 pairs其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。
提示
n spells.lengthm potions.length1 n, m 1051 spells[i], potions[i] 1051 success 1010
【二分】
/*** Note: The returned array must be malloced, assume caller calls free().*/
int cmp(void *a,void *b){return *(int*)a-*(int*)b;
}int binarysearch(int *a,int low,int high,long long target){int anshigh1; //初始化while(lowhigh){int midlow(high-low)/2;if(a[mid]target){ansmid;highmid-1;}else{lowmid1;}}return ans;
}int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {qsort(potions,potionsSize,sizeof(int),cmp);int *retmalloc(sizeof(int)*spellsSize);for(int i0;ispellsSize;i){long long t(success-1)/spells[i]; //success-1ret[i]potionsSize-binarysearch(potions,0,potionsSize-1,t);}*returnSizespellsSize;return ret;
}765 情侣牵手(11.11)
n 对情侣坐在连续排列的 2n 个座位上想要牵到对方的手。
人和座位由一个整数数组 row 表示其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号第一对是 (0, 1)第二对是 (2, 3)以此类推最后一对是 (2n-2, 2n-1)。
返回 最少交换座位的次数以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人让他们站起来交换座位。
提示:
2n row.length2 n 30n 是偶数0 row[i] 2nrow 中所有元素均无重复
【贪心】
class Solution {
public:int minSwapsCouples(vectorint row) {int len row.size(), ret 0;vectorint idxs(len); //记录情侣位置的表idxsfor (int i 0; i len; i){idxs[row[i]] i; //从值row[i]查坐标i}for (int i 0; i len; i2){int lover_0 row[i];int lover_1 lover_0 ^ 1; //异或取到情侣的另一半if (row[i1] lover_1) continue; //情侣就在身边int idx_lover_1 idxs[lover_1]; //情侣不在身边查找idxs表int bubble row[i1]; //记录错误的情侣也就是别人的swap(row[idx_lover_1], row[i1]); //交换错误的情侣和我的情侣swap(idxs[lover_1], idxs[bubble]); //idxs表也进行交换ret; //交换次数自增1}return ret;}
};715 Range模块(11.12)
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left x right 的实数 x 。
实现 RangeModule 类:
RangeModule() 初始化数据结构的对象。void addRange(int left, int right) 添加 半开区间 [left, right)跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时才返回 true 否则返回 false 。void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。
提示
1 left right 109在单个测试用例中对 addRange 、 queryRange 和 removeRange 的调用总数不超过 104 次
【有序集合】官解715. Range 模块 - 力扣LeetCode
class RangeModule {mapint, int intervals;
public:RangeModule() {}//添加区间跟踪区间内的数。void addRange(int left, int right) {auto it intervals.upper_bound(left);if (it ! intervals.begin()) {auto start prev(it);if (start-second right) {return;}if (start-second left) {left start-first;intervals.erase(start);}}while (it ! intervals.end() it-first right) {right max(right, it-second);it intervals.erase(it);}intervals[left] right;}//在当前正在跟踪区间中的每个实数时返回1bool queryRange(int left, int right) {auto it intervals.upper_bound(left);if (it intervals.begin()) {return false;}it prev(it);return right it-second;}//停止跟踪区间中当前正在跟踪的每个实数void removeRange(int left, int right) {auto it intervals.upper_bound(left);if (it ! intervals.begin()) {auto start prev(it);if (start-second right) {int ri start-second;if (start-first left) {intervals.erase(start);}else {start-second left;}if (right ! ri) {intervals[right] ri;}return;}else if (start-second left) {if (start-first left) {intervals.erase(start);}else {start-second left;}}}while (it ! intervals.end() it-first right) {if (it-second right) {it intervals.erase(it);}else {intervals[right] it-second;intervals.erase(it);break;}}}
};307 区域和检索 - 数组可修改(11.13)
给你一个数组 nums 请你完成两类查询。
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间 包含 的nums元素的 和 其中 left right
实现 NumArray 类
NumArray(int[] nums) 用整数数组 nums 初始化对象void update(int index, int val) 将 nums[index] 的值 更新 为 valint sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间 包含 的nums元素的 和 即nums[left] nums[left 1], ..., nums[right]
提示
1 nums.length 3 * 104-100 nums[i] 1000 index nums.length-100 val 1000 left right nums.length调用 update 和 sumRange 方法次数不大于 3 * 104
【分块处理】
class NumArray {
private:vectorint sum; // sum[i] 表示第 i 个块的元素和int size; // 块的大小vectorint nums;
public:NumArray(vectorint nums) : nums(nums) {int n nums.size();size sqrt(n);sum.resize((n size - 1) / size); // n/size 向上取整for (int i 0; i n; i) {sum[i / size] nums[i];}}void update(int index, int val) {sum[index / size] val - nums[index];nums[index] val;}int sumRange(int left, int right) {int b1 left / size, i1 left % size, b2 right / size, i2 right % size;if (b1 b2) { // 区间 [left, right] 在同一块中return accumulate(nums.begin() b1 * size i1, nums.begin() b1 * size i2 1, 0);}int sum1 accumulate(nums.begin() b1 * size i1, nums.begin() b1 * size size, 0);int sum2 accumulate(nums.begin() b2 * size, nums.begin() b2 * size i2 1, 0);int sum3 accumulate(sum.begin() b1 1, sum.begin() b2, 0);return sum1 sum2 sum3;}
};/*** Your NumArray object will be instantiated and called as such:* NumArray* obj new NumArray(nums);* obj-update(index,val);* int param_2 obj-sumRange(left,right);*/
