【算法题】字符串变换最小字符串

  • A+
所属分类:编程茶楼


共计 1306 个字符,预计需要花费 4 分钟才能阅读完成。

import java.util.Scanner;

/**
 * 标题:字符串变换最小字符串 | 时间限制:1秒 | 内存限制:262144K | 语言限制:不限
 * 给定一个字符串s,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序进行比较)。
 * 变换规则:交换字符串中任意两个不同位置的字符。
 * 输入描述:
 * 一串小写字母组成的字符串s
 * 输出描述:
 * 按照要求进行变换得到的最小字符串
 * 示例1
 * 输入
 * abcdef
 * 输出
 * abcdef
 * 说明
 * abcdef已经是最小字符串,不需要交换
 * 示例2
 * 输入
 * bcdefa
 * 输出
 * acdefb
 * 说明
 * a和b进行位置交换,可以等到最小字符串
 * 备注:
 * s是都是小写字符组成
 * 1<=s.length<=1000
 */
public class M_N_T_26 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();

        char[] chars = line.toCharArray();

        char ch = chars[chars.length - 1];
        int index = chars.length - 1;

        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] < ch) {
                ch = chars[i];
                index = i;
            }
        }

        for (int i = 0; i < chars.length; i++) {
            if (ch < chars[i] && index > i) {
                chars[index] = chars[i];
                chars[i] = ch;
                break;
            }
        }

        for (int i = 0; i < chars.length; i++) {
            if (i == chars.length - 1) {
                System.out.println(chars[i]);
                break;
            }
            System.out.print(chars[i]);
        }

    }
}

考试遇到,挂了,死因找到了

import java.util.Scanner;

public class HW_OD_02 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String line = scanner.nextLine();
        char[] chars = line.toCharArray();

        for (int i = 0; i < chars.length; i++) {

            int index = -1;
            char temp_char = chars[i];
            // 应该从后面向前面查找,把倒数第一个最小的与前面替换。才能保证最小(死因找到了!!!!)
            for (int j = chars.length - 1; j > i; j--) {

                if (chars[j] < temp_char) {
                    index = j;
                    temp_char = chars[j];
                }

            }

            if (index != -1) {
                chars[index] = chars[i];
                chars[i] = temp_char;
                break;
            }
        }

        for (char aChar : chars) {
            System.out.print(aChar);
        }

    }
}
  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: