1 - 简书

1题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        
        int row = array.size();
        int colume = array[0].size();
         
        int x = row - 1;
        int y = 0;
         
        while (x >= 0 && y <= colume-1) {
             
            if (target < array[x][y]) {
                --x;
            }else if (target > array[x][y]) {
                ++y;
            }else {
                return true;
            }
             
        }
         
        return false;
    }
};

2题目：请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

//思路 
//1：从前往后插入，这样移动·的次数多不建议 
//2：从后往前插入 

  

class Solution {
    public:
    void replaceSpace(char *str,int length) {
        //遍历一边字符串找出空格的数量
        if(str==NULL||length<0)
            return ;
        int i=0; 
        int oldnumber=0;//记录以前的长度 
        int replacenumber=0;//记录空格的数量
        while(str[i]!='\0')
        {
            oldnumber++;
            if(str[i]==' ')
            {
                replacenumber++;
            }
            i++;
        }
        int newlength=oldnumber+replacenumber*2;//插入后的长度 
        if(newlength>length)//如果计算后的长度大于总长度就无法插入
            return ;
        int pOldlength=oldnumber; //注意不要减一因为隐藏个‘\0’也要算里 
        int pNewlength=newlength;
        
        while(pOldlength>=0&&pNewlength>pOldlength)//放字符
        {
            if(str[pOldlength]==' ') //碰到空格就替换
            {
                str[pNewlength--]='0';
                str[pNewlength--]='2';
                str[pNewlength--]='%';
            }
            else //不是空格就把pOldlength指向的字符装入pNewlength指向的位置
            {
                str[pNewlength--]=str[pOldlength];
            }
            pOldlength--; //不管是if还是elsr都要把pOldlength前移
        }
    }
};

3题目：输入一个链表，从尾到头打印链表每个节点的值。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
   vector<int> printListFromTailToHead(ListNode* head) {
       vector<int> result;
       stack<struct ListNode*> stack;
       while(head != NULL){
           stack.push(head);
           head = head->next;
       }
       while(!stack.empty()){
           result.push_back(stack.top()->val);
           stack.pop();
       }
       return result;
   }
};

4.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

/**
 * 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> in) {
 
            int inlen=in.size();
 
            if(inlen==0)
 
                return NULL;
 
            vector<int> left_pre,right_pre,left_in,right_in;
 
            //创建根节点，根节点肯定是前序遍历的第一个数
 
            TreeNode* head=new TreeNode(pre[0]);
 
            //找到中序遍历根节点所在位置,存放于变量gen中
 
            int gen=0;
 
            for(int i=0;i<inlen;i++)
 
            {
 
                if (in[i]==pre[0])
 
                {
 
                    gen=i;
 
                    break;
 
                }
 
            }
 
            //对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边
 
            //利用上述这点，对二叉树节点进行归并
 
            for(int i=0;i<gen;i++)
 
            {
 
                left_in.push_back(in[i]);
 
                left_pre.push_back(pre[i+1]);//前序第一个为根节点
 
            }
 
            for(int i=gen+1;i<inlen;i++)
 
            {
 
                right_in.push_back(in[i]);
 
                right_pre.push_back(pre[i]);
 
            }
 
            //和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树
 
            //递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
 
           head->left=reConstructBinaryTree(left_pre,left_in);
 
           head->right=reConstructBinaryTree(right_pre,right_in);
 
           return head;
 
        }
};

5.用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

/*用两个栈实现一个队列的功能?要求给出算法和思路!
**<分析>：
**入队：将元素进栈A
**出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；
**如果不为空，栈B直接出栈。
*/
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        int a;
        // 如果栈2空
        if (stack2.empty()) {
            // 依次把栈1中的所有元素放入到栈2中去
            while(!stack1.empty()) {
                a = stack1.top();
                stack2.push(a);
                stack1.pop();
            }
        }
        // 缺少一个栈空检测
        a = stack2.top();
        stack2.pop();
        return a;
    }

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

1

推荐阅读更多精彩内容