AAAA
gaotong1991 · 共 38 篇文章
二叉树非递归先序遍历
二叉树的先序遍历使用递归很简单,代码如下: void preOrder(TNode* root) { if (root != NULL) { Visit(root); preOrder(root->left); preOrder(root->right); } } 先访问跟节点,然后访问左节点,再访问右节点。如果不用递归,那该怎么做呢?仔细看一下递归程序,就会发现,其实每次都是走树的左分支(left),直到左子树为空,然后开始从递归的最深处返回,然后开始恢复递归现场,访问右子树。 其实过程很简单:一直往左走 root->left->left->left…->null,由于是先序遍历,因此一遇…
2014-06-14 14:04 · 算法之道 · 评论(0)
你必须知道的Java并发编程基础知识
1. 并发 1.1. 什么是并发? 并发是一种能并行运行多个程序或并行运行一个程序中多个部分的能力。如果程序中一个耗时的任务能以异步或并行的方式运行,那么整个程序的吞吐量和可交互性将大大改善。现代的PC都有多个CPU或一个CPU中有多个核。是否能合理运用多核的能力将成为一个大规模应用程序的关键。 1.2. 进程 vs. 线程 进程是以独立于其他进程的方式运行的,进程间是互相隔离的。一个进程无法直接访问另一个进程的数据。进程的资源诸如内存和CPU时间片都是由操作系统来分配。 线程又被称为轻量级进程。每个线程有它独自的调用栈, 但是在同一进程下的线程又能互相访问它们间的共享数据。每个线程都有它独…
2014-05-21 22:00 · 编程吧! · 评论(1)
编程之美-阶乘末尾0的个数
这个题目是编程之美一书中给出的题目。 给定一个整数N,那么N的阶乘N!末尾有多少个0? 比如:N=10,N!=3628800,N!的末尾有2个0。 1) 递推 考虑阶乘的计算很容易溢出,直接计算阶乘肯定不合适。而每次相乘是否会有新的0产生,只和前一个阶乘的最后一位有关。因此只记录前一个阶乘0的个数和最后一位,就可推出后面的。 代码如下: 01 int countZero(int N) { 02 int ans = 0; 03 int lastBit = 1; //上一个阶乘 的最后一位数字 04 for (int i = 2; i <= N; i++) { 05 int cnt = 0;//…
2014-04-15 17:22 · 算法之道 · 评论(3)
倒水问题-经典面试题
原文: http://www.acmerblog.com/pour-water-problem-5615.html 倒水问题 这个题目的版本非常之多,有微软版的,腾讯版的,新浪版的等等,最常见的是给你一个容量为5升的杯子和一个容量为3升的杯子,水不限使用,要求精确得到4升水。问题会有两种形式: 1) 直接以简答的方式给定方案 这个比较简单,即便是不知道什么原理,也可以很快凑出来。假设两个杯子分别为x 5升杯, y 3升杯 : 装满 x ; x -> y ;清空Y ;x -> y ;装满 x ;x -> y 解决方案会有多个,写出一个即可。 2) 编程实现 解法也比较多,我首先想到的DFS(深…
2014-04-11 12:19 · 算法设计 · 评论(0)
寻找二叉树两个节点的最低公共祖先
给定一棵树,同时给出树中的两个结点(n1和n2),求它们的最低公共祖先。也就是常见的LCA(Lowest Common Ancestor )问题。 看下面的图就明白了: 方法一 下面是一个简单的复杂度为 O(n) 的算法,解决LCA问题 1) 找到从根到n1的路径,并存储在一个向量或数组中。 **2)**找到从根到n2的路径,并存储在一个向量或数组中。 3) 遍历这两条路径,直到遇到一个不同的节点,则前面的那个即为最低公共祖先. 下面的C++的程序实现 01 // O(n) 解决 LCA 02 #include <iostream> 03 #include <vector> 04 using…
2014-04-09 22:56 · 算法之道 · 评论(0)
扔鸡蛋问题(Egg Dropping Puzzle)
据说这是一道google的面试题. 看似是一个智力题,实际是编程题。 两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。现有座36层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置,可以摔碎两个鸡蛋,要求用最少的测试次数。 1 如果你从某一层楼扔下鸡蛋,它没有碎,则这个鸡蛋你可以继续用 2 如果这个鸡蛋摔碎了,则你可以用来测试的鸡蛋减少一个 3 所有鸡蛋的质量相同(都会在同一楼层以上摔碎) 4 对于一个鸡蛋,如果其在楼层i扔下的时候摔碎了,对于任何不小于i的楼层,这个鸡蛋都会被摔碎 5 如果在楼层i扔下的时候没有摔碎,则对于任何不大于i的楼层,…
2014-04-09 09:58 · 算法设计 · 评论(0)
Lua银弹之table
来做一个Brain Storm,细数一下你曾经使用过的数据结构: map, hash_map, array, queue, stack, heap...或许还有很多其它的数据结构,相信在开始接触每个数据结构的时候都花了很多的时间去了解它们的特性,因为他们每一种都是足够的复杂。那么作为一个简单至极的语言,Lua是怎么实现这些的呢?答案是Lua中根本没有这些数据结构,汗了吧!更汗的是,Lua其实只一个真正意义上我们所谓的数据结构table,所以在这个简单的语言中我们可以使用的只能table这一种数据结构,下面我们来看一下这个神奇的table吧。 1, 我们可以使用table来实现一个数组 arr…
2014-04-07 22:48 · 算法设计 · 评论(0)
聆听大师---Perl发明人及开源软件先锋Larry Perl
学习和使用 #Perl# 多年,今天终于有幸在北京的Perl Workshop见到了Perl的发明人Larry Wall。Larry对50年代到现今各种编程语言的设计哲学信手捻来,其中有吐槽有爆料,会场里笑声迭起;还娓娓道来开源社区的协作方式:不做dictator,讲究empathy; 在Q&A和demo环节也感受了Larry对于Perl6的期许与passion。 另外,在Q&A环节中,我之前在线提出三个问题被选中,在现场又提了一个关于multiple-core programming的问题。Larry对这些都做了详尽的回答,让人如沐春风。 现场拍了一些照片: https://www.dro…
2014-04-07 22:46 · 评论(1)
动态规划-01背包问题
在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 注意:在本题中,所有的体积值均为整数。01的意思是,每个物品都是一个整体,要么整个都要,要么都不要。 1)最优子结构 考虑所有物品的子集合,考虑第n个物品都有两种情况: 1. 包括在最优方案中 2. 不在最优方案中 因此,能获得的最大价值,即为以下两个值中较大的那个 1) 在剩下 n-1 个物品中(剩余 W 重量可用)的情况能得到的最大价值 (即排除了 第n个物品) 2) 第n个物品的价值 加上 剩下 剩下的 n-1 个物品(剩余W- wn的重量)能得…
2014-04-06 22:24 · 评论(0)
算法分析(2)-递归的时间复杂度
在前面的文章中,我们讨论了 循环的时间复杂度分析 。很多算法是具有递归性质的,当我们的分析的时候得到的是递推关系的时间复杂度。 例如,在归并排序中,对一个给定的数组进行排序,我们把它分成两半,并对这两半递归地重复这个过程。最后,我们合并结果。时间复杂度可以写成: T(n) = 2T(n/2) + cn. 还有许多其他算法,如二分查找,汉诺塔等都可以递推公式。 主要有三种方式来递归公式。 1)替代法 :我们做一个猜测的解,然后用数学归纳法证明的猜测是正确的或不正确的。 例如:T(n) = 2T(n/2) + n。 我们猜测解为:T(n) = O(nLogn). 现在用数学归纳法来证明我们的猜测…
2014-04-04 12:08 · 评论(0)
二分查找-你能完全正确吗?
先给大家贴个题,热乎的,最新的阿里2014实习生笔试题(2014.3.29)。 很经典的二分查找,找出其中的bug。 题目让指出bug,我想应该是具体的说明错在哪,怎么错了。 应该是有两处bug: 1) while 循环处条件有错,如果只有一个元素,则返回的肯定的-1,导致答案错误。应改为 end >= start 2) 程序会进入死循环。考虑 start =1, end= 2. 假设 middle = 1. 若每次都执行 start=midlle, 即进入死循环。应改为 start = middle+1; end = middle-1; 另外,本题没有说已排序的数组是递增还是递减的。我在答…
2014-04-01 10:33 · 算法设计 · 评论(5)
常见的概率相关面试题
在笔记题中概率相关的数学题,也有部分编程题,出现的还是挺多的。概率在生活中的应用较多,同时也可以综合考查面试者的思维能力、应变能力、数学能力。在这里整理了一些概率相关的笔试题和大家分享,此文不涉及编程题,都是一些和生活相关且很有趣的概率题。所有的分析都和背景颜色设置一样了,大家先思考,然后选中就可以看到分析了。 题目1 假设你参加了一个游戏节目,现在要从三个密封的箱子中选择一个。其中两个箱子是空的,另一个箱子里面有大奖(你偶像的签名^^)。你并不知道奖在哪一个箱子里,但主持人知道。游戏节目的主持人先要你选择一个箱子,接着他把你没有选的空箱子打开,以证明它是空的。最后主持人给你换箱子的机会,你…
2014-03-30 22:14 · 算法之道 · 评论(0)
快慢指针在链表中的应用
快慢指针也是面试中的一个常考知识点,主要是链表的问题中应用较多。 1. 判断链表是否存在环 设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下: 01 int isExitsLoop(LinkList L) { 02 LinkList fast, slow; 03 fast = slow = L; 04 while (fast && fast->next) 05 { 06 slow = slow->next…
2014-03-27 23:00 · 算法设计 · 评论(0)
我不懂技术,所以阿里技术是BAT中最强的
这周二,马云在北大的演讲 我不懂技术,所以阿里技术是BAT中最强的 人们一直认为阿里巴巴的技术可能是中国互联网中最差的,百度李彦宏懂技术、马化腾学技术,只有马云什么都不学,好像认为马云很差。 其实正因为我不懂技术,我们公司技术才最好。不懂技术,在于我们对技术的尊重,我们没法吵架。如果我很懂技术,我们公司的技术人很就会悲摧,我三天两头会告诉他们应该这样应该那样,因为我不懂,我才会好奇敬仰的看着他们说就应该这么做。 事实上也是这样,阿里巴巴的云计算在中国能够发展成这样,在全世界发展成这个样子,重要的原因是因为我不懂。这个不是笑话。王坚知道,我们六年以前,整个阿里决定未来的发展方向是哪的时候,我们…
2014-03-23 22:18 · 评论(11)