一些算法题

1. 四则运算表达式求值：

两个栈存储，中缀表达式转为后缀表达式   ok calculate1 & calculate2(其中2是一遍算完)

2. 返回数字中“1”的个数，log n的做法  O(n)的做法      ok  Howmanyone

3. 字符串全排列，如abcd的全排列输出      ok 虽然代码很短 感觉还是有点复杂的(多看几遍)

(allrange)

4. 链表反转     ok     (linkList)  非递归 三个指针；

(参考：看图理解单链表的反转)

(附上大神博客的链表问题汇总：wuchong.me/blog/2014/03/25/interview-link-questions/)

5. O(1)的空间找出一个数组中出现次数大于数组长度一半的数字 腾讯一面题   ok

出现次数大于数组长度一半的数字一定会至少有一次相邻出现。(thenumber)

6. （链表和数组的区别）数组和链表的区别

7. 二分查找  9个数字的数组需要比较多少次？ 能建多少层树就比较多少次啊，如数组长度为10， 最多比较四次（就是查找不到的情况）。

ok binarySearch (不过我写的二分好像有点蠢，回去看看之前记录的笔记。

8. 一共n个台阶，每次上一个或两个，总共有多少种上法？（本质斐波那契 剑指offer题）

f(n) = f(n-2) + f(n-1)

9. 数组和c++中vector的区别：区别

vector支持模板，自动扩容，动态分配内存。(好吧 其实就是灵活的数组)

参考：C++中各个容器的区别1，C++中各个容器的区别2

10. 堆和栈的效率区别：

分配效率：栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。

C/C++内存管理详解

11. 汉诺塔问题：

12. udp如何实现可靠性传输：

udp不属于连接型协议，因而具有资源消耗小，处理速度快的优点，所以通常音频、视频和普通数据在传送时使用UDP较多，因为它们即使偶尔丢失一两个数据包，也不会对接收结果产生太大影响。

传输层无法保证数据的可靠传输，只能通过应用层来实现了。实现的方式可以参照tcp可靠性传输的方式，只是实现不在传输层，转移到了应用层。

如实现 确认机制，重传机制、窗口确认机智。

UDT：

UDT的主要目的是支持高速广域网上的海量数据传输，而互联网上的标准数据传输协议TCP在高带宽长距离网络上性能很差。

顾名思义，UDT建于UDP之上，并引入新的拥塞控制和数据可靠性控制机制。UDT是面向连接的双向的应用层协议。它同时支持可靠的数据流传输和部分可靠的数据报传输。

blog.csdn.net/bytxl/article/details/44979669

---

参考 Gigi9 的简书

http://www.jianshu.com/p/5ecee333814f