所谓曼哈顿距离：
假设点A的坐标为x0,y0, 点B的坐标为x1,y1
那么A和B的曼哈顿距离为： abs(x0-x1)+abs(y0-y1).

现在有这样一个题目：
平面上有n个点，给出他们坐标（可能有多个点的坐标是一样的）。 一次操作可以将一个点上移、下移、左移或者右移一个单位。
现在需要平面上某个坐标上至少有k个点，问需要最好的操作次数？

solution:

Let's fix some K and try to find the best way to gather some K checkers in the same cell. To do this, we first consider a very slow approach: i

Given an expression remove the unnecessary brackets in it with out creating an ambiguity in its execution.
input                                  output
ex1: (a+(b)+c)                     a+b+c
ex2: (a*b)+c 

先看这个题目，再看这个题目的推广。
你有两个杯子，容量分别是a和b，你周围有自来水管（水无限），问能否量出c升水，也就是要求最终两个杯子中的水加起来是c升(c<=a+b)
解：
（1）设a和b的最大公约数是x，那么能量出c，当且仅当x能整除c。因为gcd(a,b)=x，则必然存在p和q，使得a*p+b*q=x。可以看到p和q必然一正一负，我们假设q为负（p为负的情况分析类似）。
那么我们先考虑如何量出x升水，从等式上看，过程就是我们设法灌满a水杯p次，再倒出q次b升水，剩下的就是恰好x升水。
举个例子吧：假设a=4，b=9，则b-2*

两个已排序数组p和q，假设将他俩合成一个有序数组，求合并后的数组的第k小元素？

首先可以明确的是，不要幻想真的把p和q合并成一个新的有序数组，时间复杂度太高，面试官不会满意的。
下面给出3中解法：
首先说明符号的使用：
$ : 代表一串有序整数，个数不限
& : 代表一串有序整数，个数不限
~ : 代表一串有序整数，个数不限
# : 代表一串有序整数，个数不限
len($$$)表示$$$这串整数的个数,每个$可以代表不同的整数串。
a,b,c,d,u,v代表整数
（一）
假设
数组p表示为：$$$a

一块矩形的巧克力，初始时由N x M个小块组成。每一次你只能把一块巧克力掰成两个小矩形。最少需要几次才能把它们掰成N x M块1×1的小巧克力？
    答案：N x M - 1次显然足够了。这个数目也是必需的，因为每掰一次后当前巧克力的块数只能增加一，把巧克力分成N x M块当然需要至少掰N x M - 1次。


A、B两人分别在两座岛上。B生病了，A有B所需要的药。C有一艘小船和一个可以上锁的箱子。C愿意在A和B之间运东西，但东西只能放在箱子里。只要箱子没被上锁，C都会偷走箱子里的东西，不管箱子里有什么。如

一个数组，找出一个递增的子序列，要求其和最大。与最长递增子序列很像，也存在nlogn算法
一个例子为：A= [50，1，2，67，30]
那么最优的序列为50，67
这个题和最长递增子序列很类似，很容易想出O(n^2)的dp算法，这里就不说了。事实上该问题存在o(n log (n))的算法。
首先计算原数组每个元素对应的rank值，上述例子为
A =     [50,1,2,67,30]
rank =[4, 1,2,5,   3 ]
A.length = n
构建一个线段树，根节点表示区间[1,n]，叶节点不是区间，是一个rank。线段树中每个节

int calc(int n,int m){
    int re=1;
    while(m){
       if(m&1)
          re*=n;
       n*=n;
       m>>=1;
    }
    return re;
}

实现八进制字符串 转变为整数
        int[] masks = { 0, 1, 2, 3, 4, 5, 6, 7};
        int re = 0;
        for (int i = 0; i < s.length(); i++)
            re = (re << 3) | masks[s.charAt(i) - '0'];
        System.out.println(re);

实现16进制字符串转变为整数

 

一. asscii to double
double atof(char *s){
    double val,power;
    int sign=1;
    if(*s=='-')
        sign=-1;
    if(*s=='-'||*s=='+')
        s++;
    for(val=0;isdigit(*s);s++)
        val=val*10+*s-'0';
    if(*s=='.')
   

我们已经得出一般性的结论,是一组非常优美对称的组合公式,并可以适用于N维的情况.
n个点最多把直线分成C(n,0)+C(n,1)份；
n条直线最多把平面分成C(n,0)+C(n,1)+C(n,2)份；
n个平面最多把空间分成C(n,0)+C(n,1)+C(n,2)+C(n,3)=(n³+5n+6)/6份；
n个空间最多把“时空”分成C(n,0)+C(n,1)+C(n,2)+C(n,3)+C(n,4)份.

emai:qingshizhuoren@163.com