堆只能是动态内存分配。malloc和new等实现。 栈一般是静态内存分配，如函数中局部变量。但是栈也可以用alloc进行动态内存分配，这时函数退出时内存自动回收。但是不建议使用。

第1层1个元素 第2层2个元素 ... 第h层2h−12^{h-1}2h−1个元素 平均查找长度 1∗1+2∗2...+h∗2h−1N,h=log2(N+1)\frac{ 1*1+2*2...+h*2^{h-1} }{N},h=log_{2}(N+1)N1∗1+2∗2...+h∗2h−1​,h=log2​(N+1) 当规模小时比如12个元素，求平均查找长度。这时第h层不满，所以不能套用这个公式，但是可以用同样的方法手工计算。 第1层1个元素 第2层2个元素 第3层4个元素 第4层5个元素 平均查找长度 (11+22+34+45)/12=3.08

顺序查找 折半查找 斐波那契查找。将一个序列（长f(n)）按斐波那契数拆分成两个序列（f(n-1)和f(n-2)）。 插值查找。 m = start + (end - start) * (findVal - arr[start]) / (arr[end] - arr[start]) findVal如果在序列范围内，则(findVal - arr[start]) / (arr[end] - arr[start])范围[0,1] 再乘以(end - start)，范围[0, end - start] 再加上start，范围在[start, end] 线性索引查找。 稠密索引，每个记录都建索引。 分...

找满足和为target的两数下标，最主要是要能快速根据数找到下标。 可以先建立数与下标的映射map。然后用i遍历数组，根据target与当前数计算出另一个数，然后在map中找，能找到，则很快能得到两数下标。 class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { map<int,int> numIndexMap; vector<int> ret; for (int i = 0; i < (int)numbers.size(); i...

以入栈3 2 1 5 1为例，维护两个栈，分别是正常栈stk和栈顶时刻为最小元素的栈minstk，观察入栈过程中两个栈的变化。栈顶在右边。 入栈原则: 比较入栈元素和minstk栈顶元素，小的入minstk。  初始状态: stk: minstk: 入栈3： stk:    3 minstk: 3 入栈2： stk:    3 2 minstk: 3 2 入栈1： stk:    3 2 1 minstk: 3 2 1 入栈5： stk:    3 2 1 5 minstk: 3 2 1 1 入栈1： stk:    3 2 1 5 1 minstk: 3 2 1 1 1  可以看出在整个入栈...

用减法来实现除法，a/b就是看a可以最多减去多少个b。 优化，可以对b进行左移n位得到c，只要c比a小。这样a可以一次减去c，也即一次减去了2的n次方个b。  class Solution { public: int divide(int dividend, int divisor) { int tag = 1; if (dividend < 0) { tag = -1; dividend = abs(dividend); } if (divisor < 0) { tag *= -1; divisor = abs(divisor); } int divisorTmp = divis...

遍历压栈序列，压入初始为空的栈stk中。在此过程中，每压入一个元素时  判断stk栈顶元素是否和出栈序列首元素相等 如果相等，删除栈顶元素，同时删除出栈序列首元素（实际实现时不用删除，用下标++访问即可）  循环这两步操作，直到不满足相等条件。 遍历完压栈序列时，stk为空，说明满足。  class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { if (pushV.size() == 0) { return false; } stack<int> st; fo...

快速幂。思路就是增大底数减少循环次数。下面用^表示指数运算，讨论a^b非负指数情况。 当b为偶数时，a^b=(a^2)^(b/2) 当b为奇数时，a^b=a(a^2)^(b/2) 程序实现时，奇偶判断可以用位与运算，除2可以用位移运算，负指数转化成正指数。 如果用递归实现看起来会更直观，下面用循环实现。  class Solution { public: double Power(double base, int exponent) { int tag = 0; if (exponent < 1) { exponent *= -1; tag = 1; } double ret = 1; ...

递增数列加法转乘法,除2转位移 结合二进制位运算用加法来实现两数相乘（与十进制乘法转加法类似）   class Solution { public: int multi(int a, int b) { int ret = 0; (a & 1) && (ret += b); a >>= 1; b <<= 1; a && (ret += multi(a, b)); return ret; } int Sum_Solution(int n) { return multi(n, 1 + n) >> 1; } }; int ma...

sum=a^b为不考虑进位的情况下进行了加法运算 carry=(a&b)<<1求出了每一位的进位，如果进位不为0,加到sum上，重新求得sum和carry。如此循环直到进位为0  class Solution { public: int Add(int num1, int num2) { int a, b; while (true) { a = num1 ^ num2; b = (num1 & num2) << 1; if (!b) { break; } num1 = a; num2 = b; } return a; } };

其实第1种情况是第2种情况的特例，只用第2种情况的证明，不管i是否为1逻辑上也是OK的。  class Solution { public: int NumberOf1(int n) { unsigned int v1 = n; int cnt = 0; while (v1) { cnt++; v1 = v1 & (v1 - 1); } return cnt; } };

将数组进行排序，排序的原则是对于数字a和b，如果ab<ba，则a在b前。   将数组中的元素连起来即可。    注意计算ab和ba过程中的性能优化，避免重复计算，包括指数运算和求位数，也可以选择性能高的排序算法。  int g_tenPow[] = { 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, }; class Solution { public: int calcDecimalLen(int n) { int cnt = 1; while (n /= 10) { cnt++; }...

统计1到N的所有数中1出现的次数，只需要计算1出现在每一位上的次数 分析：N有n位，将n位数记作(x1)...(xi-1)(xi)(xi+1)...(xn), 前i-1位组成的数记作X前, 后n-i位组成的数记作X后。  一般地，求第i位为1时的数字个数，分三种情况  N的第i位为0：X前要小于(x1)...(xi-1)，X后随意，共((x1)...(xi-1) )*10的n-i次方个 N的第i位为1: 两种情况A. X前小于(x1)...(xi-1)，X后随意，同上; B. X前为(x1)...(xi-1), X 后小于等于(xi+1)...(xn),共(xi+1)...(xn) + 1个 ...

快慢指针法 快指针速度是慢指针速度的2倍。如图所示，设快慢指针相遇在C点，相遇时快指针走过2S，则慢指针走过S。 慢指针走了S=a+b 快指针走了2S=a+b+n(b+c) 可得a=(n-1)(b+c)+c 也就是说a等于若干圆周加上c。那让两个指针同时在A点和C点出发，必然相遇在B点（入口）   class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { ListNode* fast = pHead; ListNode* slow = pHead; while (fast && fast->...