字符串变换最小字符串(C语言)

这篇具有很好参考价值的文章主要介绍了字符串变换最小字符串(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

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

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

输入描述

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

输出描述

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

用例

输入 abcdef
输出 abcdef
说明 abcdef已经是最小字符串,不需要交换。
输入 bcdefa
输出 acdefb
说明 a和b进行位置交换,可以得到最小字符串。

备注

s是都是小写字符组成

1<=s.length<=1000

代码

// 引入必要的头文件,用于输入输出和字符串操作
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义一个常量,表示字符串的最大长度
#define MAX_LEN 1000

// 自定义比较函数cmp,用于qsort对字符数组进行字典序排序
int cmp(const void *a, const void *b) {
    // 返回两个字符的ASCII码之差,使得字符按字典序排列
    return *(char *)a - *(char *)b;
}

int main() {
    // 定义原始字符串s,并读取用户输入的字符串内容
    char s[MAX_LEN];
    scanf("%s", s);

    // 计算字符串s的长度
    int len = strlen(s);

    // 创建一个新的字符数组sorted_s,用于存储原始字符串s排序后的副本
    char sorted_s[MAX_LEN];
    strcpy(sorted_s, s);

    // 使用qsort对sorted_s进行升序排序
    qsort(sorted_s, len, sizeof(char), cmp);

    // 比较排序后与原始字符串,如果相同则无需交换,直接输出原始字符串并返回
    if (strcmp(sorted_s, s) == 0) {
        printf("%s", s);
        return 0;
    }

    // 遍历原始字符串,寻找第一个未在正确位置上的字符
    for (int i = 0; i < len; i++) {
        if (s[i] != sorted_s[i]) {
            // 找到该字符在排序后字符串中的正确位置(索引)
            int index;
            for (int j = 0; j < len; j++) {
                if (sorted_s[i] == s[j]) {
                    index = j;
                    //注意:这里没有加break;
                    //s:afcdbb, sorted_s:abbcdf,index应该是最后一个b的位置,这样s变成abcdbf而不是abcdfb,abcdbf的字典序比abcdfb小
                }
            }

            // 交换原始字符串中找到的错误字符与其正确位置上的字符
            char tmp = s[i];
            s[i] = sorted_s[i];
            s[index] = tmp;

            // 由于我们只允许一次交换,所以找到一对字符后就可以结束循环
            break;
        }
    }

    // 输出经过变换后得到的最小字符串
    printf("%s\n", s);

    // 主函数返回0表示程序正常执行完毕
    return 0;
}

注意;

“最小字典序字符串”是什么意思?

“最小字典序字符串”是指在一个给定的字符集合中,按照特定排序规则(通常是字母表顺序或数字大小顺序)排列起来形成的字符串中,排在最前面的那个字符串。在计算机科学和数学中,这种排序规则通常基于ASCII码或者Unicode编码的值。

对于由小写字母组成的字符串而言,最小字典序字符串意味着字母按照英文字母表从前往后依次排列。例如,在所有可能的6个字符长度的字符串中,“abcdef”是比“abcdeg”、“abcfed”等其他字符串字典序更小的字符串,因为它的每个字符都在字母表上位置靠前。

当题目要求求解一个字符串变换后的最小字典序字符串时,目标是通过允许的操作(如交换字符、删除字符等)使得最终得到的字符串在其所有可能变化形式中处于字典序排序上的最前端。

为什么“遍历原始字符串,寻找第一个未在正确位置上的字符;交换原始字符串中找到的错误字符与其正确位置上的字符”就可以求出“最小字典序字符串”

在给定的变换规则下,要通过一次交换操作使字符串变为字典序最小,我们需要找到的是这样一对字符:其中一个字符原本位于它应该在排序后出现的位置之前,并且这个字符与它后面应当出现在该位置上的字符进行交换。

例如,如果字符串是 “bcdefa”,按照字典序排列应该是 “abcdef”。那么,我们发现 ‘a’ 字符在原始字符串中的位置(索引为 5)比它在排序后的正确位置(索引为 0)靠后。因此,将 ‘a’ 与它前面的一个字符(这里是 ‘b’)交换位置,得到 “acdefb”,此时字符串变成了字典序上可能的最小值。

这个策略的核心在于:

  1. 字典序最小意味着所有字符都应该尽可能地向左移动。
  2. 因此,我们应该优先考虑那些位于排序后对应位置之后的字符,并将其与当前所在位置之前的字符交换,以使其移动到更靠前的位置。

代码中通过遍历原字符串并比较其与已排序字符串对应位置的字符来定位需要交换的一对字符,一旦找到这样的字符对就立即进行交换,并且由于题目只允许一次交换,所以在完成首次交换后就会结束循环。这样处理的结果就是得到了字典序上仅通过一次交换能得到的最小字符串。文章来源地址https://www.toymoban.com/news/detail-834665.html

到了这里,关于字符串变换最小字符串(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • DSt:数据结构的最强学习路线之数据结构知识讲解与刷题平台、刷题集合、问题为导向的十大类刷题算法(数组和字符串、栈和队列、二叉树、堆实现、图、哈希表、排序和搜索、动态规划/回溯法/递归/贪心/分治)总

    Algorithm:【算法进阶之路】之算法面试刷题集合—数据结构知识和算法刷题及其平台、问题为导向的十大类刷题算法(数组和字符串、链表、栈和队列、二叉树、堆、图、哈希表、排序和搜索、回溯算法、枚举/递归/分治/动态规划/贪心算法)总结 目录 相关文章

    2024年02月08日
    浏览(52)
  • 算法刷题-字符串-翻转字符串里的单词

    综合考察字符串操作的好题。 力扣题目链接 给定一个字符串,逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: \\\" hello world! \\\" 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不

    2024年02月09日
    浏览(99)
  • 【C语言】字符串---刷题篇

    Hi,C站的小伙伴们大家好呀!😊🥰,欢迎来阅读我的这一篇 【C语言】字符串基础刷题篇! 不知你是否和我一样,在刚刚接触到这块的知识时,总是会和这神圣的知识隔着隔着厚厚的一堵墙,迷茫的眼神中总是会露出不理解不理解😣😣(当时的状态……) 其实后来我就发现其实

    2024年02月03日
    浏览(42)
  • C语言——oj刷题——回文字符串

    问题: 实现一个函数,判断一个字符串是否为回文字符串。 回文字符串是指正读和反读都相同的字符串。例如,\\\"level\\\"、\\\"radar\\\"和\\\"madam\\\"都是回文字符串。 要解决这个问题,我们可以使用两个指针分别指向字符串的首尾字符,然后逐步向中间移动,同时比较指针所指向的字符是

    2024年02月21日
    浏览(43)
  • 【算法刷题之字符串篇】

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 1.将 left 指向字符数组首元素,right 指向字符数组尾元素。 2.当 left right: 交换 s

    2024年02月10日
    浏览(45)
  • 探索经典算法 拓扑排序,字符串匹配算法,最小生成树

    拓扑排序、字符串匹配算法和最小生成树是计算机科学中常用的数据结构和算法,它们在解决各种实际问题中具有重要的应用价值。在本文中,我将详细介绍这三个主题,并提供相应的示例代码和应用场景,以帮助读者更好地理解和应用这些概念。 一、拓扑排序: 拓扑排序

    2024年02月05日
    浏览(50)
  • 算法刷题|583.两个字符串的删除操作、72.编辑距离

    题目:给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 dp[i][j] 表示以i-1结尾的word1子序列和以j-1结尾word2变成相同所需要的最小的步数为dp[i][j] 递推公式:分两种情况,word1.charAt(i-1) 和 word2.charAt(j-1)是否

    2024年02月08日
    浏览(39)
  • 【JavaScript数据结构与算法】字符串类(反转字符串中的单词)

    个人简介 👀 个人主页: 前端杂货铺 🙋‍♂️ 学习方向: 主攻前端方向,也会涉及到服务端(Node.js) 📃 个人状态: 在校大学生一枚,已拿多个前端 offer(秋招) 🚀 未来打算: 为中国的工业软件事业效力 n 年 🥇 推荐学习:🍍前端面试宝典 🍉Vue2 🍋Vue3 🍓Vue2/3项目

    2023年04月09日
    浏览(89)
  • 【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

      字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作: S = ′ ′ a 0 a 1 … a n − 1 ′ ′ S=\\\'\\\'a_{0} a_{1}…a_{n-1}\\\'\\\' S = ′′ a 0 ​ a 1 ​ … a n − 1 ′′ ​   其中S是串名,引号中

    2024年02月05日
    浏览(72)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包