面试时遇到的一个算法题，请教大家
面试时的时候，面试官问了我一个算法题，题目大概是这样的：一个手机键盘上的数子0-9（也就是九宫格键盘），假如有两个机械臂a和b，初始位置都在0数字上，机械臂移动一步都会消耗一定的能量，问随意给定一个手机号码，两个机械臂怎样移动才会消耗最少的能量把手机号码打印出来。
希望大家给个思路，我觉得是动态规划吧，最后能把代码贴出来，谢谢了……
2016-09-02 21:20 大连海事大学 算法工程师
关注
全部评论
gongzixiaomu
华南理工大学
各个数字之间的距离集合中求最小和，初步想法……
金八铜九炮灰十
蓝翔职业技术学校
0-9一共10个数，哪来的九宫格？
cc98
浙江大学 C++
双层的DP
呵呵哒2333
北京理工大学 C++
这个手机号码是11位的，搜索空间很小，用普通的搜索就行了：(pos1, pos2, index) = Min(dis(pos1,
telnum[index]) + (telnum[index], pos2, index+1)
/*第一个机械臂从pos1移动到telnum[index]*/，dis(pos2, telnum[index]) +
(pos1, telnum[index], index+1))
/*或者第二个机械臂从pos2移动到telnum[index]*/
；
(pos1, pos2, 11) = 0。
（其中dis函数是两个按键的移动消耗，O(1)的复杂度），然后可能会出现重复计算，那么就加个记忆set保存计算过的结果，还有（pos1,
pos2, index） == (pos2, pos1, index)。
牛客492426号
Java
让a去找第一个数字，达到后，a在第一个数字位置，b在0，计算a和b距离第二个数字的距离，谁近谁走，依次类推
（感觉就是计算两个点到第三个点的距离，近的变成第三个点，距离相等走a，再继续计算，个人想法，仅供参考，不知道对不对...）
Horanol
字节跳动_Data-商业化技术_后端开发
这不是一个局部最优的题，不能用贪心算法，也就是不能每一步都取距离最小的值，这样总的步数未必是最小的。
牛客1481368号
东北大学 C++
#include<iostream>
#include <vector>
using namespace std;
int DistanceArry[10][10];
int Mindistance=INT_MAX;
int arry[11];
int point[2];
void DFS(int index,int value)
{
if(index==11)
{
if (value<Mindistance)
{
Mindistance=value;
return ;
}
}
else
{
for(int i=0;i<2;i++)
{
int tmp=point[i];
int addvalue=DistanceArry[point[i]][arry[index]];
point[i]=arry[index];
DFS(index+1,value+addvalue);
point[i]=tmp;
}
}
}
int main()
{
for(int i=0;i<11;i++)
{
cin>>arry[i];
}
point[0]=point[1]=0;
for(int i=0;i<10;i++)
{
for(int j=i;j<10;j++)
{
if(i==0)
{
DistanceArry[j][0]=DistanceArry[0][j]=(11-j)/3+(11-j)%3;
}
else
{
DistanceArry[i][j]=DistanceArry[j][i]=((j-i)/3)+(j-i)%3;
}
}
}
DistanceArry[0][0]=0;
DFS(0,0);
cout<<Mindistance<<endl;
}
我来讲一个冷笑话
University of Helsinki C++
因为数字不多，可以动态规划吧。 数字个数1，返回a,b里移动距离最小的。 数字个数大于1，返回min（a移动距离+剩下n-1个数字移动距离最小的，b移动距离，+剩下n-1个数字移动距离最小的。
相关推荐
