E卷-(100分)字符串变换最小字符串

字符串变换最小字符串

问题描述

给定一个由小写字母组成的字符串 ，你可以最多进行一次变换操作。变换操作的规则是：交换字符串中任意两个不同位置的字符。请返回经过变换后能得到的字典序最小的字符串。

输入格式

输入一行，包含一个由小写字母组成的字符串 。

输出格式

输出一行，表示经过最多一次变换后得到的字典序最小的字符串。

样例输入

abcdef

样例输出

abcdef

样例解释

字符串 "abcdef" 已经是字典序最小的，不需要进行任何交换操作。

样例输入

bcdefa

样例输出

acdefb

样例解释

将 'a' 和 'b' 交换位置，可以得到字典序最小的字符串 "acdefb"。

数据范围

• 字符串 仅由小写字母组成。
• ，其中 表示字符串 的长度。

题解

这道题目的核心思想是找到字符串中第一个不在正确位置上的字符，然后将它与后面最小的字符交换。

具体步骤如下：

1. 首先，将输入的字符串 排序，得到一个新的字符串 。这个排序后的字符串就是理论上能得到的字典序最小的字符串。

2. 比较原字符串 和排序后的字符串 。如果它们相同，说明原字符串已经是字典序最小的，直接返回原字符串。

3. 如果不同，那么我们需要进行一次交换操作。从左到右遍历原字符串 ，找到第一个与 中对应位置不同的字符。

4. 在原字符串 中，从右向左找到与这个字符相等的字符（即 中对应位置的字符）。

5. 交换这两个字符的位置。

参考代码

• Python

def solve(s):
    # 将输入字符串转换为列表，方便操作
    s_list = list(s)
    # 对字符串进行排序，得到理论上的最小字符串
    sorted_s = sorted(s)
    
    # 如果原字符串已经是最小的，直接返回
    if s_list == sorted_s:
        return s
    
    # 找到第一个不在正确位置的字符
    for i in range(len(s)):
        if s_list[i] != sorted_s[i]:
            # 从右向左找到要交换的字符
            j = s.rindex(sorted_s[i])
            # 交换字符
            s_list[i], s_list[j] = s_list[j], s_list[i]
            break
    
    # 将列表转换回字符串并返回
    return ''.join(s_list)

# 读取输入
s = input().strip()

# 输出结果
print(solve(s))

• C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LEN 1001

// 比较函数，用于qsort
int cmp(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

// 解决问题的函数
void solve(char *s) {
    int len = strlen(s);
    char sorted_s[MAX_LEN];
    strcpy(sorted_s, s);
    
    // 对sorted_s进行排序
    qsort(sorted_s, len, sizeof(char), cmp);
    
    // 如果原字符串已经是最小的，直接返回
    if (strcmp(s, sorted_s) == 0) {
        return;
    }
    
    // 找到第一个不在正确位置的字符
    for (int i = 0; i < len; i++) {
        if (s[i] != sorted_s[i]) {
            // 从右向左找到要交换的字符
            int j;
            for (j = len - 1; j > i; j--) {
                if (s[j] == sorted_s[i]) {
                    break;
                }
            }
            // 交换字符
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            break;
        }
    }
}

int main() {
    char s[MAX_LEN];
    scanf("%s", s);
    
    solve(s);
    
    printf("%s\n", s);
    return 0;
}

• Javascript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

function solve(s) {
    // 将字符串转换为数组
    let sArr = s.split('');
    // 对字符串进行排序，得到理论上的最小字符串
    let sortedS = [...sArr].sort();
    
    // 如果原字符串已经是最小的，直接返回
    if (sArr.join('') === sortedS.join('')) {
        return s;
    }
    
    // 找到第一个不在正确位置的字符
    for (let i = 0; i < s.length; i++) {
        if (sArr[i] !== sortedS[i]) {
            // 从右向左找到要交换的字符
            let j = sArr.lastIndexOf(sortedS[i]);
            // 交换字符
            [sArr[i], sArr[j]] = [sArr[j], sArr[i]];
            break;
        }
    }
    
    // 将数组转换回字符串并返回
    return sArr.join('');
}

rl.question('', (s) => {
    console.log(solve(s));
    rl.close();
});

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static String solve(String s) {
        // 将字符串转换为字符数组
        char[] sArr = s.toCharArray();
        // 对字符串进行排序，得到理论上的最小字符串
        char[] sortedS = s.toCharArray();
        Arrays.sort(sortedS);
        
        // 如果原字符串已经是最小的，直接返回
        if (Arrays.equals(sArr, sortedS)) {
            return s;
        }
        
        // 找到第一个不在正确位置的字符
        for (int i = 0; i < s.length(); i++) {
            if (sArr[i] != sortedS[i]) {
                // 从右向左找到要交换的字符
                int j = s.lastIndexOf(sortedS[i]);
                // 交换字符
                char temp = sArr[i];
                sArr[i] = sArr[j];
                sArr[j] = temp;
                break;
            }
        }
        
        // 将字符数组转换回字符串并返回
        return new String(sArr);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        System.out.println(solve(s));
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string solve(string s) {
    // 创建一个排序后的字符串
    string sorted_s = s;
    sort(sorted_s.begin(), sorted_s.end());
    
    // 如果原字符串已经是最小的，直接返回
    if (s == sorted_s) {
        return s;
    }
    
    // 找到第一个不在正确位置的字符
    for (int i = 0; i < s.length(); i++) {
        if (s[i] != sorted_s[i]) {
            // 从右向左找到要交换的字符
            int j = s.rfind(sorted_s[i]);
            // 交换字符
            swap(s[i], s[j]);
            break;
        }
    }
    
    return s;
}

int main() {
    string s;
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}