LeetCode 2399. 检查相同字母间的距离?
题目链接：
2399. 检查相同字母间的距离 - 力扣（LeetCode）
时间复杂度O(n ^ 2)
class Solution {
public:
bool checkDistances(string s, vector<int>& distance) {
int n = s.size();
bool st[30] = {false};
int ans[30] = {0};
for (int i = 0; i < n; i ++ )
{
if (!st[s[i] - 'a'])//如果s[i]是第一次出现
for (int j = 0; j < n; j ++ )
{
if (s[i] == s[j]) ans[s[i] - 'a'] = j - i - 1;//记录两个s[i]中间有多少个数
st[s[i] - 'a'] = true;//将s[i]定义为被计算过
}
}
for (int i = 0; i < 26; i ++ ) //若s[i]出现过且distance不与ans相同返回false
if (st[i] && distance[i] != ans[i]) return false;
return true;
}
};
LeetCode 2400. 恰好移动 k 步到达某一位置的方法数目
题目链接：
2400. 恰好移动 k 步到达某一位置的方法数目 - 力扣（LeetCode）
时间复杂度(nlogn)
设r为向右走的步数，l 为向左走的步数 m = abs(endPos - startPos)
则由题意可得：r - l = m, r + l = k 即：r = (m + k) / 2
因为每一次确定的r都有唯一的l与之对应，所以总方案数位Cn, r（C是组合数，n是底数）
class Solution {
typedef long long LL;
const int mod = 1e9 + 7;
public:
int qmi(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = (LL)res * a % mod;
a = (LL)a * a % mod;
b >>= 1;
}
return res;
}
int numberOfWays(int s, int e, int k) {
int m = abs(e - s);
int r = m + k >> 1;
if ((m + k) % 2 || k < m) return 0;//若(m + k) % 2 ！= 0即r = (m + k) / 2
//为浮点数则无解，若题目要求的步数k小于他们直接的间距
int res = 1;//求组合数
for (int i = k; i > k - r; i -- ) res = (LL)res * i % mod;
for (int i = 1; i <= r; i ++ ) res = (LL)res * qmi(i, mod - 2) % mod;
return res;
}
};
LeetCode 2401. 最长优雅子数组 ?
题目链接：
2401. 最长优雅子数组 - 力扣（LeetCode）
时间复杂度： O（nlogn）
利用双指针算法，将十进制转化为二进制找出[0, 30]位中1每个位置的1恰好出现一次，记录最大长度即可
class Solution {
public:
int longestNiceSubarray(vector<int>& nums) {
int cnt[40] = {0};
int res = 0;
for (int i = 0, j = 0, tot = 0; i < nums.size(); i ++ )
{//tot表示某个位置1出现的次数大于1的个数, 双指针算法的位置: i在j后面
for (int k = 0; k < 31; k ++ )
if (nums[i] >> k & 1)//若第k位是1
if (++ cnt[k] > 1)//若加上之前的数，第k位出现的1的数目大于1
tot ++ ;//tot 加1
while (tot)//找出当tot == 0时j的位置，即枚举到每个二进制上恰好只有一个1位置
{
for (int k = 0; k < 31; k ++ )
if (nums[j] >> k & 1)
if (-- cnt[k] == 1)//若下标从j到i之间二进制的第k恰好只出现一次
tot -- ;
j ++ ;//j往后移一个直到满足：从下表j 到 i 之间每个二进制上恰好只有一个1位置
}
res = max(res, i - j + 1);//记录长度
}
return res;
}
};
LeetCode 2402. 会议室 III?
题目链接：
2402. 会议室 III - 力扣（LeetCode）
时间复杂度O(nlogn)
1：将会议按照开始时间从小到大排序，依次将会议分配给会议室。
2：定义两个小跟堆，busy和 idle，分别表示忙碌的会议室和空闲的会议室。
3：忙碌的堆由二元组 （结束时间，该会议编号）组成，堆顶为结束时间最近的会议室。
4：空闲的堆由会议室编号组成，每次取出的都是空闲的且编号最小的会议室。
5：遍历会议，对于当前会议 (st,ed)，将所有忙碌会议室的结束时间在 st?之前的会议室全部设置为空闲，并插入到空闲的堆中。
6：如果空闲的堆不为空，则取出会议室编号最小的堆，分配给当前会议，然后插入到忙碌的堆。
7：如果不存在空闲的会议室，则需要取出当前忙碌的堆中结束时间最早的会议室，分配给当前会议，然后插入到忙碌的堆。
如此重复，过程中记录下每个会议室的使用次数。
typedef long long LL;
typedef pair<LL, int> PLI;
#define x first
#define y second
class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
vector<int> cnt(n, 0);//记录使用会议室出现的次数
priority_queue<int, vector<int>, greater<int>> idle;//记录空闲会议室的编号
priority_queue<PLI, vector<PLI>, greater<PLI>> busy;//记录忙碌会议室。
sort(meetings.begin(), meetings.end());
for (int i = 0; i < n; i ++ ) idle.push(i);//开始时所有会议室都是空闲会议室
for (auto &p : meetings)
{
while (busy.size() && busy.top().x <= p[0])//当某个会议室结束，且该会议室结束的时间
{ //小于当前会议开始的时间，则把他压入空闲会议室
idle.push(busy.top().y);
busy.pop();
}
if (idle.size())//若有空闲会议室，分配空闲会议室作为会议室参加
{
int t = idle.top();//找出最小的编号
idle.pop();
busy.push({p[1], t});//该会议在这个空闲会议室t举办
cnt[t] ++ ;//t的使用次数加一
}
else//若没有空闲会议室，即所有会议室都满了
{
auto t = busy.top();//找出最找结束的会议
busy.pop();
cnt[t.y] ++ ;//该会议使用次数加一
busy.push({t.x + p[1] - p[0], t.y});//该会议结束时间 == 上一次会议结束时间t.x +
//会议持续时间 p[1] - p[0]
}
}
int ans = 0;
for (int i = 1; i < n; i++)//找出举办最多会议的房间编号
if (cnt[i] > cnt[ans])
ans = i;
return ans;
}
};
|