剑指offer - 栈的压入、弹出序列

发表于 2017-08-22 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106

题意

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

题解

借用一个辅助栈，根据入栈序列来入栈，每次入栈，然后根据出栈序列出栈，直到与出栈序列不匹配。如果是正确的出栈序列，最后辅助栈应该为空，否则不是正确的栈。

class Solution
{
    stack<int> st;
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV)
    {
        int index = 0;
        for(int i=0;i<pushV.size(); i++)
        {
            st.push(pushV[i]);
            while(!st.empty())
            {
                if(st.top()!=popV[index]) break;
                st.pop();
                index++;
            }
        }
        return st.empty();
    }
};

剑指offer - 包含min函数的栈

发表于 2017-08-22 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/4c776177d2c04c2494f2555c9fcc1e49

题意

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

题解

定义两个栈，一个栈（value）正常用，另一个栈（min）存放栈底到栈顶的最小元素，push时，比较min栈栈顶元素的push元素的值，压入两者中较小值。pop时，min栈也弹出。所以min栈顶即为当前栈中所有元素的最小值。

class Solution {
private:
    stack<int> valueStack;
    stack<int> minStack;
public:
    void push(int value) {
        valueStack.push(value);
        if(minStack.empty()||value<minStack.top())
            minStack.push(value);
        else
            minStack.push(minStack.top());
    }
    void pop() {
        valueStack.pop();
        minStack.pop();
    }
    int top() {
        return valueStack.top();
    }
    int min() {
        return minStack.top();
    }
};

剑指offer - 顺时针打印矩阵

发表于 2017-08-22 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a

题意

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

题解

记录左右上下四个边界值，以一圈为一个周期循环。
注意可能，最后一圈不够一圈。

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> ans;
       int xmin = 0,xmax = matrix.size()-1;
       int ymin = 0,ymax = matrix[0].size()-1;
       while(1){
            for(int i=ymin;i<=ymax;i++)
                ans.push_back(matrix[xmin][i]);
            if(++xmin>xmax) break;
            for(int i=xmin;i<=xmax;i++)
                ans.push_back(matrix[i][ymax]);
            if(ymin>--ymax) break;
            for(int i=ymax;i>=ymin;i--)
                ans.push_back(matrix[xmax][i]);
            if(xmin>--xmax) break;
            for(int i=xmax;i>=xmin;i--)
                ans.push_back(matrix[i][ymin]);
            if(++ymin>ymax) break;
       }
       return ans;
    }
};

剑指offer - 对称的二叉树

发表于 2017-08-22 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb

题意

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

题解

递归。

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
        return isSame(pRoot->left,pRoot->right);
    }

    bool isSame(TreeNode * left,TreeNode * right){
        if(left==NULL&&right==NULL)
            return true;
        if(left!=NULL&&right!=NULL)
            return left->val==right->val&&
                isSame(left->left,right->right)&&
                isSame(left->right,right->left);
        return false;
    }
};

顺便贴上建树的代码，建树是按照二叉树层次遍历的思想来建的。
例如树对应的序列为：A B C D E F x x x G H x I
表示的树如下图：

TreeNode * build(string seq){
    if(seq==""||seq[0]=='#') return NULL;
    int index = 0;
    TreeNode * root  = new TreeNode(seq[index++]-'0');
    queue<TreeNode *> que;
    que.push(root);
    while(index<seq.size()){
        TreeNode * top = que.front();
        que.pop();
        if(isdigit(seq[index])){
            top->left = new TreeNode(seq[index++]-'0');
            que.push(top->left);
        }else if(seq[index]=='#'){
            index++;
            top->left = NULL;
        }
        if(index>=seq.size()) break;

        if(isdigit(seq[index])){
            top->right = new TreeNode(seq[index++]-'0');
            que.push(top->right);
        }else if(seq[index]=='#'){
            index++;
            top->right = NULL;
        }
    }
    return root;
}

剑指offer - 二叉树的镜像

发表于 2017-08-22 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/564f4c26aa584921bc75623e48ca3011

题意

操作给定的二叉树，将其变换为源二叉树的镜像。

题解

递归地将左右儿子交换即可。

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot==NULL) return ;
        swap(pRoot->left,pRoot->right);
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};

剑指offer - 树的子结构

发表于 2017-08-21 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88

题意

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）。

题解

递归判断。

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};

class Solution {
public:
    bool isSubtree(TreeNode * pRoot1,TreeNode * pRoot2){
        if(pRoot2==NULL) return true;
        if(pRoot1==NULL) return false;
        if(pRoot1->val!=pRoot2->val) return false;
        return isSubtree(pRoot1->left,pRoot2->left)
            &&isSubtree(pRoot1->right,pRoot2->right);
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot2==NULL||pRoot1==NULL) return false;
        return isSubtree(pRoot1,pRoot2)||
                HasSubtree(pRoot1->left,pRoot2)||
                HasSubtree(pRoot1->right,pRoot2);
    }
};

剑指offer - 合并两个排序的链表

发表于 2017-08-20 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/d8b6b4358f774294a89de2a6ac4d9337

题意

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

题解

一种方法就是新建一条链表，依次按照顺序将两条链表中的点加上去，当然这回花费O（N）的空间。
也可以不用这O（N）的空间，用原有的链条，改变指针指向，是的两条链表连成一条，也就是，将一条链表插入另一条链表。

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==NULL) return pHead2;
        if(pHead2==NULL) return pHead1;
        ListNode * p1 = pHead1,*p2 = pHead2;
        //使得p1的第一个元素小于p2的第一个元素
        if(p1->val > p2->val){
            swap(p1,p2);
            swap(pHead1,pHead2);
        }

        ListNode * pre;
        while(p1&&p2){
            while(p1&&p1->val <= p2->val){
                pre=p1;
                p1=p1->next;
            }
            pre->next=p2;
            if(p1==NULL) break;
            while(p2&&p2->val <= p1->val){
                pre=p2;
                p2=p2->next;
            }
            pre->next=p1;
        }
        if(p2)
            pre->next=p2;
        return pHead1;
    }
};

剑指offer - 反转链表

发表于 2017-08-20 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca

题意

输入一个链表，反转链表后，输出链表的所有元素。

题解

将链表的指向反转即可，注意改变指向前要保存下原有的指向。

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL) return NULL;
        ListNode * pre=NULL,* cur=pHead,* store=pHead->next;
        while(cur){
            store=cur->next;
            cur->next=pre;
            pre=cur;
            cur=store;
        }
        return pre;
    }
};

剑指offer - 链表中环的入口结点

发表于 2017-08-20 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4

题意

一个链表中包含环，请找出该链表的环的入口结点。

题解

方法一
那个set存放每个节点，如果遍历链表时，遇到set中有的节点，那他就是环的入口。这种方法不仅需要额外的空间，还需要每次判断节点是否在set中，效率低下。
方法二
断链法。用两个指针，p1在前，p2紧随其后，每次p1移动，都将p2的next置为NULL，这样当找到尾节点时，就是环的入口。
不过这种方法会破坏链表的结构。并且还有一个问题，这种方法没有办法判断是否有环，没有环的输入会返回最后一个节点，所以，我认为并不能算正确。

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

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

方法三
快慢指针。一个快指针fast，一个慢指针slow，起点均为头节点，fast移动速度是slow移动速度的两倍。如果没有环，两者不会相遇，fast就会碰到NULL，如果有环，那么两者一定会相遇，并且相遇的点一定在环上。
如图，A为起点，B为环的入口，C为fast和slow相遇的点。

相遇时，假设slow走的距离是X，fast为2X,fast比slow多走的一定是环长度的整数倍，假设环长度为L,多走的就是kL，2X-X=kL,也就是shuoslow走的距离是kL，假设链表断开环的长度为N。
也就是图中，A和C的长度为kL，如果此时两个指针p1和p2，一个在A点，一个在C点，那么两个相同速度行进，再经过kL的路程，两个都会到C点，而且最后的B到C之间的路是携手共进的，所以其实当两者相遇时，我们就已经确定了环的入口，就是B。

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead==NULL) return NULL;//链表为空
        bool flag=true;
        ListNode *p1=pHead,*p2=pHead;
        do{
            p2=p2->next;
            flag=!flag;
            if(flag)
                p1=p1->next;
        }while(p2&&p1!=p2);
        if(p2==NULL) return NULL;//没有环
        p2=pHead;
        p1=p1->next;
        while(p1!=p2){
            p1=p1->next;
            p2=p2->next;
        }
        return p1;
    }
};

剑指offer - 链表中倒数第k个结点

发表于 2017-08-19 | 更新于 2020-09-15

题目

https://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a

题意

输入一个链表，输出该链表中倒数第k个结点。

题解

单向链表没有指向上个节点的指针，所以无法倒数。
可以正着扫一遍，计算总长度，然后就可以计算出是正数第几个。然后再扫描一遍。
也可以不扫两遍，用两个指针，p和q,p先移动，移动到第k个节点是，q开始移动，p移动到末尾时，q正好为倒数第k个节点。

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==NULL||k==0) return NULL;
        ListNode * p=pListHead,*q=pListHead;
        int pc=1;
        while(p){
            if(pc>k) q=q->next;
            p=p->next;
            pc++;
        }
        if(pc<=k) return NULL;
        return q;
    }
};