题目：一个数组里，除了三个数是唯一出现的，其余的都出现偶数个，找出这三个数中的任一个。比如数组元素为【1, 2,4,5,6,4,2】，只有1,5,6这三个数字是唯一出现的，我们只需要输出1,5,6中的一个就行。

某米的面试题，这是鄙人最喜欢的几个公司之一，和某歌公司有这相似的企业文化，当年google音乐产品经理的洪峰也转去小米，非常佩服这种为祖国事业奋斗的牛人！

这种找数题的思路就是，首选用位运算。当然这一般是优于建个数组数count，或者n^2以上的朴素算法的。

先是所有数疑惑，模仿找唯一出现一次的数的思路，结果是这三个数的异或值。然后如果找到两个数异或值，这两个再异或结果就出来了，但是两个数的异或值想了下，没思路，于是这条路放弃。

然后分析三个数异或真值表，发现奇数个1异或为1，偶数个1异或为0，那么我在想，由于三个数不可能完全相同，甚至不可能有两个相同，于是把结果为0 的 011 101 110 和异或结果为1的 001 100 010这六种情况至少出现
一次，于是方法形成，遍历一遍，遇到0，将该bit为0的全部异或，如果不等于之前n个数异或result，就继续，否则返回，遇到1，将该bit为1的全部异或，同样处理，直到遍历完最多32bit，如果是*86系统的话，

时复O(n), n+32n 空复 O(1)

题目来源：http://blog.csdn.net/wypblog/article/details/8032898#reply

Posted by richard爱闹 - 7月 25 2014
如需转载，请注明： 本文来自 Richard

这道题目，让我第一反应是跳兽问题，但是具体忘记了 ，解法也忘了。
看起来就是可以映射到矩阵链的，于是构建递推方程，中间的k似乎不能等于两个端点，然后单独处理这种可能一次跳过的，循环记住第一重是长度，保证子问题已解出。

小心翼翼码完，发现二维全局变量好像超了空间，除了runtime，于是改heap ，超了空间，后来有人说有greedy算法，我目前还没想到。。。。

class Solution {
public:
    int MAX=1000000;
    bool canJump(int A[], int n) {
        if(n==0) return 0;
        int **dp=new int*[n];
        for(int i=0;i<n;i++)
            dp[i]=new int[n];

        for(int i=0;i<=n-1;i++)
            dp[i][i]=0;
        for(int l=2;l<=n;l++)//chain length
        {
            for(int s=0;s<=n-1;s++)//start indx
            {
                int e=s+l-1;
                if(e>n-1)
                    break;
                if(A[s]>=l-1)//min 1
                    dp[s][e]=1;
                else
                {
                    int min=MAX;
                    for(int k=s+1;k<=e-1;k++)
                    {
                        if(min>dp[s][k]+dp[k][e])
                            min=dp[s][k]+dp[k][e];
                    }
                    dp[s][e]=min;
                }
            }
        }

        int minjump=dp[0][n-1];


        for(int i=0;i<n;i++)
            delete[] dp[i];
        delete[] dp;

        if(minjump!=MAX) return true;
        else return false;
        //return minjump;
    }
};

后来还是看了题解，贪心算法没有想到，也不知道怎么和贪心的模板题联系，例如活动安排，普通背包基于排序的，Dijstra Huffman基于选择最小(大)，这里就是用last记录 ret次可以跳到的最大，然后cur则是多跳
一步，ret+1的最远，如果当前遍历的i>last, 说明我已经超过当前最远了，那么需要看是否加一步能跳的更远，如果不能就不可能再往后跳了，否则就更新last为多跳一步，ret也++，但是 感觉还是不很make sense
暂时这么理解了。

int jumpgame(int *a, int n)
{
    int last=0,cur=0,ret=0;
    for(int i=0;i<n;i++)
    {
        if(i>last)
        {
            if(cur==last)
                return -1;
            last=cur;
            ret++;
        }
        if(cur<i+a[i])
            cur=i+a[i];
    }
    return ret;
}

Posted by richard爱闹 - 7月 25 2014
如需转载，请注明： 本文来自 Richard

简而言之，就是linklist的partition函数，没错快排用到的partition，于是想里面for后移用next，只是swap要注意一下，
于是我写了一个node->val交换的swap，因为这个是左值，所以可以调用C++11的引用交换的swap，但是发现WA了，后来仔细看题，发现居然
要稳定的排序，这，快排本身这种跳跃交换就是不稳定的，我就觉得很蛋疼，后来想想终于明白为啥要加稳定排序这个要求了，我a[j]>=x的话，直接后面加，
不交换肯定稳定，但是如果交换，有跳跃，那么主要是a[i+1]要交换到>=x区间的最后一个，因此导致原来的a[i+1]不能保持和已排序的>=x里的数
稳定的关系，但是linklist不是可以有高效插入这种性质么？直接把a[j]查到a[i] a[i+1]不就可以了，于是终于明白之前Qsort的linklist其实严格意义不算正确，
因为还是基于数的交换，于是开始写逻辑。

但是发现逻辑不好全部写对。要记录inext,jnext,jprev, 等等，还要处理一堆特殊情况。先把一般的写下，但是发现lumoto的partition会有子交换，
这种对于swap当然很好解决，但是linklist很蛋疼，我模拟一遍结束发现结果乱七八糟的，也没分析出原因，于是开始单独处理一下，其实子交换就是
不用动了o(╯□╰)o指针改next的next就是了。

但是发现还是挂了，[2,1] 2这个case，后来模拟一遍，发现head丢了，于是分析什么情况会丢head，其实也就是第一个数>=x的时候，只有这种情况，否则的话,后面j都是插入到第i i+1之间的，其中i>=1
所以不可能会丢head，好，那么什么时候会丢head，也即后面第一次a[j]<x的时候，而此时i=headprev始终没有修改过，于是就那这个来判断，然后j没有改之前的值为新的head，好分析完了，基本case都
OK了。

我猜会有逻辑更漂漂的代码，至少我这条路走到出口不是很漂漂，正如编程之美上一样，一开始写个代码，然后面试官温格case，挂，改，问个case，挂，改这样loop几次，然后过了，于是我挂了。。。。

体会到linklist潜在的威力了！！

ListNode partition(ListNode head, int x) {
ListNode headprev=new ListNode(0);
headprev->next=head;
ListNode i=headprev, inext, jnext, jprev=headprev;
for(ListNodej=head;j!=NULL;j=j->next)
{
if(j->valnext!=j)
{
jnext=j->next,inext=i->next;
if(i==headprev)
head=j;
i->next=j;
j->next=inext;
jprev->next=jnext;
j=jprev;
i=i->next;
}
else
i=i->next;
//int tmp=i->val;
//i->val=

            //swap(i->val,j->val);

        }
        jprev=j;
    }
    delete headprev;
    return head;
}

Posted by richard爱闹 - 7月 25 2014
如需转载，请注明： 本文来自 Richard

这种属于两种DS之间的转换，一开始没想到就地的方法，但是先序遍历一遍，然后边尾插法建立linklist，但是这样不是就地的。

后来想想先序要一直往左走，所以边改右孩子可能会丢失右孩子，如果暂时记住，后面还不知道有多少个right需要先record想了一下，没有好的方法，思路终结。
后来想，可以先left建立，然后转成right么？这样是不会丢失先序遍历的结构的，所以按照这个思路写算法。AC了，后来发现还要记得把left置为NULL。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        stack<TreeNode*> S;
        TreeNode* p=root, *lastp=NULL;
        while(!S.empty()||p!=NULL)
        {
            while(p!=NULL)
            {
                if(lastp!=NULL)
                    lastp->left=p;
                //if(lastp!=root)
                lastp=p;

                S.push(p);
                p=p->left;
            }
            p=S.top();
            S.pop();
            p=p->right;
        }
        p=root;
        while(p!=NULL)
            p->right=p->left,p->left=NULL,p=p->right;
    }
};

Posted by richard爱闹 - 7月 24 2014
如需转载，请注明： 本文来自 Richard

逆置链表升级版，选择部分reverse，首先分析m n的情况，1<=m<=n<=len, 特殊的就是head==NULL 或者 m>n 或者 m<=n 但是 m<1 这几种了，不过后面题目说了 m n满足这些条件，我没有仔细审题

m=n 直接返回，避免处理特殊出错

后面reverse 主要是把reverse后的 和前(可能没有)后(可能没有)链接起来，分析之后发现后面空的可以统一起来，
但是前面空的不行，因为OldHeadPrev没有被赋值，所以后面访问其next有bug，所以单独处理下m=1的情况，用OldHeadPrev初值NULL
是否改变来表示，也可以直接用m=1标示，里面就是普通情况OldHead->next=p 写成NULL了，可能当时分析了后面为空的，然后一下子写了特殊情况的一个赋值了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(head==NULL||m>n||m<1) return NULL;
        //find m node
        if(m==n) return head;


        int i=1;
        ListNode* p=head,*OldHeadPrev=NULL,*OldHead;
        while(i<m)
            OldHeadPrev=p,p=p->next,i++;
        OldHead=p;

        ListNode* prev=NULL,*pnext;//
        while(i<=n)
        {
            pnext=p->next;
            p->next=prev;
            prev=p;
            p=pnext;
            i++;
        }
        if(OldHeadPrev!=NULL)
            OldHeadPrev->next=prev,OldHead->next=p;
        else//m==1,OldHeadPrev not assigned
            head=prev,OldHead->next=p;
        return head;

        //record m, for next to n+1, record m-1, for next to n
        //reverse linked list entil n



    }
};

Posted by richard爱闹 - 7月 24 2014
如需转载，请注明： 本文来自 Richard

普通level order一个队列，区分强推编程之美vector模拟队列解法，于是再次联系了这个漂亮的算法。
另外学校到reverse其实里面可以是一个别的类型，未必是基本数据类型 ，总之是把外部容器里的元素逆置，只要原始都是一样类型就可以了，vector也肯定都是装一种东西的。

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<TreeNode* > vec;
        vector<vector<int> > alllevel;
        vector<int> level;

        if(root==NULL)
            return alllevel;

        vec.push_back(root);
        level.push_back(root->val);
        alllevel.push_back(level);

        int cur=0,last;
        while(cur<vec.size())
        {
            last=vec.size();
            level.clear();
            while(cur<last)
            {
                if(vec[cur]->left!=NULL)
                    vec.push_back(vec[cur]->left), level.push_back(vec[cur]->left->val);
                if(vec[cur]->right!=NULL)
                    vec.push_back(vec[cur]->right), level.push_back(vec[cur]->right->val);

                cur++;
            }
            if(level.size()>0)
                alllevel.push_back(level);
            //cout<<endl;
        }
        reverse(alllevel.begin(),alllevel.end());
        return alllevel;
    }
};

Posted by richard爱闹 - 7月 24 2014
如需转载，请注明： 本文来自 Richard

抱歉代码未通过所有case，算法有误，博主还没探索出非递归的算法，递归的算法在博主csdn同一天的博客里有，之前看July收集100题也有一篇博客。

/*/
题目比较通俗易懂，找一条从根到叶子的路径，使得元素和为给定值，如果是递归的话，可能没法弄，所以必须非递归的，先序遍历是一个好的方法，但是改成path+=这种的，还是有些需要注意的，
里面while循环是向左探，那么每次p都非空，因此path+=p->data 写在这里，那么pop时候要当心，因为p=S.pop() 有可能是p->left 时空，例如刚才左探到底了，那么而且pop出来相当于退到刚才父亲，所以path-=p->left->data,

vector<vector<int> > pathSum(TreeNode *root, int sum) {
        TreeNode* p=root;
        Stack<TreeNode* > S;
        int path=0;
        vector<<vector<int> > allpathvec;
        while(!S.empty()||p!=NULL)
        {
            while(p!=NULL)
            {
                S.push(p);
                path+=p->data;
                p=p->left;
            }
            if(path==sum)
            {
                vector<int> pathvec;
                for(Stack<TreeNode*>::iterator it=S.begin();it!=S.end();it++)
                    pathvec.push_back(it->first->data);
                allpathvec.push_back(pathvec);
            }
            p=S.pop();
            if(p->left!=NULL)
                path-=p->left->data;
            p=p->right;
        }
        return false;
    }

Posted by richard爱闹 - 7月 24 2014
如需转载，请注明： 本文来自 Richard

从上面KMP匹配代码引出的一个经典数据类型转换的问题。

int KMP(string str, string pat, int *next)
{
    int i=0, j=0;
    while(i<str.size() && j<pat.size())
    {
        if(j==-1 || str[i]==pat[j])
            i++,j++;    
        else
            j=next[j];

    }
    if(j==pat.size())
        return i-j;
    else 
        return -1;
}

这个代码看似没有问题，其实有个严重的问题，string.size() 返回的是size_t类型，这个string封装好的，实际也是长度必为正值，j=-1时，例如j=0, j=next[j] 之后j==-1，然后j<pat.size()
你猜结果如何？ 居然返回false了，然后退出循环了！！！！

结果是系统进行隐式转换，int->size_t, 然后-1二进制是32个1，然后变成无符号就是2^32-1,远大于pat.size()，于是bug了。。。

为啥系统的隐式转换是int->size_t(unsigned int)? 因为size_t范围全是非负数，从0开始最大值比int大得多，如果size_t->int的话，就像倒水一样，水比杯子容量还大，自然扑出来了。出现严重的溢出后果。
但其实int->size_t也是有验证问题，当int时负数，转的话就变成一个对应的无符号整数了。所以系统的设计，觉得size_t->int后果更严重，而int->size_t是程序员自己去控制的，因为即使前者强制转换也有可能是溢出的！

所以最好的方法就是要么非常清楚的系统的隐式转换规则，要么自己强制转换，不要寄希望于模棱两可的隐式转换。

Adhoc就是这样的，用long long的时候，给long long a赋值，LL a=0LL, 这样保证强制转换。
还有李沐MLSS talk里slide上的 稀疏矩阵里for的变量都是size_t类型的，因为下标永远都是非负数的。

正确KMP代码：

int KMP(string str, string pat, int *next)
{
    int i=0, j=0;
    while(i<(int)str.size() && j<(int)pat.size())
    {
        if(j==-1 || str[i]==pat[j])
            i++,j++;    
        else
            j=next[j];

    }
    if(j==pat.size())
        return i-j;
    else 
        return -1;
}

Posted by richard爱闹 - 7月 24 2014
如需转载，请注明： 本文来自 Richard

终于打算回顾KMP，因为最近July的焦点也在这个地方，所以打算复习。KMP是有点儿难的字符串匹配算法，但是难度带来的是多数情况下效率的提升。
当时学DS的时候，匹配过程是比较理解，回溯求next数组稍微有点儿费解，现在把他陈述以下。

首先由易到难，Brute force算法，朴素的O(mn)匹配算法，注意我们的问题集中在如何找到第一次匹配的母串位置

匹配没到底时，失效了，那么回溯，母串起点++，字串j=0,那么对于母串的offset和子串是一样的，因此可以用两个指针变量，邹博PPT用了三个，变量越多越不好感觉。

int bf(string str, string pat)
{
    int i=0,//str startpos
    j=0,//pat point
    //k=0;//matched str point relative to startpos
    while((i+j)<str.size()&&j<pat.size())
    {
        if(str[i+j]==pat[j])
            j++;
        else
            j=0,i=i+1;
    }
    if(j>=pat.size()) 
        return i;
    else 
        return -1;
}

这是最朴素的，KMP的基础在于如何利用已经匹配的结果来避免后面回溯的不必要匹配，也就是说，如果串满足一点性质，可以推导出回溯的前k个字符一定是匹配上的？

KMP关键是一个next数组，next[j] 表示失效后，j移动到字串的位置，或者说最长前缀的长度，因为是0-base的缘故，另外KMP比较关键的地方在于匹配已经不是str[i+j]==pat[j]了，而是str[i]==pat[j], 这个
问题之前也忽视掉了，导致怎么都回忆不起KMP的核心算法了，因为KMP就是想使得较长的母串不回溯，因为母串往往较长，对于较大的值减少他的系数往往带来有意义的性能提升。

因此 next[j]: str[0…..j-1]中前缀和后缀匹配的最长前缀(后缀)长度，和子串j回溯到的位置值相等。

next[j]<=j-1,这是定义的，如果能到j的话，每个next都能到j了，没有意义，且next[j]>=0 j>=1, next[j]=-1, j=0, 因为当j=0的时候[0,j-1]之间是没数的因此定义一个-1，同时也是为了避免母串子串第一个字符不等导致的无限循环，
主要是j=next[j]这个语句一定要保证j变小了，否则j=0 如果next[j]=0的话 就死循环了，另外从前向后递推next[j]<j也保证了之前的next值都是算出来了的。

int KMP(string str, string pat, int *next)
{
    int i=0, j=0;
    while(i<str.size() && j<pat.size())
    {
        if(j==-1 || str[i]==pat[j])
            i++,j++;    
        else
            j=next[j];

    }
    if(j==pat.size())
        return i-j;
    else 
        return -1;
}

但是看到的各个版本都是
while(i<str.size())
{
…
if(j==pat.size())
{
count++;
j=0;
}
}

这种版本有一个好处，就是可以计算匹配了多少次，所以比较灵活，所以还是选择这种比较好一点。

先介绍这个，再来坑计算next这块骨头，里面其实是利用了之前的一些信息来回溯的，
a[0….k-1]=a[j-k…j-1] k不能再大了，//这里感觉邹博的PPT小标有点问题
那么next[j]=k,

if a[k]==a[j]
next[j+1]=next[j]+1 //这个好理解

else
找next[next[j]],也即a[0…k-1]里面的最长前缀后缀相等，另k=next[j], 如果a[k]==a[j]那么，问题也解决了，next[j+1]=next[k]+1=next[next[j]]+1，也即利用前面的信息，a[0…k-1]中前缀等于后缀，而较短的后缀又等于a[j-k…j-1]的后缀，
因此可以推出。如果不等继续回溯，核心是k=next[k]语句

因此有了下面的CalcNext代码：

void CalcNext(string str, int *next, int n)
{
    next[0]=-1;
    int k;
    for(j=0;j<=n-2;j++)
    {
        k=next[j];
        while(k!=-1 && str[k]!=str[j])
            k=next[k];

        //if(k!=-1)
            next[j+1]=k+1;
        //else 
        //    next[j+1]=0;
    }
}

我后来看了下邹博代码，发现循环退出好像k= !=-1 可以统一起来，因为next 为负只有-1 一种可能，也只是next[0]，所以似乎代码可以更简洁些。

Posted by richard爱闹 - 7月 24 2014
如需转载，请注明： 本文来自 Richard

这里把leetcode里面permutation的题目总结一下，记得一开始看的时候，发现心里很不清楚，next_permutation也是调用库的，看了邹博的PPT
之后加上之前看的permutation基本思路理清楚了。

我直接在leetcode上coding，为了模拟纸上coding的效果

普通的permutation，如果换成字符串的话也是一样的：

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > permutationvec;
        permutation(num,0,num.size()-1,permutationvec);
        return permutationvec;
    }

    void permutation(vector<int> num, int from, int to, vector<vector<int> >& permutationvec)
    {
        if(from>to)
        {
            vector<int> eachpervec;
            for(int i=0;i<=to;i++)
                eachpervec.push_back(num[i]);
            permutationvec.push_back(eachpervec);
        }
        else
        {
            for(int i=from;i<=to;i++)
            {
                swap(num[from],num[i]);
                permutation(num,from+1,to, permutationvec);
                swap(num[from],num[i]);
            }
        }
    }
};

按照邹博的函数参数风格写，感觉自己萌萌哒！！！

然后是带有重复数的permutation，只要加一个函数，判断里面是否a[from,i-1] 中是否有数等于a[i] 就可以了。

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > permutationvec;
        permutation(num,0,num.size()-1,permutationvec);
        return permutationvec;
    }
    bool IsSwap(vector<int> num, int from, int i)
    {
        for(int j=from;j<=i-1;j++)
        {
            if(num[i]==num[j])
                return false;
        }
        return true;
    }
    void permutation(vector<int> num, int from, int to, vector<vector<int> >& permutationvec)
    {
        if(from>to)
        {
            vector<int> eachpervec;
            for(int i=0;i<=to;i++)
                eachpervec.push_back(num[i]);
            permutationvec.push_back(eachpervec);
        }
        else
        {
            for(int i=from;i<=to;i++)
            {
                if(!IsSwap(num,from,i)) continue;
                swap(num[from],num[i]);
                permutation(num,from+1,to, permutationvec);
                swap(num[from],num[i]);
            }
        }
    }
};

然后返回kth 排列，由于邹博所说的，next_permutation可以天然的去除里面有重复数的case，但是我已开始用next_permutation发现TLE了，显然每次都调用这个然后n!次调用非常费时间，还是普通permutation然后
记录下第k次的permutation的结果！

这里面我定义了一下类的成员，减少递归函数的参数，避免潜在的栈溢出情况，递归有一点很不好，就是如果我中间找到了结果想返回时返回不了的，因为栈已经压到这么深了，而迭代则可以通过break来达到目的。

class Solution {
public:
    string result;
    int kth;

    string getPermutation(int n, int k) {
        kth=k;
        string str="";
        for(int i=1;i<=n;i++)
            str+=char(i+'0');

        permutation(str,0,str.size()-1);
        return result;
    }

    void permutation(string num, int from, int to)
    {
        if(from>to)
        {

            //string eachpervec;
            //for(int i=0;i<=to;i++)
                //eachpervec.push_back(num[i]);
            //    eachpervec+=num[i];
            kth--;
            if(kth==0)
                result=num;
            //permutationvec.push_back(eachpervec);
        }
        else
        {
            for(int i=from;i<=to;i++)
            {
                swap(num[from],num[i]);
                permutation(num,from+1,to);
                swap(num[from],num[i]);
            }
        }
    }
};

还是TLE了o(╯□╰)o，所以还是需要非递归算法来剪枝达到 减少不必要的继续递归了，但是非递归的都忘记了o(╯□╰)o

Posted by richard爱闹 - 7月 23 2014
如需转载，请注明： 本文来自 Richard