阿里巴巴算法工程师编程题

＃ 第一题应该是dijkstra's algorithm的变种？没来得及仔细debug，通过率0%。第二题看起来简单，到交卷了才发现编号只能0-9，通过率0% （此处应该微笑 def minTravelTime(intersections, roads, start, goal): frontier = [] frontier.append([start, 0]) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = 0 t = 0 while len(frontier) > 0: current = min(frontier, key=lambda x: x[1]) frontier.remove(current) current = current[0] if current == goal: print(current) return cost_so_far(current) for next in get_neighbors(current, roads): wait_time = get_wait_time(next[0], intersections, t) new_cost = cost_so_far[current] + wait_time + next[2] t = t + wait_time + next[2] if next[1] not in cost_so_far or new_cost < cost_so_far[next[1]]: cost_so_far[next[1]] = new_cost frontier.append([next[1], new_cost]) came_from[next] = current def get_neighbors(node, roads): results = [] for road in roads: if node == roads[0]: results.append(road) return results def get_wait_time(node, intersection, t): change = intersection[node] if (t/change)%2 == 0: return 0 else: return ((t/change)+1)*change - t

想问一下，没点运行，直接交卷，如果程序正确，有分么。。。

第二题纯模拟可过- -。

void dfs(vector<int>& signal,vector<bool> & mask, vector<vector<int> > &path, vector<vector<int> >& matrix, int nowNode, int T,int nowTime, int & minValue){ if(nowTime >= minValue) return; if(nowNode == T){ minValue = min(minValue, nowTime); return; } int waitTime = 0; if(nowTime / signal[nowNode] % 2 == 1) { waitTime = signal[nowNode] - nowTime % signal[nowNode]; } nowTime += waitTime; mask[nowNode] = true; for(int i=0;i<path[nowNode].size();i++){ if(!mask[path[nowNode][i]]){ nowTime += matrix[nowNode][path[nowNode][i]]; dfs(signal,mask,path,matrix,path[nowNode][i],T,nowTime,minValue); nowTime -= matrix[nowNode][path[nowNode][i]]; } } mask[nowNode] = false; } int minTravelTime(int N, vector < vector < int > > intersections, int M, vector < vector < int > > roads, int s, int t) { vector<bool> mask(N,false); vector<int> signal(N,0); for(int i=0;i<N;i++){ signal[intersections[i][0]] = intersections[i][1]; } vector<vector<int> > path(N); vector<vector<int> > matrix(N,vector<int>(N,0)); for(int i=0;i<M;i++){ path[roads[i][0]].push_back(roads[i][1]); path[roads[i][1]].push_back(roads[i][0]); matrix[roads[i][0]][roads[i][1]] = roads[i][2]; matrix[roads[i][1]][roads[i][0]] = roads[i][2]; } int result = 0x7fffffff; dfs(signal,mask,path,matrix,s,t,0,result); return result; }

第二题很奇怪啊，本地明明都是对的，但是系统就是0.0%。。。

上面两个题目的思路和Python源码，http://blog.csdn.net/u014606206/article/details/77596819

来来，有大神分享下思路或者代码吗？

0%,0%

Mark 求大佬解答。。

第二题10,4的不是测试案例么？通过了也是0%？

0%,0%

第二题没想明白，感觉没问题，但是通过率0%

AK

第一题标准dfs吧，只是每次通过路口的时候处理下时间

第二题的测试用例有20%是k在45~9000中间，40%在9000~1386450中间。别问我为什么知道的。。。

*** 我Java岗跟你的编程题一样..  

为什么我觉得我投的测试岗的题目比算法还难。。

m

//第二题 #include <stdio.h>   #include <math.h>   #include <stdlib.h>   int Get(int n){     int x;     // do something     int zuhao,kaishi;     zuhao=int(sqrt(2*n));     if ((zuhao*(zuhao+1)/2>=n)&&(zuhao*(zuhao-1)/2+1<=n)){     zuhao=zuhao-1; }     kaishi=zuhao*(zuhao+1)/2+1;     x=n-kaishi+1;     return x; } int main()   {       int n;     scanf("%d",&n);     int r = Get(n);              printf("%d\n",r);   }

//第一题完全没有思路，感觉好难，选择题也没做完