leetcode与剑指offer 简单编程题(考研编程大题)

点击此处查看html页面版

题目需要小心分析,得出规律(递推式),并且大胆验证。

1.合并两个二叉树
2.阶乘后的0
3.根据身高重建队列(难度:中等)
4.有效的完全平方和(难度:简单)
5.斐波那契数(难度:简单)
6.从尾到头打印链表(剑指offer)
7.用两个栈实现队列(牛客剑指offer)
8.链表中倒数第K个节点(牛客剑指offer)
9.合并两个排序链表(牛客剑指offer)
10.翻转链表(牛客剑指offer)
11.二叉树的镜像(牛客剑指offer)
12.二维数组中查找(牛客剑指offer)
13.旋转数组中最小数字(牛客剑指offer)
14.跳台阶(牛客剑指offer)
15.变态跳台阶(牛客剑指offer)
16.矩阵覆盖(牛客剑指offer)
17.从上往下打印二叉树(牛客剑指offer)


1.合并两个二叉树

1
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:
输入:
[1,3,2,5]
[2,1,3,null,4,null,7]
输出:
[3,4,5,5,4,null,7]
注意: 合并必须从两个树的根节点开始。

代码(递归):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==NULL&&t2==NULL)return NULL;
        if(t1==NULL)return t2;
        if(t2==NULL)return t1;
        else
        {
            t1->val+=t2->val;
            t1->left=mergeTrees(t1->left,t2->left);
            t1->right=mergeTrees(t1->right,t2->right);
            return t1;
        }

       
    }
};

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


2.阶乘后的0

2
给定一个整数 n,返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

分析:末尾0的来源为5的倍数与偶数相乘,5,10,15,20,25...,其中25中含有2个5(5*5),125中含有3个5(5*5*5)

class Solution {
public:
    int trailingZeroes(int n) {
        int sum=0;
        int j=(int)(log(n)/log(5));
        for(int i=1;i<=j;i++){
            int five=(int)(pow(5,i));
            sum+=n/five;
        }
        return sum;
        
        
    }
};

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


3.根据身高重建队列(难度:中等)

3
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意:
总人数少于1100人。

示例

输入:
7,0], [4,4], [7,1], [5,0], [6,1], [5,2

输出:
5,0], [7,0], [5,2], [6,1], [4,4], [7,1

分析:先排序后插入
[c++] 排序,然后插入。
假设候选队列为 A,已经站好队的队列为 B.
从 A 里挑身高最高的人 x 出来,插入到 B.
因为 B 中每个人的身高都比 x 要高,因此 x 插入的位置,
就是看 x 前面应该有多少人就行了。比如 x 前面有 5 个人,
那 x 就插入到队列 B 的第 5 个位置。
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        // 先排序
        // [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
        
        // 再一个一个插入。
        // [7,0]
        // [7,0], [7,1]
        // [7,0], [6,1], [7,1]
        // [5,0], [7,0], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]
        sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] > b[0]) return true;
            if (a[0] == b[0] && a[1] < b[1]) return true;
            return false;
        });
        
        vector<vector<int>> res;
        for (auto& e : people) {
            res.insert(res.begin() + e[1], e);
        }
        return res;
    }
};

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/queue-reconstruction-by-height
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


4.有效的完全平方和(难度:简单)

4
给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。

说明:不要使用任何内置的库函数,如  sqrt。

示例 1:
输入:16
输出:True

示例 2:
输入:14
输出:False

提示:还可以用
二分法,
牛顿迭代法,
公式法(1+3+5+7+9+…+(2n-1)=n^2 ,即完全平方数肯定是前n个连续奇数的和)
等方法计算。
解一:4ms,8.1MB
class Solution {
public:
    bool isPerfectSquare(int num) {
        for(long i=0;i<=num/2+1;i++){   //使用long型变量,防止int型数据太大而报错。+1是为了解决当num=1时出现的错误。
            if(i*i==(long)num){
                return true;
                break;
            }
            if(i*i>(long)num){
                return false;
                break;
            }
        }
       return false; 
    }
};

解二:788ms,8.2MB
class Solution {
public:
    bool isPerfectSquare(int num) {
        for(long i=0;i<=num/2+1;i++){
            while(i*i<=(long)num){
                if(i*i==(long)num){
                    return true;
                    break;
                }
                break;
            }      
        }
        return false; 
    }
};

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-perfect-square
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


5.斐波那契数

5
斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N,计算 F(N)。

示例 1:
输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2:
输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2.

解一(非递归):4ms,8.2MB
class Solution {
public:
    int fib(int N) {
        int a=0,b=1,sum=0;
        if(N==0)sum=0;
        if(N==1)sum=1;
        for(int i=2;i<=N;i++){
            sum=a+b;
            a=b;
            b=sum;

        }
        return sum;
        
    }
};

解二(递归):
class Solution {
public:
    int fib(int N) {
        if(N==0)return 0;
        if (N == 1 || N == 2) return 1;
        return fib(N - 1) + fib(N - 2);

    }
};

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fibonacci-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


6.从尾到头打印链表(牛客剑指offer)


题目描述
输入一个链表,按链表从尾到头的顺序返回一个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<int> node;   //使用栈来进行逆序打印
        vector<int> outnode;
        while(head!=NULL)
        {
            node.push(head->val);
            head=head->next;
        }
        while(!node.empty())
        {
            outnode.push_back(node.top());      
            //push_back()是vector类中的一个函数,作用是在vector类中vector变量结尾插入一个数据,本题用来生成数组。
            node.pop();
        }
        return outnode;
    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/profile/5032552/codeBookDetail?submissionId=60774124


7.用两个栈实现队列(牛客剑指offer)


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

class Solution
{
public:
    void push(int node) {
        stack1.push(node); 
        //输入时全部入栈1;
    }

    int pop() {
        if(stack2.empty())      
        //当栈2为空时,将栈1数据入栈2,实现数据的顺序翻转,从而实现队列。
        //栈2不为空时,栈2的数据已经是翻转两次的数据,直接输出就行。
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int tmp=stack2.top();
        stack2.pop();
        return tmp:       
    }

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

来源:牛客剑指offer
链接:https://www.nowcoder.com/profile/5032552/codeBookDetail?submissionId=60775063


8.链表中倒数第K个节点(牛客剑指offer)

题目描述
输入一个链表,输出该链表中倒数第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(k<1)return NULL;
        if(pListHead==NULL)return NULL;
        //鲁棒性
        
        ListNode *p1=pListHead;
        ListNode *p2=pListHead;
        for(int i=1;i<k;i++){
            if(p1->next==NULL)return NULL;//若链表长度小于K,返回NULL。
            p1=p1->next;
        }
        while(p1->next!=NULL){
            p1=p1->next;
            p2=p2->next;
        }
        return p2;
    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a


9.合并两个排序链表(牛客剑指offer)

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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode* p1=pHead1;
        ListNode* p2=pHead2;
        if(p1==NULL)return p2;
        if(p2==NULL)return p1;
        
        ListNode* p=NULL;
        //递归选出两个链表中最小值,将其节点放入新链表p中。
        if(p1->val<p2->val){
            p=p1;
            p->next=Merge(p1->next,p2);   
        }else{
            p=p2;
            p->next=Merge(p1,p2->next);
        }
        return p;
    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337


10.翻转链表(牛客剑指offer)

本题有点小毛病,稍后更新

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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)return NULL;
        ListNode* p1=pHead;
        
        std::stack<ListNode*> s1;
        while(p1->next){
            s1.push(p1);
            p1=p1->next;
        }
        
        ListNode* head=p1;
        while(!s1.empty()){
           p1->next=s1.top();
           p1=p1->next;
           s1.pop();
        }
        p1->next=NULL;
        return head;

    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca


11. 二叉树的镜像(牛客剑指offer)

题目描述
操作给定的二叉树,将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义:
源二叉树
8
/
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ /
11 9 7 5

/*
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) {
        if(pRoot==NULL)return;

        TreeNode *tmp;
        tmp=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=tmp;
        //交换左右子树,并递归调用交换,直至全部交换
        Mirror(pRoot->left);
        Mirror(pRoot->right);
       
    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011


12.二维数组中查找

题目描述

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

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

13.旋转数组中最小数字(牛客剑指offer)

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

解一:33ms,760K
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()==0)return 0;
        int min=rotateArray[0];
        for(int i=0;i<rotateArray.size();i++){
            if(rotateArray[i]<min){
                min=rotateArray[i];
                break;
            }
        }
        return min;
    }
};
解二:42ms,1100K
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
       sort(rotateArray.begin(),rotateArray.end());
         
        return rotateArray[0];
         
    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba


14.跳台阶(牛客剑指offer)

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

分析:
假设现在6个台阶,我们可以从第5跳一步到6,
另外我们也可以从4跳两步跳到6,即f(6) = f(5) + f(4)class Solution {
public:
    int jumpFloor(int n) {
        int sum=0;
        int n1=1,n2=2;
        if(n==1)return 1;
        if(n==2)return 2;
        for(int i=3;i<=n;i++){
            sum=n1+n2;
            n1=n2;
            n2=sum;
        }
        return sum;
    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4


15.变态跳台阶(牛客剑指offer)

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

【分析一】 
每个台阶可以看作一块木板,让青蛙跳上去,n个台阶就有n块木板,最后一块木板是青蛙到达的位子, 必须存在,其他 (n-1) 块木板可以任意选择是否存在,则每个木板有存在和不存在两种选择,(n-1) 块木板 就有 [2^(n-1)] 种跳法,可以直接得到结果。
【分析二】
F0=1
F1=1
F2=F1+F0=2
F3=F2+F1+F0=4
F4=F3+F2+F1+F0=8
...
FN=2F(N-1)

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==1)return 1;
        int t=1;
        for(int i=1;i<number;i++){
            t*=2;
        }
        return t;
    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387


16.矩阵覆盖(牛客剑指offer)

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

分析:本题看似有点难度,实际上分析后发现递推式F(N)=F(N-1)+F(N-2),类似斐波那契数列。
class Solution {
public:
    int sum=0;
    int rectCover(int number) {
        if(number==0)return 0;
        if(number==1)return 1;
        if(number==2)return 2;
        else{
            sum=rectCover(number-1)+rectCover(number-2);
        }
        return sum;
    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6


17.从上往下打印二叉树(牛客剑指offer)

题目描述
从上往下打印出二叉树的每个节点,同层节点从左至右打印。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> que;            //注意,函数的返回类型为vector
        std::queue<TreeNode*> q;    //定义一个队列
        TreeNode* t;
       if(root==NULL)return que;
        q.push(root);               //入队
        while(!q.empty()){
            t=q.front();            //取队首(即将出队)的元素
            que.push_back(t->val);  //将t的val值插入vector类的que变量尾部
            if(t->left!=NULL){
                q.push(t->left);
            }
            if(t->right!=NULL){
                q.push(t->right);
            }
            q.pop();
        }
        return que;
        

    }
};

来源:牛客剑指offer
链接:https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701



CopyRight 2019-2020 Qiaoyu All Right Reserved
有需要请联系qiaoyurensheng@163.com
皖ICP备17002449号