2019阿里内推实习编程：数字串转换的最少步骤

本文主要是介绍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;  
}