【LeetCode】移除指定数字得到的最大结果 Java 题解

2022 年 5 月 10 日
本文字数：1679 字
阅读完需：约 6 分钟

题目描述

给你一个表示某个正整数的字符串 number 和一个字符 digit 。

从 number 中恰好移除一个等于 digit 的字符后，找出并返回按十进制表示最大的结果字符串。生成的测试用例满足 digit 在 number 中出现至少一次。

示例 1：
输入：number = "123", digit = "3"输出："12"解释："123" 中只有一个 '3' ，在移除 '3' 之后，结果为 "12" 。
示例 2：
输入：number = "1231", digit = "1"输出："231"解释：可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。由于 231 > 123 ，返回 "231" 。
示例 3：
输入：number = "551", digit = "5"输出："51"解释：可以从 "551" 中移除第一个或者第二个 '5' 。两种方案的结果都是 "51" 。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/remove-digit-from-number-to-maximize-result著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是字符串处理题目，题目含义简单明了。解决这个题目，我们要对 Java 字符串处理的相关函数熟悉，比如：substring() 的用法。
首先我们可以使用朴素解法，按照题目要求，枚举出每一种去掉 digit 字符的情况，然后比较大小，得到答案。
朴素解法之后，我们对题目有了更深的理解，观察题目的重要条件，从 number 中 恰好移除一个 等于 digit 的字符后，找出并返回按 十进制 表示最大的结果字符串。
十进制是我们最常使用的数值表示方法，可以直接比较。分析例子 2，找到第一个 digit 之后，下一个字符 2 > 1, 得到的数值比较大，我们可以假设 number.charAt(i) > digit && number.charAt(i + 1) > digit, 极为相对较大的数值。使用贪心找较大的值的位置即可。实现代码如下，供参考。

通过代码

朴素解法

class Solution {    public String removeDigit(String number, char digit) {        String ans = "";        int n = number.length();        for (int i = 0; i < n; i++) {            if (number.charAt(i) == digit) {                String temp = "";                String pre = number.substring(0, i);                temp = pre;                if (i + 1 < n) {                    String next = number.substring(i + 1, n);                    temp = pre.concat(next);                }                if (ans.length() < temp.length()) {                    ans = temp;                } else if (ans.length() == temp.length()) {                    int tempLength = ans.length();                    int j = 0;                    while (j < tempLength) {                        if (ans.charAt(j) > temp.charAt(j)) {                            break;                        } else if (ans.charAt(j) < temp.charAt(j)) {                            ans = temp;                            break;                        }                        j++;                    }                                    }
            }        }
        return ans;    }}

复制代码

贪心解法

class Solution {    public String removeDigit(String number, char digit) {        StringBuilder ans = new StringBuilder();        int n = number.length();        int removeDigitIdx = -1;        for (int i = 0; i < n; i++) {            if (number.charAt(i) == digit) {                removeDigitIdx = i;                if (i < n - 1 && number.charAt(i + 1) > digit) {                    break;                }            }        }
        ans.append(number.substring(0, removeDigitIdx));        ans.append(number.substring(removeDigitIdx + 1));
        return ans.toString();    }}