首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >挑战数据结构与算法面试题——80题全解析(三)

挑战数据结构与算法面试题——80题全解析(三)

作者头像
felixzhao
发布2018-03-14 16:07:09
6100
发布2018-03-14 16:07:09
举报
文章被收录于专栏:null的专栏null的专栏

题目来源“数据结构与算法面试题80道”。这是第三部分,包含其中的第11题到第15题。 在此给出我的解法,如你有更好的解法,欢迎留言。

这里写图片描述
这里写图片描述

问题分析:涉及的知识点是二叉树的遍历,遍历的方法主要有:

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层次遍历

在本题中,使用先序遍历的方法。

方法:

void m_length(BSTreeNode *root, int *length, int *max_length){
    if (NULL == root ||
        (NULL == root->m_pLeft && NULL == root->m_pRight)){
        if ((*length) > (*max_length)) (*max_length) = (*length);
        return;
    }
    (*length) ++;
    m_length(root->m_pLeft, length, max_length);
    (*length) --;

    (*length) ++;
    m_length(root->m_pRight, length, max_length);
    (*length) --;
}
这里写图片描述
这里写图片描述

问题分析:可以使用类的构造方法,在类的每次实例化对象时都会调用构造方法,那么只需要实例化n个对象,就会调用n次构造方法,这就模拟了循环的过程,此时,只需要有一个全局变量记录累加的值即可。

方法:

#include <stdio.h>

class calnum{
    public:
        calnum(){
            n ++;
            sum += n;
        }
        ~calnum(){}

        int get_num(){
            return sum;
        }
    private:
        static int sum;
        static int n;
};

int calnum::sum = 0;
int calnum::n = 0;

int main(){
    // 声明n个对象
    calnum *sum = new calnum[100];

    printf("%d\n", sum->get_num());

    delete[] sum;
    return 1;
}
这里写图片描述
这里写图片描述

问题分析:遍历一遍链表的时间复杂度为O(n),但是链表节点的遍历只能按顺序遍历,问题中是需要取到倒数第k个,最直接的想法是遍历两遍链表,第1遍得到链表的长度,第2遍是取到倒数第k个;那么能否只遍历一遍就能取到倒数第k个节点,最关键的点是需要确定链表的长度,我们可以使用双指针的方法:第一个指针用于遍历整个链表,第二个链表用于遍历部分链表,第一个指针比第二个指针多走k步,当第一个指针遍历完链表,第二个指针所指的即为倒数第k个数,如下图所示:

这里写图片描述
这里写图片描述

方法:

ListNode* get_reverse_k(ListNode *head, int k){
    if (NULL == head) return NULL;

    ListNode *p = head;
    ListNode *q = head;
    int step = 0;
    while (NULL != p->m_pNext){
        if (step >= k){
            q = q->m_pNext;
        }
        p = p->m_pNext;
        step ++;
    }
    if (step < k) return NULL;
    else return q;
}
这里写图片描述
这里写图片描述

问题分析:时间复杂度为O(n),即只能遍历一次数组,考虑到数组是排好序的,考虑从头部和从尾部同时向数组的中部遍历,假设i从头部遍历,j从尾部开始遍历:

  • 如果a[i] + a[j] == num,直接返回;
  • 如果a[i] + a[j] > num,应该减小其和的值,则减小j;
  • 如果a[i] + a[j] < num,应该增大其和的值,则增加i;

方法:

void get_sum(int *a, int length, int n){
    if (NULL == 0 || length <= 0) return;

    int start = 0;
    int end = length - 1;
    while (start < end){
        if (a[start] + a[end] == n){
            printf("%d,%d\n", a[start], a[end]);
            break;
        }else if (a[start] + a[end] > n){
            end --;
        }else{
            start ++;
        }
    }
}
这里写图片描述
这里写图片描述

问题分析:实质上仍然是二叉树的遍历,上述已经介绍过二叉树的不同的遍历方法,当遍历到每一个节点的时候,交换其左右子树,依次下去,直到叶子节点。

方法:

1、递归的方法:

void tree_swap(BSTreeNode *root){
    BSTreeNode *p_tmp = root->m_pLeft;
    root->m_pLeft = root->m_pRight;
    root->m_pRight = p_tmp;
}

void tree_mirror(BSTreeNode *root){
    if (NULL == root ||
        (NULL == root->m_pLeft && NULL == root->m_pRight)){
        return;
    }

    tree_swap(root);
    tree_swap(root->m_pLeft);
    tree_swap(root->m_pRight);
}

2、循环的方法

void tree_mirror_loop(BSTreeNode *root){
    if (NULL == root ||
        (NULL == root->m_pLeft && NULL == root->m_pRight)){
        return;
    }

    BSTreeNode *p = root;
    queue<BSTreeNode *> q_tree;
    q_tree.push(p);
    while (! q_tree.empty()){
        BSTreeNode *q = q_tree.front();
        q_tree.pop();
        if (NULL != q->m_pLeft || NULL != q->m_pRight){
            tree_swap(q);
        }
        if (NULL != q->m_pLeft) q_tree.push(q->m_pLeft);
        if (NULL != q->m_pRight) q_tree.push(q->m_pRight);
    }
}       
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档