第343场周赛

929code / 2023-05-03 / 原文

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;
    }
};