阅微客栈: 最新帖子

阅微客栈: 最新帖子 http://zhiqiang.org/bbs/ 阅微客栈: 最新帖子 en Sun, 12 Oct 2008 22:33:34 +0000 sevear 在 "给一些不同的正整数和ｍ，求所有ａ，ｂ使得ａ＋ｂ＝ｍ" http://zhiqiang.org/bbs/topic/76#post-258 星期四, 09 Oct 2008 13:47:32 +0000 sevear 258@http://zhiqiang.org/bbs/ 嗯，排序后查找是啥意思 szuxjq 在 "给一些不同的正整数和ｍ，求所有ａ，ｂ使得ａ＋ｂ＝ｍ" http://zhiqiang.org/bbs/topic/76#post-257 星期四, 09 Oct 2008 03:37:06 +0000 szuxjq 257@http://zhiqiang.org/bbs/ "标记数是否出现过"? 复杂度为　O(n)? 不是很明白哦 zhang 在 "构造最小深度树" http://zhiqiang.org/bbs/topic/77#post-256 星期四, 09 Oct 2008 00:44:43 +0000 zhang 256@http://zhiqiang.org/bbs/ 已知一颗无向无环连通图T的所有顶点和边的信息，现需要将其转换为一棵树，要求树的深度最小，请设计一个算法找到所有满足要求的树的根结点，并分析时空复杂度（描述算法即可，无需代码） 算法：两次深度优先求出Ｔ的直径，直径中间的两点即为所求。 zhang 在 "给一些不同的正整数和ｍ，求所有ａ，ｂ使得ａ＋ｂ＝ｍ" http://zhiqiang.org/bbs/topic/76#post-255 星期四, 09 Oct 2008 00:43:07 +0000 zhang 255@http://zhiqiang.org/bbs/ 排序后查找　O(n\log n). 空间换时间，使用ｍ长数组标记数是否出现过，不计算分配空间消耗的时间外，复杂度为　O(n). zhang 在 "关于STL里重排数组算法random_shuffle()" http://zhiqiang.org/bbs/topic/71#post-254 星期一, 29 Sep 2008 13:21:00 +0000 zhang 254@http://zhiqiang.org/bbs/ 这个先给我们讲讲函数都是啥意思吧，我还看不懂这些源代码。 szuxjq 在 "求一个缺失的数" http://zhiqiang.org/bbs/topic/74#post-253 星期五, 26 Sep 2008 01:34:07 +0000 szuxjq 253@http://zhiqiang.org/bbs/ 这种题目我老是没思路~~ zhang 在 "找重复的数 - MSRA面试题" http://zhiqiang.org/bbs/topic/75#post-252 星期二, 23 Sep 2008 05:33:26 +0000 zhang 252@http://zhiqiang.org/bbs/ 题目是这样的，给定一个包含4300000000个32位整数的顺序文件，请问如何找到一个至少出现两次的整数？ 顺序文件，不允许随机访问。 zhang 在 "求一个缺失的数" http://zhiqiang.org/bbs/topic/74#post-251 星期二, 23 Sep 2008 05:31:41 +0000 zhang 251@http://zhiqiang.org/bbs/ 给你很多很多数（32位整数），求一个不在这些数里的数（亦为32位整数） zhang 在 "求运算次数 - 百度面试题" http://zhiqiang.org/bbs/topic/73#post-250 星期二, 23 Sep 2008 05:30:23 +0000 zhang 250@http://zhiqiang.org/bbs/ 简述：实现一个函数，对一个正整数n,算得到1需要的最少操作次数： 如果n为偶数，将其处以2； 如果n为奇数，可以加1或减1； 一直处理下去。 求最小运算次数。 king 在 "关于STL里重排数组算法random_shuffle()" http://zhiqiang.org/bbs/topic/71#post-248 星期一, 07 Jul 2008 12:42:14 +0000 king 248@http://zhiqiang.org/bbs/ 源码如下： template <class RandomAccessIterator, class Distance> void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last, Distance*) { if (first == last) return; for (RandomAccessIterator i = first + 1; i != last; ++i) #ifdef __STL_NO_DRAND48 iter_swap(i, first + Distance(rand() % ((i - first) + 1))); #else iter_swap(i, first + Distance(lrand48() % ((i - first) + 1))); #endif } 这里的iter_swap(i, first + Distance(rand() % ((i - first) + 1)));能否保证数组是均匀的重排呢？ 如何保证？ Yuanyuan 在 "Amazon面试题：八个球中找出重量不同的一个" http://zhiqiang.org/bbs/topic/20#post-247 星期二, 24 Jun 2008 06:57:18 +0000 Yuanyuan 247@http://zhiqiang.org/bbs/ 看了半天，终于找到一个简单的了，hahahaha 八个秋，一边放四个，看指针往那边倾斜····然后再这样称几次就好了 a piece of cake :-) Yuanyuan 在 "据说是google的电面题目" http://zhiqiang.org/bbs/topic/40#post-246 星期二, 24 Jun 2008 06:53:13 +0000 Yuanyuan 246@http://zhiqiang.org/bbs/ 。。。。。。。。。。。 Yuanyuan 在 "魔方相邻格子能否不同色？" http://zhiqiang.org/bbs/topic/69#post-245 星期二, 24 Jun 2008 06:51:34 +0000 Yuanyuan 245@http://zhiqiang.org/bbs/ 应该可以吧···· Yuanyuan 在 "微软面试题 - 找路径条数" http://zhiqiang.org/bbs/topic/46#post-244 星期二, 24 Jun 2008 06:50:50 +0000 Yuanyuan 244@http://zhiqiang.org/bbs/ 呵呵呵呵····还是不会···· Yuanyuan 在 "Amazon面试题 - 找最短的cover" http://zhiqiang.org/bbs/topic/38#post-243 星期二, 24 Jun 2008 06:49:17 +0000 Yuanyuan 243@http://zhiqiang.org/bbs/ 额滴神呀~~~~ 看着有点像数列， 嗯·····sorry ,i don't know ... 521zheng 在 "算法 - 旋转数组" http://zhiqiang.org/bbs/topic/47#post-242 星期二, 03 Jun 2008 07:35:00 +0000 521zheng 242@http://zhiqiang.org/bbs/ 先整个数组旋转，再分别旋转前k和后n-k个 zhiqiang 在 "尺规作图问题" http://zhiqiang.org/bbs/topic/70#post-241 星期六, 24 May 2008 02:22:17 +0000 zhiqiang 241@http://zhiqiang.org/bbs/ 给你一个三角形ABC，请用圆规和尺找出点P，保证三角形ABP、ACP和BCP周长相等 。 apunix 在 "微软面试题 - 找路径条数" http://zhiqiang.org/bbs/topic/46#post-240 星期二, 20 May 2008 01:07:15 +0000 apunix 240@http://zhiqiang.org/bbs/ void FindPath(Graph& G, int v, int vj, Edge* &path, int l) //G是图，v是当前结点，vj是目标结点，path保存当前路径的数组，l是当前路径的长度 { if(v == vj) { printPath(path, l); return; } for(Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) { if(!InPath(G.ToVetex(e))) { //Inpath判断下一搜索结点是否已经在路径中出现过 l++; path[l] = G.ToVetex(e); FindPath(G, G.ToVetex(e), vj, path, l); l--; //恢复路径 } } 就是一个回溯法搜索的过程 zhshlin 在 "魔方相邻格子能否不同色？" http://zhiqiang.org/bbs/topic/69#post-239 星期日, 27 Apr 2008 05:31:05 +0000 zhshlin 239@http://zhiqiang.org/bbs/ yes you can szuxjq 在 "魔方相邻格子能否不同色？" http://zhiqiang.org/bbs/topic/69#post-234 星期六, 26 Apr 2008 04:22:09 +0000 szuxjq 234@http://zhiqiang.org/bbs/ 从原始的一面一色状态的魔方，能否扭转到任两相邻格子都是不同的颜色呢？ lemonutzf 在 "微软面试题 - 找路径条数" http://zhiqiang.org/bbs/topic/46#post-233 星期日, 13 Apr 2008 16:20:31 +0000 lemonutzf 233@http://zhiqiang.org/bbs/ 反向迭代，有点类似与dijkstra求最短路径 lemonutzf 在 "算法 - 旋转数组" http://zhiqiang.org/bbs/topic/47#post-232 星期日, 13 Apr 2008 16:16:41 +0000 lemonutzf 232@http://zhiqiang.org/bbs/ 生成元就是前gcd(n,k)个数 lemonutzf 在 "判断一个图是否为一个二叉树" http://zhiqiang.org/bbs/topic/59#post-231 星期日, 13 Apr 2008 16:10:32 +0000 lemonutzf 231@http://zhiqiang.org/bbs/ v=e+1 d(v)<=3 lemonutzf 在 "自然数按一定运算变为1的运算次数" http://zhiqiang.org/bbs/topic/61#post-230 星期日, 13 Apr 2008 16:05:18 +0000 lemonutzf 230@http://zhiqiang.org/bbs/ zhang 的算法对3来说就不是最优。得稍微修改一下。从高位做，对于第一段连续的1，如果个数>3用＋1除以2，<3用-1除以2。以后的连续1段用 zhang的策略就行 lemonutzf 在 "求部分有序的数列的中位数" http://zhiqiang.org/bbs/topic/62#post-229 星期日, 13 Apr 2008 15:47:51 +0000 lemonutzf 229@http://zhiqiang.org/bbs/ 另外，两组长为n的各自有序的数组，找到在两者里面第k大的成员，时间复杂度是lgk * lgk lemonutzf 在 "求部分有序的数列的中位数" http://zhiqiang.org/bbs/topic/62#post-228 星期日, 13 Apr 2008 15:46:23 +0000 lemonutzf 228@http://zhiqiang.org/bbs/ wsamc 的算法还可进一步优化：如果sum(a的位置) > n^2/2，将所有 {i | ai>=a } 所对应的序列长度减半. 可改成：将所有 {i | ai>=a } 和 {i | i< a的位置-(sum(a的位置)-n^2/2) } 剪去 lemonutzf 在 "算法 - 均分数组" http://zhiqiang.org/bbs/topic/49#post-227 星期日, 13 Apr 2008 08:15:04 +0000 lemonutzf 227@http://zhiqiang.org/bbs/ 其实就是子集和问题。 mathena 说对了，他们的平均值, 就是数组的平均值. 把数组中所有数都减去数组的平均值，这样问题就变成求一个子集其和为0的问题。 lemonutzf 在 "Amazon面试题 - 找最短的cover" http://zhiqiang.org/bbs/topic/38#post-226 星期日, 13 Apr 2008 07:32:23 +0000 lemonutzf 226@http://zhiqiang.org/bbs/ LCS ＋标记起始位置 lemonutzf 在 "找缺失的数" http://zhiqiang.org/bbs/topic/58#post-225 星期日, 13 Apr 2008 07:15:38 +0000 lemonutzf 225@http://zhiqiang.org/bbs/ 判断第一位是0 or 1，并计数，根据计数和n的奇偶性来判断缺失的数所在的集合 继续判断第二位。。。。。 复杂度 n + n/2 + n/4 + .. < 2n lemonutzf 在 "数组中元素和最接近于0的子数组" http://zhiqiang.org/bbs/topic/67#post-224 星期日, 13 Apr 2008 06:50:47 +0000 lemonutzf 224@http://zhiqiang.org/bbs/ 转化成全连通有向图，再用floyd算法（判定条件改成abs最小)，注意排除回路。时间复杂度应该是O(n^3). Wanting的算法没仔细看。不过，感觉这个问题不大可能有O(n^2)的解 szuxjq 在 "数组中元素和最接近于0的子数组" http://zhiqiang.org/bbs/topic/67#post-223 星期六, 12 Apr 2008 08:33:48 +0000 szuxjq 223@http://zhiqiang.org/bbs/ to Wanting 老兄你blabla写这么多代码，看晕眼啊。写个算法描述和复杂度出来就得了嘛。对于一维数组，显然有线性复杂度的解法。对于二维数组，别的帖子有讨论。 szuxjq 在 "How to in-place right-rotate a two dimensional array?" http://zhiqiang.org/bbs/topic/68#post-222 星期六, 12 Apr 2008 05:01:06 +0000 szuxjq 222@http://zhiqiang.org/bbs/ 某知名网站的讨论， For example, given a MxN (3x4) two dimensional array 1, 2, 3, 4 5, 6, 7, 8 9,10,11,12 You need to rearrange it into: 9 , 5, 1, 10, 6, 2, 11, 7, 3, 12, 8, 4 Write a function to do it in-place. e.g. M=3, N=4, and a memory block contains: [1,2,3,4,5,6,7,8,9,10,11,12] You need to change the memory block into [9,5,1,10,6,2,11,7,3,12,8,4] "In-place" means memory constaint is O(1). lemonutzf 在 "据说是google的电面题目" http://zhiqiang.org/bbs/topic/40#post-221 星期五, 11 Apr 2008 03:37:53 +0000 lemonutzf 221@http://zhiqiang.org/bbs/ 第一题 如果不考虑整型表示范围（题目似乎也没强调），那么有个很简单的方法： 遍历一遍，找到最小值min，输出 min-1 就哦了。 如果有范围，比如sizeof(int)=4，Wanting 的bit标记法应该可以很容易解1GB. 而对于10MB的情况，bit标记法最坏情况下要pass 50遍。用取模MOD 做可能会快一些 Sainkei 在 "据说是google的电面题目" http://zhiqiang.org/bbs/topic/40#post-220 星期四, 10 Apr 2008 03:41:48 +0000 Sainkei 220@http://zhiqiang.org/bbs/ sorry,上面所说是错的。汗！ 应该用bit建立一个二叉树来解 521zheng 在 "面试题 - 旋转排序数组的二分查找" http://zhiqiang.org/bbs/topic/48#post-219 星期四, 10 Apr 2008 02:38:47 +0000 521zheng 219@http://zhiqiang.org/bbs/ 为何不找到分界点，然后判断在左侧还是右侧查找呢？ 测试通过的算法 int binarysearch(int key, int* arr, int n) { int low = 0; int high = n-1; while(low<=high) { int mid = (low+high)/2; if(arr[mid] == key) return mid; if(arr[mid]<key) low = mid+1; else high = mid-1; } return -1; } int getoffset(int *arr, int n) { if(n<=1) return 0; if(arr[0] <arr[n-1])return 0; int low =0; int high= n-1; while(high-low>1) { int mid = (low+high)/2; if(arr[mid] >=arr[low]) low = mid; else high = mid; } return high; } int searchlooparray(int key, int * arr, int n) { int offset = getoffset(arr,n); if(offset ==0) return binarysearch(key, arr, n); if(key>=arr[0] && key <=arr[offset-1]) return binarysearch(key, arr, offset); else if(key>=arr[offset] && key<=arr[n-1]) { int result = binarysearch(key,arr+offset, n-offset); return result==-1 ? result:offset + result; } else return -1; }