2023.4.30LeetCode第343場周賽

A. 保齡球游戲的獲勝者

思路

根據(jù)題意模擬

代碼

class Solution {
public:
    int get(vector<int>& arr) {
        int res = 0;
        for (int i = 0; i < arr.size(); i ++ ) {
            res += arr[i];
            if (i && arr[i - 1] == 10 || i > 1 && arr[i - 2] == 10)
                res += arr[i];
        }
        return res;
    }

    int isWinner(vector<int>& player1, vector<int>& player2) {
        int a = get(player1);
        int b = get(player2);
        if (a > b) return 1;
        else if (a < b) return 2;
        return 0;
    }
};

B. 找出疊涂元素

思路

使用哈希表記錄每個(gè)數(shù)出現(xiàn)的位置，再用m+n個(gè)集合記錄每一行和每一列被涂滿的格子數(shù)，若某行或某列全部被涂滿則返回答案

代碼

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<unordered_set<int>> row(n), col(m);
        unordered_map<int, pair<int, int>> mp;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ ) {
                mp[mat[i][j]] = {i, j};
            }
        for (int i = 0; i < arr.size(); i ++ ) {
            int x = mp[arr[i]].first, y = mp[arr[i]].second;
            row[x].insert(y);
            col[y].insert(x);
            if (row[x].size() == m || col[y].size() == n)
                return i;
        }
        return -1;
    }
};

C. 前往目標(biāo)的最小代價(jià)

思路

BFS
首先將距離大于兩點(diǎn)的曼哈頓距離的特殊路徑去掉
每個(gè)點(diǎn)考慮經(jīng)過每個(gè)特殊路徑到達(dá)，分成兩段，一段是當(dāng)前點(diǎn)到特殊路徑的起點(diǎn)，使用普通方式，另一段是特殊路徑的起點(diǎn)到終點(diǎn)，使用特殊方式
若能更新最短距離，則加入隊(duì)列繼續(xù)更新其他點(diǎn)
每個(gè)點(diǎn)出隊(duì)時(shí)，都和終點(diǎn)使用普通方式更新最短距離

代碼

class Solution {
public:
    typedef pair<int, int> PII;
    
    int get(PII a, PII b) {
        return abs(a.first - b.first) + abs(a.second - b.second);
    }
    
    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
        vector<vector<int>> a;
        for (auto x : specialRoads) {
            if (abs(x[2] - x[0]) + abs(x[3] - x[1]) > x[4])
                a.push_back(x);
        }
        queue<PII> q;
        map<PII, int> d;
        q.push({start[0], start[1]});
        d[{start[0], start[1]}] = 0;
        PII tar = {target[0], target[1]};
        d[tar] = get(tar, {start[0], start[1]});
        while (q.size()) {
            auto t = q.front();
            q.pop();
            d[tar] = min(d[tar], d[t] + get(tar, t));
            for (auto i : a) {
                int dis = d[t] + get(t, {i[0], i[1]}) + i[4];
                PII ed = {i[2], i[3]};
                if (!d.count(ed) || d[ed] > dis) {
                    d[ed] = dis;
                    q.push(ed);
                }
            }
        }
        
        return d[tar];
    }
};

D. 字典序最小的美麗字符串

思路

每次檢查回文只用考慮前相鄰一位和間隔一位是否相同，即如果不存在長度為2或3的回文串，就不存在長度2以上回文串
要使字典序盡量小，就盡量讓右邊的數(shù)位變大，當(dāng)所有數(shù)位都滿足不是回文串時(shí)直接返回文章來源地址http://www.zghlxwxcb.cn/news/detail-434320.html

代碼

class Solution {
public:
    string smallestBeautifulString(string s, int k) {
        int n = s.size();
        int i = n - 1; //從最右邊開始考慮
        s[i] ++ ;
        while (i < n && i >= 0) {
            if (s[i] == 'a' + k) { //超出最高位
                if (i == 0) return ""; //此時(shí)已經(jīng)是最左
                s[i] = 'a';
                s[ -- i] ++ ; //上一位進(jìn)位
            } else if (i > 0 && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) { ///不滿足回文
                s[i] ++ ;
            } else {
                i ++ ; //檢查右邊是否滿足
            }
        }
        return s;
    }
};

到了這里，關(guān)于LeetCode第343場周賽的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！