In function for different processing of input buffer

今天在写基于KMP的计算字符串匹配次数的时候,处理casen和字符串又犯了当年刚学C++时的错误,究其原因就是没有仔细读函数的说明,尤其是这几个输入函数或者cin对于输入缓冲区的处理。

  1. cin
    cin>>n,一般如果敲入一个\n或者space或者\t来使他识别出前面是需要输入的整数,cin居然会把这个delim符留在inputbuffer里,保留!!另外有一点要注意,任何输入函数只要inputbuffer里面有东西就会优先抽取
    这里的数据,等到空了,才会请求或抽取键盘的输入

2.string::getline(istream& cin, str,delim)
这里cin对应的形参是istream类型,iostream, istringstream, ifstream等等都是继承了它的,因此文件流,字符串流,控制台输入流都是可以调用的

这里为了强调,把这段文档说明写在这里,
If the delimiter is found, it is extracted and discarded, i.e. it is not stored and the next input operation will begin after it.

这里delim其实是包含了默认的\n的,所以看到了么,他会抽取再丢弃作为字符串抽取结束的标志!!丢弃\n!!

另外std::getline() string这个函数是重载了istream::getline的

3.istream::cin.getline(str,n,delim)
这里cin对应的也是istream,调用同上。本质区别就是这个是C字符串的输入函数

The delimiting character is the newline character (‘\n’) for the first form, and delim for the second: when found in the input sequence,
it is extracted from the input sequence, but discarded and not written to s.

由于C的,自然特殊的结束符要考虑,这里参数n是包含\0,所以函数全称是抽取长度为n-1的字符串或者不到n-1但是遇到delim,然后str加上\0,同时将delim(如果出现的话)丢弃,也即删除出input buffer
A null character (‘\0’) is automatically appended to the written sequence if n is greater than zero, even if an empty string is extracted.

好的现在总结已经非常清楚了估计,以后不能再犯这个错误了。

另外今天有个神奇的输入问题,就是http://www.cnblogs.com/A-Song/archive/2012/01/29/2331204.html

#include <iostream>
using namespace std;
int main()
{
    char str[8];
    cin.getline(str, 5);
    cout<<str<<endl;
    cin.getline(str, 5);
    cout<<str<<endl;
    return 0;
}

输入abcdefgh\n 居然程序结束,而且第二个空。后来问了大神,才知道cin的一个badbit被置位了,例如也即这种属于抽取字符串失败了,后面也没必要再读了,认为也是错误的,所以只要没有抽完第一个串的所有字符,
就认为出错了,badbit值1,后面读取,由于char[] 的缘故,自动赋\0, 而其他的类型都不会。。。。while(cin>>x)… 如果要读入整数,却输入字符,就置failbit为1,cin也是返回false了。 cin确实很复杂,所以慢慢总结,

今天输入这样的数据:
3
A 1 1
类似这样的数据,然后发现要一直用scanf之类的,尤其是大量输入的时候cin会非常慢,因为需要凑齐到缓冲器再输入到内存中。

scanf("%d");
scanf("%c%d%d")

类似这样的写法是不能过的,因为输入3之后有一个\n,然后还在缓冲区,然后抽取%c遇到\n, 是一个whitespace(include \t \n space这三种),于是抽取字符变成空的,同时后面的抽取一个非nonwhitespace,于是后面都乱,具体为啥是个野值还不清楚。

一开始以为用个变量抽取掉%c

scanf("%d");
scanf("%c");
scanf("%c%d%d");

后来发现瞿神代码是这样的

char s[5];
scanf("%d");
scanf("%s%d%d");

看了scanf文档,似乎char和char* 好像都是遇到whitespace就结束,但是瞿神说scanf(非%c) 和cin 如果遇到whitespace就会智能的跳过,我一直怀疑,因为之前getline好像inputbuffer里的
whiltespace是会读取然后出错的,后来实验果然瞿神是对的。于是发现只是getline会读取任何whilespace导致string出错,但是cin和scanf处理字符串都不会因此出错,
也即

cin>>n;
cin>>str;

是对的,但是

cin>>n;
getline(cin,str);

是会出错的,因为cin scanf对于输入给字符串可以跳过whiletespace,getline则不会导致出错。

Posted by richard爱闹 - 7月 29 2014
如需转载,请注明: 本文来自 Richard

match string count based on kmp

之前已经实现了KMP,不过July师兄确实非常热情,不断修改,争取所有人都懂。July师兄的博客典型的特点就是特别接地气!!!
这也是我的目标。

标准KMP实现的找出第一次匹配的pat在母串的start index,找不到返回-1

如果要数匹配的count,是不是直接把里面找到的分支里面 j=0,然后出口只有i走到头了就OK了?
我已开始也以为是,但是测了几个例子发现不对,因为i是一直往前走,不后退,那么可能会丢弃匹配的一个子串中有个length>=1后缀和模式串前缀匹配的情况,举例来说
ADA
ADADADA
这两个串,第一次匹配结束,i=3,j=3,此时如果j=0的话,那么就丢了 ADA和母串str(2,4)匹配了,因为i匹配第一个结束已经到3了。

那么这个怎么办,是不是要改回BF算法呢?不需要,因为利用next数组发现,pat(0)A=pat(2)A, 而str(0)=str(2),由于前面匹配了一段,因此str[2]=pat[2]=pat[0], 因此看str[i=3]?=pat[1=next[3]]即可。
所以这里需要为next数组多加一位,最简单的做法pat最后加一个前面不会出现的字符(现在发现其实不需要是不出现的,任意一个字符都可以,因为不会匹配到这个字符 下标j就回溯了),然后KMP匹配时pat长度还是原来长度,因此有了下面的代码,这样是再次利用next数组的有趣的性质。

#include <iostream>
#include <string>

using namespace std;
#define read freopen("in.txt","r",stdin);
#define write freopen("out.txt","w",stdout);
#define STRMAXNUM 1000000
#define PATMAXNUM 10000
int next[PATMAXNUM+1];//add end char

void GetNext(string str)
{
    int strlen=str.size();
    next[0]=-1;
    int k;
    for(int j=0;j<=strlen-2;j++)
    {
        k=next[j];
        while(k!=-1 && str[k]!=str[j])
            k=next[k];
        next[j+1]=k+1;
    }
}

int Kmp(string str, string pat)
{
    GetNext(pat);
    int i=0,j=0,strlen=str.size(),patlen=pat.size()-1;

    int matchedcount=0;
    while(i<strlen)
    {
        if(j==-1 || str[i]==pat[j])
            i++,j++;
        else
            j=next[j];
        if(j==patlen)
        {
            j=next[j];//add end char, avoid missing part matched which was in just matched substr
            matchedcount++;
        }
    }
    return matchedcount;
}

int main()
{
    //read;
    //write;
    int casen;
    cin>>casen;
    string str,pat;
    //char c_str[STRMAXNUM+1], c_pat[PATMAXNUM+1];
    getline(cin,pat);
    while(casen--)
    {
        getline(cin,pat);
        getline(cin,str);
        pat+='$';//any char is ok
        /*
        gets(c_pat);
        gets(c_str);
        gets(c_str);
        pat=c_pat, str=c_str;*/
        cout<<Kmp(str,pat)<<endl;
        //gets(c_pat);
    }
    return 0;
}

Posted by richard爱闹 - 7月 29 2014
如需转载,请注明: 本文来自 Richard

4sum

4sum,之前2sum 3sum用这个都完成了,但是现在TLE了,时间复杂度O(n^3 logn)

对重复的情况处理就是如果4次循环每一次如果前后都相同的话,一定会重复,因为当前这一个数选了重复的,后面会找到同样的数,但是似乎有点问题,之前还没想到,1 1 2.。。i指向第一个1,j指向第二个1,
如果接下来i指向第二个1,那么j往后指似乎不会和前面重复,似乎算法还有问题,不太确定。

vector<vector<int> > fourSum(vector<int> &num, int target) 
{
        //int sum=0;
        vector<vector<int> >allsolution;
        if(num.size()<=3) return allsolution;
        sort(num.begin(),num.end());
        for(int i=0;i<=num.size()-1;i++)
        {
            if(i>=1 && num[i]==num[i-1]) continue;
            for(int j=i+1;j<=num.size()-1;j++)
            {
                if(j>=i+2 && num[j]==num[j-1]) continue;
                for(int k=j+1;k<=num.size()-1;k++)
                {
                    if(k>=j+2 && num[k] == num[k-1]) continue;

                    //binarysearch
                    int low=k+1,high=num.size()-1,x=target-num[i]-num[j]-num[k];
                    while(low<=high)
                    {
                        int mid=(low+high)/2;
                        if(num[mid]==x)
                        {
                            vector<int> onesolution;
                            onesolution.push_back(num[i]);
                            onesolution.push_back(num[j]);
                            onesolution.push_back(num[k]);
                            onesolution.push_back(num[mid]);
                            allsolution.push_back(onesolution);
                            break;
                        }
                        else if(num[mid]<x)
                            low=mid+1;
                        else
                            high=mid-1;
                    }
                    /*
                    bool found=binary_search(num+k,num+num.size()-1,sum-a[i]=a[j]=a[k]);
                    if(found==true)
                        return 

                    for(int l=k+1;l<=num.size()-1;l++)
                    {
                        if(l>=k+2 && num[l]==num[l-1]) continue;
                        if(num[i]+num[j]+num[k]+num[l]>target) break;
                        if(num[i]+num[j]+num[k]+num[l]==target)
                            {
                                vector<int> onesolution;
                                onesolution.push_back(num[i]);
                                onesolution.push_back(num[j]);
                                onesolution.push_back(num[k]);
                                onesolution.push_back(num[l]);
                                allsolution.push_back(onesolution);
                            }
                    }*/
                }
            }
        }

        return allsolution;

    }

Posted by richard爱闹 - 7月 29 2014
如需转载,请注明: 本文来自 Richard

Notes

unix: adduser, 这个比较好,需要提示输入一堆信息,useradd 三无账户,无home, 无密码,无系统账户
优先选择adduser

vector有一个reserve是可以给vector设定一个较大的capacity容量的,使得以后push_back时候避免较多的元素搬移。

看李沐的MLSS, 里面有个spartse matrix的存储和二分查找,默认index是sorted,才意识到其实二分 STL肯定也有的,之前都自己实现,但是他实现的版本其实和基本的有一些差别,这三个一起配套使用
binary_search lower_bound upper_bound

bool binary_search(first, last, val, comp) comp不写,默认是递增,
我在想,如何返回找到的index呢?原来里面其实是调用lower_bound,所以直接lower_bound就可以了。

iterator lower_bound(first, last, val, comp) comp不写,默认是递增,
注意lower_bound定义:返回左到右第一个(等价于index最小)>=x的iterator,本质是修改版的二分,所以和binary_search的返回值配套就可以知道找到(返回mid),和没找到返回>x的最小的index

iterator upper_bound(first, last, val, comp) comp不写,默认是递增,
注意upper_bound定义:返回第一个<x的iterator,binary_search没有调用这个,但是本质是修改版的二分

今天听别人说有就地归并,于是瞬间长知识了
http://www.ahathinking.com/archives/103.html#more-103

绝对经典位运算求绝对值:
int i=a>>31;
return (a^i)-i;

正数i=0,最后还是a
负数i=-1,32bit 1, 最后相当于a取反加1,正好是对应的正值。

一直以为string::getline函数参数是这样的

istream& getline (istream& is, string& str, char delim=’\n’);

后来才发现是这样两个函数重载

istream& getline (istream& is, string& str, char delim);
istream& getline (istream& is, string& str);\读到\n结束

感觉两种设计似乎是一样的。

Posted by richard爱闹 - 7月 29 2014
如需转载,请注明: 本文来自 Richard

Remove Nth Node from end of List

由于题目对于n给了约束,一定是合法的,所以1<=n<=length(Linklist),
如果长度为0的话,n也不存在,不过还是判断下链表为空的情况。

模仿找倒数第n个结点,其实和两遍遍历操作次数没太大差别,只是说方法比较巧,用两个指针同步走。

由于需要删掉倒数第n个结点,实际是找倒数第n+1个结点,所以后指针要向后移n+1次,我已开始移了n次,然后后面
判断循环结束是找到尾结点就结束,而不是到NULL,其实是一样的,但是用p->next==NULL要多一步检查p是否空这么一步越界判断。

这里边界主要就是判断n=length(Linklist)这种情况,因为找到倒数第n个就是head,那倒数n+1不在链表里,所以直接
head=head->next就可以了。

ListNode *removeNthFromEnd(ListNode *head, int n) {
        if(head==NULL) return NULL;
        ListNode*p=head;
        int i=1;
        while(i<=n)
        {
            p=p->next;
            i++;
        }
        ListNode* pprev=head;
        if(p==NULL)//length==n
        {
            head=head->next;
            return head;
        }
        while(p->next!=NULL)//length>n>=1
            pprev=pprev->next,p=p->next;
        pprev->next=pprev->next->next;
        return head;
    }

如果选择后移n+1位,就要考虑了,因为while循环要保证n+1<=length(Linklist), 当n==length(Linklist),可能p到了NULL还要next,这个时候可以确定需要
倒数第n个结点,也即head,所以直接head=head->next就可以了,这个case提到前面找p的时候来处理掉

ListNode *removeNthFromEnd(ListNode *head, int n) {
        if(head==NULL) return NULL;
        ListNode*p=head;
        int i=1;
        while(i<=n+1)
        {
            if(p==NULL) {head=head->next;return head;}//length==n
            p=p->next;
            i++;
        }
        ListNode* pprev=head;
        while(p!=NULL)//length>n>=1
            pprev=pprev->next,p=p->next;
        pprev->next=pprev->next->next;
        return head;
    }

Posted by richard爱闹 - 7月 29 2014
如需转载,请注明: 本文来自 Richard

BSTtoDLL

将二叉搜索树转化为排序的双链表。又是一道两种DS之间的转化,这两种指针都很多,一定要注意别丢。

看到BST,我就想到中序遍历就是排序,然后是否可以边遍历边调整指针,最后结束就是DLL呢?
关键是不能丢指针,plast p可以保持遍历过程的前后关系,这种思路在程设里屡见不鲜,例如fibonacci数列的遍历,用backtwo backone current记录当前和前两个的关系,只要前k这个k是常数,就可以
通过用k个变量来记录这种关系,空间复杂度仍然O(1), 前后关系要么是坐下走的时候,因为left已经被使用了,所以plast不丢left指针,p是否丢right指针?也不丢,因为从left跳到right是通过pop栈来找到parent的,
所以修改p的right指针是不影响的,后面各种情况下中序的前后关系修改left right指针都不影响后面的中序遍历的,所以完全可以通过中序遍历来实现这一过程。

TreeNode* BST->DoubleLinklist(TreeNode* root)//based on PreOrder and InOrder Traverse
{
    if(root==NULL) return NULL;
    TreeNode* p=root, *head, *plast;
    bool first=true;

    while(!S.empty() || p!=NULL)
    {
        while(p!=NULL)
        {
            S.push(p);
            p=p->left;
        }
        p=S.top();
        S.pop();

        if(first==true)
        {
            head=p;
            first=false;
            head->left=NULL;
        }
        else
        {
            plast>right=p;
            p->left=plast;
        }
        plast=p;

        p=p->right;
    }
    plast->right=NULL;
}

后来看了答案,发现其实不需要初始化head 和tail两个指针的left 和right因为 初始时一定都是NULL,head必为最左下,tail必为最右下

Posted by richard爱闹 - 7月 28 2014
如需转载,请注明: 本文来自 Richard

From MergeIntervals to list and vector iterator

这个是之前做过的题目,但是再做发现还是要花很多时间,花时间的原因:

  1. 忘记是start 还是end排序,然后想再证明发现不会了,猜了end,结果挂了
  2. 若不单独考察链表操作时用list,但是list的bidirectional的iterator爆难用,由于不能随机访问,所以iterator只能++ — 不能+1 -1, ++之后还会修改iterator值,要特别当心,
    另外vector和list的 插入 insert 删除 erase 都只能用iterator,所以即使vector要插入删除也要用迭代器遍历,vector删除不需要记录下返回的迭代器,因为内存是连续的,
    直接迭代器加1都可以的,但是list可能就不行了,因为删除了*it, it就回不到链表上了,erase返回的iterator是删除之后的第一个元素的指针,所以for的时候++ 要特别当心不要移动过了,
    如果— 然后再中和掉for的++ 有风险,如果一开始指向begin可能就会越界了,所以最好是for不写++ 这个分支也不— 而在另一个分支++
  3. 一开始觉得vector删除会大量移动元素,估计比list慢,但是不确定慢多少,后来测试确实TLE了,估算下,移动元素上限是n-2+…+1, O(n^2),linklist利用链表删除高效,每次操作都是O(1),总复杂度O(n)。
  4. sort内嵌的comp函数再次忘记写成静态成员函数,今天想通了似乎,写的每个solution class里的函数都是成员函数,实际都是
    solution的instance来调用的,而sort内嵌的comp函数则不允许这样的类型,所以写成静态成员函数,是整个class一份的成员函数。同时comp函数还没有仔细
    考虑多种case,如果start相同的怎么办,这个也是需要处理的,不然可能是出现start相同,结果end大的再前面,这样merge可能会有问题。
  5. 分析interval merge 情况的时候比较慢,主要就是三类情况,关键是怎么设计if else 嵌套来分类

第一次写的自己控制linklist的mergeintervals,还比较青涩o(╯□╰)o:

struct Node
{  
    Interval interval;
    Node* next;
};
class Solution {
public:

static bool SortComp(const Interval& T1, const Interval&T2)
{
    return T1.start<T2.start;
}
Node* CreateLinkList(vector<Interval> data)  
{  
    Node* head=NULL;  
    head=new Node();  
    head->interval=data[0];  
    head->next=NULL;  
    Node* rail=head,*p;// record each rail  
    for(int i=1;i<data.size();i++)  
    {  
        p=new Node();  
        p->interval=data[i];  
        p->next=NULL;  
        rail->next=p;  
        rail=rail->next;  
    }  
    return head;  
}
bool ShouldMerge(Interval n1,Interval n2, Interval& mergedn)
{
    if(n1.start<=n2.start&&n2.start<=n1.end&&n1.end<=n2.end)//intersect
    {
        mergedn.start=n1.start;
        mergedn.end=n2.end;
        return true;
    }
    if(n1.start<=n2.start&&n2.end<=n1.end)//subset of another
    {
        mergedn.start=n1.start;
        mergedn.end=n1.end;
        return true;
    }
    return false;
}
vector<Interval> merge(vector<Interval> &intervals)
{
    if(intervals.size()<=1) return intervals;
    sort(intervals.begin(),intervals.end(),SortComp);//start sort descending, for vector pop_back
    Node* head=CreateLinkList(intervals);

    //merge interval with linklist
    Node* p=head;
    while(p->next!=NULL)//at least two node initially
    {
        Interval mergedn;
        if(  ShouldMerge(p->interval,p->next->interval,mergedn) ||    ShouldMerge(p->next->interval,p->interval,mergedn)   )
        {
            //delete p, p->next;
            //insert mergedn;
            p->interval=mergedn;
            p->next=p->next->next;
        }
        else
            p=p->next;
    }


    /*
    for(int i=0;i<intervals.size()-1;i++)
    {
        Interval mergedn;
        if(ShouldMerge(intervals.at(i),intervals.at(i+1),mergedn)|| ShouldMerge(intervals.at(i+1),intervals.at(i),mergedn))
        {
            intervals.erase(intervals.begin()+i);
            intervals.at(i)=mergedn;
            //intervals.erase(intervals.begin()+i);
            //intervals.insert(intervals.begin()+i,mergedn);
            i--;
        }
        else 
            ;
    }*/

    //copy linklist to vector

    p=head;
    intervals.clear();
    while(p!=NULL)
    {
        intervals.push_back(p->interval);
        p=p->next;
    }

    return intervals;
}
};

基于vector的mergeinterval:

    static bool IntComp(Interval i1,Interval i2)//end ascending
    {
        if(i1.start<i2.start)
            return true;
        else if(i1.start>i2.start)
            return false;
        else
        {
            if(i1.end<i2.end)
                return true;
            else
                return false;
        }
    }
    bool MergeInterval(Interval i1, Interval i2, Interval& newi)
    {
        if(i1.end < i2.start)
            return false;
        else if(i1.end<=i2.end){
            newi.start=i1.start;newi.end=i2.end;return true;}
        else if(i1.end>i2.end)
        {
            newi.start=i1.start;
            newi.end=i1.end;
            return true;
        }
    }


    vector<Interval> merge(vector<Interval> &intervals)
    {
        sort(intervals.begin(),intervals.end(),IntComp);

        list<Interval> lis;
        for(int i=0;i<intervals.size();i++)
            lis.push_back(intervals[i]);
        for(list<Interval>::iterator it=lis.begin();it!=lis.end();)
        {
            Interval i1,i2,newi;
            i1=*it;
            it++;
            if(it==lis.end()) break;
            i2=*it;
            if(MergeInterval(i1,i2,newi))
            {
                *it=newi;
                it--;
                it=lis.erase(it);
            }
        }
        intervals.clear();
        //int i=0;
        for(list<Interval>::iterator it=lis.begin();it!=lis.end();it++)
            intervals.push_back(*it);
        return intervals;
    }

基于list的mergeintervals(IntComp,MergeInterval函数同vector的):

vector<Interval> merge(vector<Interval> &intervals)
{
    sort(intervals.begin(),intervals.end(),IntComp);

    list<Interval> lis;
    for(int i=0;i<intervals.size();i++)
        lis.push_back(intervals[i]);
    for(list<Interval>::iterator it=lis.begin();it!=lis.end();)
    {
        Interval i1,i2,newi;
        i1=*it;
        it++;
        if(it==lis.end()) break;
        i2=*it;
        if(MergeInterval(i1,i2,newi))
        {
            *it=newi;
            it--;
            it=lis.erase(it);
        }
    }
    intervals.clear();
    //int i=0;
    for(list<Interval>::iterator it=lis.begin();it!=lis.end();it++)
        intervals.push_back(*it);
    return intervals;
}

附上之前的解题报告 http://blog.csdn.net/richardzrc/article/details/31454199

学到一个阿三的短语,get a life, 享受生活

Posted by richard爱闹 - 7月 26 2014
如需转载,请注明: 本文来自 Richard

SortedArrayToBST

一开始看这道题目,典型的两种DS之间的转化。

两种思路,一种是先随便插入,例如从前向后,或者后向前,然后update BT为BST,另一种就是按照特定的元素访问顺序插入, 使得查完刚好为BST。
思路1,插入采用BST的插入算法,然后调整为BBST,但是调整为BBST似乎算法挺烦,看AC率挺高,估计不是放弃。
思路2,似乎有点像二分的顺序,插入就可以,先mid然后左区mid,然后右区mid,然后左左区mid一直下去,但是代码不好控制成这种顺序的。

后来想想,发现有这思路忘记了,就是recursive,遇到BT问题,recursive都是最好理解算法,虽然执行过程不make sense,于是开始递归了。按照二分思路,下插入中间
因此需要申请一个结点为根,然后递归插入左区,递归插入右区,需要上下断点 ,原函数参数不行,因此重新写一个,里面有new,想起之前先序顺序简历二叉树的心得,一定要引用传递指针,不然
堆空间的地址丢了,发现空数组又忘记处理= =附上代码

class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        if(num.size()==0) return NULL;
        TreeNode* root;
        f(root,num ,0, num.size()-1);
        return root;
    }

    void f(TreeNode*& root, vector<int>&num, int low, int high)
    {
        if(low>high)
            return;
        else
        {
            int mid=(low+high)/2;
            root=new TreeNode(num[mid]);
            f(root->left, num, low,mid-1);
            f(root->right, num, mid+1, high);
        }
    }
};

总结一下,现在还是不那么全面,三个流程缺一不可,任意一个DS alg题都要有这三步:

1)想出最优算法,写代码
2)检查代码边界,无非是访问数组越界,字符串越界,访问结构体成员指针知否空,stack空的pop之类的
3)检查特殊输入case是否可以统一到一般的算法流程里,不然单独处理

但是这里有个疑惑,二叉搜索树调整为平衡的,和普通BT调整为balanced又和区别。

Posted by richard爱闹 - 7月 26 2014
如需转载,请注明: 本文来自 Richard

IsBalancedOneRecursive

这种最容易写的方法就是严格按定义,BBT(Balanced Binary Tree):要么空,要么左右子树高度相差最多1,且左右子树都为BBT。显然递归定义,判定也是递归的,
因此根据这句描述,有句求高度的语句,我之前用了朴素的调用计算高度的函数,而且这个是递归写的,当然用站站的层序遍历也是可以的,当时两层递归居然也让我过了,对我有点放任了= =

class Solution {
public:
    int Depth(TreeNode* root)
    {
        if(root==NULL) return 0;
        int leftdepth=Depth(root->left);
        int rightdepth=Depth(root->right);
        if(leftdepth>rightdepth) return 1+leftdepth;
        else return 1+rightdepth;
    }
    bool isBalanced(TreeNode *root) {
        if(root==NULL) return true;
        int leftDepth=Depth(root->left);
        int rightDepth=Depth(root->right);
        return abs(leftDepth-rightDepth)<=1 && isBalanced(root->left) && isBalanced(root->right);

    }
};

后来想想有么有一次递归搞定的,也即递归判定二叉树的同时 ,还可以计算出高度来?

自己想的时候还不是很清晰,后来看了一篇似乎很强的童鞋写的一堆递归解二叉树问题的代码,瞬间觉得有了思路。

为什么自己没这么想,主要是不知道怎么把height这个副产品潜逃到递归函数里面。后来看了下,觉得自己还是要严格按照定义来。

IsBBT(root)+height: root==NULL || (|leftheight-rightheight|<=1 && IsBBT(root->left) && IsBBT(root->right) )

这句逻辑语句把代码高度概括了,但是leftheight不用调用外部函数的方法来实现,那怎么弄呢?

仔细看height定义: root_height=max(root->left_height,root->right+height)+1,

IsBBT肯定还是返回bool,结果,里面如果要把副产品height算出来,只能引用传递,因为要把root的height返回回来,所以子树调用的时候,用leftheight=0 引用传递进去,调用完成后,就是树高了,
然后切记,每个递归出口同样要加上计算height这个副产品的语句,root空 height=0,如果有子树,并且满足定义,height=max(leftheight,rightheight)+1 然后返回主要的bool值,因此代码如下:

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        int height=0;
        return isBalancedHeight(root,height);
    }
    bool isBalancedHeight(TreeNode* root,int& height)
    {
        if(root==NULL) {height=0;return true;}
        else
        {
            int leftheight=0;
            bool leftisBalanced=isBalancedHeight(root->left, leftheight);

            int rightheight=0;
            bool rightisBalanced=isBalancedHeight(root->right, rightheight);

            if(leftisBalanced && rightisBalanced && abs(leftheight-rightheight)<=1)
            {
                height=max(leftheight,rightheight)+1;
                return true;
            }
            else
            {
                height=max(leftheight,rightheight)+1;
                return false;
            }
        }
    }
};

当然和前面一样,直接用函数返回值作为临时变量也是可以的,因为函数返回值只用来逻辑判断一次就可以了,不需要保留,引用传递的值调用完也就算完了。
代码改成如下的:

class Solution {
    public:
        bool isBalanced(TreeNode *root) {
            int height=0;
            return isBalancedHeight(root,height);
        }
        bool isBalancedHeight(TreeNode* root,int& height)
        {
            if(root==NULL) {height=0;return true;}
            else
            {
                int leftheight=0;
                int rightheight=0;
                if(isBalancedHeight(root->left, leftheight) && isBalancedHeight(root->right, rightheight) && abs(leftheight-rightheight)<=1)
                {
                    height=max(leftheight,rightheight)+1;
                    return true;
                }
                else
                {
                    height=max(leftheight,rightheight)+1;
                    return false;
                }
            }
        }
    };

因为鄙人之前都直接函数作为临时变量来参与逻辑判断语句,逻辑更精炼,这里三个与编译器会先算前两个,算完之后leftheight rightheight也都算出来了,所以后面应该不会出错

顺便赋上似乎很牛的博客:http://blog.csdn.net/luckyxiaoqiang/article/details/7518888

Posted by richard爱闹 - 7月 26 2014
如需转载,请注明: 本文来自 Richard

BTLevelOrder-SeparateLevel

今天偶然看到师弟站站大神的博客,题目本是求BT的高度,但是他用层序遍历的方法,突然发现这种代码之前好像都不是这么写的,于是有种发现新大陆的感觉。

主要是之前知道层序遍历,但是区分层的时候,要么是编程之美vector cur last来控制,借助的数据结构不那么make sense,要么miloyip的两个队列交换来记录每层的遍历,
总觉得这么一个功能还要用牛刀,于是终于看到用一个queue来实现,思路和编程之美一样,只需要添加每层遍历之前记录当前的queue大小的遍历就可以了,保证这一层访问到这里
一定结束了,但是不需要额外的cur last来记录,好的算法应该这样,这些细节是封装在DS里面的。

附上记录层序遍历结果的代码,以后层序遍历如果区分层就用这个了。注意里面有一点注意,就是for可能一个都没有,此时onelevel空,后面push到总结果要过滤掉空vector的情况。

vector<vector<int> > levelOrder(TreeNode *root) {
        vector<int> onelevel;
        vector<vector<int> > alllevel;

        if(root==NULL) return alllevel;

        queue<TreeNode*> Q;
        Q.push(root);
        TreeNode* p;


        onelevel.push_back(root->val);
        alllevel.push_back(onelevel);

        while(!Q.empty())
        {
            int size=Q.size();
            onelevel.clear();
            for(int i=0;i<size;i++)
            {
                p=Q.front();
                Q.pop();
                if(p->left!=NULL) 
                    Q.push(p->left), onelevel.push_back(p->left->val);
                if(p->right!=NULL)
                    Q.push(p->right), onelevel.push_back(p->right->val);
            }
            if(onelevel.size()!=0)
                alllevel.push_back(onelevel);
        }

        return alllevel;
    }

我之前也没想到这么简洁的层序遍历,mileyip博客里几个代码似乎也没有这么简洁的,编程之美团队也没想到么,虽然vector思路一样,但是queue的更好。

附上友情链接:
http://www.chengzhanzhan.cn/leetcode-2/maximum-depth-of-binary-tree/#comment-8 师弟的博客,强推
http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html mileyip的,还上了编程之美
http://blog.csdn.net/richardzrc/article/details/27677067 鄙人之前总结的,以后都会用上述的算法代替了,除非还有特殊需求。
: )

另外用这个简洁的算法连了下差不多的题,发现自己急于提交,很多细节都没考虑全,这个如果在面试一定会被扣分的,千万不要急着说完成了,一定要考虑全,不要怕时间长。

每次遍历之后奇偶层的bool变量都要反转的 ,然后每次遍历前onelevel都clear的,然后记得把第一层root push进去, 然后后面
如果onelevel可能为空的需要过滤一下。再考虑root空,从这样一个代码都是需要各方面都考虑全面的,如果onelevel为空了,
说明也是遍历到最后一层了,后面就结束了。

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int> >alllevel;
        vector<int> onelevel;
        if(root==NULL)
            return alllevel;
        queue<TreeNode*> Q;
        Q.push(root);
        onelevel.push_back(root->val);
        alllevel.push_back(onelevel);

        TreeNode*p;

        bool evenlevel=true;
        while(!Q.empty())
        {
            int size=Q.size();
            onelevel.clear();
            for(int i=0;i<size;i++)
            {
                p=Q.front();
                Q.pop();
                if(p->left!=NULL)
                    Q.push(p->left), onelevel.push_back(p->left->val);
                if(p->right!=NULL)
                    Q.push(p->right), onelevel.push_back(p->right->val);
            }
            if(onelevel.size()!=0)
            {
                if(evenlevel)
                    reverse(onelevel.begin(),onelevel.end());

                evenlevel=!evenlevel;
                alllevel.push_back(onelevel);
            }
        }
        return alllevel;
    }

Posted by richard爱闹 - 7月 26 2014
如需转载,请注明: 本文来自 Richard