首页 > 试题广场 >

删除字符

[编程题]删除字符

热度指数：1908 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个长度为 $\mathit n$ 的字符串 $\mathit s$ ，你可以删除其中的 $\mathit m$ 个字符，使剩余字符串的字典序最小，输出这个剩余字符串。

输入描述:

第一行输入一个整数，代表接下来有组测试数据。
对于每一组测试数据，第一行输入两个数代表字符串的长度和可以删除的字符数量。
接下来输入长度为字符串。

输出描述:

对于每一组数据，输出一个答案

示例1

输入

2
5 2
abcab
10 4
lkqijxsnny

输出

aab
ijsnny

算法知识视频讲解

pein531

要想字典序小，那么字符串中的字母应该尽可能满足升序。因此只需遵循一个原则，当前字母的ASCII码不能比前面字母的小，如果出现这种情况，就要把前面的字母删除掉，从当前字母重新开始算字符串。最后需要注意，返回的字符串长度应该为n-m。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while(T -- > 0){
            String[] params = br.readLine().split(" ");
            int n = Integer.parseInt(params[0]);
            int m = Integer.parseInt(params[1]);
            String str = br.readLine().trim();
            System.out.println(delete(str.toCharArray(), n, m));
        }
    }
    
    private static String delete(char[] str, int n, int m) {
        Stack<Character> stack = new Stack<>();
        int removeCharNums = 0;
        for(int i = 0; i < n; i++){
            char c = str[i];
            while(!stack.isEmpty() && c < stack.peek() && removeCharNums < m){
                stack.pop();
                removeCharNums += 1;
            }
            stack.push(c);
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty())
            sb.append(stack.pop());
        return sb.reverse().toString().substring(0, n - m);
    }
}

scala版

import scala.io.StdIn
import scala.collection.mutable._

object Main {
    def main(args: Array[String]): Unit = {
        var T = StdIn.readInt
        while(T > 0){
            val params = StdIn.readLine.trim.split(" ")
            val n = params(0).toInt
            val m = params(1).toInt
            var str = StdIn.readLine.trim
            str = deleteChar(n, m, str)
            println(str)
            T -= 1
        }
    }
    
    def deleteChar(n: Int, m: Int, str: String): String = {
        val stack = Stack[Char]()
        var removeCharNum = 0
        val chars = str.toArray
        for(i <- chars.indices){
            val c = chars(i)
            while(!stack.isEmpty && stack.top > c && removeCharNum < m){
                stack.pop
                removeCharNum += 1
            }
            stack.push(c)
        }
        val buffer = ArrayBuffer[Char]()
        while(!stack.isEmpty)
            buffer.append(stack.pop)
        buffer.reverse.mkString.substring(0, n - m)
    }
}

编辑于 2021-08-26 16:04:33 回复(2)

墨羽魂韶

$xbay(x, y为子串)\Longrightarrow\begin{cases} xay & 删掉b \\ xby & 删掉a \\ xbay_1 & 删掉y中的 \end{cases}$

可知要想使一个字符串的字典序变小, 优先消除的应该是最左边的逆序对, 之后删除的应该是最右边的元素

可以用一个栈找到找到删掉逆序对后字典序最小的子序列, 不足m的依次出栈即可

#include <iostream>
using namespace std;
void slove() {
    int n, m; cin >> n >> m;
    string s; cin >> s;
    string res; int cnt = 0;
    for(int i = 0; i < n; ++ i) {
        while(!res.empty() && res.back() > s[i] && cnt < m) {
            res.pop_back();
            cnt ++ ;
        }
        res.push_back(s[i]);
    }
    while(cnt < m) {
        res.pop_back();
        cnt ++;
    }
    cout << res << endl;
}
signed main() {
    int T; cin >> T; while(T--) slove();
}

发表于 2022-03-13 08:24:21 回复(0)

Python

O_n2

用栈结构

def compute(s, n, m):
    stack = []
    remove = []
    for c in s:
        while len(stack) > 0 and c < stack[-1] and len(remove) < m:
            remove.append(stack.pop(-1))
        stack.append(c)
    return ''.join(stack)[:n-m]

编辑于 2021-04-29 16:09:50 回复(0)

找口饭吃

#include <iostream>
#include <string>

using namespace std;
int main(){
    int T, n, m;
    string str;
    cin>>T;
    while(T){
        T--;
        cin >> n >> m;
        cin >> str;
        //寻找逆序，若当前字符大于下一个字符，则将当前字符循环删除，
        //直到当前字符小于下一个字符
        string ss = "";
        int p = 0;
        while(p<n){
            //当前字符小于下一个字符,或者删除字符数量已经到m
            if(ss.empty() || m<=0 || ss.back()<=str[p]){
                ss += str[p];
                p++;
            }
            //当前字符大于下一个字符，需将当前字符删除
            else{
                while(m && !ss.empty() && ss.back()>str[p]){
                    ss.pop_back();
                    m--;
                }
            }
        }
        //最后全升序，没删够数，从后向前删除
        while(m){
            ss.pop_back();
            m--;
        }
        cout << ss <<endl;
    }
    
    return 0;
}

发表于 2022-05-28 16:49:17 回复(0)

不想看论文

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while(T-- > 0){
            int n = cin.nextInt();
            int m = cin.nextInt();
            cin.nextLine();
            String str = cin.nextLine();
            Deque stack = new LinkedList();
            for(int i = 0; i < n; i++){
                while(m > 0 && !stack.isEmpty() && stack.peek() > str.charAt(i)){
                    stack.pop();
                    m--;
                }
                stack.push(str.charAt(i));
            }
            StringBuffer sb = new StringBuffer();
            while(!stack.isEmpty()){
                sb.insert(0, stack.pop());
            }
            System.out.println(sb.toString().substring(0, sb.length() - m));
        }

    }
}

最后 substring(0, sb.length() - m) 的作用是，循环结束后可能 m 还是大于0的，说明后面字符已经没有逆序，则只能从尾巴截掉剩余的m个字符

发表于 2022-03-27 13:41:57 回复(0)

夜晨星

两个易错点。

字典序最小，n个字符删除机会必然用完。可能出现 abccccccc，要用光n次，删掉结尾的c，也可以使字典序变小。

习惯性前面用 `n--;` 会导致 n变化了，后面用n判断字符串长度时就离谱了。。

发表于 2022-03-17 13:52:07 回复(0)

kangjinci

#include <iostream>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        string s;
        cin >> s;
        string ans;
        for (char c : s) {
            while (!ans.empty() && an***ack() > c && m) {
                ans.pop_back();
                --m;
            }
            ans.push_back(c);
        }
        while (m--) {
            ans.pop_back();
        }
        cout << ans << endl;
    }

}

编辑于 2021-11-10 14:13:07 回复(0)

yosoro25252

def cal(s):
    n = len(s)
    arr = [n] * n
    stack = []
    for i in range(n - 1, -1, -1):
        if stack:
            while stack and s[stack[-1]] >= s[i]:
                stack.pop()
            if stack:
                arr[i] = stack[-1]
        stack.append(i)
    return arr

t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    s = input()
    arr = cal(s)
    res = []
    i = 0
    while i < n:
        if m == 0:
            res.append(s[i])
            i += 1
        else:
            d = arr[i] - i
            if d > m:
                res.append(s[i])
                i += 1
            else:
                m -= d
                i = arr[i]
    print(''.join(res))

发表于 2021-08-14 23:44:56 回复(0)

牛客756189174号

#include<bits/stdc++.h>
using namespace std;

int main(){
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        string in;
        cin>>in;
        stack<char> tmp;
        int deleteNumber = 0;
        for (int i = 0;i<in.length();i++){
            char x = in[i];
            while(!tmp.empty() && x<tmp.top() && deleteNumber<m){
                tmp.pop();
                deleteNumber++;
            }
            tmp.push(x);
        }
        string result;
        while(!tmp.empty()){
            result+=tmp.top();
            tmp.pop();
        }
        reverse(result.begin(),result.end());
        cout<<result.substr(0,n-m)<<endl;
    }
    return 0;
}

发表于 2021-08-12 21:42:26 回复(0)