Feb 7, 2016

与家书-初一上班

父母大人膝下、见字如唔：

见信，我已入睡，临春节佳日，遥祝父母安康，万事如意。

近年远在海外，身不由己，离家九千公里而有余，归少离多，我与众同辈，每逢佳节，无不搞到惭愧有加。而立未满，逾弱冠数载。飘洋越海求学，仍碌碌无为。外无以有所作为，成名成家，内无以常绕于膝下，朝夕相伴，以尽孝义。虽常无亲昵之言语，实则片刻不敢忘怀父母之恩。万望见谅，我在外面一切皆安好，顺利，望勿挂念。

工作已三月有余，夫人生光阴有几，只如白驹过隙。连日来，倍感韶华易逝。我虽业未精，但个人饮食起居皆能照应，不必为我谋钱财。望勿吝惜钱财，切不可节俭成性不舍用，私以为，钱财乃取其花之有道而后快即可。

身在寓中虽独处，不敢忘常警醒慎独。不能贪恋假期良辰美景，常自省，节劳，节欲，节饮食。食必淡节，眠必虚恬。方能以强健体魄迎接每日工作。

少时读书，诚愚钝，如今工作，实难以尽孝。无以锦绣博士以提高个人修养，诚因自己愚笨，未尽心竭力赴以学业。现已处社会，工作定当尽心尽责，学习必不敢怠慢。不求大富大贵，人中龙凤，但能凭一己之力小有成绩，技艺有所长，修养有所提升，为人处世有所成长，以慰双亲。

谨禀

Feb 6, 2016

程序员面试金典 chapter3 Stacks and Queues

数据结构栈的实现

根据某大学的教材，栈多用于递归(recursive)和多线程(multithread)，秉持先进后出(FILO)的原则，现在我要试着亲手实现一个基本的栈，基本的function应该有:

push()
pop()
peek()
isFull()
isEmpty() 顾名思义，isFull和isEmpty就是判断栈满栈空的的function，主要说下两个主要的函数，pop和push。以链表的形式定义一个struct来代表这个stack

struct elt {
  struct elt *next;int value;
};
typedef struct elt *Stack;

对于push来说主要做两件事情，第一先把此时stack指针指向的value赋值，第二部就是将指针指向next，具体代码如下：

void stackPush(Stack *s, int value)

{
    struct elt *e;
    e = malloc(sizeof(struct elt));
    assert(e);
     e->value = value;
     e->next = *s; *s = e;
}

那木pop呢，也很简单，就是将此时top的value取出来，再将next指向top的位置，而此时的next指向origin next的下一个，具体代码实现如下：

int stackPop(Stack *s){
    int ret;
    struct elt *e;
    assert(!stackEmpty(s));
    ret = (*s)->value;
    e = *s; *s = e->next;
    free(e);
    return ret;
}

第一题集合栈

题目描述，实现将每个大小为给定size的栈填满，并且当当前栈填满时新建一个栈。题目所给出的标准class 函数定义为:

class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
}

所以这题应该就是基本的入栈出栈，而所谓的“集合栈”就是另一层的入栈和出栈，最后的时候返回这个默认的”集合栈”。具体代码实现如下:

class SetOfStacks {
public:
    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
        int ope_size;
        ope_size = ope.size();
        
        vector<vector<int> > setofstacks;
        vector<int> stacks;
        for(int i = 0;i<ope_size;i++){
            if(ope[i][0] == 1){
                if(stacks.size() == size ){
                    setofstacks.push_back(stacks);
                    stacks.clear();
                    stacks.push_back(ope[i][1]);
                }
                else
                    stacks.push_back(ope[i][1]);
            }
            else if(ope[i][0] == 2){
                if (stacks.size() != 0) {
                        stacks.pop_back();
                    }
                else{
                    stacks = setofstacks[setofstacks.size()-1];
                    stacks.pop_back();
                    setofstacks.pop_back();
                }
            }
        }
        if(!stacks.empty())
            setofstacks.push_back(stacks);
        return setofstacks;
    }
};

第二题用两个栈实现队列

题目描述为用两个栈完成队列基本的pop和push 我没学过数据结构，所以还是先来看一下队列在数据结构的定义。队列不一样的是先进先出(FIFO)，并且有指向head和tail的指针，下面为简单队列实现的struct定义：

struct elt {
    struct elt *next;
    int value;
};
struct queue {
    struct elt *head;
    struct elt *tail;
};
  typedef struct queue *q;

那么这道题目就变成了，怎样用两个实现先进后出stack来实现先进先出的队列形式，我认为很自然的就会想到，将其中一个队列用来将原本的数据倒序，以作为原本数据的先进先出，而倒序了的数据自然符合先进后出的原则。一下为实现代码：

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
     int result;
        if(!stack2.empty())//判断是否为空，不为空那么说明已经压入了栈，倒序了stack1，直接pop就可以了
         {
            result=stack2.top();
            stack2.pop();
            return result;
         }
        else
        {  //不为空的话就需要重新压栈
            int num=stack1.size();
            for(int i=0;i<num;++i)
            {
                int temp=stack1.top();
                stack1.pop();
                stack2.push(temp);
            }                     
            result=stack2.top();
            stack2.pop();
            return result;
        }   
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

第三题双栈排序

题目描述为将一个乱序排放的数据栈重新排序，最大的元素在栈的顶端。既然有两个栈，那么实现方式应该和上一题大同小异，两个栈中的最顶元素进行比较和压栈出栈。首先，原始的数据链先pop_back()出最顶元素到新定义的栈中，当新定义的临时栈不为空时，每次循环比较最顶元素的大小，我天真的认为这个和数组中的冒泡法理想一样，通过多次的循环比较以达到排序。第一步新定义一个栈，并且pop_back()出原数据栈中的最顶元素:

vector<int> forSort;
        if(numbers.size() <= 1) return numbers;
        forSort.push_back(numbers.back());
        numbers.pop_back();

第二步，建立第一层循环，while loop直到比较到最先压入原数据栈的元素

while(numbers.size() > 0)
            {
                int temp = numbers.back();
                numbers.pop_back();
                int popNum = 0;  
            }

每一次首先拿出原数据栈中的最顶元素，以一个integer作为存储以便之后的比较，将此时最顶元素pop_back()。将取出来的原数据栈的顶层元素与届时的sort stack的顶层元素作比较，将更大的元素压入sort stack，而将较小的元素重新压回原数据栈，这样在最后把循环比较之后剩余在原数据栈中的所有元素按顺序一一压入sort stack数据栈中，这样最大的元素就最后压入最终返回的stack。示例代码如下：

while(!forSort.empty() && temp > forSort.back()){
                    numbers.push_back(forSort.back());
                    forSort.pop_back();
                    popNum++;
                }
                forSort.push_back(temp);
                while(popNum > 0){
                    forSort.push_back(numbers.back());
                    numbers.pop_back();
                    popNum--;
                }

第四题猫狗收容所

题目描述，有两种收养方式，一个是收养所有最早进入收容所的动物，另一个是选择性的收养最早进入收容所的猫或者狗。首先，最早意味着先进先出，所以应该选择队列的数据结构来做。因为有猫狗两种动物，都有先进先出，所以第一步先将两个队列分别对应猫和狗定义。

queue<int> cat;
queue<int> dog;
vector<int> vec;

首先在循环内判断是入收养所还是被收养，也就是入还是出的问题:

if(ope[i][0] == 1)
            {
                //入收养所
            }
 else if (ope[i][0] == 2)
{
      //出收养所
}

情况很简单了，那么入收养所的时候只需要一个判断，是狗还是猫，出收养所的时候麻烦一些，第一步判断是哪种收养方式，若是第二种就只需要进一步看猫狗的选择直接在cat和dog两个定义的队列中pop最先进入的元素即可。若是第一种那么就需要比较了，在两个定义的队列中选取更早进入的一个。所以这就需要在每一次push到两个猫狗队列的同时，增加一个计数的index，完整的代码示例如下：

class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        // write code here
        queue<int> cat;
        queue<int> dog;
        queue<int> s
        vector<int> vec;
        int index=0;
        int size1=ope.size();
        for(int i=0;i<size1;i++)
        {
            int kind=ope[i][0];
            if(kind==1)
            {
                if(ope[i][1]>=0)
                {
                    dog.push(index++);
                    dog.push(ope[i][1]);
                }
                else
                {
                    cat.push(index++);
                    cat.push(ope[i][1]);
                }
            }
            else
            {
                if(ope[i][1]==0)
                {
                    int min=0;
                    if(cat.empty()&&!dog.empty())
                        min=1;
                    if(!cat.empty()&&dog.empty())
                        min=-1;
                    if(!cat.empty()&&!dog.empty())
                        min=dog.front()>cat.front()?-1:1;
                    if(min==-1)
                    {
                        cat.pop();
                        vec.push_back(cat.front());
                        cat.pop();
                    }
                    if(min==1)
                    {
                        dog.pop();
                        vec.push_back(dog.front());
                        dog.pop();
                    }
                }
                else
                {
                    if(ope[i][1]==1&&!dog.empty())
                    {
                        dog.pop();
                        vec.push_back(dog.front());
                        dog.pop();
                    }
                    if(ope[i][1]==-1&&!cat.empty())
                    {
                        cat.pop();
                        vec.push_back(cat.front());
                        cat.pop();
                    }
                }
 
            }
        }
        return vec;
    }
};

Jan 24, 2016

程序员面试金典Chapter2

第一题输出链表中的倒数第n个结点

给出的结构体为：

struct ListNode {

  int val;

  struct ListNode *next;

  ListNode(int x) :

  val(x), next(NULL) {

    }
};

我觉得首先应该要把整个链表的长度先求出来，然后在不判断不遍历整个链表的情况下只比对数字。下面是示例代码：

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* temp = pListHead;
        int count=0;
        while(temp){
            count++;
            temp=temp->next;
        }
        for(int i=0;i<count;){
            if(i == count-k){
                return pListHead;
                break;
            }
            pListHead=pListHead->next;
            i++;
        }
        return NULL;
    }
};

第二题删除单向链表中的一个节点

我觉得删除节点分两步，一个是删除单向链表中上一个只想该节点的链接和该节点指向下一个节点的链接，而变成第n-1个节点->next指向原先的n+1个节点。第二步就是当删除了链接并不代表当前删除的节点不占用内存空间，所以就要free这个空间。下面是通过的代码示例：

class Remove {
public:
    bool removeNode(ListNode* pNode) {
        // write code here
        if(pNode->next == NULL)
            return false;
        ListNode* temp=pNode->next;
        pNode->next=temp->next;
        free(temp);
        return true;
    }
};

第三题分割链表

题目描述的是要将小于给定x值的节点与大于x值的节点分割成两部分，而本身链表的顺序不能够改变。最后需要返回小于x值的链表+大于x值的链表的头节点。想法很单纯，既然要分割链表就自然需要定义两个新的链表，第一步遍历整个给定的链表将每个节点的值与给定的x值作对比，当小于x的时候就把新定义的p1链表的下一个节点指向此时的temp节点，而当大于x值得时候自然就将此时的temp节点赋给p2的下一个节点。在过程中需要保存两个新定义链表的表头，也就是要判断一下p1和p2的头结点以便最后返回头节点。下面为最终的代码示例：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* p1 = NULL;
        ListNode* p2 = NULL;
        ListNode* temp = NULL;
        ListNode* p1Head = NULL;
        ListNode* p2Head = NULL;
        while(pHead){
            temp = pHead->next;
            if(pHead->val<x){
                if(p1 == NULL){
                    p1=pHead;
                    p1Head=pHead;
                }
                   
                else{
                  p1->next=pHead;
                  p1=p1->next;  
                }
            }
            else{
                if(p2 == NULL){
                   p2=pHead;
                    p2Head=pHead;
                }
                    
                else{
                	p2->next=pHead;
                	p2=p2->next; 
                }   
            }
            pHead=temp;
        }
        if(p2)
            p2->next=NULL;
        if(p1 == NULL)
            p1Head=p2Head;
        else
            p1->next=p2Head;
        return p1Head;
    }
};

第四题链表A+B

题目描述为相加两个给出的链表A与B，比如说：{1,2,3} + {3,2,1}需要返回一个结果链表为{4,4,4}。在中间的加法运算中主要分为两步，第一步计算每每两个数字相加的结果，第二部提取出相应结果的进位和需要保留的个位数结果。下面为这一部分实现的代码示例：

val1 = a?a->val:0;
val2 = b?b->val:0;
int val = val1 + val2+carry;
carry = val/10;

定义两个新的ListNode结构的新链表，一个用来做最后返回的链表头，一个作为链表的存储。因为不知道两个给定的链表长度，所以判断的时候两个链表都判断是否为NULL再进入循环来遍历两个链表。当遍历时判断一下最终返回链表的头节点，下面为完整的代码示例：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Plus {
public:
    ListNode* plusAB(ListNode* a, ListNode* b) {
        // write code here
        ListNode* pNode = NULL;
        ListNode* pHead = NULL;
        int carry=0;
        if(a == NULL && b == NULL)
            return NULL;
        while(a || b || carry>0){
            int val1,val2;
            val1 = a?a->val:0;
            val2 = b?b->val:0;
            int val = val1 + val2+carry;
            carry = val/10;
            
            ListNode* temp = new ListNode(val%10);
            if(pNode == NULL){
                pNode = temp;
                pHead = pNode;
            }
            else{
                pNode->next = temp;
                pNode=pNode->next;
            }
            a=a?a->next:NULL;
            b=b?b->next:NULL;
        }
        pNode->next = NULL;
        return pHead;
    }
};

第五题回文链表

题目描述是这样的，需要判断一个给定的链表是否为回文链表，若给定链表如{1,2,3,2,1}则返回true，反之返回false。想法应该说并不难，但是我在链表的地址和赋值之间来回徘徊了很久才大概明白代码测试一直不能通过是因为什么，下面先来看这个代码

class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here·
        ListNode* reverseNode = NULL;
        ListNode* originalNode = pHead;
        ListNode* temp = NULL;
        ListNode* next = NULL;
        if(pHead == NULL)
            return false;
        while(pHead){
            next = pHead->next;
            temp = reverseNode;//temp=current
            reverseNode = pHead;//prev=current
            reverseNode->next = temp;//next=current
            pHead = next;
        }
        while(originalNode && reverseNode){
            if(originalNode->val != reverseNode->val){
                return false;
                break;
            }
            originalNode = originalNode->next;
            reverseNode = reverseNode->next;
        }
        return true;
    }
};

首先定义了两个链表节点分别指向第一个给定节点和NULL，然后遍历给定的链表将链表反转。在遍历的过程中，将reverse这个想象中是反转后的链表先传给一个temp以做保留，将reverse指向遍历当前的节点，而reverse->next指向先前的地址也就是temp，然而此时我想也就破坏了给定链表指向next的这个节点链接了。先贴一个正常反转链表并返回反转之后链表表头的leetcode上通过的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp,*current,*next;
        ListNode* reverse = NULL;
        current = head;
        //prev = NULL;
        while(current){
            next = current->next;
            temp = reverse;
            reverse = current;
            reverse->next = temp;
            current = next;
        }
        return reverse;
    }
};

同样将这段代码整齐的贴进这道题再去遍历做比较，依然会不能通过测试，始终返回true，以我的专业出身和智商还没有真正深究出原因，不过我猜想是因为永远指向同一个地址那么比较的时候肯定会不如人意，当在反转时有必要将反转之后的链表reverse和在遍历当前给定链表的时候new一个新的ListNode而不是在同一条地址链上进行多次的重复操作以至于最后比对的original链表丢失。这也是为什么当只是单纯做反转链表的时候遍历第一步就要保存好当前节点next指向的地址。所以重新定义并new一个链表reverse为NULL，然后遍历整个给定的链表，将当前节点值给该次循环中的reverse节点，将该被改动的reverse节点的next指向上一循环中的reverse节点，以此类推，直到把NULL推到最后一个位置。这个方法我很熟悉，跟做硬件编译时传输10101010….类的数据相差不大，都是按照一定的顺序你推我我推你到穷尽。

这里很想插一句

一直以来人们给所谓程序员配的图满是10101010…..，看黑客帝国就知道了，我想说没错，计算机是接受二进制，可是在我自学Nodejs开发和这些满满的上层软件面向对象碰到过10101010现象的机会远远不如我作为公司的一名新晋嵌入式开发来的平常。

程序员分很多种，我希望我哪种都不是，我不是一名程序员或者软件、硬件工程师，我只是一名普通人，懂得少学得慢。

好吧，插了一句嘴，下面来贴上纠结了我一下午的最终通过代码示例：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        
        ListNode* temp = NULL;
        ListNode* current = pHead;
        ListNode* reverse = new ListNode(NULL);
        if(pHead == NULL)
            return false;
        while(current){
            //temp = reverse;
            //reverse->next = temp;
            //reverse = current->next;
            temp=reverse;
            ListNode* nextnode = new ListNode(current->val);//reverse = current->next;
            reverse = nextnode;
            reverse->next = temp;
            current = current->next;
        }
         
        while(pHead){
            if(pHead->val!=reverse->val)
                {
                return false;
                break;
            }
                
            pHead=pHead->next;
            reverse=reverse->next;
        }
        return true;
    }
};

CATAMO(Bingjie Gao)

与家书-初一上班

程序员面试金典 chapter3 Stacks and Queues

数据结构 栈的实现

第一题 集合栈

第二题 用两个栈实现队列

第三题 双栈排序

第四题 猫狗收容所