自学内容网 自学内容网

力扣周赛:力扣第407场周赛

力扣第407场周赛:将 1 移动到末尾的最大操作次数、使数组等于目标数组所需的最少操作次数,涉及思维、单调栈、分类讨论等知识点。

T3-将 1 移动到末尾的最大操作次数

题目描述

给你一个 二进制字符串 s s s

你可以对这个字符串执行任意次下述操作:

  • 选择字符串中的任一下标 i i i i + 1 < s . l e n g t h i + 1 < s.length i+1<s.length ),该下标满足 s [ i ] = = 1 且 s [ i + 1 ] = = 0 s[i] == 1 且 s[i + 1] == 0 s[i]==1s[i+1]==0
  • 将字符 s [ i ] s[i] s[i] 向右移直到它到达字符串的末端或另一个 1 1 1

例如,对于 s s s = “010010”,如果我们选择 i = 1 i = 1 i=1,结果字符串将会是 s s s = “000110”。

返回你能执行的最大操作次数。

数据范围
  • 1 < = s . l e n g t h < = 1 0 5 1 <= s.length <= 10^5 1<=s.length<=105
  • s [ i ] s[i] s[i] 0 0 0 1 1 1
解题思路

考虑如下移动方案

  1. 移动第 1 1 1 1 1 1,操作次数合计为 1 1 1
  2. 移动第 2 2 2 1 1 1,然后又可以移动第 1 1 1 1 1 1,操作次数合计为 2 2 2
  3. 移动第 3 3 3 1 1 1,然后又可以移动第 2 2 2 1 1 1,然后又可以移动第 1 1 1 1 1 1,操作次数合计为 3 3 3
  4. 以此类推。

注意,并非每个 1 1 1 都可以移动。

代码实现
int maxOperations(string s) {
    int n = s.size(), res = 0, r = n - 1, c1 = 0;
    for (int i = 0; i < r; i++) {
        if (s[i] == '1') {
            // 记录当前1的个数
            c1++;
            // 1的后面如果是0,则现在可以移动
            if (s[i + 1] == '0')res += c1;
        }
    }
    return res;
}

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( 1 ) O(1) O(1)

T4-使数组等于目标数组所需的最少操作次数

题目描述

给你两个长度相同的正整数数组 n u m s nums nums t a r g e t target target

在一次操作中,你可以选择 n u m s nums nums 的任何子数组,并将该子数组内的每个元素的值增加或减少 1。

返回使 n u m s nums nums 数组变为 t a r g e t target target 数组所需的最少操作次数。

数据范围
  • 1 < = n u m s . l e n g t h = = t a r g e t . l e n g t h < = 1 0 5 1 <= nums.length == target.length <= 10^5 1<=nums.length==target.length<=105
  • 1 < = n u m s [ i ] , t a r g e t [ i ] < = 1 0 8 1 <= nums[i], target[i] <= 10^8 1<=nums[i],target[i]<=108
解题思路

v [ i ] = n u m [ i ] − t a r g e t [ i ] v[i]=num[i]-target[i] v[i]=num[i]target[i],要使得 n u m s nums nums 变为 t a r g e t target target,等价于使得 v [ i ] v[i] v[i] 全为 0 0 0

v [ i ] v[i] v[i] 由若干如下数段组成:连续正数段、连续负数段、连续 0 0 0 段。

注意,数段需满足与数段相邻的数的符号与数段不同, 0 0 0 既不是正数也不是负数。举个例子,若连续正数段 a a a b b b 相邻,则 a a a b b b 应视为一个连续正数段。

对于每个数段,单独处理。既然数段之间互不影响,则可将连续负数段转为连续正数段处理,又由于连续 0 0 0 段已满足题目要求,故不处理。所以,只需要处理连续正数段即可。

连续且相等的若干个数可视作同一个数,视作同一个数不影响操作次数。

准备单调栈 s k sk sk,对于一个连续正数段 a a a,考虑将 a i a_i ai 入栈:

  1. 若栈为空或者 a i > s k . t o p a_i>sk.top ai>sk.top ,则直接入栈。
  2. 否则,若 a i = s k . t o p a_i=sk.top ai=sk.top,可视作同一个数, a i a_i ai 不入栈,忽略。
  3. 否则,令 x = s k . t o p x=sk.top x=sk.top,栈顶元素出栈
    • 若栈为空,则操作 x − a i x-a_i xai 次,使得 x x x 变成 a i a_i ai a i a_i ai 入栈。 x x x a i a_i ai 现在被视作同一个数,仅让 a i a_i ai 留在栈中即可,后续不用考虑 x x x
    • 若栈不为空,则比较 s k . t o p sk.top sk.top a i a_i ai
      • s k . t o p > a i sk.top>a_i sk.topai,则操作 x − s k . t o p x-sk.top xsk.top 次,将 x x x 变成 s k . t o p sk.top sk.top, 回到步骤 1 1 1
      • 否则,操作 x − a i x-a_i xai 次,将 x x x 变成 a i a_i ai,若 a i ! = s k . t o p a_i!=sk.top ai!=sk.top 则入栈,否则忽略。
代码实现
long long minimumOperations(vector<int> &nums, vector<int> &target) {
    typedef long long ll;
    int n = nums.size();
    auto &v = nums;
    for (int i = 0; i < n; i++)v[i] -= target[i];
    // 逐一处理每段
    int l = 0, r, sk[n], tp;
    ll res = 0;
    while (l < n) {
        // 重置栈指针
        tp = -1;
        // 找非零段
        while (l < n && !v[l])l++;
        if ((r = l) >= n)break;
        // 处理非零段
        for (int tv; r < n && v[r] && (v[l] ^ v[r]) >= 0; r++) {
            tv = abs(v[r]);
            while (tp != -1 && sk[tp] > tv) {
                int x = sk[tp--];
                if (tp == -1 || sk[tp] < tv)res += x - tv;
                else res += x - sk[tp];
            }
            // 待入栈元素与栈顶元素相同时无需入栈
            if (tp == -1 || sk[tp] != v[r]) sk[++tp] = tv;
        }
        // 处理栈中剩余元素
        while (tp != -1) {
            int x = sk[tp--];
            res += tp == -1 ? x : x - sk[tp];
        }
        // 换下一个区间
        l = r;
    }
    return res;
}

时间复杂度: O ( n ) O(n) O(n),每个元素最多入栈 1 1 1 次、出栈 1 1 1 次。

空间复杂度: O ( n ) O(n) O(n)

END

文章文档:公众号 字节幺零二四 回复关键字可获取本文文档。

题目来源:力扣第407场双周赛

文章声明:题目来源 力扣 平台,如有侵权,请联系删除!


原文地址:https://blog.csdn.net/qq_53469830/article/details/140592490

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!