剑指Offer_C++题解1

二维数组中的查找

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

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

替换空格

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

//两个指针，第一个指向字符串末尾，第二个指向替换后的末尾；
//一次复制，至第一个遇到空格，替换%20，第一个指针移动一个，第二个移动三格
//直至两个指针指向同一个位置
class Solution {
public:
	void replaceSpace(char *str,int length) {
        //判断非空字符串
        if( str == NULL && length < 0)
            return;
        //统计空格个数
        int originallength = 0;
        int newlength = 0;
        int blanknum = 0;
        int i = 0;
        while( str[i] != '\0'){
            ++ originallength;
            if(str[i] == ' ')
                ++blanknum;
            ++i;
        }
        newlength = originallength + blanknum * 2;
        if(newlength > length)
            return;
        int indexO = originallength;
        int indexN = newlength;
        while(indexO >=0 && indexN > indexO)
        {
            if(str[indexO]==' ')
            {
                str[indexN--]='0';
                str[indexN--]='2';
                str[indexN--]='%';
            }
            else
            {
                str[indexN--]=str[indexO];
            }
            indexO--;
        }
	}
};

从尾到头打印链表

题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
//先压栈 再出栈
//方法一
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        std::stack<ListNode*> nodes;
        vector<int> res;
        ListNode* pNode = head;
        while(pNode != NULL){
            nodes.push(pNode);
            pNode = pNode -> next;
        }
        
        while(!nodes.empty()){
            pNode = nodes.top();
            res.push_back(pNode->val);
            nodes.pop();
        }
        return res;
    }
};


//方法二：递归
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        if(head != NULL){
              if(head->next != NULL){
                  res=printListFromTailToHead(head -> next);
              }
              res.push_back(head -> val);
        }
        return res;
    }
};

重建二叉树

题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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> vin) {
        if(pre.empty() || vin.empty())
            return NULL;     
        int rootval = pre[0];
        for(int i = 0;i<vin.size();++i){
            if(rootval == vin[i])
                continue;
        }
        int pos;
        for(pos = 0;pos < vin.size();++pos){
            if(vin[pos] == rootval)
                break;
        }
        
        vector<int> leftpre,rightpre,leftvin,rightvin;
        
        TreeNode *root = new TreeNode(rootval);

        for(int i = 0;i<vin.size();++i){
            if(i<pos){
                leftpre.push_back(pre[i+1]);
                leftvin.push_back(vin[i]);
            }
            else if(i>pos){
                rightpre.push_back(pre[i]);
                rightvin.push_back(vin[i]);
            }
        }
        
        root -> left = reConstructBinaryTree(leftpre,leftvin);
        root -> right = reConstructBinaryTree(rightpre,rightvin);
        
        return root;
        
    }
};

两个栈实现队列

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

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

    int pop() {
        int res;
        if(stack2.size() <= 0){
            while(stack1.size() > 0){
                int data = stack1.top();
                stack1.pop();
                stack2.push(data);
            }
        }
        //if(stack2.size() == 0){
            //throw new exception("queue is empty");
    
        if(stack2.size() > 0){
        res = stack2.top();
        stack2.pop();
        }
        return res;
    }

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

旋转数组的最小数字

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0 )
            return 0;
        int index1 = 0;
        int index2 = rotateArray.size() - 1;
        int indexMid = index1;
        
        while(rotateArray[index1] >= rotateArray[index2]){
            if(index2 - index1 == 1){
                indexMid = index2;
                break;
            }
            
            indexMid = (index2 + index1) / 2;
            
            if(rotateArray[index1] == rotateArray[index2] && rotateArray[indexMid] == rotateArray[index2])
                return MinInOrder(rotateArray,index1,index2);
            
            if(rotateArray[indexMid] >= rotateArray[index1])
                index1 = indexMid;
            else if(rotateArray[indexMid] <= rotateArray[index2])
                index2 = indexMid;
        }
        
        return rotateArray[indexMid];
    }
    
    int MinInOrder(vector<int> &array,int index1,int index2){
        int result = array[index1];
        for(int i=index1 + 1;i <= index2;i++){
            if(result > array[i])
                result = array[i];
        }
        return result;
    }
};

斐波那契数列

题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

class Solution {
public:
    int Fibonacci(int n) {
        if(n==0 || n == 1)
            return n;
        else{
            int a=0,b=1;
            int m=0;
            for(int i=2;i<=n;i++){
                m = a + b;
                a = b;
                b = m;
            }
            return m;
        }
    }
};

跳台阶

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

class Solution {
public:
    int jumpFloor(int number) {
        if(number == 0)
            return 0;
        if(number == 1)
            return 1;
        if(number == 2)
            return 2;
        
        long long one = 1;
        long long two = 2;
        long long n = 0;
        for(int i= 0;i< number-2;i++){
            n = one + two;
            one = two;
            two = n;
        }
        return n;
         
    }
};

变态跳台阶

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

class Solution {
public:
    int jumpFloorII(int number) {
        return 1<<(number - 1);
    }
};

矩形覆盖

题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

class Solution {
public:
    int rectCover(int number) {
        if(number == 0 || number == 1 || number == 2){
            return number;
        }
        else{
            int a = 1,b = 2,c;
            for(int i = 1;i<number - 1;i++){
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }
    }
};

二进制中1的个数

题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         while(n){
             n = n & (n-1);
             count++;
         }
         return count;
     }
};

数值的整数次方

题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

class Solution {
public:
    double Power(double base, int exponent) {
        
        bool invalid_input = false;
        if(equal(base,0.0) && exponent < 0){
            invalid_input = true;
            return 0.0;
        }
        
        long long p = abs( (long long) exponent);
        double r = 1.0;
        while (p) {
            if (p & 1)
                r *= base;
            base *= base;
            p >>= 1;
        }
        return ( exponent > 0 ) ? r : 1/r; 
        
    }
    
    bool equal(double a,double b){
        if((a - b < 0.000001) && (a - b > -0.000001)){
            return true;
        }
        else
            return false;
    }
    
};

调整数组顺序使奇数位于偶数前面

题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
  
        int len = array.size();
        //int j = 0;
        vector<int> new_array;
        for(int i = 0;i < len;i++){
            if(array[i] % 2){
                new_array.push_back(array[i]);
            }
        }
        for(int i = 0;i < len; i++){
            if(!(array[i]% 2)){
                new_array.push_back(array[i]);
            }
        }
        
        array = new_array;
        
    }
};

链表中倒数第K个结点

题目描述
输入一个链表，输出该链表中倒数第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* pa = pListHead;
    ListNode* pb = pListHead;//定义双指针
//指针pa先走 k 步，
    for(unsigned int i = 0;i < k-1;++i){
        if(pa->next != NULL)
            pa = pa -> next;
        else
            return NULL;
    }
//指针pa,pb同时走，pa指向末尾时，pb正好指向倒数第k个结点；
    while(pa ->next != NULL){
        pa = pa -> next;
        pb = pb -> next;
    }
    return pb;
    }
};

反转链表

题目描述
输入一个链表，反转链表后，输出新链表的表头。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pPrev = NULL;
        ListNode* pNode = pHead;
        ListNode* pReverseHead = NULL;
        while(pNode != NULL){   //判断链表不为空
            ListNode* pNext = pNode -> next;   //保存反转结点后一个结点，在链表断裂后依然能遍历到该点
            if(pNext == NULL)        //判断是否遍历到尾部
                pReverseHead = pNode;  //到尾部后，使当前结点变成反转后的头结点
            pNode -> next = pPrev;    //反转
            pPrev = pNode;    //向后移动前一个结点
            pNode = pNext;     //向后移动当前结点
        }
        return pReverseHead;
    }
};

合并两个排序的链表

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

/*
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;
        else if(pHead2 == NULL)
            return pHead1;
        
        ListNode* pMergeHead = NULL;
        if(pHead1->val < pHead2->val){
            pMergeHead = pHead1;
            pMergeHead->next = Merge(pHead1->next,pHead2);
        }
        else{
            pMergeHead = pHead2;
            pMergeHead->next = Merge(pHead1,pHead2->next);
        }
        return pMergeHead;
    }
};

树的子结构

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

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

//解1
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result = false;
        if( pRoot1 != NULL && pRoot2 != NULL){
            if(pRoot1 -> val == pRoot2 -> val)
                result = Have(pRoot1,pRoot2);
            if(!result)
                result = HasSubtree(pRoot1 -> left,pRoot2);
            if(!result)
                result = HasSubtree(pRoot1 -> right,pRoot2);
        }
        return result;
    }
    
    bool Have(TreeNode* pRoot1, TreeNode* pRoot2){
        if(pRoot2 == NULL)
            return true;
        if(pRoot1 == NULL)
            return false;
        if(pRoot1 -> val != pRoot2 -> val)
            return false;
        return Have(pRoot1 -> left,pRoot2 -> left) && Have(pRoot1 -> right,pRoot2 -> right);
    }
};
//解2
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result=false;
        if(pRoot1!=NULL && pRoot2!=NULL){
            if(pRoot1->val == pRoot2->val)
                result=DoConTree(pRoot1,pRoot2);
            if(!result)
                result=HasSubtree(pRoot1->left,pRoot2);
            if(!result)
                result=HasSubtree(pRoot1->right,pRoot2);
        }
        return result;
    }
    bool DoConTree(TreeNode *pRoot1,TreeNode *pRoot2){
        if(pRoot2==NULL)
            return true;
        if(pRoot1==NULL)
            return false;
        if(pRoot1->val==pRoot2->val)
            return DoConTree(pRoot1->left,pRoot2->left)&&DoConTree(pRoot1->right,pRoot2->right);
        return false;
    }
};

//解3
class Solution {
public:
    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);
    }
      
    bool isSubtree(TreeNode* pRoot1 , TreeNode* pRoot2){
        if(pRoot2 == NULL)
            return true;
        if(pRoot1 == NULL)
            return false;
        return pRoot1->val == pRoot2->val && isSubtree(pRoot1->left,pRoot2->left) && isSubtree(pRoot1->right,pRoot2->right);
    }
};