51.构建乘积数组

• 题目：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。即不包括B[i]的所有乘积
• 思路：

B[i]的值可以看作下图的矩阵中每行的乘积。
下三角用连乘可以很容求得，上三角，从下向上也是连乘。
因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n=A.size();
        vector<int> b(n);
        int ret=1;
        for(int i=0;i<n;ret*=A[i++]){
            b[i]=ret;
        }
        ret=1;
        for(int i=n-1;i>=0;ret*=A[i--]){
            b[i]*=ret;
        }
        return b;
    }
};

52.正则表达式匹配

• 题目：请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
• 思路：

解这题需要把题意仔细研究清楚
首先，考虑特殊情况：
1. 两个字符串都为空，返回true
2. 当第一个字符串不空，而第二个字符串空了，返回false（因为这样，就无法匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成功的，比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次，所以有可能匹配成功）
之后就开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。但考虑到pattern下一个字符可能是‘*’， 这里我们分两种情况讨论：pattern下一个字符为‘*’或不为‘*’：
1. pattern下一个字符不为‘*’：这种情况比较简单，直接匹配当前字符。如果匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的“匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的当前字符为‘.’,同时str的当前字符不为‘\0’。
2. pattern下一个字符为‘*’时，稍微复杂一些，因为‘*’可以代表0个或多个。
这里把这些情况都考虑到：
a. 当‘*’匹配0个字符时，str当前字符不变，pattern当前字符后移两位，跳过这个‘*’符号；
b. 当‘*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符不变。（这里匹配1个或多个可以看成一种情况，因为：当匹配一个时，由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况a；当匹配多于一个字符时，相当于从str的下一个字符继续开始匹配）
之后再写代码就很简单了。

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if (*str == '\0' && *pattern == '\0')
            return true;
        if (*str != '\0' && *pattern == '\0')
            return false;
        //if the next character in pattern is not '*'
        if (*(pattern+1) != '*')
        {
            if (*str == *pattern || (*str != '\0' && *pattern == '.'))
                return match(str+1, pattern+1);
            else
                return false;
        }
        //if the next character is '*'
        else
        {
            if (*str == *pattern || (*str != '\0' && *pattern == '.'))
                return match(str, pattern+2) || match(str+1, pattern);
            else
                return match(str, pattern+2);
        }
    }
};

53.表示数值的字符串

• 题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
• 思路：见代码注释

class Solution {
public:
    bool isNumeric(char* string)
    {
    // 标记符号、小数点、e是否出现过
        bool sign = false, decimal = false, hasE = false;
        for (int i = 0; i < strlen(string); i++) {
            if (string[i] == 'e' || string[i] == 'E') {
                if (i == strlen(string)-1) return false; // e后面一定要接数字
                if (hasE) return false;  // 不能同时存在两个e
                hasE = true;
            } else if (string[i] == '+' || string[i] == '-') {
                // 第二次出现+-符号，则必须紧接在e之后
                if (sign && string[i-1] != 'e' && string[i-1] != 'E') return false;
                // 第一次出现+-符号，且不是在字符串开头，则也必须紧接在e之后
                if (!sign && i > 0 && string[i-1] != 'e' && string[i-1] != 'E') return false;
                sign = true;
            } else if (string[i] == '.') {
              // e后面不能接小数点，小数点不能出现两次
                if (hasE || decimal) return false;
                decimal = true;
            } else if (string[i] < '0' || string[i] > '9') // 不合法字符
                return false;
        }
        return true;
    }
}; 

54.字符流中的第一个不重复字符

• 题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
• 思路：用hash表判断即可

class Solution
{
public:
  //Insert one char from stringstream
    string s;
    char hash[256]={0};
    void Insert(char ch)
    {
        s+=ch;
        hash[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
         
        int size=s.size();
        for(int i=0;i<size;++i)
        {
            if(hash[s[i]]==1)
                return s[i];
        }
        return '#';
    }

};

55.链表中环的入口结点

• 题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
• 思路：

如果链表中环 有n个结点，指针P1在链表上向前移动n步，然后两个指针以相同的速度向前移动。
当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈又回到了入口结点。
所以首先要得到环中结点的数目。

• 第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
• 第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
    if(pHead == NULL || pHead->next == NULL)
            return NULL;
        ListNode* p1 = pHead;
        ListNode* p2 = pHead;
        while(p2 != NULL && p2->next != NULL ){
            p1 = p1->next;
            p2 = p2->next->next;
            if(p1 == p2){
                p2 = pHead;
                while(p1 != p2){
                    p1 = p1->next;
                    p2 = p2->next;
                }
                if(p1 == p2)
                    return p1;
            }
        }
        return NULL;
    }
};

56.删除链表中重复的结点

• 题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
• 思路：
  

1.加一个头结点用于储存Head地址
2.两个临时指针p,q
3.找前后不相等的节点

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
     if (pHead == NULL || pHead->next == NULL)
            return pHead;
        /*---------先为链表创建一个头结点---------*/
        int firstNumber = pHead->val;
        //假设我的头结点数值为-1
        int myFirst = -1;
        //万一链表的头结点也为-1，那么我就改成-2
        if (myFirst == firstNumber)
        {
            myFirst = -2;
        }
        ListNode *head = new ListNode(myFirst);
        head->next = NULL;
        head->next = pHead;
        ListNode *p = head;
        ListNode *q = head->next;
        while (q)
        {
            while (q->next && (q->next->val == q->val))
            {
                q = q->next;
            }
            if (p->next != q)
            {
                 
                q = q->next;
                p->next = q;
            }
            else
            {
                p = q;
                q = q->next;
            }
        }
        //返回的时候，注意去掉头结点（自己创建的辅助节点）
        return head->next;
    }
};

57.二叉树的下一个结点

• 题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
• 思路：

首先知道中序遍历的规则是：左根右，然后作图

结合图，我们可发现分成两大类：

1. 有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G）
2. 没有右子树的，也可以分成两类，a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (pNode == NULL)
            return NULL;
        if (pNode->right != NULL)
        {
            pNode = pNode->right;
            while (pNode->left != NULL)
                pNode = pNode->left;
            return pNode;
        }
        while (pNode->next != NULL)
        {
            TreeLinkNode *proot = pNode->next;
            if (proot->left == pNode)
                return proot;
            pNode = pNode->next;
        }
        return NULL;
    }
};

58.对称的二叉树

• 题目：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
• 思路：

代码很简单，关键还是知道怎么样才能判断一个二叉树是否对称，只要采用前序、中序、后序、层次遍历等任何一种遍历方法，分为先左后右和先右后左两种方法，只要两次结果相等就说明这棵树是一颗对称二叉树。

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
        queue<TreeNode*> q1,q2;
        TreeNode *left,*right;
        q1.push(pRoot->left);
        q2.push(pRoot->right);
        while(!q1.empty() and !q2.empty())
        {
            left = q1.front();
            q1.pop();
            right = q2.front();
            q2.pop();
            //两边都是空
            if(NULL==left && NULL==right)
                continue;
            //只有一边是空
            if(NULL==left||NULL==right)
                return false;
             if (left->val != right->val)
                return false;
            q1.push(left->left);
            q1.push(left->right);
            q2.push(right->right);
            q2.push(right->left);
        }
        return true;
    }
};

59.按之字形顺序答应二叉树?

• 题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
• 思路：

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if (pRoot == NULL)
            return res;
        vector<TreeNode*> q1;
        vector<TreeNode*> q2;
        q1.push_back(pRoot);
        bool model = true;//ture表示方向从左向右
        while (!q1.empty()){
            q2 = q1;
            q1.clear();
            vector<int> row;
            while (!q2.empty()){//把当前层全部访问，并将孩子按一定顺序入栈
                TreeNode *temp = q2.back();
                q2.pop_back();
                row.push_back(temp->val);
                if (model == true){//turew为从左向右
                    if (temp->left) q1.push_back(temp->left);
                    if (temp->right) q1.push_back(temp->right);
                }
                else{//false为从右向左
                    if (temp->right) q1.push_back(temp->right);
                    if (temp->left) q1.push_back(temp->left);
                }
            }
            model = !model;//变换方向
            res.push_back(row);
        }
        return res;
    }  
};

60.把二叉树打印成多行???

• 题目：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
• 思路：bfs方法

class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>> result;
            if(pRoot==NULL)
                return result;
            queue<TreeNode*> q;
            q.push(pRoot);
            q.push(NULL);
            vector<int> re;
            while(!q.empty()){
                TreeNode* tmp=q.front();
                q.pop();
                
                if(tmp==NULL){
                    result.push_back(re);
                    re.clear();
                    if(q.size()>0)
                        q.push(NULL);
                }
                else{
                    re.push_back(tmp->val);
                    if(tmp->left) q.push(tmp->left);
                    if(tmp->right) q.push(tmp->right);
                }
            }
            return result;
        }
};