华为OD机试E卷 --字符串变换最小字符串

题目描述

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。 变换规则：交换字符串中任意两个不同位置的字符。

输入描述

一串小写字母组成的字符串s

输出描述

按照要求进行变换得到的最小字符串

用例

输入

abcdef

输出

abcdef

说明 abcdef已经是最小字符串，不需要交换

输入

bcdefa

输出

acdefb

说明 a和b进行位置交换，可以得到最小字符串

备注： s是都是小写字符组成 1<=s.length<=1000

题目解析

遍历字符串：从左到右遍历字符串，找到第一个可以交换的位置。

寻找最小字符：对于每个字符，从当前位置之后的字符中找到最小的字符。

交换字符：如果找到的最小字符比当前字符小，则进行交换。

返回结果：如果进行了交换，返回交换后的字符串；如果没有进行交换，返回原字符串。

JS算法源码

function getMinString(s) {
    let chars = s.split('');
    let n = chars.length;

    for (let i = 0; i < n - 1; i++) {
        let minChar = chars[i];
        let minIndex = i;

        for (let j = i + 1; j < n; j++) {
            if (chars[j] < minChar) {
                minChar = chars[j];
                minIndex = j;
            }
        }

        if (minIndex !== i) {
            [chars[i], chars[minIndex]] = [chars[minIndex], chars[i]];
            return chars.join('');
        }
    }

    return s;
}

// 示例输入
const s = "acb";
console.log(getMinString(s)); // 输出 "abc"

java算法源码

public class Main {
    public static String getMinString(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;

        for (int i = 0; i < n - 1; i++) {
            char minChar = chars[i];
            int minIndex = i;

            for (int j = i + 1; j < n; j++) {
                if (chars[j] < minChar) {
                    minChar = chars[j];
                    minIndex = j;
                }
            }

            if (minIndex != i) {
                char temp = chars[i];
                chars[i] = chars[minIndex];
                chars[minIndex] = temp;
                return new String(chars);
            }
        }

        return s;
    }

    public static void main(String[] args) {
        String s = "acb";
        System.out.println(getMinString(s)); // 输出 "abc"
    }
}

python算法源码

def get_min_string(s):
    chars = list(s)
    n = len(chars)

    for i in range(n - 1):
        min_char = chars[i]
        min_index = i

        for j in range(i + 1, n):
            if chars[j] < min_char:
                min_char = chars[j]
                min_index = j

        if min_index != i:
            chars[i], chars[min_index] = chars[min_index], chars[i]
            return ''.join(chars)

    return s

# 示例输入
s = "acb"
print(get_min_string(s))  # 输出 "abc"

c算法源码

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

char* getMinString(char* s) {
    int n = strlen(s);

    for (int i = 0; i < n - 1; i++) {
        char minChar = s[i];
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (s[j] < minChar) {
                minChar = s[j];
                minIndex = j;
            }
        }

        if (minIndex != i) {
            char temp = s[i];
            s[i] = s[minIndex];
            s[minIndex] = temp;
            return s;
        }
    }

    return s;
}

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

c++算法源码

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

std::string getMinString(std::string s) {
    int n = s.length();

    for (int i = 0; i < n - 1; i++) {
        char minChar = s[i];
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (s[j] < minChar) {
                minChar = s[j];
                minIndex = j;
            }
        }

        if (minIndex != i) {
            std::swap(s[i], s[minIndex]);
            return s;
        }
    }

    return s;
}

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