144. 字典序最小的 01 字符串(卡码网周赛第二十六期(23年阿里淘天笔试真题))

题目链接
144. 字典序最小的 01 字符串(卡码网周赛第二十六期(23年阿里淘天笔试真题))

题目描述

小红有一个 01 字符串,她可以进行最多 k 次提作,每次操作可以交换相邻的两个字符,问可以得到的字典序最小的字符串是什么。

输入

第一行包含两个整数,n(1 < n < 10^5)和 k(1 < k < 10^9),表示字符串的长度和可以进行的操作次数。
接下来一行一个长度为 n 的 01 字符串。

输出

输出一个长度为 n 的字符串,表示字典序最小的字符串。

样例1输入

5 2
01010

样例1输出

00101

样例1解释

数据范围 n < 1 0 5 n<10^5 n<105,说明算法的时间复杂度不能超过O(nlogn),即不能使用暴力解法
在这里插入图片描述

样例2输入

5 10
10000

样例2输出

00001

样例2解释

在这里插入图片描述

样例3输入

10 10
1111101100

样例3输出

0110111110

样例3解释

在这里插入图片描述

题解1(C++版本)

// 贪心, 左边的0尽可能往前放
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
char s[N];

int n, k, pos0[N], cnt; // pos0[i]表示从左往右数,第i个字符'0'的下标

int main(){
    scanf("%d%d%s", &n, &k, s + 1);
    int last = 0; // 用来标记第一个字符'1'的下标
    for(int i = 1; i <= n; i++){
        if(s[i] == '0') pos0[++cnt] = i;
        else if(!last){
            last = i;
        }
    }
    if(!last || last >= pos0[cnt]){ // 字符串s中没有字符'1'或者所有的字符'1'在任何一个字符'0'的后面
        printf("%s\n", s+1);
        return 0;
    }
    int i = 1;
    while(i <= cnt && last > pos0[i]) i++; // 由于要求移动的字典序最小,因此,可以过滤掉第一个1前面的字符'0',
    while(k > 0 && i <= cnt && last <= n) {
        int R0 = pos0[i]; // 当前要移动的字符'0'的下标
        int L1 = last; // 当前要移动的字符'1'的下标
        if(R0 - L1 <= k){ // 当前移动(R0 - L1)次后,还可以往下移动,使得最终的字典序更小
            k -= (R0 - L1);
            s[R0] = '1'; s[L1] = '0';
            last++;
            i++;
        }else {
            s[R0] = '1'; s[R0 - k] = '0';
            k = 0;
        }
        while(last <= n && s[last] == '0') last++; // 寻找上一次移动之后的下一个字符'1'的下标
    }
    
    printf("%s\n", s + 1);
    return 0;
}

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-23 09:32:05       104 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-23 09:32:05       115 阅读
  3. 在Django里面运行非项目文件

    2024-07-23 09:32:05       94 阅读
  4. Python语言-面向对象

    2024-07-23 09:32:05       100 阅读

热门阅读

  1. 数学建模--图论与最短路径

    2024-07-23 09:32:05       21 阅读
  2. mariadb安装在服务器(Linux)

    2024-07-23 09:32:05       26 阅读
  3. 银行卡二三四要素核验的多种应用场景

    2024-07-23 09:32:05       29 阅读
  4. 怎么在 Ubuntu 中卸载已经安装的软件

    2024-07-23 09:32:05       26 阅读
  5. ubuntu 源码安装postgis插件

    2024-07-23 09:32:05       29 阅读
  6. SpringCloud-Zuul-03

    2024-07-23 09:32:05       28 阅读
  7. uniapp picker-view 搜索选择框

    2024-07-23 09:32:05       26 阅读
  8. 前端面试题

    2024-07-23 09:32:05       23 阅读