剑指offer刷题记(C++版本)

bool Find(int target, vector<vector<int> > array) {
        if(array.empty())    return false;
        int rows=array.size();
        int cols=array[0].size();
        int row=0;
        int col=cols-1;
        while(row<rows&&col>=0)
        {
            if(array[row][col]==target)  return true;
            else if(array[row][col]>target)
            {
                col--;
            }
            else  row++;
        }
        return false;
    }

 //C风格的字符串最后一个字符是\n，而且是记在字符串长度里的。
    void replaceSpace(char *str,int length) {
        int i=0;
        int cnt=0;
        
        if(length==0||str==nullptr) return ;     //空字符串
        
        for(i=0;i<length;i++)      //统计空格数
        {
            if(str[i]==' ')
                cnt++;
        }
        if(cnt==0)  return;     //如果没有空格自然不用替换
        
        int newlength=length+2*cnt;     //新字符串的长度 
        
        int index_new=newlength-1;
        int index_old=length-1;
        
        while(index_old>=0&&index_new>index_old)   //没有到头或者两个指针追上了
        {
            if(str[index_old]==' ')
            {
                //依次替换三个字符，并且把index_old--
                str[index_new--]='0';
                str[index_new--]='2';
                str[index_new--]='%';    
                index_old--;
            }
            else 
            {
                //如果不是空格直接复制就可以了
                str[index_new--]=str[index_old--];
            }
        }

    }

vector<int> printListFromTailToHead(ListNode* head) {
        if(head==nullptr)
            return vector<int>();
        stack<int> tmp_stack;
        vector<int> res;
        ListNode *phead=head;   //如果要求不改变原链表，这里换一下
        while(phead!=nullptr)
        {
            tmp_stack.push(phead->val);
            phead=phead->next;
        }
        while(!tmp_stack.empty())
        {
            res.push_back(tmp_stack.top());
            tmp_stack.pop();   //出栈
        }
        return res;
    }

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/*
必须注意到前序遍历的第一个节点是根节点，中序遍历的和根节点相同的那个节点（不含重复节点）是根节点且
把树分成左右两个子树，左边子树是左子树，右边是右子树，左右两个子树也都是同样的规律，所以可以用递归
来做，我递归写的不好，借鉴了别人的思路，自己改进了下。
*/


class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        //如果size为0，则返回为空
        if(pre.size()==0||vin.size()==0)
            return NULL;
        
        vector<int> pre_left,pre_right;    //前序遍历的左子树和右子树
        vector<int> vin_left,vin_right;   //中序遍历的左子树和右子树
        //根据前序遍历的首节点为根节点这一个规律，找到中心节点，然后把原来的分成两个子二叉树，
        //准备使用递归来做。
        TreeNode *head=new TreeNode(pre[0]);   //调用构造函数先把第一个放进去。
        
        //找首节点在中序遍历中的位置。
        auto head_position=find(vin.begin(),vin.end(),head->val);
        int position=head_position-vin.begin();   //这里找到是第几个，下面取构建。
        pre_left=vector<int>(pre.begin()+1,pre.begin()+position+1);
        pre_right=vector<int>(pre.begin()+position+1,pre.end());
        //复制到前序遍历的左子树和右子树
        vin_left=vector<int>(vin.begin(),vin.begin()+position);
        vin_right=vector<int>(vin.begin()+position+1,vin.end());
        //复制到中序遍历的左子树和右子树 
        
        //调用递归
        head->left=reConstructBinaryTree(pre_left,vin_left);
        head->right=reConstructBinaryTree(pre_right,vin_right);
        
        //返回树
        return head;

    }
};

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

    int pop() {
        //题目要求返回删除的那个元素，C++satck的pop是不返回值得，而只是删除，所以就要自己来做了！
        int tmp;
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
            tmp=stack2.top();
            stack2.pop();
        }
        else 
        {
            tmp=stack2.top();
            stack2.pop();
        }
        return tmp;
    }

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