2259-移除指定数字得到的最大结果

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

给你一个表示某个正整数的字符串 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" 。

提示：

  • 2 <= number.length <= 100
  • number 由数字 '1' 到 '9' 组成
  • digit 是 '1' 到 '9' 中的一个数字
  • digit 在 number 中出现至少一次

方法一：枚举移除下标

思路与算法

我们可以遍历 number 寻找所有可以移除的下标。同时我们用字符串 res 记录可以得到的最大结果。res 初始为空字符串。每当我们找到 number}[i] = \textit{digit 的下标 i，我们构造移除下标 i 后的字符串 tmp。由于移除下标后字符串的长度一定相等，因此字典序的大小关系等于对应数值的大小关系。同时由于空字符串在字典序中小于任何非空字符串，我们只需要令 res 等于 res 与 tmp 的较大值即可。最终，我们返回 res 作为答案。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string removeDigit(string number, char digit) {
        int n = number.size();
        string res;   // 可以得到的最大结果
        for (int i = 0; i < n; ++i) {
            if (number[i] == digit) {
                string tmp = number.substr(0, i);
                tmp.append(number.substr(i + 1, n - i));
                res = max(res, tmp);
            }
        }
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        n = len(number)
        res = ""   # 可以得到的最大结果
        for i in range(n):
            if number[i] == digit:
                tmp = number[:i] + number[i+1:]
                res = max(res, tmp)
        return res

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 为 number 的长度。我们至多需要移除 O(n) 次字符串，每次生成移除后字符串并比较的时间复杂度为 O(n)。

  • 空间复杂度：O(n)，即为生成移除后字符串时辅助字符串的空间开销。

方法二：贪心

提示 1

按照以下策略移除数字可以使得最终结果最大：

  1. 我们从左至右遍历 number，如果遍历到 number}[i] = \textit{digit，且 number}[i] < \textit{number}[i + 1]（如果存在，下同），则我们删除该字符后得到的结果最大；

  2. 如果遍历完成依旧不存在满足上一个条件的下标，则我们删除 digit 出现的最后一个下标，此时删除该字符后得到的结果最大。

提示 1 解释

我们可以以条件 2 得到的数 num 作为基准，并将其与其它可能得到的结果进行比较。

首先，如果移除的位数 i 更靠前，移除后的结果与 num 之差的绝对值一定更高。

其次，我们根据 number}[i] 与 number}[i + 1] 的大小关系分类讨论：

  • number}[i] < \textit{number}[i + 1]，此时删除后的结果一定大于 num，且大于删除后面所有位置得到的结果。

  • number}[i] = \textit{number}[i + 1]，此时删除 number}[i] 与删除 number}[i + 1] 得到的结果相同；

  • number}[i] > \textit{number}[i + 1]，此时删除后的结果一定小于 num，因此我们不能删除该元素。

综上，提示 1 中的方法一定可以使得最终结果最大。

思路与算法

我们可以根据 提示 1 找到最佳的删除下标。

具体地，我们从左至右遍历 为 number，并用 last 记录最近遍历到的可以删除的下标。如果遍历到 number}[i] = \textit{digit时，我们将 last 更新为 i。如果还满足 number}[i] < \textit{number}[i + 1]，则我们返回删除该字符得到的结果作为答案。

如果遍历完成后仍未找到符合上述要求的下标，则我们删除 last 下标对应的字符并返回。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string removeDigit(string number, char digit) {
        int n = number.size();
        int last = -1;   // 最后一个可删除的下标
        for (int i = 0; i < n; ++i) {
            if (number[i] == digit) {
                last = i;
                if (number[i] < number[i+1]){
                    string res = number.substr(0, i);
                res.append(number.substr(i + 1, n - i));
                return res;
                }
            }
        }
        string res = number.substr(0, last);
        res.append(number.substr(last + 1, n - last));
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        n = len(number)
        last = -1   # 最后一个可删除的下标
        for i in range(n):
            if number[i] == digit:
                last = i
                if i < n - 1 and number[i] < number[i+1]:
                    return number[:i] + number[i+1:]
        return number[:last] + number[last+1:]

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 number 的长度。即为寻找最佳移除位置和构造移除后字符串的时间复杂度。

  • 空间复杂度：O(n)，即为生成移除后字符串时辅助字符串的空间开销。

 Comments
On this page
2259-移除指定数字得到的最大结果