小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. 剑指offer
  6. 正文

《剑指Offer》题目解析(6)

2019年3月5日 1056点热度 0人点赞 0条评论

题目1 二叉树的镜像

题目描述

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

题目解析

一定要考虑到两种特殊情况:

  • 二叉树为空
  • 二叉树的左子树为空且二叉树的右子树为空

设计代码的时候一定要考虑代码的鲁棒性。所以需要设计到两个if语句,如果不在这两种特殊情况里面,再去新建一个TreeNode,然后交换进行做镜像。

代码

void Mirror(TreeNode *pRoot) {
    if(pRoot == NULL)//特殊情况1
        return;
    //特殊情况2
    if((pRoot->left == NULL)&&(pRoot->right == NULL))
        return ;
    TreeNode *tmp;
    tmp=pRoot->left;
    pRoot->left=pRoot->right;
    pRoot->right=tmp;
    if(pRoot->left)
        Mirror(pRoot->left);
    if(pRoot->right)
        Mirror(pRoot->right);
}

题目2 顺时针打印矩阵

题目描述

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

题目解析

用左上和右下的坐标定位出一次要旋转打印的数据,一次旋转打印结束后,往对角分别前进和后退一个单位。

代码

vector<int> printMatrix(vector<vector<int> > matrix) {
    vector<int> result;
    int row=matrix.size();
    int col=matrix[0].size();
    if(row==0||col==0)
        return result;
    int left = 0,right = col-1,top=0,end =row-1;
    while(left<=right && top<= end)
    {
        //第一行从左往右
        for(int i=left;i<=right;i++)
            result.push_back(matrix[top][i]);
        //最右侧从上往下
        if(top<end)
        {
            for(int i=top+1;i<=end;i++)
                result.push_back(matrix[i][right]);
        }
        //最下侧从右往左
        if(top<end && left<right)
        {
            for(int i=right-1;i>=left;i--)
                result.push_back(matrix[end][i]);
        }
        //最左侧从下往上
        if(top+1<end && left<right)
        {
            for(int i=end-1;i>=top+1;i--)
                result.push_back(matrix[i][left]);
        }
        left++;
        right--;
        top++;
        end--;
    }
    return result;
}

题目3 包含min函数的栈

题目描述

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

题目解析

我们需要一个辅助堆栈来得到我们所需要数据,因为只有一个堆栈的话,我们没办法比较得出最小值。加入我们的数据压入顺序是3,4,2,1。那么可以这样:

步骤 操作 数据栈 辅助栈 最小值
1 压入3 3 3 3
2 压入4 3,4 3,3 3
3 压入2 3,4,2 3,3,2 2
4 压入1 3,4,2,1 3,3,2,1 1
5 弹出 3,4,2 3,3,2 2
6 弹出 3,4 3,3 3
7 压入0 3,4,0 3,3,0 0

代码

stack<int> stack1,stack2;
    void push(int value) {
        stack1.push(value);
        if(stack2.empty()||value<stack2.top())
            stack2.push(value);
        else
        {
            stack2.push(stack2.top());
        }
    }

    void pop() {

        stack2.pop();
        stack1.pop();

    }

    int top() {
        return stack1.top();       
    }

    int min() {
        return stack2.top();
    }

题目4 栈的压入、弹出序列

题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

题目解析

这个程序的代码思路跟我们手工做题的思路一样,所以也许不是复杂度最低的算法,它的思路是这样的:
1. 新建一个vector数组temp;
2. 然后将pushV的最头上的元素压入temp;
3. 判断该元素是否和popV中最上面的元素(即要被弹出的元素)是否相等,若不相等正则去执行第2步,直到找到相等的,然后temp里面的元素弹出;
4. 然后开始第2个元素的比较,步骤重复2和3,直到所有的完成。

代码

bool IsPopOrder(vector<int> pushV,vector<int> popV) {
    bool result =false;
    stack<int>temp;
    int Index = 0;
    for(int i=0;i<pushV.size();i++)
    {
        temp.push(pushV[i]);
        while(!temp.empty() && temp.top()==popV[Index])
        {
            temp.pop();
            ++Index;
        }
    }
    result=temp.empty();
    return result;

}

题目5 从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个结点,同层结点从左至右打印。

题目解析

这就是层序遍历。用层序遍历的法子,借助队列来实现。其实广度优先搜索也借鉴了层序遍历的思想。

代码

 vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> q;
        q.push(root);//把根结点push进去
        if(root == NULL)//稳健性
            return result;
        while(!q.empty())
        {
            root=q.front();//获取到队列q的头元素
            q.pop();
            result.push_back(root->val);//把头元素的值送入result
            if(root->left)//向左遍历
                q.push(root->left);
            if(root->right)//向右遍历
                q.push(root->right);
        }
        return result;
    }
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 剑指offer
最后更新:2019年3月5日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
2017 CSL 5th: Shandong Luneng Taishan F.C VS Beijing Sinobo Guoan F.C 《剑指Offer》题目解析(7) 再忆陈毅中学 吴恩达深度学习课程 DeepLearning.ai 编程作业(1-3) 高一第二次学分认定考试反思 本站公告
标签聚合
linux 高中 算法 生活 python学习 Java 学习 Python leetcode 鸟哥的linux私房菜
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号