剑指offer

本文题目答案分析来源《剑指offer》和牛客网，包含个人理解，仅为参考。强烈大家去阅读《剑指offer》原书。

fengjingtu

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

答案一：简单循环遍历

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        
        for(int i=0;i<array.size();i++)
        {
            for(int j=0;j<array[i].size();j++)
            {
                if(target==array[i][j])
                {
                    return true;
                }
            }
        }
        return false;
    }
};

答案二：从对角线开始遍历，从右上角开始


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

        for(i=0,j=cols;i<=rows&&j>=0;)
        {
            if(array[i][j]==target)
                return true;
            else if(array[i][j] > target)
            {
                j--;
            }
            else
                i++;
        }
        return false;
    }
};

答案三：从对角线开始遍历，从左下角开始。（不能从左上角或右下角开始）

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {

        int rows=0;
        int cols=0;
        rows=array.size()-1;
        if(rows<0)
        return false;
        cols=array[0].size()-1;
        int i=0;
        int j=0;

        for(i=rows,j=0;i>=0&&j<=cols;)
        {
            if(array[i][j]==target)
                return true;
            else if(array[i][j] > target)
            {
                i--;
            }
            else
                j++;
        }
        return false;
    }
};

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

答案一：使用辅助空间

class Solution {
public:
	void replaceSpace(char *str,int length) {
        char *str2=new char(length*3+1);
        int j=0;
        for(int i=0;i<length;i++)
        {
            if(str[i]=='\0')
                break;
            if(str[i]==' ')
            {
                str2[j++]='%';
                str2[j++]='2';
                str2[j++]='0';
            }
            else
                str2[j++]=str[i];
        }
        str2[j]='\0';
        strcpy(str,str2);
        delete [] str2;
        //str=str2;

	}
};

答案二：不使用辅助空间,从后往前开始替换

class Solution {
    public:
    void replaceSpace(char *str,int length) {
        char *newstr=str;
        char *oldstr=str;
        int space_count=0;
        while(*oldstr!='\0')
        {
            if(*oldstr==' ')
                space_count++;
            oldstr++;
        }
        newstr=oldstr;
        for(int i=0;i<space_count*2;i++)
        {
            newstr++;
        }

        while(oldstr!=newstr)
        {
            if(*oldstr==' ')
            {
                *newstr='0';
                newstr--;
                *newstr='2';
                newstr--;
                *newstr='%';
            }
            else
            {
                *newstr=*oldstr;
            }
            newstr--;
            oldstr--;
        }
    }
}

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

时间限制：1秒空间限制：32768K

本题知识点：链表

答案：

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int>ArrayList;
        ListNode *l=head;
        while(l)
        {
            ArrayList.insert(ArrayList.begin(),l->val);
            l=l->next;
        }
        return ArrayList;
            
        
    }
};

运行时间：3ms
占用内存：480k

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

时间限制：1秒空间限制：32768K

本题知识点：二叉树

答案：

/**
 * 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) {
        TreeNode *cur=new TreeNode(0);
        if(pre.size()==0)
        {
            return NULL;
        }
        if(pre.size()==1)
        {
            cur->right=NULL;
            cur->left=NULL;
            cur->val=pre[0];
            return cur;
        }
        else
        {
            int i=0;
            vector<int> lefttreePre;
            vector<int> lefttreeVin;
            vector<int> righttreePre;
            vector<int> righttreeVin;
            cur->val=pre[0];
            for(i=0;i<vin.size();i++)
            {
                if(cur->val==vin[i])
                {
                    break;
                }
                lefttreePre.insert(lefttreePre.end(),pre[i+1]);
                lefttreeVin.insert(lefttreeVin.end(),vin[i]);
            }
             
            for(i=i+1;i<vin.size();i++)
            {
                righttreePre.insert(righttreePre.end(),pre[i]);
                righttreeVin.insert(righttreeVin.end(),vin[i]);
            }
            cur->left=reConstructBinaryTree(lefttreePre,lefttreeVin);
            cur->right=reConstructBinaryTree(righttreePre,righttreeVin);
            return cur;
        }
         
    }
};

运行时间：4ms
占用内存：480k

使用Python实现：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        elif len(pre) == 1:
            treeNode = TreeNode(pre[0])
            return treeNode
        else:
            index = 0
            for i in range(len(tin)):
                if tin[i] == pre[0]:
                    index = i
                    break
                    
            treeNode = TreeNode(pre[0])
            treeNode.left = self.reConstructBinaryTree(pre[1:index+1], tin[:index])
            treeNode.right = self.reConstructBinaryTree(pre[index+1:], tin[index+1:])
            return treeNode
             
运行时间：58ms
占用内存：5616k

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

时间限制：1秒空间限制：32768K

本题知识点：队列，栈

答案：

class Solution
{
public:
    void push(int node) {
        while(!stack2.empty())
        {
            stack1.push(stack2.top());
            stack2.pop();
        }
        stack1.push(node);
    }

    int pop() {
        int val;
        while(!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
        val=stack2.top();
        stack2.pop();
        return val;
        
    }

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

运行时间：3ms
占用内存：476k

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

时间限制：3秒空间限制：32768K

本题知识点：查找

答案：

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int min=rotateArray[0];
        for(int i=0;i<rotateArray.size()-1;i++ )
        {
            if(rotateArray[i]>rotateArray[i+1])
            {
                return rotateArray[i+1];
            }
            if(rotateArray[i]==rotateArray[i+1])
            {
                if(min<rotateArray[i+1])
                    min=rotateArray[i+1];
            }
        }
        return min;
        
    }
};

运行时间：30ms
占用内存：476k

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

时间限制：1秒空间限制：32768K

本题知识点：递归和循环

答案：

class Solution {
public:
    int Fibonacci(int n) {
        static int array[40]={0};
        if(n==0 || n==1)
        {
            array[n]=n;
            return array[n];
        }
        else
        {
            if(array[n-2]==0)
            {
                array[n-2]=Fibonacci(n-2);
            }
            if(array[n-1]==0)
            {
                array[n-1]=Fibonacci(n-1);
            }
            return array[n-1] + array[n-2];

        }
            
    }
};

运行时间：3ms
占用内存：480k

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

时间限制：1秒空间限制：32768K

本题知识点：递归和循环

答案：

#define MAX_NUMBER 10000
class Solution {
public:
    int jumpFloor(int number) {
        static int floor[MAX_NUMBER]={0};
        if(number<=0)
            return 0;
        else if(number==1 || number==2)
        {
            floor[number]=number;
        }
        else
        {
            if(floor[number-2]==0)
            {
                floor[number-2]=jumpFloor(number-2);
            }
            if(floor[number-1]==0)
            {
                floor[number-1]=jumpFloor(number-1);
            }
            floor[number]=floor[number-1]+floor[number-2];
        }
        return floor[number];

            
    }
    
};



运行时间：4ms
占用内存：476k

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

时间限制：1秒空间限制：32768K

本题知识点：递归和循环

答案：

#define MAX_NUMBER 10000
class Solution {
public:
    int jumpFloorII(int number) {
        static int over_floor[MAX_NUMBER]={0};
        if(number==0)
            return 0;
        else if(number==1||number==2)
        {
            over_floor[number]=number;
        }
        else
        {
            for(int i=1;i<number;i++)
            {
                if(over_floor[i]==0)
                {
                    over_floor[i]=jumpFloorII(i);
                }
                over_floor[number]+= over_floor[i];
            }
            over_floor[number]=over_floor[number]+1;
        }
        return over_floor[number];
    }
};

运行时间：3ms
占用内存：476k

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

时间限制：1秒空间限制：32768K

本题知识点：递归和循环

答案：


#define MAX_SIZE 10000
class Solution {
public:
    int rectCover(int number) {
        static int method[MAX_SIZE]={0};
        if(number==0)
        {
            return 0;
        }
        else if(number==1 || number==2)
        {
            method[number]=number;
        }
        else{
            if(method[number-2]==0)
            {
                method[number-2] = rectCover(number-2);
            }
            if(number%2==0)
            {
                method[number]= method[number-2]+2;
            }
            else
                method[number]= method[number-2]+1;
        }
        
        return method[number];
    }
};

运行时间：4ms
占用内存：360k

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

时间限制：1秒空间限制：32768K

本题知识点：位运算

答案：

class Solution {
public:
     int  NumberOf1(int n) {
         int count=0;
         if(n==0)
             return 0;
         for(int i=0;i<32;i++)
         {
             if((n&1)==1)
                 count++;
             n = n>>1;
         }
         return count;

     }
};
运行时间：4ms
占用内存：480k

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

时间限制：1秒空间限制：32768K

本题知识点：代码的完整性

答案：

class Solution {
public:
    double Power(double base, int exponent) {
        
        double val=1;
        if(exponent<0)
        {
            for(int i=0;i<-exponent;i++)
            {
                val=val*base;
            }
            return 1/val;
        }
        else
        {
            for(int i=0;i<exponent;i++)
            {
                val=val*base;
            }
            return val;
        }
    }
};
运行时间：4ms
占用内存：364k

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

时间限制：1秒空间限制：32768K

本题知识点：数组

答案：

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


运行时间：3ms
占用内存：480k

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

时间限制：1秒空间限制：32768K

本题知识点：链表

答案：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* end;
        ListNode* kend;
        end=pListHead;
        kend=pListHead;
        int number=0;
        while(end)
        {
            if(number>=k)
            {
                kend=kend->next;
            }
            end=end->next;
            number++;
        }
        if(number>=k)
            return kend;
        else
            return NULL;
    
    }
};

运行时间：4ms
占用内存：484k

输入一个链表，反转链表后，输出新链表的表头。

时间限制：1秒空间限制：32768K

本题知识点：链表

答案：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* p1;
        ListNode* p2;
        ListNode* p3;
        p1=pHead;
        if(p1==NULL)
            return NULL;
        p2=p1->next;
        if(p2==NULL)
            return p1;
        p3=p2->next;
        p1->next=NULL;
        while(p1)
        {
            p2->next=p1;
            p1=p2;
            p2=p3;
            if(p2==NULL)
                return p1;
            p3=p2->next;
        }
        return p1;
    }
};
运行时间：4ms
占用内存：464k

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

时间限制：1秒空间限制：32768K

本题知识点：链表

答案：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode* M;
        ListNode* p=M;
        if(pHead2==NULL)
        {
            return pHead1;
        }
        if(pHead1==NULL)
        {
            return pHead2;
        }
        if(pHead1->val<=pHead2->val)
        {
            p=pHead1;
            M=pHead1;
            pHead1=pHead1->next;
        }
        else
        {
             p=pHead2;
             M=pHead2;
             pHead2=pHead2->next;
        }
        
        
        while(pHead2||pHead1)
        {
            if(pHead2==NULL)
            {
                M->next=pHead1;
                break;
            }
                
            if(pHead1==NULL)
            {
                M->next=pHead2;
                break;
            }
            if(pHead1->val<=pHead2->val)
            {
                M->next=pHead1;
                pHead1=pHead1->next;
            }
            else
            {
                M->next=pHead2;
                pHead2=pHead2->next;
            }
            if(!(pHead2||pHead1))
                break;
                M=M->next;
            
        }
            return p;
           
    }
};

运行时间：5ms
占用内存：492k

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

时间限制：1秒空间限制：32768K

本题知识点：二叉树

答案：


/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
    public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result = false;

        if(pRoot1 != NULL && pRoot2 != NULL)
        {
            if(pRoot1->val == pRoot2->val)
                result = DoesTree1HaveTree2(pRoot1, pRoot2);
            if(!result)
                result = HasSubtree(pRoot1->left, pRoot2);
            if(!result)
                result = HasSubtree(pRoot1->right, pRoot2);
        }
        return result;
    }
    bool DoesTree1HaveTree2(TreeNode* pRoot1 ,TreeNode* pRoot2)
    {
        if(pRoot2 == NULL)
            return true;

        if(pRoot1 == NULL)
            return false;

        if(pRoot1->val != pRoot2->val)
            return false;

        return DoesTree1HaveTree2(pRoot1->left, pRoot2->left) &&
            DoesTree1HaveTree2(pRoot1->right, pRoot2->right);
    }
};

运行时间：6ms
占用内存：584k

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

输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5

时间限制：1秒空间限制：32768K
本题知识点：二叉树

/*
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) {
        struct TreeNode *temp;;
        if(pRoot==NULL)
            return ;
        else
        {
            if(pRoot->left==NULL&&pRoot->right==NULL)
                return ;
            else{
                Mirror(pRoot->left);
                Mirror(pRoot->right);
            }
            temp=pRoot->left;
            pRoot->left=pRoot->right;
            pRoot->right=temp;
            return;
        }

    }
};

运行时间：3ms
占用内存：476k

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.

时间限制：1秒空间限制：32768K

本题知识点：数组

答案：

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int y_start = 0, y_end = matrix[0].size()-1;
        int x_start = 0, x_end = matrix.size()-1;
        int x=0, y=0;
        vector<int> a;
        while(!(x_start>x_end || y_start>y_end))
        {
            while(y<=y_end &&(!(x_start>x_end || y_start>y_end)))
            {
                a.push_back(matrix[x][y]);
                y++;
            }
            x_start++;
            x=x_start;
            y=y_end;
            while(x<=x_end &&(!(x_start>x_end || y_start>y_end)))
            {
                a.push_back(matrix[x][y]);
                x++;
            }
            y_end--;
            x = x_end;
            y = y_end;
            while(y>=y_start&&(!(x_start>x_end || y_start>y_end)))
            {
                a.push_back(matrix[x][y]);
                y--;
            }
            x_end--;
            x = x_end;
            y = y_start;
            while(x>=x_start&&(!(x_start>x_end || y_start>y_end)))
            {
                a.push_back(matrix[x][y]);
                x--;
            }
            y_start++;
            x = x_start;
            y = y_start;
        }
        return a;

    }
};
运行时间：4ms
占用内存：480k

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

时间限制：1秒空间限制：32768K

本题知识点：栈

答案：

#define MAX_SIZE 10000
class Solution {
public:
    void push(int value) {
        t++;
        array[t]=value;
        if(t==0)
            min_val=value;
        else if(min_val>value)
            min_val=value;
        else
            return;
        return ;
    }
    void pop() {
         if(t==-1)
            return;
        if(top()==min_val)
        {
            t--;
            min_val=find_min();
            
        }
        else
            t--;
    }
    int top() {
        if(t==-1)
            return -1;
        return array[t];
    }
    int min() {
        return min_val;
    }
     
private:
    int array[MAX_SIZE]={0};
    int t=-1;
    int min_val=-1;
    int find_min()
    {
        min_val=top();
        for(int i=0;i<=t;i++)
        {
            if(min_val>array[i])
            {
                min_val=array[i];
            }
        }
        return min_val;
    }
};

运行时间：5ms
占用内存：504k

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

时间限制：1秒空间限制：32768K
本题知识点：链表

答案：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode* entrance=NULL;
        ListNode* NextNode=NULL;
        ListNode* pass=new ListNode(0);
        entrance=pHead;
        if(entrance)
        {
            NextNode=pHead->next;
            while(entrance)
            {

                entrance->next=pass;
                entrance=NextNode;
                NextNode=entrance->next;
                if(entrance==NULL || entrance->next==pass )
                    break;
            }
        }
        delete [] pass;
        return entrance;
    }
};
运行时间：4ms
占用内存：484k

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

时间限制：1秒空间限制：32768K
本题知识点：链表

答案：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        int exist=0;
        ListNode* l=pHead;
        ListNode* formar=pHead;
        vector<int>v;
        vector<int>repeat;
        while(l)
        {
            vector<int>::iterator result=find(v.begin(),v.end(),l->val);
            if(result== v.end())
            {
                v.push_back(l->val);
            }
            else
            {
                repeat.push_back(l->val);
            }
            l=l->next;
                
        }
        l=pHead;
        while(l)
        {
             vector<int>::iterator result=find(repeat.begin(),repeat.end(),l->val);
            if(result== repeat.end())
            {
                break;
            }
            else
                l=l->next;
        }
        formar=l;

        while(l && l->next)
        {
            vector<int>::iterator result=find(repeat.begin(),repeat.end(),l->next->val);
            if(result== repeat.end())
            {
                l=l->next;
            }
            else
            {
                l->next=l->next->next;
            }
        }
        return formar;
    }
};
运行时间：4ms
占用内存：456k

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

时间限制：1秒空间限制：32768K
本题知识点：链表

答案：

1
2

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

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

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

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

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

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

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

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

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

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

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

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

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

输入一个链表，反转链表后，输出新链表的表头。

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

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

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

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

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

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。