Easy

题目描述

给你一个仅由数字组成的字符串 s，返回在将 s 中具有相同奇偶性的相邻数字交换 至多一次 后，可以得到的字典序最小的字符串。

如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、以及 2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。

示例 1：

输入：s = "45320"
输出："43520"
解释：s[1] == '5' 和 s[2] == '3' 都是奇数，交换它们可以得到字典序最小的字符串。

示例 2：

输入：s = "001"
输出："001"
解释：无需进行交换，因为 s 已经是字典序最小的。

提示：

  • 2 <= s.length <= 100
  • s 仅由数字组成

解题思路

这道题要求我们通过最多一次交换相邻且具有相同奇偶性的数字，得到字典序最小的字符串。

核心思路：

  1. 贪心策略：为了得到字典序最小的字符串，我们应该尽可能让前面的位置放置更小的数字。
  2. 从左到右遍历：遍历字符串的每个位置 i，检查位置 i 和 i+1 的数字是否具有相同奇偶性。
  3. 交换条件：如果 s[i] > s[i+1] 且它们奇偶性相同，那么交换它们可以让字符串变得更小。
  4. 最多一次交换：由于只能交换一次，找到第一个满足条件的位置就立即交换并返回。

算法步骤：

  • 遍历字符串，对于每个位置 i（0 ≤ i < n-1）
  • 检查 s[i] 和 s[i+1] 是否满足：s[i] > s[i+1] 且奇偶性相同
  • 如果满足条件，交换这两个字符并返回结果
  • 如果遍历完都没有找到可交换的位置，返回原字符串

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

代码实现

class Solution {
public:
    string getSmallestString(string s) {
        int n = s.length();
        for (int i = 0; i < n - 1; i++) {
            int digit1 = s[i] - '0';
            int digit2 = s[i + 1] - '0';
            
            // 检查奇偶性是否相同且第一个数字大于第二个数字
            if ((digit1 % 2 == digit2 % 2) && digit1 > digit2) {
                swap(s[i], s[i + 1]);
                return s;
            }
        }
        return s;
    }
};

class Solution:
    def getSmallestString(self, s: str) -> str:
        s = list(s)
        n = len(s)
        
        for i in range(n - 1):
            digit1 = int(s[i])
            digit2 = int(s[i + 1])
            
            # 检查奇偶性是否相同且第一个数字大于第二个数字
            if (digit1 % 2 == digit2 % 2) and digit1 > digit2:
                s[i], s[i + 1] = s[i + 1], s[i]
                return ''.join(s)
        
        return ''.join(s)

public class Solution {
    public string GetSmallestString(string s) {
        char[] chars = s.ToCharArray();
        int n = chars.Length;
        
        for (int i = 0; i < n - 1; i++) {
            int digit1 = chars[i] - '0';
            int digit2 = chars[i + 1] - '0';
            
            // 检查奇偶性是否相同且第一个数字大于第二个数字
            if ((digit1 % 2 == digit2 % 2) && digit1 > digit2) {
                char temp = chars[i];
                chars[i] = chars[i + 1];
                chars[i + 1] = temp;
                return new string(chars);
            }
        }
        
        return s;
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var getSmallestString = function(s) {
    let arr = s.split('');
    
    for (let i = 0; i < arr.length - 1; i++) {
        let curr = parseInt(arr[i]);
        let next = parseInt(arr[i + 1]);
        
        if (curr % 2 === next % 2 && curr > next) {
            [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
            break;
        }
    }
    
    return arr.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1) 或 O(n)

说明：

  • 时间复杂度：O(n)，其中 n 是字符串的长度，最多需要遍历一次字符串
  • 空间复杂度：对于 C++ 可以原地修改为 O(1)；对于 Python、C#、JavaScript 需要创建字符数组，为 O(n)

相关题目