咱们好,我是梁唐。
LeetCode系列原本是周一更新的,但因为昨日恰了个饭,因此推延一天。
LeetCode周赛309由大名鼎鼎的米哈游赞助,米哈游也是近期仅有一个不提供简历直通内推时机的赞助商……
这一场的难度比之前略大一些,许多同学在谈论区反响心态崩了……
很遗憾这一场比赛我没有参与(刚好收到密接短信联系社区去了……),我是赛后补的。但即便是在赛后比较轻松的状况下,依然做得不是很顺畅,也旁边面体现这一场的难度。
好了,咱们闲言少叙,来看题吧。
检查相同字母间的间隔
给你一个下标从 0 开端的字符串 s
,该字符串仅由小写英文字母组成,s
中的每个字母都 刚好 呈现 两次 。另给你一个下标从 0 开端、长度为 26
的的整数数组 distance
。
字母表中的每个字母按从 0
到 25
顺次编号(即,'a' -> 0
, 'b' -> 1
, 'c' -> 2
, … , 'z' -> 25
)。
在一个 匀整 字符串中,第 i
个字母的两次呈现之间的字母数量是 distance[i]
。假如第 i
个字母没有在 s
中呈现,那么 distance[i]
能够 忽略 。
假如 s
是一个 匀整 字符串,回来 true
;不然,回来 false
。
题解
主要的坑点在读题,需求留意假如某个字符串没有呈现过,那么它的间隔通通视为合法。
class Solution {
public:
bool checkDistances(string s, vector<int>& distance) {
map<char, int> mp;
for (int i = 0; i < s.length(); i++) {
char c = s[i];
if (!mp.count(c)) mp[c] = i;
else distance[c-'a'] -= (i - mp[c] - 1);
}
for (int i = 0; i < 26; i++) {
if (distance[i] != 0 && mp.count('a'+i)) return false;
}
return true;
}
};
刚好移动 k 步到达某一方位的办法数目
给你两个 正 整数 startPos
和 endPos
。最初,你站在 无限 数轴上方位 startPos
处。在一步移动中,你能够向左或许向右移动一个方位。
给你一个正整数 k
,回来从 startPos
动身、刚好 移动 k
步并到达 endPos
的 不同 办法数目。因为答案可能会很大,回来对 109 + 7
取余 的成果。
假如所履行移动的顺序不完全相同,则以为两种办法不同。
留意:数轴包含负整数。
题解
表面上看很简单想到查找或许是动态规划,但实际上这是一道数学题。
因为咱们只需求考虑可行解的数量,咱们能够强行规则左边的点是起点,右边的点是终点。加上咱们 知道了一共需求的步数k
,所以咱们能够算出向左、向右移动的步数。到这里会发现这其实是一个组合问题,咱们假定向左移动lef
,向右移动rig
。
那么应该满意lef + rig = k,start + rig - lef = end
。这是一个很简单的二元一次方程,求解即可。别的还需求留意,rig和lef
都是非负整数。假如算出来是负数或许不为整数,阐明无解。
求出了lef
和rig
之后,剩余的便是一个组合问题,咱们要求的答案便是CkrigC_k^{rig}。
这里有一个问题,因为答案可能很大,所以咱们需求在计算的进程傍边取模。但是组合数的运算会用到除法,但对于取模运算,除法不满意结合律,即a mod p∗b mod p=ab mod pa \bmod p * b \bmod p = ab \bmod p,但是没有amod pb mod p≠ab mod pa \mod p \div b \bmod p \neq \frac a b \bmod p。
要处理这个问题有两种办法,第一种办法是经过Cij=Ci−1j+Ci−1j−1C_i^j = C_{i-1}^j + C_{i-1}^{j-1}来推算,第二种办法是求逆元。咱们要求ab mod p\frac a b \bmod p的成果,能够转化成乘上bb关于aa和pp的逆元。
这两种办法都能够,我个人用的是逆元法。关于逆元的原理以及计算办法,这里不做过多介绍了,咱们感兴趣能够查阅相关资料。
附上代码:
class Solution {
public:
typedef long long lint;
void Exgcd(lint a,lint b,lint &x,lint &y){
if(!b) x=1,y=0;
else Exgcd(b,a%b,y,x), y-=a/b*x;
}
int inverse(lint a, lint p){
lint x, y;
Exgcd (a,p,x,y);
x = (x%p+p)%p;
return x;
}
int numberOfWays(int st, int ed, int k) {
int Mod = 1e9 + 7;
int start = min(st, ed);
int end = max(st, ed);
int rig = end - start;
int lef = k - rig;
if (lef < 0 || lef % 2) return 0;
rig += lef / 2;
lint ret = 1;
for (int i = 0; i < rig; i++) {
ret = ret * (k - i) % Mod;
ret = ret * inverse(i+1, Mod) % Mod;
}
return ret;
}
};
最长高雅子数组
给你一个由 正 整数组成的数组 nums
。
假如 nums
的子数组中坐落 不同 方位的每对元素按位 **与(AND)**运算的成果等于 0
,则称该子数组为 高雅 子数组。
回来 最长 的高雅子数组的长度。
子数组 是数组中的一个 接连 部分。
**留意:**长度为 1
的子数组一直视作高雅子数组。
题解
这题题意里藏着坑,主要是子数组而非子序列,这两者的意思完全不同。子序列能够不接连,但子数组必须接连。
咱们很简单发现,假定咱们找到了一个完美子数组,那么这个子数组内的恣意两个数的与值为0。转化成二进制,即这若干个数的每一个二进制位最多只要一个1。
有了这个约束条件之后很简单想到two pointers算法,咱们维护一段区间内一切二进制位1的个数。假如新增一个数之后会导致某一位的个数大于1,那么从左边进行弹出操作,直到每一个二进制位最多只要一个1为止。
class Solution {
public:
// 将整数转化成二进制表明
vector<int> to_bit(int x) {
vector<int> ret(33, 0);
for (int i = 0; i < 32; i++) {
if (x & (1 << i)) ret[i] = 1;
}
return ret;
}
int longestNiceSubarray(vector<int>& nums) {
int ret = 1;
int l = 0, st = nums[0];
int n = nums.size();
// 寄存当时区间内二进制1的数量
vector<int> bits = to_bit(nums[0]);
for (int r = 1; r < n; r++) {
vector<int> cur = to_bit(nums[r]);
// 符号是否存在某一位的1的数量大于1
bool flag = false;
for (int i = 0; i < 32; i++) {
bits[i] += cur[i];
if (bits[i] > 1) flag = true;
}
while (flag) {
cur = to_bit(nums[l]);
flag = false;
for (int i = 0; i < 32; i++) {
bits[i] -= cur[i];
if (bits[i] > 1) flag = true;
}
l++;
}
ret = max(ret, r - l + 1);
}
return ret;
}
};
会议室 III
给你一个整数 n
,共有编号从 0
到 n - 1
的 n
个会议室。
给你一个二维整数数组 meetings
,其中 meetings[i] = [starti, endi]
表明一场会议将会在 半闭 时刻区间 [starti, endi)
举办。一切 starti
的值 互不相同 。
会议将会按以下方式分配给会议室:
- 每场会议都会在未占用且编号 最小 的会议室举办。
- 假如没有可用的会议室,会议将会延期,直到存在闲暇的会议室。延期会议的持续时刻和原会议持续时刻 相同 。
- 当会议室处于未占用状况时,将会优先提供给原 开端 时刻更早的会议。
回来举办最屡次会议的房间 编号 。假如存在多个房间满意此条件,则回来编号 最小 的房间。
半闭区间 [a, b)
是 a
和 b
之间的区间,包含 a
但 不包含 b
。
题解
模拟题,因为会议开端的时刻各不相同,咱们能够对会议进行排序,从最早开端的会议开端组织。
对于每一个会议,咱们要找到最早空出来的会议室,假如有多个空的,咱们挑选序号最小的。观察一下数据规模,会议最多是1e5个,会议室最多有100个。对于每个会议咱们需求遍历一次一切的会议室。那么总的复杂度便是1e7,在可接受的规模内。
当然假如想要优化也能够运用线段树这样的数据结构,能够把会议室的查询降低到logN。但我个人感觉含义不大,咱们假如感兴趣能够看看大佬的博客。
要留意会议延续的时刻可能会很长,超过int的规模,所以要用int64
。
class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
typedef long long lint;
vector<lint> mst(n, 0), cnt(n, 0);
const lint MAXI = 0x3f3f3f3f3f3f3f3f;
sort(meetings.begin(), meetings.end());
for (auto &vt: meetings) {
lint sta = vt[0], end = vt[1];
int choose = -1;
lint mini = MAXI;
bool not_exceed = false;
for (int i = 0; i < n; i++) {
if (mst[i] <= sta) {
choose = i;
not_exceed = true;
break;
}
if (mst[i] < mini) {
mini = mst[i];
choose = i;
}
}
if (not_exceed) {
mst[choose] = end;
}else {
mst[choose] += end - sta;
}
cnt[choose] ++;
}
int mxi = -1, ret = -1;
for (int i = 0; i < n; i++) {
if (cnt[i] > mxi) {
mxi = cnt[i];
ret = i;
}
}
return ret;
}
};