第284场周赛

6031. 找出数组中的所有 K 近邻下标 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    vector<int> findKDistantIndices(vector<int>& nums, int key, int k) {
        vector<int> idxs;
        for (int i = 0; i < nums.size(); i ++) 
            if (nums[i] == key) 
                idxs.push_back(i);
        vector<int> res;
        for (int i = 0; i < nums.size(); i ++) {
            for (auto idx: idxs) {
                if (abs(i - idx) <= k) {
                    res.push_back(i);
                    break;
                }
            }
        }
        return res;
    }
};

5203. 统计可以提取的工件 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
    typedef pair<int, int> pii;

    bool check(vector<int> &vec, set<pii> &st) {
        for (int i = vec[0]; i <= vec[2]; i++) 
            for (int j = vec[1]; j <= vec[3]; j++)
                if (!st.count(pii(i, j))) return false;
        return true;
    }
public:
    int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
        set<pii> st;
        for (auto &vec : dig) st.insert(pii(vec[0], vec[1]));
        int ans = 0;
        for (auto &vec : artifacts) if (check(vec, st)) ans++;
        return ans;
    }
};

5227. K 次操作后最大化顶端元素 - 力扣（LeetCode） (leetcode-cn.com)

/*
如果 nums.length=1，那么如果 k 是偶数，那么栈里存在nums[0]；如果 k 是奇数，那么栈里一定没有任何元素，返回 -1−1。
否则，栈顶元素可以是：
nums 的前 k−1 个数的最大值；
nums 的第 k+1 个数（如果有，此时出栈前 kk 个数即可）；
注意，nums 的第 k 个数永远不会出现在栈顶。
*/
class Solution {
public:
    int maximumTop(vector<int>& nums, int k) {
        if (nums.size() == 1 && k & 1) return -1;
        int mx = 0;
        for (int i = 0; i < nums.size() && i + 1 < k; i ++) {
            mx = max(mx, nums[i]);
        }
        if (k < nums.size()) {
            mx = max(mx, nums[k]);
        }
        return mx;
    }
};

6032. 得到要求路径的最小带权子图 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:

    typedef pair<int, int> PII;
    typedef pair<long long, int> PLLI;

    long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
        vector<PII> grid[n], fgrid[n];
        for (auto &e: edges) {
            grid[e[0]].emplace_back(e[1], e[2]);
            fgrid[e[1]].emplace_back(e[0], e[2]);
        }
        vector<long long> dist1(n, 1e15), dist2(n, 1e15), dist3(n, 1e15);

        dijkstra(src1, grid, dist1);
        dijkstra(src2, grid, dist2);
        dijkstra(dest, fgrid, dist3);
        long long res = 1e15;

        for (int i = 0; i < n; i ++) {
            res = min(res, dist1[i] + dist2[i] + dist3[i]);
        }
        if (res > 1e12) {
            return -1;
        }
        return res;
    }

    void dijkstra(int s, vector<PII> grid[], vector<long long> &dist) {
        priority_queue<PLLI, vector<PLLI>, greater<PLLI>> q;
        dist[s] = 0;
        q.emplace(0, s);
        while (q.size()) {
            auto [cost, node] = q.top();
            q.pop();
            if (cost > dist[node]) continue;
            for (auto [ne, w]: grid[node]) {
                if (cost + w < dist[ne]) {
                    dist[ne] = cost + w;
                    q.emplace(cost + w, ne);
                }
            }
        }
    }
};