(C卷,100分)- 字符串变换最小字符串（Java & JS & Python & C）

题目描述

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。

变换规则：交换字符串中任意两个不同位置的字符。

输入描述

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

输出描述

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

备注

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

用例

题目解析

我的思路如下，先将输入的字符串str进行字典排序，得到一个新串minStr，如果str和minStr相同，则说明str已经是最小字符串，不需要任何变换，直接返回str。

如果str和minStr不同，则说明str不是最小字符串，我们需要遍历出str的每一个字符，对比str[i] 和 minStr[i] ，具体处理逻辑如下图

Java算法源码

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

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.nextLine()));
  }

  public static String getResult(String s) {
    char[] minSArr = s.toCharArray();
    Arrays.sort(minSArr);

    String minS = new String(minSArr);
    if (minS.equals(s)) return s;

    char[] sArr = s.toCharArray();

    for (int i = 0; i < s.length(); i++) {
      if (sArr[i] != minSArr[i]) {
        char tmp = sArr[i];
        sArr[i] = minSArr[i];

        int swapIndex = s.lastIndexOf(minSArr[i]);
        sArr[swapIndex] = tmp;
        break;
      }
    }

    return new String(sArr);
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

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

rl.on("line", (line) => {
  console.log(getMinStrAfterOneSwap(line));
});

function getMinStrAfterOneSwap(str) {
  const minStrArr = [...str].sort();
  if (str === minStrArr.join("")) return str;

  const strArr = [...str];

  for (let i = 0; i < strArr.length; i++) {
    if (strArr[i] !== minStrArr[i]) {
      let tmp = strArr[i];
      strArr[i] = minStrArr[i];

      let swapIndex = str.lastIndexOf(minStrArr[i]);
      strArr[swapIndex] = tmp;
      break;
    }
  }

  return strArr.join("");
}

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult():
    minSArr = list(s)
    minSArr.sort()

    if s == "".join(minSArr):
        return s

    sArr = list(s)

    for i in range(len(s)):
        if sArr[i] != minSArr[i]:
            tmp = sArr[i]
            sArr[i] = minSArr[i]

            swapIdx = s.rindex(minSArr[i])
            sArr[swapIdx] = tmp
            break

    return "".join(sArr)


# 调用算法
print(getResult())

C算法源码

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

#define MAX_SIZE 1000

char *getResult(char s[]);

int main() {
    char s[MAX_SIZE];
    gets(s);

    puts(getResult(s));

    return 0;
}

int cmp(const void *a, const void *b) {
    return (*(char *) a) - (*(char *) b);
}

char *getResult(char s[]) {
    int len = strlen(s);

    char minS[len + 1];
    strcpy(minS, s);

    qsort(minS, len, sizeof(char), cmp);

    if (strcmp(minS, s) == 0) {
        return s;
    }

    for (int i = 0; i < len; i++) {
        if(s[i] != minS[i]) {
            char tmp = s[i];
            s[i] = minS[i];

            int swapIdx = strrchr(s, minS[i]) - s;
            s[swapIdx] = tmp;
            break;
        }
    }

    return s;
}