题解 | #牛牛摇骰子#
牛牛摇骰子
http://www.nowcoder.com/practice/f9e26ad67525493bab009c66c5ad36fe
题意：
给你一个无限长的数轴，刚开始你在位置
处，你每次可以向左或者向右移动
个单位，现在有
次询问，第
次询问给你一个数字
，问从起点位置到所在位置最少需要多少步？
解法一（最短路，不可AC）
显然我们可以根据题意构建一张以数轴上的数字为点，边权为
的无向图，边)
表示数字
变化成数字
的一次操作
那么对于第个询问，答案为起点到点的最短路
代码：
class Solution {
public:
vector<int> MinimumTimes(vector<int>& arr) {
int mx_q=0;//询问最大的数字
for(auto& x:arr){
mx_q=max(mx_q,x);//求解询问最大的数字
}
mx_q+=20;//由于可以向左走，且一次最多走11个单位，故将范围扩大20
vector<int> dis(mx_q+1,0x3f3f3f3f);//动态分配内存，且初始化一个极大值
vector<int>* gr=new vector<int>[mx_q+1];//邻接表存图，动态内存分配
for(int i=0;i<=mx_q;i++){//对于每个点向周围连边
if(i+3<=mx_q){
//向右走3
gr[i].push_back(i+3);
gr[i+3].push_back(i);
}
if(i+7<=mx_q){
//向右走7
gr[i].push_back(i+7);
gr[i+7].push_back(i);
}
if(i+11<=mx_q){
//向右走11
gr[i].push_back(i+11);
gr[i+11].push_back(i);
}
if(i-3>=0){
//向左走3
gr[i].push_back(i-3);
gr[i-3].push_back(i);
}
if(i-7>=0){
//向左走7
gr[i].push_back(i-7);
gr[i-7].push_back(i);
}
if(i-11>=0){
//向左走11
gr[i].push_back(i-11);
gr[i-11].push_back(i);
}
}
queue<int> que;//bfs队列
que.push(0);//起点
dis[0]=0;
while(!que.empty()){
int x=que.front();
que.pop();
for(auto v:gr[x]){
if(dis[v]>dis[x]+1){
//松弛操作
dis[v]=dis[x]+1;
que.push(v);
}
}
}
vector<int> ans;
for(auto x:arr){
//记录答案
ans.push_back(dis[x]);
}
return ans;
}
}; 时间复杂度： 空间复杂度：)
，邻接表存图，距离数组，队列的空间大小都是)
级别的，答案数组的空间大小为)
级别的，故总的空间复杂度为
解法二（取模优化）
我们知道当足够大时，肯定是先走很多步11，直到走到距离足够近时，再走小的步数进行微调
于是我们可以对一个较小的距离范围求解最短路
然后对于一个询问，我们可以枚举最后一段的长度，前面的长度全部用步数11的方法走，最后取最小的步数即可
代码：
class Solution {
public:
/**
* 把所有询问的答案按询问顺序放入vector里
* @param arr int整型vector 要查询坐标的数组
* @return int整型vector
*/
int dis[31];//30>=2*11，足够小的范围
vector<int> gr[31];//邻接表存图
vector<int> MinimumTimes(vector<int>& arr) {
memset(dis,0x3f,sizeof dis);//初始化一个极大值
for(int i=0;i<=30;i++){
gr[i].clear();//多测清空
}
for(int i=0;i<=30;i++){
//枚举每个点
if(i+3<=30){
//向右走3
gr[i].push_back(i+3);
gr[i+3].push_back(i);
}
if(i+7<=30){
//向右走7
gr[i].push_back(i+7);
gr[i+7].push_back(i);
}
if(i+11<=30){
//向右走11
gr[i].push_back(i+11);
gr[i+11].push_back(i);
}
if(i-3>=0){
//向左走3
gr[i].push_back(i-3);
gr[i-3].push_back(i);
}
if(i-7>=0){
//向左走7
gr[i].push_back(i-7);
gr[i-7].push_back(i);
}
if(i-11>=0){
//向左走11
gr[i].push_back(i-11);
gr[i-11].push_back(i);
}
}
dis[0]=0;
queue<int> que;
que.push(0);
while(!que.empty()){
int x=que.front();
que.pop();
for(auto v:gr[x]){
if(dis[v]>dis[x]+1){
//松弛操作
dis[v]=dis[x]+1;
que.push(v);
}
}
}
vector<int> ans;
for(auto x:arr){
int res=0x3f3f3f3f;
for(int k=0;k<=2;k++){
//枚举一共走多少个11
if(x>=k*11){
//x/11-k为走的11的个数
res=min(res,dis[x-(x/11-k)*11]+(x/11-k));
}
}
ans.push_back(res);
}
return ans;
}
}; 时间复杂度： 空间复杂度：，邻接表存图，距离数组，队列所占空间都为)
级别，答案数组的空间为级别，故总的空间复杂度为
