Easy

题目描述

给你一个只包含字符 ‘1’ 和 ‘2’ 的字符串 s。

你可以从 s 中删除任意数量的字符，而不改变剩余字符的顺序。

返回表示偶数的最大可能结果字符串。如果没有这样的字符串，则返回空字符串 “"。

示例 1：

输入：s = "1112"
输出："1112"
解释：字符串已经表示可能的最大偶数，因此不需要删除。

示例 2：

输入：s = "221"
输出："22"
解释：删除 '1' 得到可能的最大偶数，等于 22。

示例 3：

输入：s = "1"
输出：""
解释：无法得到偶数。

约束条件：

  • 1 <= s.length <= 100
  • s 只包含字符 ‘1’ 和 ‘2’

提示：

  • 以 ‘1’ 结尾的数字是奇数
  • 在 s 中找到最后一个 ‘2’。如果没有，返回 “"。否则返回到该 ‘2’（包括）的前缀

解题思路

这道题的关键在于理解偶数的性质：一个数要是偶数，必须以偶数位结尾。

核心思路： 由于字符串只包含 ‘1’ 和 ‘2’，而 ‘1’ 是奇数，‘2’ 是偶数，所以要构成偶数必须以 ‘2’ 结尾。

解法分析：

  1. 贪心策略：要得到最大的偶数，我们需要保留尽可能多的数字，同时确保最后一位是 ‘2’
  2. 关键观察：找到字符串中最后一个 ‘2’ 的位置，然后保留从开头到该位置（包括）的所有字符
  3. 边界情况：如果字符串中没有 ‘2’，那么无法构成偶数，返回空字符串

算法步骤：

  1. 从右往左遍历字符串，找到最后一个 ‘2’ 的位置
  2. 如果找到了，返回从开头到该位置的子字符串
  3. 如果没找到，返回空字符串

这种方法保证了结果是最大的偶数，因为我们保留了尽可能多的高位数字。

时间复杂度为 O(n)，空间复杂度为 O(1)（不考虑输出字符串）。

代码实现

class Solution {
public:
    string largestEven(string s) {
        int lastTwoPos = -1;
        
        // 从右往左找最后一个 '2'
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == '2') {
                lastTwoPos = i;
                break;
            }
        }
        
        // 如果没有找到 '2'，返回空字符串
        if (lastTwoPos == -1) {
            return "";
        }
        
        // 返回从开头到最后一个 '2' 的子字符串
        return s.substr(0, lastTwoPos + 1);
    }
};

class Solution:
    def largestEven(self, s: str) -> str:
        # 从右往左找最后一个 '2'
        last_two_pos = -1
        for i in range(len(s) - 1, -1, -1):
            if s[i] == '2':
                last_two_pos = i
                break
        
        # 如果没有找到 '2'，返回空字符串
        if last_two_pos == -1:
            return ""
        
        # 返回从开头到最后一个 '2' 的子字符串
        return s[:last_two_pos + 1]

public class Solution {
    public string LargestEven(string s) {
        int lastTwoPos = -1;
        
        // 从右往左找最后一个 '2'
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == '2') {
                lastTwoPos = i;
                break;
            }
        }
        
        // 如果没有找到 '2'，返回空字符串
        if (lastTwoPos == -1) {
            return "";
        }
        
        // 返回从开头到最后一个 '2' 的子字符串
        return s.Substring(0, lastTwoPos + 1);
    }
}

var largestEven = function(s) {
    let lastTwoPos = -1;
    
    // 从右往左找最后一个 '2'
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串找到最后一个 ‘2’，最坏情况下遍历整个字符串
空间复杂度O(1)只使用了常数级别的额外空间（不考虑输出字符串的空间）