剑指offer例题分享--4

简介:   前言:搁置许久的更新要继续开始了!前一段时间一直在忙项目和C++的学习,所以搁置了!要改变注意了,要用C++进行编写了,因为要不断练习C++!  面试题15: 书中要求只能遍历链表一次,所以代码如下:#include#includeusing namespace std;st...

  前言:搁置许久的更新要继续开始了!前一段时间一直在忙项目和C++的学习,所以搁置了!要改变注意了,要用C++进行编写了,因为要不断练习C++!

  面试题15:

 

书中要求只能遍历链表一次,所以代码如下:

#include<iostream>
#include<cstdlib>
using namespace std;

struct ListNode
{
    int data;
    ListNode * next;
};

typedef struct ListNode  linknode_t; 
typedef struct ListNode* linklist_t;
linknode_t *CreateLink()         // 创建空的链表  返回值 链表的首地址
{    
    linknode_t *H;
    H = (linklist_t)malloc(sizeof(linknode_t)); 
    
    H->next = NULL;
    return H;
}   
void InitLink(linknode_t *H)        // 初始化一个空的链表  
{
    linknode_t *r, *p;
    int i;
    r = H;                     //  r 指向 队尾位置 
    for(i = 0; i < 5; i++)
    {
        p = (linknode_t *)malloc(sizeof(linknode_t));
        p->data = i+1;
        p->next = NULL;         // 没有下一个节点
        r->next = p;            // 将p 放在 r 的后面
        r = p;                  //  r 指向新的队尾
    }
    
}

void ShowLink(linknode_t* H)           // 从队首->队尾 打印所有节点
{
    linknode_t *p;
    p = H->next;
  while(p != NULL){        
        cout << " " << p->data;
        p = p->next;   
    }
    cout << endl;
}

ListNode *FindKthToTail(ListNode *pListHead,unsigned int k)
{
    if(pListHead == NULL || k == 0)
        return NULL;

    ListNode *pAhead = pListHead;
    ListNode *pBehind = NULL;

    for(unsigned int i=0;i<k-1;++i)
    {
        if(pAhead->next != NULL)
            pAhead = pAhead->next;
        else
        {
            return NULL;
        }
    }

    pBehind = pListHead;
    while(pAhead->next != NULL)
    {
        pAhead = pAhead->next;
        pBehind = pBehind->next;
    }
    
    return pBehind;
}

int main()
{
    linknode_t *H = CreateLink();
    InitLink(H);
    ShowLink(H);
    
    linknode_t *S = FindKthToTail(H,2);
    cout << "data:" << S->data << endl;
    
    return 0;
}

  总结:要熟练对单链表的使用!当我们用一个指针不能解决问题,可以尝试用两个指针遍历链表,可以让其中一个指针遍历的速度快一些(比如一次在链表上走两步),或者让它在链表上走若干步!

  面试题16:

  主要考察链表的反转:

  代码如下:

  

#include<iostream>
#include<cstdlib>
using namespace std;

struct ListNode
{
    int data;
    ListNode * next;
};

typedef struct ListNode  linknode_t; 
typedef struct ListNode* linklist_t;
linknode_t *CreateLink()         // 创建空的链表  返回值 链表的首地址
{    
    linknode_t *H;
    H = (linklist_t)malloc(sizeof(linknode_t)); 
    
    H->next = NULL;
    return H;
}   
void InitLink(linknode_t *H)        // 初始化一个空的链表  
{
    linknode_t *r, *p;
    int i;
    r = H;                     //  r 指向 队尾位置 
    for(i = 0; i < 4; i++)
    {
        p = (linknode_t *)malloc(sizeof(linknode_t));
        p->data = i+1;
        p->next = NULL;         // 没有下一个节点
        r->next = p;            // 将p 放在 r 的后面
        r = p;                  //  r 指向新的队尾
    }
    
}

void ShowLink(linknode_t* H)           // 从队首->队尾 打印所有节点
{
    linknode_t *p;
    p = H->next;
  while(p != NULL){        
        cout << " " << p->data;
        p = p->next;   
    }
    cout << endl;
}

ListNode *ReverseList(ListNode *pHead)
{
    ListNode *pReversedHead = NULL;
    ListNode *pNode = pHead;
    ListNode *pPrev = NULL;
    while(pNode != NULL)
    {
        ListNode *pNext = pNode->next;

        if(pNext == NULL)
            pReversedHead = pNode;

        pNode->next = pPrev;
        pPrev = pNode;
        pNode = pNext;
    }

    return pReversedHead;
}

int main()
{
    linknode_t *H = CreateLink();
    InitLink(H);
    ShowLink(H);
    
    linknode_t *S = ReverseList(H);
    ShowLink(S);    
    
    return 0;
}

  面试17:

  题目如下:

  

   代码如下:

#include<iostream>
#include<cstdlib>
using namespace std;

struct ListNode
{
    int data;
    ListNode * next;
};

typedef struct ListNode  linknode_t; 
typedef struct ListNode* linklist_t;
linknode_t *CreateLink()         // 创建空的链表  返回值 链表的首地址
{    
    linknode_t *H;
    H = (linklist_t)malloc(sizeof(linknode_t)); 
    
    H->next = NULL;
    return H;
}   
void InitLink(linknode_t *H,int n=1)        // 初始化一个空的链表  
{
    linknode_t *r, *p;
    int i;
    r = H;                     //  r 指向 队尾位置 
    for(i = 0; i < 4; i+=n)
    {
        p = (linknode_t *)malloc(sizeof(linknode_t));
        p->data = i+n;
        p->next = NULL;         // 没有下一个节点
        r->next = p;            // 将p 放在 r 的后面
        r = p;                  //  r 指向新的队尾
    }
    
}

void ShowLink(linknode_t* H)           // 从队首->队尾 打印所有节点
{
    linknode_t *p;
    p = H->next;
  while(p != NULL){        
        cout << " " << p->data;
        p = p->next;   
    }
    cout << endl;
}

ListNode *Merge(ListNode *pHead1,ListNode *pHead2)
{
    //鲁棒性处理,空指针会造成程序崩溃
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode * pMergedHead = NULL;

    if(pHead1->data < pHead2->data)
    {
        pMergedHead = pHead1;
        pMergedHead->next = Merge(pHead1->next,pHead2);//递归处理
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->next = Merge(pHead1,pHead2->next);//递归处理
    }

    return pMergedHead;
}

int main()
{
    linknode_t *H = CreateLink();
    InitLink(H);
    linknode_t *H1 = CreateLink();
    InitLink(H1,2);
    ShowLink(H);
    ShowLink(H1);
    
    linknode_t *S = Merge(H->next,H1->next);    
    while(S != NULL){        
        cout << " " << S->data;
        S = S->next;   
    }
    cout << endl;
    
    return 0;
}

  总结:理解递归部分的思想。

  面试题18:

  面试题18是关于二叉树的,先简单介绍一下二叉树吧。 

    二叉树特点: 第i层 最多节点的个数 2^(i-1)

  树的深度 h , 树节点 最多 2^h-1

  遍历二叉树方法:先序遍历  中序遍历 后序遍历,具体遍历方法介绍可以在网上找,这里就不具体介绍了。

  程序中三种方法都写出来了,但只用了先序遍历。

  题目如下:

   

  代码如下:

  

#include<iostream>
#include<cstdlib>
using namespace std;

struct BinaryTreeNode
{
    int data;                                                    //节点数据
    BinaryTreeNode *lchild,*rchild;        //左孩子、右孩子
};
typedef struct BinaryTreeNode tree_t;

/******
    构造一个二叉树 递归实现
    参数:形参1:开始值,形参2:结束值
 ******/
tree_t *CreateTree(int i, int max) 
{
    //递归结束条件
    if(i > max)
    {
        return NULL;  //  == return 0;
    }
    
    tree_t *T;

    T = (tree_t *)malloc(sizeof(tree_t));    

    T->data = i;
    T->lchild = CreateTree(2*i, max); 
    T->rchild = CreateTree(2*i+1, max);
    return T;
}

//先序遍历输出二叉树
void FirstRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return ;
    cout << " " << p->data;    
    FirstRoot_DLR(p->lchild);
    FirstRoot_DLR(p->rchild);
}

//中序遍历输出二叉树 程序中未使用
void MiddleRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    MiddleRoot_DLR(p->lchild);
    cout << " " << p->data;    
    MiddleRoot_DLR(p->rchild);
}

//后序遍历输出二叉树 程序中未使用
void LastRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    LastRoot_DLR(p->lchild);    
    LastRoot_DLR(p->rchild);
    cout << " " << p->data;
}

bool DoesTree1HaveTree2(tree_t *pRoot1,tree_t *pRoot2)
{
    //树B为空直接不检查
    if(pRoot2 == NULL)
        return true;

    if(pRoot1 == NULL)
        return false;

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

    return DoesTree1HaveTree2(pRoot1->lchild,pRoot2->lchild)&&DoesTree1HaveTree2(pRoot1->rchild,pRoot2->rchild);
}

bool HasSubtree(tree_t *pRoot1,tree_t *pRoot2)
{
    bool result = false;

    if(pRoot1!=NULL && pRoot2!=NULL)
    {
        result = DoesTree1HaveTree2(pRoot1,pRoot2);
        if(!result)
            HasSubtree(pRoot1->lchild,pRoot2);
        if(!result)
            HasSubtree(pRoot1->rchild,pRoot2);
    }
    return result;
}

int main()
{
    tree_t *T1 = CreateTree(1,4);
    FirstRoot_DLR(T1);
    cout << endl;
    tree_t *T2 = CreateTree(1,2);
    FirstRoot_DLR(T2);
    cout << endl;
    //使用boolalpha输出为bool类型
    cout << boolalpha <<HasSubtree(T1,T2) << endl; 
    
    return 0;
}

  总结:书中第三章主要强调了代码的规范性、完整性和鲁棒性,鲁棒性例如对空指针的判断和处理...,用链表和二叉树做的例子,要熟悉掌握这两种数据结构!

 

作者: 柳德维

-------------------------------------------

个性签名:独学而无友,则孤陋而寡闻。做一个灵魂有趣的人!

如果觉得这篇文章对你有小小的帮助的话,记得在右下角点个“推荐”哦,博主在此感谢!

万水千山总是情,打赏一分行不行,所以如果你心情还比较高兴,也是可以扫码打赏博主,哈哈哈(っ•̀ω•́)っ⁾⁾!

目录
相关文章
|
6月前
|
算法
LeetCode刷题---167. 两数之和 II - 输入有序数组(双指针-对撞指针)
LeetCode刷题---167. 两数之和 II - 输入有序数组(双指针-对撞指针)
蓝桥杯AcWing 题目题解 - 递归与递推
蓝桥杯AcWing 题目题解 - 递归与递推
|
算法 C++
【每日算法Day 108】一道简单的二叉树题目,写法还是挺多的。
【每日算法Day 108】一道简单的二叉树题目,写法还是挺多的。
|
人工智能 算法 C++
蓝桥杯第十讲--贪心【例题】(一)
蓝桥杯第十讲--贪心【例题】
162 0
蓝桥杯第十讲--贪心【例题】(一)
|
人工智能
蓝桥杯第十讲--贪心【例题】(二)
蓝桥杯第十讲--贪心【例题】
172 0
蓝桥杯第十讲--贪心【例题】(二)
蓝桥杯第十三讲--树状数组与线段树【例题】(二)
蓝桥杯第十三讲--树状数组与线段树【例题】
139 0
蓝桥杯第十三讲--树状数组与线段树【例题】(二)
|
算法 C++
蓝桥杯第十三讲--树状数组与线段树【例题】(一)
蓝桥杯第十三讲--树状数组与线段树【例题】
170 0
蓝桥杯第十三讲--树状数组与线段树【例题】(一)
|
存储 算法 C++
蓝桥杯第二讲--递推【例题】
蓝桥杯第二讲--递推【例题】
141 0
蓝桥杯第二讲--递推【例题】
|
算法 C++
蓝桥杯第六讲--简单dp【例题】
蓝桥杯第六讲--简单dp【例题】
217 0
蓝桥杯第六讲--简单dp【例题】
|
机器学习/深度学习 算法 C++
蓝桥杯第一讲--递归【习题】
蓝桥杯第一讲--递归【习题】
134 0
蓝桥杯第一讲--递归【习题】