通过交换相邻数字（差值为奇数）来最小化给定数字

本文旨在实现一个程序，通过交换相邻数字（差值为奇数）来最小化给定数字。

目标是确定仅使用字符“1”、“2”和“3”通过任意次数交换相邻字符，从表示整数的长度为 N 的字符串中可以创建的最小值。

众所周知，在 C 语言编程中，字符串是一组以空字符“\0”结尾的字符。C 字符串中的字符存储在一个字符数组中。C 字符串与字符数组的区别在于它以特殊的字符“\0”结尾。

示例 1

Let the Input string be,
S = “211323”
Output obtained here is: 112233

示例 2

Let the Input string be,
S = “112323”
Output obtained here is: 112233

示例 3

Let the Input string be,
S = “231213”
Output obtained here is: 223113

示例 4

Let the Input string be,
S = “123123”
Output obtained here is: 122313

问题陈述

实现一个程序，通过交换相邻数字（差值为奇数）来最小化给定数字

方法

解决这个问题并获得一个程序来最小化给定数字的方法，该程序通过交换相邻数字（差值为奇数）来实现。

通过以下见解，可以使用贪心算法来解决这个问题：

贪心算法究竟是什么？

贪心算法逐段构建解决方案，始终选择提供最明显和直接好处的组件作为下一步。因此，贪心算法非常适合于选择局部最优解也能导致全局最优解的问题。

在这种情况下，由于 1 和 3 之间的差是 2（偶数），因此它们不能交换。

由于 1 和 2 之间的差是 1（奇数），因此 2 和 3 之间的差也是如此。

由于 1 和 2 之间的差是 1（奇数），因此 2 和 3 之间的差也是如此。

算法

下面给出了实现程序的算法，该程序通过交换相邻数字（差值为奇数）来最小化给定数字

  • 步骤 1 - 定义一个函数来交换相邻数字（如果差值为奇数），以获得与给定字符串匹配的最小数字。

  • 步骤 2 - 查找给定字符串的长度

  • 步骤 3 - 声明一个整型变量来存储 3 的第一次出现位置

  • 步骤 4 - 声明变量来跟踪字符串中 2 的总数和第一个 3 之前的 1 的计数

  • 步骤 5 - 现在，遍历字符串时，计算第一个 3 之前的 1 的数量和 2 的总数。

  • 步骤 6 - 将第一个 3 出现之前的所有 1 都添加到结果中

  • 步骤 7 - 将每个 2 都添加到结果中

  • 步骤 8 - 将剩余的 3 和 1 以与给定字符串相同的顺序添加到结果中

  • 步骤 9 - 最后，打印输出结果。

示例：C 程序

以下是上述算法的 C 语言程序实现，该程序通过交换相邻数字（差值为奇数）来最小化给定数字

Open Compiler
#include <stdio.h>
#include <string.h>
void findMinimumString(char S[]){
   int N = strlen(S);
   int pos = -1;
   int count1 = 0, count2 = 0;
   for (int i = 0; i < N; i++) {
      if (pos == -1 && S[i] == '1')
         count1++;
      else if (pos == -1 && S[i] == '3')
         pos = i;
      else if (S[i] == '2')
         count2++;
   }
   while (count1--)
      printf("1");
   while (count2--)
      printf("2");
   if (pos != -1) {
      while (pos < N) {
         if (S[pos] != '2')
            printf("%c", S[pos]);
         pos++;
      }
   }
}
int main(){
   char S[] = "211323";
   findMinimumString(S);
   return 0;
}

输出

112233

结论

同样，我们可以得到一个程序，通过交换相邻数字（差值为奇数）来最小化给定数字。“通过交换相邻数字（差值为奇数）来最小化给定数字”这一挑战已在本文中得到解决。

本文提供了 C 语言代码以及实现程序的算法和方法，该程序通过交换相邻数字（差值为奇数）来最小化给定数字。

更新于：2023年10月30日

浏览量：110

启动您的职业生涯

完成课程后获得认证

开始
广告