|
发信人: fengisan (一个人......), 信区: Job 标 题: [合集] google昨晚的笔试题,最后3道 发信站: 珞珈山水BBS站 (Sat Oct 28 13:06:46 2006), 站内 ☆─────────────────────────────────────☆ qinyubin (转向你的方向@E.I.S) 于 (Wed Oct 18 13:51:29 2006) 提到: 写的很快,不过发现自己写的很烂.下面的解法不是我的. 2.1 // search the value on the Binary Search Tree struct Node { Node* left; Node* right; int value; }; Node* Search(Node* root, int value) { while(NULL != root && root->value != value) root = root->value > value ? root->left : root->right; return root; } 2.2 //Tribonacci number : T(i) = i (if i = 0, 1, 3); T(i) = T(i-1) + T(i-2) + T(i-3) (if i > 2) int Tribonacci(int n) { int t[] = {0, 1, 2}; for (; n > 2; --n) { t[1] += t[0]; t[2] += t[1]; t[0] = t[1] - t[0]; t[1] = t[2] - t[1]; } return t[n]; } 一个n个顶点的连通图. 写一个算法,求任意两个点之间是否存在长度为k的通路,通路上可以有重复的点. 写时间和空间复杂度 用matrix multiple, 复杂度是O(N^3logK) ☆─────────────────────────────────────☆ tube (tube) 于 (Wed Oct 18 13:56:27 2006) 提到: 第3题通路上可以有重复的点？我没看题目上有写这句阿 ☆─────────────────────────────────────☆ qinyubin (转向你的方向@E.I.S) 于 (Wed Oct 18 14:01:05 2006) 提到: 通路上可以有重复的点, 恩,我刚发现.没有. 我转的帖子. ☆─────────────────────────────────────☆ dragonflywww (龙飞) 于 (Wed Oct 18 14:15:57 2006) 提到: 最后一题不用乘整个距阵吧 可以做到O(n^2*k) 那个logk怎么来的? ☆─────────────────────────────────────☆ tube (tube) 于 (Wed Oct 18 14:16:41 2006) 提到: 说下你的算法？目前还不知道最后一题怎么做 ☆─────────────────────────────────────☆ tube (tube) 于 (Wed Oct 18 14:19:18 2006) 提到: 上面那个答案是按2点间路径长可以有回路做的，通路定义应该是不算回路的， 邻接矩阵做的就不对了，另外K应该是常数因子把 ☆─────────────────────────────────────☆ dragonflywww (龙飞) 于 (Wed Oct 18 14:25:46 2006) 提到: 用一个bool数组a[n]表示i步可以达到的点 如果求x,y有没有k的路径 初始a[x]=1;其他为0 for(step=0;step for(i = 0; i < n; ++i) { if(!a[x])continue; for(j = 0; j < n; ++j) if(matrix[i][j])b[j] = 1; } 把b复制到a; } 最后判断a[y]==1就存在，否则不存在 ☆─────────────────────────────────────☆ dragonflywww (龙飞) 于 (Wed Oct 18 14:35:04 2006) 提到: 你搞错概念了 另外k是需要输入的不能算常数因子 ☆─────────────────────────────────────☆ Grope (Grope) 于 (Wed Oct 18 23:24:44 2006) 提到: 第2题可以写log(n)的算法 第3题 logk*n^3和k*|e|的算法 ☆─────────────────────────────────────☆ Grope (Grope) 于 (Wed Oct 18 23:31:48 2006) 提到: 不对 我刚刚看了题目 你我都搞错了 是求任意的 不是任意给定的 应该矩阵乘法 N^3logK ☆─────────────────────────────────────☆ Grope (Grope) 于 (Thu Oct 19 11:23:26 2006) 提到: 最终发现只要O(n^3)的复杂度 方法都想复杂了 ☆─────────────────────────────────────☆ dragonflywww (龙飞) 于 (Thu Oct 19 13:23:17 2006) 提到: 你在哪里看的原始的题目? 求任意和给定的算法思想都一样撒 就距阵的k次方可以log一下 你说的n^3是用floyd?只能求无向图的吧? （责任编辑：职场达人） |
