阅微客栈: 最新帖子

阅微客栈: 最新帖子 http://zhiqiang.org/bbs/ 阅微客栈: 最新帖子 en Thu, 04 Dec 2008 22:50:49 +0000 sntianren 在 "Amazon面试题：八个球中找出重量不同的一个" http://zhiqiang.org/bbs/topic/20#post-263 星期三, 26 Nov 2008 12:01:30 +0000 sntianren 263@http://zhiqiang.org/bbs/ 现在是不知道重量不同的那个球是重一点还是轻一点的。 不可以自己作出假设的吧 jeff lee 在 "求运算次数 - 百度面试题" http://zhiqiang.org/bbs/topic/73#post-262 星期二, 04 Nov 2008 15:03:33 +0000 jeff lee 262@http://zhiqiang.org/bbs/ int min(int n) while(n!=1) { if (n%2==0) n=n/2; else if (n+1/2%2==0) n++; else n--; count++; } count 是主函数定义的变量计算循环次数即运算次数 不知道对不对请不吝赐教 -------计算机初学者 cyberyao 在 "找缺失的数" http://zhiqiang.org/bbs/topic/58#post-261 星期日, 02 Nov 2008 16:41:17 +0000 cyberyao 261@http://zhiqiang.org/bbs/ to lemonutzf 没有看懂，能详细点么 cyberyao 在 "Amazon面试题：八个球中找出重量不同的一个" http://zhiqiang.org/bbs/topic/20#post-260 星期六, 01 Nov 2008 16:47:40 +0000 cyberyao 260@http://zhiqiang.org/bbs/ 2次足够 假设有一个重些。 首先将8个球分成3分，3，3，2 然后天平左边3个，右边3个。 如果左边重，则在其中任选2个称，有重量差别显然可以分辨，一样中的话，没有称的重。 如果右边重，如上做法。 如果一样重，则重的必在2个中，再称一下即可。 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写这么多代码，看晕眼啊。写个算法描述和复杂度出来就得了嘛。对于一维数组，显然有线性复杂度的解法。对于二维数组，别的帖子有讨论。