学步园

master method:
T(n)=t(n/2)+lgn T(n)=O(lgn*lgn). n^lg1 = 0 < lgn << n^e for e > 0. the gap between case 2 and case 3. but the factor is lgn, then result is to take an extra logn.
see exercise 4.4-2

工作分配问题是个O（n!）复杂度不是O(n^n)复杂度

二分加线性是个好办法：先用二分查找缩小范围，在小范围内再使用线性查找。 比如100层鸡蛋问题：先用二分缩小范围，13,26,38.。。如果在某一层鸡蛋碎了，则可以使用另一个鸡蛋从上一次尝试成功那一层开始测试到鸡蛋碎了为止。最多8+12=20次。不是最优解，但是是一种方法。

analysis:
when we cannot determine the parameters to analyze the complexity try to find the worst case.

multiple thread algorithm:
T infinity: the critical path line: the longest path in the spawn graph where every node is the parent of another except the first node. that means the nodes in this path cannot be executed parallel. they must executed one by one. so T infinity = the length
of the critical path line. P bar = T1/T infinity.

删除整形数组中的冗余整数：

题目：给一个未排序的n个元素的数组，数组中所有的元素都在1到n之间，删除数组中所有冗余的数字

例如： {1，3，2，3，2，6，4，3}

删除冗余后数组： {1，2，3，4，6}

1. O(n)时间，O(n)空间：

用O(n)空间记录每个元素的出现次数

2. O(n)时间，O(1)空间

在有O(n)空间情况下，可以O(n)空间记录每个数字的出现情况，但是现在没有空间，则需要利用原有数组记录每个数字出现情况，同时为了不改变原有数组的信息，这里将原有数字设为原来数字的负绝对值。因为原来的数组里面是没有负数的，所以可以这样做。

seq[abs(seq[i])-1] = -abs(seq[abs(seq[i]-1)])

void removedup(int *a,int n)
{
    for(int i = 0;i<n;i++)

    {
        a[abs(a[i])-1]=-abs(a[abs(a[i])-1]);
    }

    for(int i = 0;i<n;++i)

    {
        if(a[i]<0)printf("%d\n",i+1);
    }
}

求整形数组中满足两数之和为sum的数值对

方法1：O(n^2)方法，两两相加
方法2：O(nlgn)排序后两边搜。
方法3：O(nlgn)排序后b[i]=sum-a[i],用二分查找找b[i]

PS:微软题目，用bitmap记录每个元素的出现情况（前提是每个元素出现一次，如果多次只能用bucket）
似乎快速找到数值对和为sum的方法只有bucket？
 

【题目35】和为n连续正数序列

//维持low，high两个变量，cnt=low+low+1+...+high
//从低到高
void findSeq1(int n){
    int low = 1;
    int high = 2;
    int cnt = low+high;
    while(low < high && high <=n/2+1){
        if(cnt == n){
            for(int i =low;i<=high;i++)printf("%d,",i);
            printf("\n");
            cnt -= low;
            cnt += high+1;
            low ++;
            high++;
        }
        else if(cnt > n){
            cnt -= low;
            low+=1;
        }
        else{
            high+=1;
            cnt+=high;
        }
    }
}

//从高到低
void findSeq(int n){
    int high =(n+1)/2;
    int low = high - 1;
    int cnt = low+high;
    while(low >= 1){
        if(cnt == n){
            for(int i =low;i<=high;i++)printf("%d,",i);
            printf("\n");
            cnt = cnt - high + low - 1;
            --high;
            --low;
        }
        else if(cnt > n){
            low-=1;
            cnt =cnt - high + low;
            high-=1;
        }
        else{
            low-=1;
            cnt+=low;
        }
    }
}

方法3. 假设 a + (a+1) + ... + b = n 是一个答案，则根据求和公式就是 (a + b) * (b - a

+ 1) / 2 = n, 则 (a+b)和 (b-a+1)分别是2N的一个因子，枚举其中一个，就可以判断求出第二个，

然后求出a和b了。时间复杂度是O(sqrt(n)).2n的因子范围肯定在[2,sqrt(2n)]之间。

   具体步骤：假设（b-a+1)是其中一个因子，可以通过2n%i == 0找到一个因子i,然后根据上面的

（a+b)*(b-a+1)/2 = n的公式可以推导出 2*a*i = 2n - i^2 + i, 因此只要判断a存在正整数解，就

可以知道满足上面条件的2n的另一个因子也是存在的。

注意：归并排序关键在于当一个数组遍历结束了另一个数组可能没有到结尾处，需要将剩余部分放入结果中。

O(1)取min的栈

解题思路：解题的关键是用一个链表结构来存储当前栈

中元素最小值的索引，每压入一个元素，该元素与链表

中记录的当前最小元素索引指向的元素比较，如果小于

最小值，将压入元素的索引存入链表中，否则，将原先

最小值的索引继续存储在链表中。

栈： 8， 3 ， 5， 10， 1

最小元素索引：

        0     1     1      1     5

弹出一个元素后：

栈:  8,    3 ,   5,  10

最小元素索引：

      0， 1 ，  1     1

所以，无论是压入或弹出一个元素，栈都可以准确的获取

到当前栈中的最小值。

http://hi.baidu.com/372405898/blog/item/a208b324ce239a7a35a80f40.html
【网易有道笔试】
1. 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是 这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度
int depth(int nodeId){
    if(nodeId == 0){
        return 0;
    }
    int l = depth(trees[nodeId].left);
    int r = depth(trees[nodeId].right);
    return l>r?l+1:r+1;
}

int findMax(int nodeId){
    if(nodeId == 0) return 0;
    int left = depth(trees[nodeId].left);
    int right = depth(trees[nodeId].right);
    int distance = left + right;
    int l = findMax(trees[nodeId].left);
    int r = findMax(trees[nodeId].right);
    if(distance < l )distance = l;
    if(distance < r)distance = r;
    return distance;
}

构造完美二叉树：
 void build(int node,int l, int r){
    if(l>r)return;
    int m = (l + r) / 2;
    trees[node].value = m;
    if(l<=m-1)
        trees[node].left = 2*node;
    if(m+1<=r)
        trees[node].right = 2*node+1;
    build(node*2,l,m-1);
    build(node*2+1,m+1,r);
}

牛掰，n个节点的二叉树的不同形状个数为：
// f(0) = 1       //0个节点1个形状
// f(1) = 1      //1个节点一个形状
// f(2) = f(1)*f(0) + f(0)*f(1) = 2        //2个节点，1个节点是根节点，根节点左边取一个节点，右边取0个，或者根节点左边取0个节点，右边取1个节点。
// f(3) = f(2)*f(0) + f(1)*f(1) + f(0)*f(2) = 2*1 + 1*1 + 1*2 = 5       //3个节点，一个根节点，根节点左边取2个，右边取0个，或者左边取1个，右边1个，或者左边0个，右边2个
// f(4) = f(3)*f(0) + f(2)*f(1) + f(1)*f(2) + f(0)*f(3) = 5*1 + 2*1 + 1*2 + 1*5 = 14       //4个节点，一个根，左边3个，右边0个，或者左边2个，右边1个，或者左边1个，右边2个，或者左边0个，右边3个。
依次类推，f(5) = f(4)*f(0) + f(3)*f(1) + f(2)*(f2) + f(1)*f(3) + f(0)*f(4)=14+5+4+5+14=42

低数据类型往高数据类型转可以，高的往低的转可能损失精度。

99！中末尾0的个数
统计1-99中5个因子数。
5,10,15,20,25,30....
由于25=5*5，所以有两个5的因子，同样50=5*5*2，有两个5的因子，75=5*5*3，有两个5的因子，所以所有是25的倍数的都有2个或以上的5的因子数。
这样99!中的末尾0的个数为19+3=22（19是由5,10,15,20,25，。。。等产生的，3是由25,50,75等产生的）。

n个m+1字符串相互连接，用图算法floryd算法。求最长路径。
http://blog.csdn.net/acezhangcunyi/article/details/6629965

y个球中找到一个轻的球，要试x次，求y和x的关系:y=3^x
每次分3堆，每次可以排除2/3个球，比如8个球找到一个轻的。

8个分成3份，2份有3个球，一份有2个球。2份3个球先比下，如果一样重，则2个球的那个比下就知道那个轻了。如果不一样重，那个轻的3个球在分成3份，每一份1个球，再拿2个比下，如果一样重，则剩下的那个轻，如果不一样重那么那个轻的就是要求的。

蓄水池算法：http://wansishuang.iteye.com/blog/443902
从很大的流中随机取出m个数，怎么做？有好多种做法：
1. programming pearls的做法是第i个数被选中的概率是1/i。然后位置随机。
2. 对每一个元素产生一个随机数[0-1]，用一个保存m个数的堆维持这些随机数，始终保存最大的m个随机数或者最小的随机数。
3. 蓄水池算法：第i个元素被取到的概率是m/i。和第一个方法差不多。

n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，存储在一个二维数组w[n][n]中，w[i][j] 的值代表编号为i，j的队伍中更强的一支 所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是 4对3， 5对8。。。。。。
胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，
下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4对5,直至出现第一名
编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组result[n]，求出result

//号称google的笔试题目：一般题目，不难 :代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

inline void swap(int & a, int & b){int t= a;a = b;b=t;}

void game(int * order, int n,int (*w)[9],int * result){
    int cnt = n;
    int k = 1;
    int ret = n;
    while(cnt>1){
        for(int i = 1;i<=cnt;i+=2){
            if(w[order[i]][order[i+1]] == order[i+1]){
                swap(order[i],order[i+1]);
            }
            swap(order[k],order[i]);
            result[ret]=order[i+1];
            ret-=1;
            k+=1;
        }
        k=1;
        cnt/=2;
    }
    result[1] = order[1];
}

int main()
{
    const int n = 8;
    int order[n+1]={0,4,3,2,1,5,6,7,8};
    int w[n+1][n+1];
    for(int i= 1;i<=n;++i){
        for(int j = 1;j<=n;j++){
            w[i][j] = order[i]<order[j]?i:j;
        }
    }
    int result[1+n];
    game(order,n,w,result);
    for(int i =1;i<=n;i++){
        printf("%d\n",result[i]);
    }
}

雅虎笔试题：
2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6}可以分成{3，2，4，3，6}
m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3

这道题算法上可能有多种解法，在此只给出时间复杂度是log(n^2）的一种动态规划算法

数组长度的上限是2000，对于组合问题而言是不可解决的，既然不能通过对数组直接进行组合级判断，那么可以考虑获得一个数有多少种组合。具体流程

首先计算出所有数之和A，最大的数M，找出所有大于等于M的A的约数集合S，对数组n进行排序得到有序无重复数组N，因为要求m的最大值，也就是S中的最小值是否合适，穷举S中的每个值k，由小到大，知道找到合适的为止。对于每个k，可以用动态规划的办法得到加和为k并且加数都在N中的组合z1、z2
……..zl，那么现在问题就变成了类似于背包的问题，每个组合都对应一个或者多个N中的数，并且N中每个数的个数是确定的

 //学到一招，从一个数组中找到一组数的和正好为N的办法是背包问题。（牛掰啊，我怎么没想到）。
一个数组[1,2,3,4,5,6],要求和为6的子数组。可以转换成背包问题，W=6，w=[1,2,3,4,5,6],v=[1,2,3,4,5,6]，使得价值最大，因为每个数的v/w=1,所以W=6的情况下最大的价值=6，即我们要求的和。（回去把背包问题再看看）。
但为什么是log(n^2)?假设和为A,则最大约数为A/2,所以背包问题O(n*A/2)，

//0-1背包问题，求1-n里面所有何为m的组合。http://blog.csdn.net/wuzhekai1985/article/details/6728657，这两个算法都是O(2^n)
可以使用原始的动态规划方法，在O(n*m)时间内找到每个组合。

LRU cache可以用双向链表做，怎么用单链表做？

异或是个很好的工具，存在差异就可以异或。

单链表环以及入口：
x+y+nr=2s
x+y=s
nr = x+y
x=nr - y
所以一个在链表口开始走，一个在相遇点x+y处开始走，两个相遇了则是环入口。

解题笔记（26）——排队问题

问题描述：12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种?
12个人从低到高排序，（i,j）表示第i排，第j列。第一个人只能排在（0,0），第二个人可以排在（0,1）或者（1,0），第三个开始如果第0排与第1排得个数相同则只能放第0排，如果不同，可以放第0排或第1排。以此类推。

//以后遇到这类题目要一个个放，不要所有的都一起放，看不出规律，就像小球跳楼梯一样，一层层走，才能看出规律。
 

解题笔记（35）——旋转数组中的最小元素:

  问题描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

有序数组一定要想到用二分，否则就白有序了。
//这个题目只能求最小值与最大值。不能用二分求某一个值。
 

解题笔记（33）——按层次遍历二元树

不错的题目：利用数组记录层次遍历的次序，以及每一层的开始与结束节点
 

一串首尾相连的珠子(m 个)，有N 种颜色(N<=10),
用个数组保存n个颜色的出现次数。
用两个指针front，rear记录子数组的位置，rear一直往后遍历，每次访问一个就记录该元素的颜色直到n种颜色满了。
front一直往前遍历，没遍历一个元素对应的元素颜色个数减一。直到某个颜色的个数为0，次数rear与front间隔即当前的最短长度，继续该操作直到数组尾。
代码：
/*
 *  baidu written test
 *
 *  find min set that include 3 colors
 *
 * */
int minSet(int * a, int n){
    int colors[4];
    for(int i = 1;i<=3;++i){
        colors[i] = 0;
    }

    int front=0 , rear =0, cnt = 0,len = 0,minLen = n+1;
    while(rear<n){
        while(rear < n){
            if(colors[a[rear]] == 0){
                cnt += 1;
                colors[a[rear]] = 1;
                if(cnt == 3)break;
            }
            else{
                colors[a[rear]]++;
            }
            rear++;
        }

        while(front < rear){
            if(--colors[a[front]]<=0)break;
            front++;
        }

        cnt = 0;
        len = rear - front + 1;
        if(len < minLen)minLen = len;
        front = rear = rear + 1;
        for(int i = 1;i<=3;i++){colors[i]=0;}
    }
    return minLen;
}

百度试题讲解：两棵树是否相等的比较

int CompBinTree (BinTree * tree1, BinTree * tree2){ // 嘿嘿，一句return搞定～

  return (!tree1 && !tree2) ||
    (
     tree1 && tree2 && tree1->data == tree2->data &&
     (
      (CompBinTree(tree1->leftChild, tree2->leftChild) &&
       CompBinTree(tree1->rightChild, tree2->rightChild)) ||
      (CompBinTree(tree1->leftChild, tree2->rightChild) &&
       CompBinTree(tree1->rightChild, tree2->leftChild))
      )
     );
}

就是当前节点是否相等，相等则左子树是否相等，然后右子树是否相等，或者左右子树相等。