「知识点:哈希」
枚举过程中,使用 anw
记录时间最长的字符,使用 duration
记录对应的时长。
通过 releaseTimes[i] - releaseTimes[i-1]
即可得出按键 keysPressed[i]
的时长 d[i]
。
通过比较 d[i] 与 duration[i] 大小关系
,以及 keysPressed[i] 与 anw 的字典序关系
,更新 anw
和 duration
即可。
class Solution {
public:
char slowestKey(vector<int>& releaseTimes, string keysPressed) {
char anw;
int duration = -1;
for(int pre = 0, i = 0; i < releaseTimes.size(); i++) {
char c = keysPressed.at(i);
int d = releaseTimes[i] - pre;
if(d > duration || (d == duration && c > anw)) {
anw = c;
duration = d;
}
pre = releaseTimes[i];
}
return anw;
}
};
「知识点:排序」
鉴于此题的数据规模,直接暴力处理每一次查询也能接受。(当然我也没想到更高级的解决方案)
枚举每一次请求,将对应的子数组拷贝一份,记为 sub
。
将 sub
排序,然后检查是否所有的 sub[i] - sub[i-1]
都相等即可。
class Solution {
public:
vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
vector<bool> anw;
for(int i = 0; i < l.size(); i++) {
int L = l[i], R = r[i];
bool flag = true;
vector<int> tmp(nums.begin() + L , nums.begin()+R+1);
sort(tmp.begin(), tmp.end());
for(int j = 1; j < tmp.size() && flag; j++) {
flag = ((tmp[1] - tmp[0]) == (tmp[j]-tmp[j-1]));
}
anw.push_back(flag);
}
return anw;
}
};
「知识点:二分,广度优先遍历」
题目要求,在给定地图上,找出消耗体力最少的可以到达终点的路径。
我们不妨换一个思路,在给定地图和体力消耗上限
的情况下,判断是否存在一条路径可以到达终点
。
那么如何判断呢?根据 heights 和 limit 建立一张图,判断起点和终点是否联通即可(BFS,DFS,并查集等算法均可)。
通过这个思路,我们可以在 [0, 100000] 的取值范围内,枚举体力消耗上限 limit
,并判断是否存在一条消耗体力不超过 limit
的可以到达终点的路径。
其中,存在可达路径的最小的 limit,就是答案。
不难发现,随着 limit 的增大,边只会加入,而不会被删除
。也就是说,如果当体力限制为 limit 时存在可达路径,那么当限制为 limit+1 及更大值时,均存在可达路径。反之,当限制为 limit 时不存在可达路径,那么 limit-1 及更小值均不会存在路径。
针对这种具备单调性的问题,直接使用二分来代替枚举即可~
class Solution {
public:
// BFS 检查是否存在路径可以到达终点
bool check(int limit, vector<vector<int>>&heights) {
queue<pair<int, int>> q;
q.push(make_pair(0,0));
vector<vector<bool>> mark(heights.size(), vector<bool>(heights[0].size(), false));
mark[0][0] = true;
while(q.empty() == false) {
auto f = q.front();
q.pop();
if(f.first == heights.size()-1 && f.second == heights[0].size()-1) {
return true;
}
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1};
for(int i = 0; i < 4; i++) {
int nx = dx[i] + f.first;
int ny = dy[i] + f.second;
if(0 <= nx && nx < heights.size() && 0 <= ny && ny < heights[0].size() && mark[nx][ny] == false) {
// 判断一下,在限制为 limit 时,这条边能不能走
if(abs(heights[nx][ny] - heights[f.first][f.second]) <= limit) {
q.push(make_pair(nx, ny));
mark[nx][ny] = true;
}
}
}
}
return false;
}
int minimumEffortPath(vector<vector<int>>& heights) {
int L = 0, R = 1000000;
// 二分
while(L <= R) {
int mid = (L+R)>>1;
if(check(mid, heights)) {
R = mid-1;
} else {
L = mid+1;
}
}
return L;
}
};
「知识点:BFS,排序」
根据 秩
的定义可以总结出两个规律:
不在同一行、列的相同元素也可能会互相影响
。根据第一个规律,不难想到优先计算较小值的秩
。我们先考虑所有元素都不相等
的情况:
都尚未计算
,说明 x 是其中最小的值
,其秩为 1。其中最大的秩为 rank
,那么 x 秩为 rank+1。因为题目要求秩要尽可能的小。当输入数据中有相同元素的时候呢?
假设所有值小于 x
的元素的秩都已经得到了,现在有 k 个值为 x 的元素
需要处理。
设这些元素为
。
通过上述规则可以得到其对应的秩
。
考虑这样一种情况,此时得到的秩有可能是错的。设输入数据如下图:
设 x = 5,则小于 5 的元素的秩都得到了,如下:
根据上述规则,不难得出:
。
但这不满足同行、列中相同元素的秩相等
的限制。所以要更新其中一部分秩。那要如何更新呢?可以通过构造连通分量的方法解决这个问题。
将
视为点,如果两个元素在同一行、列中则建立一条边
。得到的图如下:
在同一联通分量中的秩,都应该更新为该分量中最大的秩。即
。
class Solution {
public:
vector<int> fa;
vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
vector<int> row(matrix.size(), 0);
vector<int> col(matrix[0].size(), 0);
vector<pair<int, pair<int, int>>> value;
vector<vector<int>> anw(matrix.size(), vector<int>(matrix[0].size(), 0));
for(int i = 0; i < matrix.size(); i++) {
for(int j = 0; j < matrix[0].size(); j++) {
value.push_back(make_pair(matrix[i][j], make_pair(i, j)));
}
}
// 排序,优先计算较小值得秩
sort(value.begin(), value.end(), [](const pair<int, pair<int, int>> &l, const pair<int, pair<int, int>>& r)->bool {
return l.first < r.first;
});
for(int pre = 0, i = 1; i <= value.size(); i++) {
// 寻找连续的值相等的子数组
if(i == value.size() || value[i].first != value[i-1].first) {
vector<pair<int, int>> rank;
// 先计算一遍秩
for(int j = pre; j < i; j++) {
const pair<int, int> &pos = value[j].second;
int tmprank = max(col[pos.second], row[pos.first])+1;
rank.push_back(make_pair(tmprank, j));
}
unordered_map<int, unordered_set<int>> row_set;
unordered_map<int, unordered_set<int>> col_set;
// 优先更新较大值,更新在同一联通分量的秩
sort(rank.begin(), rank.end(), [](const pair<int, int> &l, const pair<int, int> &r) -> bool {
return l.first > r.first;
});
// 构图
for(int j = 0; j < rank.size(); j++) {
const auto &pos = value[rank[j].second].second;
row_set[pos.first].insert(j);
col_set[pos.second].insert(j);
}
vector<bool> mark(rank.size(), false);
// BFS 寻找联通分量
for(int j = 0; j < rank.size(); j++) {
if(mark[j]) {
continue;
}
queue<int> q;
q.push(j);
mark[j] = true;
while(q.empty() == false) {
int f = q.front();
q.pop();
const auto &pos = value[rank[f].second].second;
for(auto next : row_set[pos.first]) {
if(mark[next]) { continue; }
rank[next].first = rank[f].first;
q.push(next);
mark[next] = true;
}
row_set.erase(pos.first);
for(auto next : col_set[pos.second]) {
if(mark[next]) { continue; }
rank[next].first = rank[f].first;
q.push(next);
mark[next] = true;
}
col_set.erase(pos.second);
}
}
for(int j = 0; j < rank.size(); j++) {
const auto &pos = value[rank[j].second].second;
anw[pos.first][pos.second] = rank[j].first;
row[pos.first] = rank[j].first;
col[pos.second] = rank[j].first;
}
pre = i;
} else {
// do nothing
}
}
return anw;
}
};