华为OD E卷（100分）30-字符串变换最小字符串

前言

        工作了十几年，从普通的研发工程师一路成长为研发经理、研发总监。临近40岁，本想辞职后换一个相对稳定的工作环境一直干到老, 没想到离职后三个多月了还没找到工作，愁肠百结。为了让自己有点事情做，也算提高一下自己的编程能力，无聊之余打算用一些大厂的编程题练练手。希望通过这些分享能够帮到一些人，也希望能和看到此文的大神们沟通交流，提升自己，更希望在此期间能够找到一份理想的工作。

题目描述

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

输入

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

•  s是都是小写字符组成
• 1<=s.length<=1000

输出

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

示例 

示例1

输入
abcdef
输出
abcdef

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

示例2

输入
bcdefa
输出
acdefb
说明
a和b进行位置交换，可以得到最小字符串。

解题思路

        因为要找最小字符串，所有后面替换的字符串越靠后越小。

题解

Java实现

package huawei.e100;

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

/**
* @author arnold
* @date 2024年12月19日
* 字符串变换最小字符串
*/
public class T30 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			String str = sc.nextLine();
			String s = run(str);
			System.out.println(s);
		}
		
	}
	
	static String run(String str) {
		// 判断是否是最小字符串
		char[] cs = str.toCharArray();
		Arrays.sort(cs);
		if (new String(cs).equals(str)) {
			return str;
		}
		// 查找最优的字符和位置
		char minchar = Character.MAX_VALUE;
		int changeIndexStart = cs.length-1;
		int changeIndexEnd = 0;
		for (int i = 0; i < cs.length-1 && i <= changeIndexStart; i++) {
			for (int j = i+1; j < cs.length; j++) {
				if(str.charAt(j) < str.charAt(i) && str.charAt(j) <= minchar) {
					minchar = str.charAt(j);
					changeIndexStart = i;
					changeIndexEnd = j;
				}
			}
		}
		// 交换位置
		cs = str.toCharArray();
		cs[changeIndexEnd] = cs[changeIndexStart];
		cs[changeIndexStart] = minchar;
		return new String(cs);
	}

}