小奥的学习笔记

  • 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》题目解析(5)

2019年3月4日 1181点热度 0人点赞 0条评论

题目7 链表倒数第k个结点

题目描述

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

题目解析

我们很容易可以想到,由于这是一个单向链表,所以我们可以第一遍先遍历这个链表,看有多少个结点(假设为n),然后计算出pos=n-k+1,然后我们只需要再遍历一遍这个链表,输出第n-k+1个结点的值即可。
但是要注意鲁棒性。我们要考虑,如果这个链表为空呢?如果这个链表的结点数不到k个呢?那就需要对代码进行补充和完善。

代码

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL)
            return NULL;
        ListNode* list1 = pListHead;
        int count=1;
        int pos = 0;
        while (list1)
        {
            ++count;
            list1 = list1->next;
        }
        if (count<=k)
            return list1;
        pos = count - k + 1;
        int n = 1;
        ListNode* list2 = pListHead;
        while (list2 && n < pos - 1)
        {
            list2 = list2->next;
            ++n;
        }
        return list2;

    }

题目8 翻转链表

题目描述

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

题目解析

首先我们应该考虑两个问题(鲁棒性):
1. 链表为空呢?返回空。
2. 链表就只有一个结点呢?返回这个结点。

其它一般情况就是多个结点了。为了正确翻转一个链表,需要调整链表中指针的方向。我们假设有下面三个结点:a->b->c,假设我们要翻转b的next指向a,那么指向a之后,b和c之间的联系就断了,因此我们需要把结点c的地址保存下来。也就是说,我们在调整结点b的next指针的时候,除了需要知道结点b本身,还需要知道结点b的前一个结点a,因为我们要把结点b的next指针指向a。同时,我们还需要实现保存b的一个结点c,以防止链表断开。

我们新建一个next指针,让它来保存b指针的next所指向的地址,然后把a的next指向NULL,然后令node=a,然后把lnode=b;这个时候,进入下一个循环,next指向了c,然后把b的next指向了a,然后令node=b,然后将lnode往下指向c;下一个循环,next=空了,然后把c的next指向了b,然后node=c,然后lnode=空。这个时候判断了lnode为空,结束循环,形成了a<-b<-c。

代码

ListNode* ReverseList(ListNode* pHead) {
    if (pHead == NULL)
        return NULL;
    ListNode *node = NULL;
    ListNode *lnode = pHead;
    while(lnode!= NULL){
        ListNode *next = lnode->next;
        lnode->next = node;
        node = lnode;
        lnode = next;

    }
    return node;
}

题目9 合并两个排序的链表

题目描述

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

题目解析

一定要考虑鲁棒性:
1. 若第一个链表为空,则直接返回第2个;
2. 若第二个链表为空,则直接返回第1个;
3. 其实若两个链表都为空的话,在第一个if语句判断的时候返回了第二个链表,而第2个链表为空,所以正好也是返回了NULL。
4. 这个时候我们新建一个result的链表存储结果,并为空,对于头结点来说,判断第一个链表和第二个链表的值,若第一个小于第二个,则把第一个链表的头结点给result,然后继续往下进行递归调用Merge函数(Merge(pHead1->next,pHead2));否则,把第二个链表的头结点给result,继续往下进行递归调用Merge函数(Merge(pHead1,pHead2->next)。

代码

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1==NULL)
        return pHead2;
    if(pHead2==NULL)
        return pHead1;
    ListNode* result=NULL;
    if(pHead1->val<pHead2->val)
    {
        result=pHead1;
        result->next=Merge(pHead1->next,pHead2);
    }
    else
    {
        result=pHead2;
        result->next=Merge(pHead1,pHead2->next);
    }
    return result;
}

题目10 树的子结构

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

题目解析

第一步在树A中查找与根节点的值一样的结点,这实际上就是树的遍历。如HasSubtree()函数中所述。如果根值相同,则去继续比较,否则有A的左子树和B比较,如果还不行就用A的右子树和B比较。
我们一定要注意边界条件的检查,即检查空指针。当树A或B为空的时候,定义相应的输出。本代码里面就是if不符合之后直接返回result。
第二步是判断树A中以R为根节点的子树是不是和B具有相同的结构,这里也是用递归来实现的,如果A为空了B还不是空的,那么B肯定不是A的子树;如果B空了A还没空,那么肯定也不是;如果两个结点值不一样,那就返回false;如果值相同,则继续对左子树和右子树进行比较。
一个可以提现专业的细节:double和float表示小数的时候都有误差,所以判断两个小数的时候不能直接判断相等,而是要判断他们的误差是不是在一个很小的范围内,如果很小,就认为相等。所以可以定义下面的函数:

bool Equal(double a,double b)
{
    if((num1-num2>-0.0000001)&&(num1-num2<0.0000001)
        return true;
    else
        return false;
}

代码

bool HasSub(TreeNode* root1, TreeNode* root2)
    {
        if(root1 ==NULL && root2 !=NULL)
            return false;
        if(root2==NULL)
            return true;
        if(root1->val != root2->val)
            return false;
        return HasSub(root1->left,root2->left)&&HasSub(root1->right,root2->right);

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

        return result;
    }
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 剑指offer
最后更新:2019年3月4日

yszhang

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

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

文章评论

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
《鸟哥的Linux私房菜》(基础篇)笔记整理(第8章) Python语言程序设计(第4周)整理 全国首条市内高铁济莱高铁开工建设 吴恩达深度学习课程 DeepLearning.ai 编程作业(2-2) C++面向对象程序设计课程笔记(第四周) 个人日记-091223
标签聚合
Java leetcode linux 学习 高中 python学习 生活 算法 鸟哥的linux私房菜 Python
最近评论
davidcheung 发布于 6 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 6 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 10 个月前(10月20日) :wink:
niming 发布于 11 个月前(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号