2025-02-28：交换后字典序最小的字符串。用go语言，给定一个只包含数字的字符串 s，允许你最多交换一次相邻且奇偶性相同的数字，目标是返回字典序最小的字符串。

在这种情况下，具有相同奇偶性的数字包括所有偶数（如 0, 2, 4, 6, 8）和所有奇数（如 1, 3, 5, 7, 9）。也就是说，5 和 9、以及 2 和 4 都属于相同的奇偶性分类，而 6 和 9 则不同。

2 <= s.length <= 100。

s 仅由数字组成。

输入： s = “45320”。

输出： “43520”。

解释：

s[1] == ‘5’ 和 s[2] == ‘3’ 都具有相同的奇偶性，交换它们可以得到字典序最小的字符串。

答案2025-02-28：

chatgpt

题目来自leetcode3216。

大体步骤如下：

1.将输入的字符串 “45320” 转换为一个字符数组 r，方便后续操作。

2.在 getSmallestString 函数中，通过遍历字符数组 r，找到第一对相邻且奇偶性相同的字符。

3.如果找到了这样的一对字符（r[i] 和 r[i+1]），则交换这两个字符，使得第 i 位的数字更小（字典序更小），即得到字典序最小的字符串。

4.返回交换后的字符数组 r 转换为字符串后的结果。

总的时间复杂度分析：

• 遍历字符数组 r 的时间复杂度为 O(n)，其中 n 为字符串的长度。

• 所以整体的时间复杂度为 O(n)。

总的额外空间复杂度分析：

• 除了函数参数和返回值占用的空间外，在 getSmallestString 函数中只使用了常数级别的额外空间（变量r，i），不随输入规模增长。

• 所以整体的额外空间复杂度为 O(1)。

Go完整代码如下：

package main

import (
	"fmt"
)

func getSmallestString(s string) string {
	r := []rune(s)

	for i := 0; i+1 < len(r); i++ {
		if r[i] > r[i+1] && r[i]%2 == r[i+1]%2 {
			r[i], r[i+1] = r[i+1], r[i]
			break
		}
	}
	return string(r)
}

func main() {
	s := "45320"
	result := getSmallestString(s)
	fmt.Println(result)
}

Rust完整代码如下：

fn get_smallest_string(s: &str) -> String {
    let mut chars: Vec<char> = s.chars().collect();

    for i in 0..(chars.len() - 1) {
        // 检查当前字符与下一个字符
        if chars[i] > chars[i + 1] && (chars[i] as u32) % 2 == (chars[i + 1] as u32) % 2 {
            chars.swap(i, i + 1); // 交换
            break; // 交换后退出循环
        }
    }

    chars.iter().collect() // 将 Vec<char> 转回 String
}

fn main() {
    let s = "45320";
    let result = get_smallest_string(s);
    println!("{}", result);
}

Python完整代码如下：

# -*-coding:utf-8-*-

def get_smallest_string(s: str) -> str:
    r = list(s)  # 将字符串转为列表以便修改

    for i in range(len(r) - 1):
        # 检查当前字符与下一个字符
        if r[i] > r[i + 1] and (ord(r[i]) % 2) == (ord(r[i + 1]) % 2):
            r[i], r[i + 1] = r[i + 1], r[i]  # 交换
            break  # 交换后退出循环

    return ''.join(r)  # 将列表转回字符串
if __name__ == "__main__":
    s = "45320"
    result = get_smallest_string(s)
    print(result)