当前位置:   article > 正文

LeetCode 318 周赛_ans += sum[i + 1][j + 1] <= k;

ans += sum[i + 1][j + 1] <= k;

2460. 对数组执行操作

给你一个下标从 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]

返回结果数组。

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

提示:

  • 2 <= nums.length <= 2000
  • 0 <= nums[i] <= 1000

示例

输入:nums = [1,2,2,1,1,0]
输出:[1,4,2,0,0,0]
解释:执行以下操作:
- i = 0: nums[0] 和 nums[1] 不相等,跳过这步操作。
- i = 1: nums[1] 和 nums[2] 相等,nums[1] 的值变成原来的 2 倍,nums[2] 的值变成 0 。数组变成 [1,4,0,1,1,0] 。
- i = 2: nums[2] 和 nums[3] 不相等,所以跳过这步操作。
- i = 3: nums[3] 和 nums[4] 相等,nums[3] 的值变成原来的 2 倍,nums[4] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。
- i = 4: nums[4] 和 nums[5] 相等,nums[4] 的值变成原来的 2 倍,nums[5] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。
执行完所有操作后,将 0 全部移动到数组末尾,得到结果数组 [1,4,2,0,0,0] 。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

思路

简单模拟题,使用双指针,可以进行原地删除。

// C++
class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int n = nums.size(), i = 0, j = 0;
        while (i < n) {
            if (nums[i] != 0) {
                if (i + 1 < n && nums[i] == nums[i + 1]) nums[j++] = 2 * nums[i++];
                else nums[j++] = nums[i];
            }
            i++;
        }
        while (j < n) nums[j++] = 0;
        return nums;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

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

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

  • 子数组的长度是 k,且
  • 子数组中的所有元素 各不相同 。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件,返回 0

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

提示:

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 105

示例

输入:nums = [1,5,4,2,9,9,9], k = 3
输出:15
解释:nums 中长度为 3 的子数组是:
- [1,5,4] 满足全部条件,和为 10 。
- [5,4,2] 满足全部条件,和为 11 。
- [4,2,9] 满足全部条件,和为 15 。
- [2,9,9] 不满足全部条件,因为元素 9 出现重复。
- [9,9,9] 不满足全部条件,因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和,所以返回 15 。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

思路

简单滑动窗口,维护窗口内的和即可

// C++
typedef long long LL;
const int N = 1e5 + 10;
class Solution {
public:
    // 用于判重
    bool st[N];
    
    LL maximumSubarraySum(vector<int>& nums, int k) {
        LL ans = 0, sum = 0;
        int n = nums.size();
        for (int i = 0, j = 0; i < n; i++) {
            // 当出现重复时
            while (st[nums[i]]) {
                st[nums[j]] = false;
                sum -= nums[j];
                j++;
            }
            st[nums[i]] = true; // 纳入当前窗口
            sum += nums[i];
            
            // 刚好>k, 则减1
            if (i - j + 1 > k) {
                st[nums[j]] = false;
                sum -= nums[j];
                j++;
            }
            
            if (i - j + 1 == k) ans = max(ans, sum);
        }
        return ans;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

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

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

同时给你两个整数 kcandidates 。我们想根据以下规则恰好雇佣 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 位工人的总代价。

提示:

  • 1 <= costs.length <= 10^5
  • 1 <= costs[i] <= 10^5
  • 1 <= k, candidates <= costs.length

示例

输入:costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
输出:11
解释:我们总共雇佣 3 位工人。总代价一开始为 0 。
- 第一轮雇佣,我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ,有两位工人,我们选择下标更小的一位工人,即第 3 位工人。总代价是 0 + 2 = 2 。
- 第二轮雇佣,我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ,下标为 4 ,总代价是 2 + 2 = 4 。
- 第三轮雇佣,我们从 [17,12,10,7,11,20,8] 中选择,最小代价是 7 ,下标为 3 ,总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。
总雇佣代价是 11 。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

思路

用一个小根堆,维护当前纳入考虑范围的所有candidates,并且维护左右两侧的边界。每次从堆顶弹出一个元素,累加这个元素的cost,并查看其下标,若其下标在[0, l],则左侧边界往右拓展一位;反之若在右侧[r, n - 1],则右侧边界往左拓展一位。

// C++
typedef long long LL;
typedef pair<int, int> PII;
class Solution {
public:
    LL totalCost(vector<int>& costs, int k, int c) {
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        int n = costs.size(), l = c - 1, r = n - c;
        for (int i = 0; i <= l; i++) heap.push({costs[i], i});
        for (int i = n - 1; i >= r && i > l; i--) heap.push({costs[i], i});
        LL ans = 0;
        for (int i = 0; i < k; i++) {
            PII p = heap.top();
            heap.pop();
            ans += p.first;
            int pos = p.second;
            if (pos <= l && l + 1 < r) {
                heap.push({costs[l + 1], l + 1});
                l++;
            } else if (pos >= r && r - 1 > l) {
                heap.push({costs[r - 1], r - 1});
                r--;
            }
        }
        return ans;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

2463. 最小移动总距离

X 轴上有一些机器人和工厂。给你一个整数数组 robot ,其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ,其中 factory[j] = [position_j, limit_j] ,表示第 j 个工厂的位置在 position_j ,且第 j 个工厂最多可以修理 limit_j 个机器人。

每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置

所有机器人一开始都是坏的,他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向,要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时,这个工厂会维修这个机器人,且机器人停止移动。

任何时刻,你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。

请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。

注意:

  • 所有机器人移动速度相同。
  • 如果两个机器人移动方向相同,它们永远不会碰撞。
  • 如果两个机器人迎面相遇,它们也不会碰撞,它们彼此之间会擦肩而过。
  • 如果一个机器人经过了一个已经达到上限的工厂,机器人会当作工厂不存在,继续移动。
  • 机器人从位置 x 到位置 y 的移动距离为 |y - x|

提示:

  • 1 <= robot.length, factory.length <= 100
  • factory[j].length == 2
  • -10^9 <= robot[i], position_j <= 10^9
  • 0 <= limit_j <= robot.length
  • 测试数据保证所有机器人都可以被维修。

示例

输入:robot = [0,4,6], factory = [[2,2],[6,2]]
输出:4
解释:如上图所示:
- 第一个机器人从位置 0 沿着正方向移动,在第一个工厂处维修。
- 第二个机器人从位置 4 沿着负方向移动,在第一个工厂处维修。
- 第三个机器人在位置 6 被第二个工厂维修,它不需要移动。
第一个工厂的维修上限是 2 ,它维修了 2 个机器人。
第二个工厂的维修上限是 2 ,它维修了 1 个机器人。
总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

思路

思路一

坐标离散化+二分+贪心

做虚拟比赛时我的思路是:坐标离散化+二分。

具体来说,就是先把所有机器人的坐标存在一个数组里,所有工厂的坐标存在一个数组里。然后对两个数组从小到大排序。随后从坐标最小的机器人开始枚举,每次决定当前机器人应该往左走还是往右走。

怎么决定呢?从当前机器人的位置,往左,往右,找到距离最近的2个工厂,比较2个工厂到机器人的距离,选择较小的那个工厂。

typedef long long LL;
class Solution {
public:
    
    vector<int> indexR, indexF;
    
    unordered_map<int, int> f; // 工厂下标 - 剩余可修理次数
    
    // x 是机器人的下标
    // 找到左侧第一个可用工厂的位置
    int findLeft(int x) {
        int l = 0, r = indexF.size() - 1;
        while (l < r) {
            int mid = l + r + 1>> 1;
            if (indexF[mid] <= x) l = mid;
            else r = mid - 1;
        }
        if (indexF[l] <= x) return l;
        return -1;
    }
    
    int findRight(int x) {
        int l = 0, r = indexF.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (indexF[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (indexF[l] >= x) return l;
        return -1;
    }
    
    
    LL minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        for (auto& i : robot) indexR.push_back(i);
        for (auto& i : factory) {
            indexF.push_back(i[0]);
            f[i[0]] += i[1]; // 工厂的可修理次数
        }
        // 坐标离散化
        sort(indexR.begin(), indexR.end());
        sort(indexF.begin(), indexF.end());

        // 对每个robot, 找到最近的工厂
        LL ans = 0;
        for (int i = 0; i < indexR.size(); i++) {
            // 往左找, 往右找
            int l = findLeft(indexR[i]), r = findRight(indexR[i]);
            // x是最终决定的工厂
            int x = l != -1 ? l : -1;
            if (x == -1) x = r;
            else if (r != -1) {
                // 左右两侧都有可用工厂时, 优先选择距离更近的
                int dl = abs(indexF[l] - indexR[i]), dr = abs(indexF[r] - indexR[i]);
                if (dl < dr) x = l;
                else if (dl > dr) x = r;
                else x = l; // 选左边的
            }
            // 选好后, 计算距离
            LL d = abs(indexF[x] - indexR[i]);
            ans += d;
            // 将这个工厂的可用次数减去1
            // 若这个工厂剩余可用次数为0, 则从工厂下标数组中将其删除
            if (--f[indexF[x]] == 0) indexF.erase(indexF.begin() + x);
        }
        return ans;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

提交后WA了。来看一组错误数据:

[9,11,99,101]
[[10,1],[7,1],[14,1],[100,1],[96,1],[103,1]]
  • 1
  • 2

根据上面的代码,对这组数据进行模拟。可以发现我们的决策是这样的:

  • 位于9的机器人,往右去位于10的工厂进行修理,移动1
  • 位于11的机器人,往右去位于14的工厂进行修理,移动3
  • 位于99的机器人,往右去位于100的工厂进行修理,移动1
  • 位于101的机器人,往右去位于103的工厂进行修理,移动2

总的移动次数为1 + 3 + 1 + 2 = 7

而实际的最优解为6,其决策是(下面用R表示机器人,F表示工厂)

  • R9去F7,移动2
  • R11去F10,移动1
  • R99去F100,移动1,
  • R101去F103,移动2

总的移动次数是2 + 1 + 1 + 2 = 6

可以看到,我上面的策略是对每个机器人在当前状态下做出最优选择,但这样并不能保证达到最终的全局最优。

我这样尝试通过局部最优去得到全局最优的贪心策略是不可行的。

原因是当前的决策会对后续的决策产生影响,每一次决策之间不是互相独立的

比如R9选择了F10,对于R9来说是最优选择,但这样的决策会使得R11只能选择F14,从而使得R9和R11的总移动次数为1 + 3 = 4;而如果R9稍微牺牲下自己,去选择F7,这样就能使得R11可以选择F10,从而使得R9和R11的总移动次数为2 + 1 = 3,反而更小了。

思路二

中心扩散

接下来我又有了这样的想法:以每个工厂作为中心,分别同时往左右两端进行扩散(对于每个工厂,维护一下其往左右两边扩散的半径,每个工厂,其半径每秒钟增长1)。

对于某个机器人,其一定会在某个时刻被某个工厂扩散出来的半径所覆盖,当某个机器人第一次被某个工厂扩散的半径所覆盖时,这个工厂就是与该机器人距离最近的且可用的工厂。当某个工厂扩散的半径刚好到达某个机器人时,若该工厂还有剩余维修次数,则将该工厂的维修次数减1,且把该机器人标记为已被维修。扩散终将结束,并且那时所有的机器人都会被覆盖掉。每个工厂都会尽可能的维修与自己距离更近的机器人。这样看来好像是一种可行的方法。

但是!有些情况无法被处理。比如某个工厂的可维修次数只有1,并且在某一时刻,恰好有2个机器人被该工厂的半径所覆盖,那么该工厂应该选择维修哪个机器人呢?这个是不太好判断的,因为还需要更多的额外信息。比如上面的样例,F10在第一秒钟时,其扩散出来的区间范围是[9, 11],恰好到达了R9和R11,由于它只有1次可维修次数,此时它应该选择维修R9还是R11呢?此时需要看,如果不维修R9,那么R9被后来的工厂所覆盖的最短距离是多少;以及如果不维修R11,那么R11被后来的工厂所覆盖的最短距离是多少。如果R9被后来的工厂所覆盖的最短距离比R11的更短,那么应该选择不维修R9,维修R11。这个信息的计算可能会产生嵌套。

并且,由于整个坐标的值域很大,[-10^9, 10^9],我们每次对所有工厂扩散1,则一个工厂最多需要扩散 10^9次,这样肯定就超时了。所以该思路最终没有走下去。

思路三

动态规划

很自然的,我们先对机器人和工厂的坐标,从小到大排个序。

随后,能观察到这样一个事实:假设有两个机器人Rx和Ry,设在最优解中,它们最终被送到的工厂分别是Fx和Fy。若两个机器人之间的坐标关系是 Rx <= Ry,那么一定有 Fx <= Fy。

也就是说,排完序后,从左往右的机器人,一定是依次被送到了从左往右的工厂里去维修。也就是说,从左往右遍历每个机器人时,是先将若干个机器人送到了第一个工厂,第一个工厂的维修次数用完后,又将若干个机器人送到第二个工厂,又将若干个机器人送到第三个工厂… (当然,这样描述其实并不准确,甚至是有问题的,但可以近似这样来理解)

先用反证法,证明一下这个结论。

不妨设 Rx < Ry,假设Rx是往左走,到达的Fx,接下来我们考虑Fy的位置,若Fy < Fx(违反上述结论时),如下图

那么Rx移动的距离是b,Ry移动的距离是a + b + c,Rx和Ry总的移动距离是a + 2b + c

此时如果交换一下,让Rx去Fy,让Ry去Fx,那么Rx的移动距离是a + b,Ry的移动距离是b + c,它俩的总移动距离是a + 2b + c,是不变的。

所以,只要存在Rx < Ry,且Fx > Fy的情况,我们总是能够做一下交换,而总的移动距离并不会变得更大。

所以,我们总是能够保证,对于机器人Rx <= Ry,最优解中一定有 Fx <= Fy。即两个机器人之间的坐标的前后关系,和它们最终选择的工厂的坐标的前后关系,是一致的

于是我们就能够按上面所描述的,从左往右处理每个机器人,依次将机器人送到从左往右的工厂里去维修。

i个工厂,一定是维修了前j个机器人的,不可能存在 前i个工厂,维修了[0, k]以及[k + x, j] 这些机器人,中间还有x个机器人没有被维修,这样的情况。

所以我们可以这样设置状态表示:dp[i][j]表示用前i个工厂,维修了前j个机器人时,机器人总的移动距离。

状态转移时,我们考虑第i个工厂。

i个工厂

  • 要么一个机器人都不维修
  • 要么维修了[0, j]中,最右侧连续若干个机器人(一定是维修了最右侧的若干个,而不是跳过最右侧去维修更左侧的机器人),

对于第二种情况,我们假设第i个工厂,维修了k个机器人,只需要枚举一下k的所有可能的取值,计算一下状态转移即可,状态转移的方程是:dp[i][j] = dp[i - 1][j - k] + cost[?],其中的cost[?]表示这k个机器人到第i个工厂的距离之和。

最终的答案当然就是dp[n][m],即使用全部的工厂,维修全部的机器人的距离之和。

typedef long long LL;
const LL INF = 1e13; // 由于此题的数据范围, 机器人最多有100个, 整个坐标值域最大为10^9, 所以将正无穷开为10^13
class Solution {
public:
    LL minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        int m = robot.size(), n = factory.size();
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());
        vector<vector<LL>> dp(n + 1, vector<LL>(m + 1, INF));
        // 状态边界
        for (int i = 0; i <= n; i++) dp[i][0] = 0; // 维修0个机器人时, 距离全都为0
        // 开始转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j]; // 第i个工厂, 1个机器人也不维修时
                LL sum = 0;
                // 枚举第i个工厂能维修的机器人的数量
                for (int k = 1; k <= min(factory[i - 1][1], j); k++) {
                    int idx = j - k; // 此次维修的机器人的坐标, 下标从0开始
                    sum += abs(robot[idx] - factory[i - 1][0]); // 累加距离之和
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - k] + sum); // 状态转移
                }
            }
        }
        return dp[n][m];
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

这道题目,最重要的是要推出,机器人之间的坐标前后关系,与它们选择的工厂的坐标前后关系,是一致的。只有具备这个条件,才能按照上述的思路进行状态的转移。

总结

T1是双指针模拟;T2是滑动窗口;T3是双指针+堆;T4是动态规划

这次周赛是在周日上午,由于前一周拔了牙,当天周日早上去医院拆线,所以这场周赛没有参加。后来做了下虚拟比赛,只做出3题,T4还差点思维。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/732796
推荐阅读
相关标签
  

闽ICP备14008679号