ACM模式–每日一题练习 —— 删除重复数字后的最大数字

开发调优
,
1

题目

一个长整型数字，消除重复的数字后，得到最大的一个数字。

如 12341 ，消除重复的 1，可得到 1234 或 2341，取最大值 2341。

如 42234，消除 4 得到 4223 或者 2234 ，再消除 2，得到 423 或 234，取最大值 423。

输入

输入一个数字，范围 [1, 100000]

输出

输出经过删除操作后的最大值

示例一

输入

12341

输出

2341

示例二

输入

42234

输出

423

题解

使用单调栈做法，需要去重判断，所以需要定义一个计数、一个是否使用的变量。

使得保留的数最大，那么就需要移除排在前面较小的数（需满足重复条件）。

/*
 * @hw id=2023Q1A lang=java
 *
 * 删除重复数字后的最大数字
 */

// @hw code=start
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        Map<Character, Integer> cnt = new HashMap<>();
        for(char c : s.toCharArray()) {
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);
        }

        List<Character> stack = new ArrayList<>();
        Set<Character> used = new HashSet<>();

        for(char c : s.toCharArray()) {
            if(used.contains(c)) {
                // 如果这个数字已经被使用，那么就直接数量减1，避免入栈，减少计算次数
                cnt.put(c, cnt.get(c) - 1);
            } else {
                // 如果这个数字没有被使用，那么就入栈，入栈前需要检查是否需要移除若干栈顶元素
                while (!stack.isEmpty() && c > stack.get(stack.size() - 1) && cnt.get(stack.get(stack.size() - 1)) > 1) {
                    // 计数大于1，并且小于c，则移除（移除较小数）
                    cnt.put(stack.get(stack.size() - 1), cnt.get(stack.get(stack.size()-1))-1);
                    used.remove(stack.get(stack.size() - 1));
                    stack.remove(stack.size() - 1);
                }
                stack.add(c);
                used.add(c);
            }
        }
        
        // 得到的栈就是最终结果
        StringBuilder sb = new StringBuilder();
        for(Character c : stack) {
            sb.append(c);
        }
        System.out.println(sb.toString());
    }
}
// @hw code=end
1 个赞
2

学习了

1 个赞
3

惯他臭毛病？直接遍历（

1 个赞
4

刷题佬！

1 个赞
5

c++ 实现

/*
 * @hw id=2023Q1A lang=cpp
 *
 * 删除重复数字后的最大数字
 */

// @hw code=start
#include<iostream>
#include<vector>
#include<map>
#include<set>

using namespace std;

int main() {
    string s;
    cin >> s;
    map<char, int> cnt;
    for (char c : s) {
        cnt[c] = cnt.find(c)!=cnt.end() ? cnt[c]+1 : 1;
    }
    set<char> used;
    vector<char> stack;
    for(char c : s) {
        if(used.find(c) != used.end()) {
            cnt[c]--;
        } else {
            while(stack.size()>0 && c > stack.back() && cnt[stack.back()]>1) {
                cnt[stack.back()]--;
                used.erase(stack.back());
                stack.pop_back();
            }
            stack.push_back(c);
            used.insert(c);
        }
    }
    for(char c : stack) {
        cout << c;
    }
    cout << endl;
}
// @hw code=end
6

python实现

#
# @hw id=2023Q1A lang=python3
#
# 删除重复数字后的最大数字
#

# @hw code=start
s = list(input())
cnt = {}

for c in s:
   if c in cnt:
       cnt[c] += 1
   else:
       cnt[c] = 1

used = set()
stack = list()

for c in s:
   if c in used:
       cnt[c] -= 1
   else:
       while len(stack) > 0 and c > stack[-1] and cnt[stack[-1]] > 1:
           oldc = stack.pop()
           cnt[oldc] -= 1
           used.remove(oldc)
       used.add(c)
       stack.append(c)

print("".join(stack))
# @hw code=end
7

From 算法 to 开发调优