作者 | 梁唐
出品 | 公众号:Coder梁(ID:Coder_LT)
大家好,我是梁唐。
今天是周一,我们照惯例来一起做一下昨天的LeetCode周赛。
昨天是LeetCode第334场周赛,由LeetCode自己赞助自己举办……奖品也是LeetCode周边,电脑包是没戏了,能拿个官方扑克也挺好的。
和之前的周赛相比,这一场难度要略低一些,挺适合新人练手的。
摘录一些有意思的评论:
给你一个下标从 0 开始的整数数组 nums
,请你找出一个下标从 0 开始的整数数组 answer
,其中:
answer.length == nums.length
answer[i] = |leftSum[i] - rightSum[i]|
其中:
leftSum[i]
是数组 nums
中下标 i
左侧元素之和。如果不存在对应的元素,leftSum[i] = 0
。rightSum[i]
是数组 nums
中下标 i
右侧元素之和。如果不存在对应的元素,rightSum[i] = 0
。返回数组 answer
。
模拟题,按照题意计算出leftSum
和rightSum
即可。
class Solution {
public:
vector<int> leftRigthDifference(vector<int>& nums) {
int n = nums.size();
int lef[n+1], rig[n+1];
memset(lef, 0, sizeof lef);
memset(rig, 0, sizeof rig);
lef[0] = nums[0];
for (int i = 1; i < n; i++) {
lef[i] = lef[i-1] + nums[i];
}
rig[n-1] = nums[n-1];
for (int i = n-2; i > -1; i--) {
rig[i] = rig[i+1] + nums[i];
}
vector<int> ret;
for (int i = 0; i < n; i++) {
ret.push_back(abs(lef[i] - rig[i]));
}
return ret;
}
};
给你一个下标从 0 开始的字符串 word
,长度为 n
,由从 0
到 9
的数字组成。另给你一个正整数 m
。
word
的 可整除数组 div
是一个长度为 n
的整数数组,并满足:
word[0,...,i]
所表示的 数值 能被 m
整除,div[i] = 1
div[i] = 0
返回 word
的可整除数组。
我们要求出所有的word[:i]
表示的数值对于m
取模之后的情况,这里要用到一个常用的技巧,即取模的可传递性:
所以利用这一点,我们在计算word[:i+1]
时,我们只需要利用word[:i]
的结果进行递推即可。这里有一个小trick,m
的最大范围是
,那么m
的余数最多也能到这个量级。如果m
的余数也是1e9的话,那么再加入一个数字计算下一位的余数时可能会超过int
的范围。
所以我们用来递推的中间变量需要用long long
。
class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
vector<int> ret;
int n = word.length();
long long md = 0;
for (int i = 0; i < n; i++) {
// word[i] - '0',即将字符数字转成int
// 加入一个新的数字,即md * 10再加上末尾数字
md = (md * 10 + word[i] - '0') % m;
ret.push_back(md % m == 0);
}
return ret;
}
};
给你一个下标从 0 开始的整数数组 nums
。
一开始,所有下标都没有被标记。你可以执行以下操作任意次:
i
和 j
,满足 2 * nums[i] <= nums[j]
,标记下标 i
和 j
。请你执行上述操作任意次,返回 nums
中最多可以标记的下标数目。
这题拿到手第一反应是贪心,先把数字排序,之后优先匹配数字小的。但这样连第二个样例都过不去。
[2, 4, 5, 9]
,在贪心策略下会导致2和4匹配,而5不能和9匹配。而2和5匹配可以将4空出来和9匹配,此时能够构成的答案更多。
于是我又想着反过来贪心,从大到小匹配,对于每个大数,尽可能匹配数字大的。还是[2, 4, 5, 9]
,优先从9开始匹配,9最大能匹配4,5能匹配2,这样就能得到答案了。但这么做同样有反例,比如[1, 1, 4, 9]
,9会和4匹配,那么剩下的两个1将无法构成匹配。而显然两个1分别和4和9匹配更优。
所以无论怎样贪心都不能保证没有反例,说明贪心的思路不可行,我们要寻找其他方法。
既然我们正面思考没有头绪,不如尝试反向思考。我们直接计算答案是多少行不通,能不能枚举答案来验证可行性呢?我们想要验证在当前的数组情况下能不能构成k
组匹配,怎么办呢?很简单,如果真的存在,那么一定是前k
小的数和前k
大的数匹配。数组排好序之后,前k
小和前k
大都是确定的,我们直接判断就可以了。对于确定的k
,我们验证可行性的复杂度是
。
那么剩下的就很明显了,我们使用二分法来寻找最大可行的k
即可。
我发现LeetCode挺喜欢出二分答案的,已经遇到过好几次了。其实遇见多了就能开窍了,正面想不出来都可以试试反向思考验证答案。
class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
int l = 0, r = n/2 + 1;
while (l+1 < r) {
int m = (l + r) >> 1;
bool flag = true;
for (int i = 0; i < m; i++) {
if (2 * nums[i] > nums[n-m+i]) {
flag = false;
break;
}
}
if (flag) {
l = m;
}else {
r = m;
}
}
return l * 2;
}
};
给你一个 m x n
的矩阵 grid
,每个元素都为 非负 整数,其中 grid[row][col]
表示可以访问格子 (row, col)
的 最早 时间。也就是说当你访问格子 (row, col)
时,最少已经经过的时间为 grid[row][col]
。
你从 最左上角 出发,出发时刻为 0
,你必须一直移动到上下左右相邻四个格子中的 任意 一个格子(即不能停留在格子上)。每次移动都需要花费 1 单位时间。
请你返回 最早 到达右下角格子的时间,如果你无法到达右下角的格子,请你返回 -1
。
这题拿到手第一反应就是bfs,但也很明显,这么大的数据范围bfs一定会超时。不信邪尝试了一下果不其然……
稍微思考一下可以发现,无解只有一种情况,就是第二个样例当中grid[0][1]
和grid[1][0]
都大于1,此时从左上角出发无处可去。只要有一个格子可以走,那么可以通过反复横跳的方式消磨时间,那么最终一定能将整个网格都走完。
可能有些同学会想到动态规划,然而也不可行,因为每个位置可以重复遍历,存在后效性。
正确的做法是把它当做图论题,每个点能够到达相邻的点,我们可以看做是相邻的边。当我们最早能在x
时刻到达A点之后如果满足B点的时间限制,则可以转移到B点。如果x
时刻小于B点的时限,我们可以在A点和到达A点之前的点上反复横跳消磨时间,直到满足B的时限为止。
但是这里有一个小问题,我们假设到达A点的时间是7,B点的时限是8。那么我们可以直接到达B点,但如果A点的时限是9。A点在横跳一次之后在9时刻回到A点,到达B点最快也要10。即横跳消磨时间时不能改变奇偶性,我们在转移到B时需要考虑到这点。那有没有可能有一个B点相邻的点可以在8时刻到达呢,这样就可以在9时刻到达B点了。
答案还是不可能,因为矩阵里每个点到达的时间的奇偶性都是确定的。反复横跳或者是走弯路都不会改变到达时刻的奇偶性。既然如此,那么我们就可以把它当做图论的最短路来做,使用dijkstra算法,用一个优先队列维护到达每个点的时间。每次都选取最小时间的点开始松弛与它相邻的点,这样就可以保证每个点被访问到的时候都是最优的。如此每个点只会进出队列一次,由于优先队列每次维护优先级需要
的复杂度,那么整体的复杂度就是
。
更多细节参考代码:
class Solution {
public:
int minimumTime(vector<vector<int>>& grid) {
// 定义缩写
typedef pair<int, int> pii;
typedef pair<int, pair<int, int>> piii;
priority_queue<piii> que;
que.push({0, {0, 0}});
// 方向数组
int dr[4][2]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int n = grid.size()-1, m = grid[0].size()-1;
// 判断无解的情况
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
// 记录每个点到达的最小时间
vector<vector<int>> dis(n+3, vector<int>(m+3, -1));
dis[0][0] = 0;
while (!que.empty()) {
piii f = que.top();
que.pop();
// 由于优先队列默认是优先级高的在前,所以要取反,这样就成了距离短的在前了,也可以定义优先队列的优先级,不过稍微麻烦一些,直接取反比较简单
int tt = -f.first;
int xx = f.second.first;
int yy = f.second.second;
for (int i = 0; i < 4; i++) {
int x = xx + dr[i][0];
int y = yy + dr[i][1];
int t = tt + 1;
// 如果越界或者已经访问过了,则跳过
if (x < 0 || x > n || y < 0 || y > m || dis[x][y] >= 0) continue;
// 根据奇偶性计算到达的最小时间
int nxt;
if (t > grid[x][y]) nxt = t;
else nxt = grid[x][y] + (grid[x][y] + t) % 2;
// 记录,入队列
dis[x][y] = nxt;
que.push({-nxt, {x, y}});
}
}
return dis[n][m];
}
};
这里多说一句,同样是图论最短路,但是本题一定要用dijkstra,而不能使用spfa。因为dijkstra算法是O(n\log n) 的复杂度,这里的n 是点的数量。而spfa是O(V) 的复杂度,这里的V 是边的数量。在本题当中边的数量要多余点,因此会导致超时……
辛苦写好了代码却被卡时限了,非常难受……希望大家不要学我偷懒,该用dijkstra的时候就用dijkstra,不要为了省事用spfa……