$\large\color{orange}{比赛入口:}$$ \color{orange}{LeetCode343} $$ \large\color{orange}{周赛} $
$\large\color{green}{2660. 保龄球游戏的获胜者}$
class Solution {
public:
int get_score(vector<int>& player){
int score = 0;
for(int i = 0; i < player.size(); i ++ ){
bool flag = false;
if(i >= 2) flag = flag || (player[i - 2] == 10);
if(i >= 1) flag = flag || (player[i - 1] == 10);
if(flag) score += player[i] * 2;
else score += player[i];
}
return score;
}
int isWinner(vector<int>& player1, vector<int>& player2) {
int score1 = get_score(player1), score2 = get_score(player2);
if(score1 == score2) return 0;
if(score1 > score2) return 1;
return 2;
}
};
$\large\color{orange}{2661. 找出叠涂元素}$
class Solution {
public:
static const int N = 1e5 + 10;
int row[N], col[N];
typedef pair<int, int> pii;
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
memset(row, 0, sizeof row);
memset(col, 0, sizeof col);
unordered_map<int, pii> mp;
int n = mat.size(), m = mat[0].size();
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
mp[mat[i][j]] = {i, j};
int len = arr.size();
for(int i = 0; i < len; i ++ ){
pii loc = mp[arr[i]];
row[loc.first] ++ , col[loc.second] ++ ;
if(row[loc.first] == m || col[loc.second] == n) return i;
}
return 0;
}
};
$\large\color{orange}{2662. 前往目标的最小代价素}$
class Solution {
public:
typedef pair<int, int> pii;
static const int N = 500;
int graph[N][N];
map<pii, int> mp;
int dist[N];
bool vis[N];
int k;
int get_dis(pii &point1, pii &point2){
return abs(point1.first - point2.first) + abs(point1.second - point2.second);
}
void dijkstra(int s){
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
dist[s] = 0;
for(int i = 1; i < k; i ++ ){
int nx = -1;
for(int j = 1; j < k; j ++ ){
if(!vis[j] && (nx == -1 || dist[nx] > dist[j])) nx = j;
}
vis[nx] = true;
for(int j = 1; j < k; j ++ ){
dist[j] = min(dist[j], dist[nx] + graph[nx][j]);
}
}
}
int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
set<pii> st;
st.insert({start[0], start[1]}), st.insert({target[0], target[1]});
int n = specialRoads.size();
for(int i = 0; i < n; i ++ ){
st.insert({specialRoads[i][0], specialRoads[i][1]});
st.insert({specialRoads[i][2], specialRoads[i][3]});
}
k = 1;
for(set<pii>::iterator it = st.begin(); it != st.end(); it ++ ) mp[*it] = k ++ ;
for(set<pii>::iterator it1 = st.begin(); it1 != st.end(); it1 ++ ){
for(set<pii>::iterator it2 = it1; it2 != st.end(); it2 ++ ){
pii point1 = *it1, point2 = *it2;
graph[mp[point1]][mp[point2]] = get_dis(point1, point2);
graph[mp[point2]][mp[point1]] = get_dis(point1, point2);
}
}
for(int i = 0; i < n; i ++ ){
pii point1 = {specialRoads[i][0], specialRoads[i][1]};
pii point2 = {specialRoads[i][2], specialRoads[i][3]};
int distance = min(get_dis(point1, point2), specialRoads[i][4]);
graph[mp[point1]][mp[point2]] = min(distance, graph[mp[point1]][mp[point2]]);
}
dijkstra(mp[{start[0], start[1]}]);
return dist[mp[{target[0], target[1]}]];
}
};
注:样例存在重复变,且边均是单向的
$\large\color{red}{2663. 字典序最小的美丽字符串}$
class Solution {
public:
string smallestBeautifulString(string s, int k) {
int n = s.size();
int i = n - 1;
s[i] ++ ;
char bound = k + 'a';
while(i < n){
if(s[i] == bound){
s[i] = 'a';
if(i == 0) return "";
s[i - 1] ++ ;
i -- ;
}else if((i >= 1 && s[i] == s[i - 1]) || (i >= 2 && s[i] == s[i - 2])){
s[i] ++ ;
}else i ++ ;
}
return s;
}
};
参考题解: 贪心(Python/Java/C++/Go)