1. 保龄球游戏的获胜者
只用看前两个直接暴力判断
class Solution {
public:
int isWinner(vector<int>& player1, vector<int>& player2) {
int score1 = 0;
int score2 = 0;
for(int i=0;i<player1.size();i++){
if(i==0){
score1+=player1[i];
score2+=player2[i];
continue;
}
else if(i==1){
if(player1[i-1]==10) score1+=player1[i]*2;
else score1+=player1[i];
if(player2[i-1]==10) score2+=player2[i]*2;
else score2+=player2[i];
continue;
}
if(player1[i-1]==10||player1[i-2]==10) score1+=player1[i]*2;
else score1+=player1[i];
if(player2[i-1]==10||player2[i-2]==10) score2+=player2[i]*2;
else score2+=player2[i];
}
if(score1==score2) return 0;
else if(score1>score2) return 1;
else return 2;
}
};
2. 找出叠涂元素
行/列数组哈希
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = mat.size();
int n = mat[0].size();
vector<int> row(m);
vector<int> col(n);
map<int,pair<int,int>> hash;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){//记录值对应坐标
int val = mat[i][j];
hash[val] = {i,j};
}
for(int i=0;i<arr.size();i++){
int val = arr[i];
if(++row[hash[val].first]==n) return i;
if(++col[hash[val].second]==m) return i;
}
return 0;
}
};
3. 前往目标的最小代价
4. 字典序最小的美丽字符串
从后往前试探增加，满足条件继续往后走，同时判断是否满足回文
class Solution {
public:
string smallestBeautifulString(string s, int k) {
k += 'a';
int n = s.length(), i = n - 1;
++s[i]; // 从最后一个字母开始
while (i < n) {
if (s[i] == k) { // 超过范围
if (i == 0) return ""; // 无法进位
// 进位
s[i] = 'a';
++s[--i];
} else if (i && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) {
++s[i]; // 如果 s[i] 和前面的字符形成回文串，就继续增加 s[i]
} else {
++i; // 检查 s[i] 是否和后面的字符形成回文串
}
}
return s;
}
};