牛客剑指offer刷题记录（一）

迷南。 2022-06-13 07:57 164阅读 0赞

牛客刷题记录  
[github][]

## **1.二维数组查找** ##

本题的关键就在于二维数组具有一定的特性：  
从左往右，从上往下呈递增序列。

如果二次遍历，就失去了这个题目的意义因为复杂度是O(n2)

对于这个矩阵来说，左上角的值a(0,0)一定为最小值，右下角的值a(m,n)一定是最大值，当与target比较完了之后，我们不知道该往哪边走。因此，可以选取左下角a(m,0)或者右上角a(0,n)开始，这样如果target比较大，一定往下(上)走，target比较小，一定往左(右)走。

class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            int m = array.size();
            int n = array[0].size();
            if (m == 0 || n == 0)
                return false;
            int i = 0;
            int j = n - 1;
            while ((i < m)&&(j >= 0))
            {
                if (array[i][j] < target)
                    ++i;
                else if (array[i][j] > target)
                    --j;
                else
                    return true;
            }
            return false;
        }
    };

--------------------

## **2.替换空格** ##

这题主要是考察，对数组扩容的时候可以先计算扩容后的大小，比如这题，先计算空格有多少个，然后加上原有字符的个数，就是扩容后的大小。最后插入的时候从后往前操作，可以保证算法的**原地的执行（in place）**

此题的扩展就是，两个排好序的数组合并成一个有序数组，可以考虑先对其中一个数组进行扩容，之后再把另一个数组的值从后往前插入。

class Solution {
    public:
        void replaceSpace(char *&str,int length) {
            if(NULL==str)
                return;
            char *p=str;
            int space=0;
            while(*p!='\0')
            {
                if(*p==' ')
                    ++space;
                ++p;
            }
            char *copy= (char *)malloc((2*space+length+1)*sizeof(char));
            *(copy+2*space+length)='\0';
            int j=2*space+length-1;
            int i=length-1;
            while(i>=0)
            {
                if(*(str+i)==' ')
                {
                    *(copy+j)='0';
                    *(copy+j-1)='2';
                    *(copy+j-2)='%';
                    j-=3;
                    --i;
                }
                else
                {
                    *(copy+j)=*(str+i);
                    --j;
                    --i;
                }
            }
            char *tmp=copy;
            copy=str;
            str=tmp;
            cout<<str<<endl;
        }
    };

--------------------

## **3.从尾到头打印链表** ##

链表这个数据结构，如果指针域是单向的，那么它的迭代也是单向的，也即不能向数组那样，随机的访问最后一个元素，再往前打印。

解决的方案有很多。最直观的方法是，从前往后遍历，然后将遍历的value压栈，这样弹栈的时候就是原链表相反的顺序。

递归是另一种形式，递归的调用函数使其以链表的下一个节点做当前节点，就达到了遍历的效果，然后在递归返回之际打印相应值，就反序了。因为递归其实就是函数栈，所以思想跟上一个差不多

class Solution {
    private:
        void help(ListNode * head,vector<int>&v)
        {
            if(head!=NULL)
            {
                if(head->next!=NULL)
                {
                    help(head->next,v);
                }
                v.push_back(head->val);
            }
        }
    public:
        vector<int> printListFromTailToHead(ListNode* head) {
            if(NULL==head)
                return vector<int>();
            vector<int>tmp;
            help(head,tmp);
            return tmp;
    
        }
    };

--------------------

## **4.重建二叉树** ##

此题的扩展就是，假设我们现在要序列化一个二叉树，那么我们可以保存其先序和中序的序列，数据到remote端以后，然后再rebuild一下。

先序遍历序列找到根节点，中序遍历序列将又通过根节点划分两个左右子树。为了方便快捷的在中序遍历的序列中找到根节点所在位置，可以用一个map记录根节点值和索引的key-value对。

此外，在先序遍历中，要找到子树根的位置，还必须通过中序遍历计算划分之后，左子树和右子树的节点个数。因此，我用了4个参数来记录：

preStart//子树先序开始
    preEnd//子树先序结束
    inStart//子树中序开始
    inEnd//子树中序结束

递归的方式去构建二叉树，每次都去更新这些数的值

class Solution {
    private:
        TreeNode * help(vector<int>&pre,//pre seq
            vector<int>&vin,//in seq
            int preStart,   //pre start idx
            int preEnd,     //pre end idx
            int inStart,    //in start idx
            int inEnd,    //in end idx
            unordered_map<int, int>&index)// map find idx in vin
        {
            if (inStart > inEnd)//
            {
                return NULL;
            }
            //先拿到根节点的值
            int rootval = pre[preStart];//root val
            //创建根节点
            TreeNode * root = new TreeNode(rootval); //root node
            //找到中序遍历中根节点的索引
            int idx = index[rootval];//root index in vin
            //split vin with idx
            //通过索引计算中序中对左右子数的划分（计算节点的个数），以便在先序中找到子树的根
            //递归左子树
            root->left = help(pre, vin, preStart + 1, preStart + idx - inStart, inStart, idx - 1, index);
            //递归右子树
            root->right = help(pre, vin, preStart + idx - inStart + 1, preEnd, idx + 1, inEnd, index);
            return root;
        }
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
        {
            unordered_map<int, int>index;
            //计算中序遍历序列中 值和索引的Key-value对
            for (int i = 0; i < vin.size(); ++i)
            {
                index[vin[i]] = i;
            }
            return help(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1, index);
    
        }
    };

--------------------

## **5.两个栈实现队列** ##

栈是后进先出，first-in-last-out  
队列是先进先出，first-in-first-out

现在由两个栈，将元素插入到第一个栈中，再逐个弹出压入第二个栈中，这样在栈1中先入栈的元素，到了栈2中就越靠近栈顶，然后从栈2中弹栈，就达到了FIFO的效果。

这里，不是每次弹栈都要讲栈1的序列全部压入栈2，只有当栈2为空的时候才这样做。

class Solution
    {
        public:
            void push(int node)
            {
                stack1.push(node);
            }
            int pop() 
            {
                if(!stack1.empty()||!stack2.empty())
                {
                    if(stack2.empty())
                    {
                        while(!stack1.empty())
                        {
                            stack2.push(stack1.top());
                            stack1.pop();
                        }
                    }
                    int t=stack2.top();
                    stack2.pop();
                    return t;
                }
                return -1;
            }
        private:
            stack<int> stack1;
            stack<int> stack2;
    };

[github]: https://github.com/NearXdu/-offer