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

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

＃ 第一题应该是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

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

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

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; }

第二题纯模拟可过- -。

第一题,用dfs就行.关键在于求刚到达路口的时间.关于时间的求解可以参考 https://code.google.com/codejam/contest/8284487/dashboard#s=a&a=0

第二题poj1019，第一题poj1158改动

第2题高效做法：首先用下三角求出所在的行列，再用等差乘以等比前n项求和算出对应的数值。   源自博客：http://blog.csdn.net/yuhua_zhou/article/details/77601124 #include<iostream>   #include<string> #include<cmath>   using namespace std; int main() {     long long k;     while (cin >> k)     {         long long row = floor((-1.0 + sqrt(1.0 + 8.0 * k)) / 2.0);         long long col;         if (k - (1 + row)*row / 2>0)         {             col = k - (1 + row)*row / 2;         }         else         {             col = row;         }         long long sum = 0;          int q = 10;         long long n = 0;         while(sum < col)         {             n++;             sum = ( n * 9 * powl(q, n) - 9 - (9 * 10 * (1 - powl(q, n - 1)) / (1 - q)) ) / (q - 1);         }         long long n_last = n - 1;         long long sum_last = (n_last * 9 * powl(q, n_last) - 9 - (9 * 10 * (1 - powl(q, n_last - 1)) / (1 - q))) / (q - 1);         long long d_col = col - sum_last - 1;//d_col大于等于零的整数         long long digit = powl(10 , n - 1) + floorl(d_col / n);         string str = to_string(digit);         cout << str[d_col % n] << endl;     }     return 0; }

第二题下来想了想，用模拟那个模式做的，简单测试下没啥问题，不知道有不有更高效的算法 #include<iostream> #include<vector> #include<climits> #include<sstream> using namespace std; int Get(int n) { int x; int n1 = n; int cnt = 9; int step = 1; int startn = 0 + step; int endn = cnt*step + 0; int numl = 0; while (1) { // 统计当前 step 的所有段总共覆盖 grid 编号数 // step 为 1：45个 // step 为 2：9000个 numl = (startn + endn) * cnt / 2; if (n1 <= numl ) break; n1 -= numl; step <<=1; cnt *= 10; startn = endn + step; endn = endn + step * cnt; } // 确定了step，确定在某一段的第几位 // step 为1：| 1 | 12 | 123 | 1234 |... // step 为2：| 12345678910 | 1234567891011| ... int m = startn;// 第一段的编号数 int prevm = 0; int ii = 1; while ( n1 > m ) { prevm = m; m += (startn+ii*step); // 逐段查看，累积前面的编号数 ++ii; } n1 -= prevm; // 从grid 编号段中（1234567891011...），要取出 第 n1 位的数（以1为索引开始） step = 1; cnt = 9; int candinum = 0; while (1) { // 当前 step 所有数字的位数 // step为1: 9 (1~9) // step为2: 180 (10~99) numl = cnt * step; if (n1 <= numl) break; n1 -= numl; candinum += cnt; step <<= 1; cnt *= 10; } // 再次确定step，从编码段 以step位数递增的某个数 的第 n1 位数 // 如：|123.....100101102| // 101就是以step=3递增的第2个数， int a = n1 / step; // 第几个数 int b = n1 % step; // 第几位 candinum += a; if (b > 0) candinum += 1; stringstream s; string str; s << candinum; s >> str; if(b==0) x = str[step-1] - '0'; else x = str[b-1] - '0'; return x; } int main() { int n; while (cin >> n) { int r = Get(n); cout << '\t' << r << endl; } }

# -*- coding: UTF-8 -*-. #!/bin/python import sys import os import math length = 1 s='' _N = int(raw_input()) for i in range(2,10000000): n = range(1,i) if len(n)>0: for k in range(len(n)): s +=str(n[k]) last_length = length length = s.__len__() if _N in range(last_length,length): print s[_N-1] break

//侥幸AC了 #include <stdio.h>   #include <math.h>   #include <stdlib.h>   int Get(int n){ int x; int lo = 1, start = 1, end = 9; double p10 = 10.0; while (1){ int temp = (start + end) * 9 * pow(p10, lo - 1) / 2; if (temp > n)  break; n -= temp; lo++; start = end + lo; end = start + lo*pow(p10, lo - 1) * 9; } while (1){ if (start >= n) break; n -= start; start += lo; } start = 9; lo = 1; while (1){ if (start > n) break; n -= start; lo++; start = 9 * pow(p10, lo - 1)*lo; } start = 9 * pow(p10, lo - 2)*(lo-1) + n / lo; stringstream str; str<<start; x = str[n%lo] - '0'; return x; } int main() { int n; scanf("%d", &n); int r = Get(n); printf("%d\n", r); }

第一题dfs找出所有点到点的路径，但是求那个等待时间总是出错。。。。。

对一道编程题，能参加面试吗

第一题来不及了。。没写完。。 //第二题的代码这样是0，所以题目到底啥意思？。 #include <stdio.h>   #include <math.h>   #include <stdlib.h>   #include<iostream> int Get(int n){ //printf("%d\n",n);     int x,i=1; while((1+i*(i-1)/2)<n){ // printf("%d\n",i); i++; } if(n!=(1+i*(i-1)/2)) { i--;            x=n-i*(i-1)/2; } else x=1;         //printf("%d\n",x);     return x; } int main()   {       int n;     scanf("%d",&n);     int r = Get(n);            printf("%d\n",r);   }

菜鸟仓库AC，第一题不知道为啥0%..

int Get(int n){     int x;     // do something     string data = "1";     string data_temp = "1";     int count = 2;     while(data.size() < (n)){         data_temp = data_temp + to_string(count);         count++;         data = data + data_temp;     }     x = data[n-1] - '0';     return x; }

第一题，先觉得是bfs，写不出来，又觉得有点儿动归，归不出来，又觉得像Floyd还是写不出来，这一个小时。思维倒是挺活跃，就是写不出来，数据处理不好，吐槽这么多，还不是要死

第二题找了好久原因最后发现是题意理解错了 我理解的是|*|符号隔开的每个单元内的格子数量为1,2,3,---,n递增，然后每个单元内的格子按照123456789101112这样来编号，每个格子对应0-9的一个数字 貌似题意应该是|*|符号隔开的每个单元内的数（不是数字）为1,2,3,---,n递增，然后单元内的一个数字对应一个格子。 好像有点拗口，不知道是不是这样。anyway, 和阿里拜拜了

bfs或者dfs都可以做，但是题意的描述让我很郁闷，0-3时刻可以通过，3-6时刻不能通过，那3到底能不能通过😞