本文主要是介绍2019阿里内推实习编程：数字串转换的最少步骤，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定两个长度为 n ( 0 < n <= 8 ) 的 数字串 (由1到9构成) ，我们希望对第一个数字串做一系列如下操作：
1、将数字串的某一位加1
2、将数字串的某一位减1
3、交换数字串中任意两个数字的位置
最终使得第一个数字串变成第二个数字串， 请问最少需要多少操作。
分析：
有三种方式改变原数字串，我们可以将1、2两种归为变数操作；将3称之为 交换操作；
基本思想：
给定数字串A： a1, a2,…an B:b1, b2,…bn (<0=n<=8)
假如我们动态看这个变化过程，即分步的看：
假如有一次交换的机会（也可以选择不用），会出现两种可选择的方案：
方案一：不使用交换数字的机会，直接进行数字加减 得到操作步数N1；
方案二：使用这次交换的机会，并比较所有交换的情况，使得最终两个数字串差的绝对值之和最小，这个“最小值”+1（1为交换成本）就是方案二的次数N2；
接下来判断N2是否小于N1，若是则说明交换有利，可以使得操作次数更少；否则说明无法通过交换使得次数更小
如此迭代，直到无法利用交换的操作使得两个数字串更接近…..循环终止。
#include "stdafx.h"#include <iostream>
#include <math.h> void swap(int arr[], int index1, int index2) { int temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp;
} //对应位置相减，返回绝对值的和，
//int d1 ,d2: 临时交换位置的索引号
//int bSwap: 是否进行临时交换
int GetDirectDiff(const int sArr[], const int dArr[], int num, int d1=0, int d2=0, bool bSwap=false)
{int absDif=0;if (!bSwap)//no swap{for (int i=0; i<num; ++i){absDif+=abs(sArr[i]-dArr[i]);}}else{for (int i=0; i<num; ++i){if ((i!=d1)&&(i!=d2)){absDif+=abs(sArr[i]-dArr[i]);}}absDif+=(abs(sArr[d1]-dArr[d2])+abs(sArr[d2]-dArr[d1]));}return absDif;
}int numStrSwap(char* src, char* dst) { int s = atoi(src); int d = atoi(dst); int n = 0; //计算数字的位数 int temp = s; while (temp != 0) { temp /= 10; ++n; } int sArr[8]; int dArr[8]; for (int i = n-1; i >= 0; --i) { sArr[i] = s % 10; s /= 10; dArr[i] = d % 10; d /= 10; } if (0 == n){return 0;}if (1 == n){return abs(sArr[0]-dArr[0]);}//int result = getMin(sArr, dArr, 0, n-1); //modified by Yuanpei Lin //思路就是试探能不能通过交换 改变两个字符串相差的绝对值之和//获取初始位置相差值int result=GetDirectDiff(sArr, dArr, n);int tempResult=result;int nSwap=0;//**记录进行过多少次交换 2018年3月21日21:14:03**bool goOn=false;do {goOn=false;int tempMin=INT_MAX;//交换后差的绝对值之和int tempI=0, tempJ=0;//用于记录最终可能用于交换的位置for (int i=0; i<n-1; ++i){for (int j=i+1; j<n; ++j){int dif=GetDirectDiff(sArr, dArr, n, i, j, true);if (tempMin>dif){tempMin=dif;tempI=i;tempJ=j;}}}tempResult=tempMin+1;//加上交换操作if (tempResult<result){swap(sArr,tempI,tempJ);//do swapresult=tempMin;nSwap++;goOn=true; //试探循环继续进行}} while (goOn);result+=nSwap;//**加上进行过多少次交换**return result;
} int main() { int result = numStrSwap("2345", "3456"); printf("%d \n", result); return 0;
}
这篇关于2019阿里内推实习编程：数字串转换的最少步骤的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
