第318场周赛

第 318 场周赛 - 力扣（LeetCode）https://leetcode.cn/contest/weekly-contest-318/

今天只更新三道题，嘿嘿。

2460. 对数组执行操作-Easy

题目描述：

给你一个下标从 0 开始的数组 nums ，数组大小为 n ，且由 非负 整数组成。

你需要对数组执行 n - 1 步操作，其中第 i 步操作（从 0 开始计数）要求对 nums 中第 i 个元素执行下述指令：

如果 nums[i] == nums[i + 1] ，则 nums[i] 的值变成原来的 2 倍，nums[i + 1] 的值变成 0 。否则，跳过这步操作。
在执行完 全部 操作后，将所有 0 移动 到数组的 末尾 。

例如，数组 [1,0,2,0,0,1] 将所有 0 移动到末尾后变为 [1,2,1,0,0,0] 。
返回结果数组。

注意 操作应当 依次有序 执行，而不是一次性全部执行。

题目解析：

使用一个数组进行数值存储，只需将不为0的数压入存储即可，然后将数组补0至长度与原数组相同，代码如下：

class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int len = nums.size();
        vector<int> res(len);
        for(int i = 0 ; i-1 ; i++){
            if(nums[i+1]==nums[i]){
                nums[i] *= 2;
                nums[i+1] = 0;
            }
        }
        int pos = 0;
        for(int i = 0 ; i
            if(nums[i]!=0)res[pos++] = nums[i];
        }
        return res;
    }
};

也可以通过原地修改，实现O（1）的空间复杂度，代码如下：

// O（1）的空间
class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int len = nums.size();
        int pos = 0;
        for(int i = 0 ; i-1 ; i++){
            if(nums[i]==0)continue;
            if(nums[i]==nums[i+1]){
                nums[i] *= 2;
                nums[i+1] = 0;
            }
            nums[pos++] = nums[i];
        }
        nums[pos++] = nums[len-1];
        for(int i = pos ; i
            nums[i] = 0;
        }
        return nums;
    }
};

---

2461. 长度为K子数组中的最大和-Medium

题目描述：

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

子数组的长度是 k，且
子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组 是数组中一段连续非空的元素序列。

题目解析：

滑动窗口，使用一个unordered_set来保证窗口内不存在重复元素，如果有重复元素则左边界右移一位，直到窗口内不存在重复元素后，移动右边界，当窗口大小为K时，进行输出值判断，值的更新只需要在原有窗口的值总和上判断右边界和左边界的移动加减对应的数值即可，代码如下：

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        int left = 0;
        int right = 0;
        unordered_set<int> uset;
        long long temp = 0;
        long long res = 0;
        while(right
             if(uset.count(nums[right])==1||right-left==k){
                 uset.erase(nums[left]);
                 temp -= nums[left];
                 left++;
             }
            else{
                uset.emplace(nums[right]);
                temp += nums[right++];
                if(right-left==k)res = max(res,temp);
            }
        }
        return res;
    }
};

执行用时：220 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：92.1 MB, 在所有 C++ 提交中击败了100.00%的用户

---

2462. 雇佣K位工人的总代价

题目描述：

给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。

同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：

总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。
在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 [3,2,7,7,1,2] 。
第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[3,2,7,7,2] 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
一位工人只能被选择一次。
返回雇佣恰好 k 位工人的总代价。

题目解析：

这道题是我最遗憾的，我用了一个小根堆来进行维护左右两边的最小值，然后将每个值对应的坐标从小到大进行hashmap存储，小根堆弹出一个值，查找对应的哈希表中最小坐标在左边界还是右边界进行边界的更新和数据入堆，并将对应坐标从哈希表中删除，这导致了超时，今天看了眼答案，直接两个堆分别维护左右边界内的值，如果左堆顶小于等于右堆顶，弹出即可，不需要进行坐标的判断，因为左边界内的坐标肯定小于右边界的坐标，随后根据边界条件进行后续处理即可。

这里需要注意的是，如果在计算过程中，左边界大于右边界了，这时就不需要进行边界更新了，根据堆顶大小依次弹出即可，代码如下：

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        int len = costs.size();
        int std = k;
        long long ans = 0;
        if(2*candidates
            priority_queue<int,vector<int>,greater<int>> heap_l;
            priority_queue<int,vector<int>,greater<int>> heap_r;
            int left = 0 , right = len-1;
            for( ; left
                heap_l.push(costs[left++]);
            }
            for( ; right>=len-candidates ;){
                heap_r.push(costs[right--]);
            }
            while(k>0&&left<=right){
                if(heap_l.top()<=heap_r.top()){
                    ans += heap_l.top();
                    heap_l.pop();
                    heap_l.push(costs[left++]);
                }
                else{
                    ans += heap_r.top();
                    heap_r.pop();
                    heap_r.push(costs[right--]);
                }
                k--;
            }
            while(k>0){
                if(!heap_l.empty()&&heap_l.top()<=heap_r.top()){
                    ans += heap_l.top();
                    heap_l.pop();
                }
                else{
                    ans += heap_r.top();
                    heap_r.pop();
                }
                k--;
            }
        }
        else{
            sort(costs.begin(),costs.end());
            for(int i = 0 ; i
                ans += costs[i];
            }
        }
        return ans;
    }
};

执行用时：160 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：68.7 MB, 在所有 C++ 提交中击败了100.00%的用户