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

赵志勇

2017-08-07

题目来源“数据结构与算法面试题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);
    }
}

读者评论

相关博文

  • 社区使用反馈专区

    陈晓猛 2016-10-04

    尊敬的博文视点用户您好: 欢迎您访问本站,您在本站点访问过程中遇到任何问题,均可以在本页留言,我们会根据您的意见和建议,对网站进行不断的优化和改进,给您带来更好的访问体验! 同时,您被采纳的意见和建议,管理员也会赠送您相应的积分...

    陈晓猛 2016-10-04
    1016 154 0 3
  • 迎战“双12”!《Unity3D实战核心技术详解》独家预售开启!

    陈晓猛 2016-12-05

    时隔一周,让大家时刻挂念的《Unity3D实战核心技术详解》终于开放预售啦! 这本书不仅满足了很多年轻人的学习欲望,并且与实际开发相结合,能够解决工作中真实遇到的问题。预售期间优惠多多,实在不容错过! Unity 3D实战核心技术详解 ...

    陈晓猛 2016-12-05
    1153 34 0 1
  • 新书试读员征集

    陈晓猛 2016-12-01

    活动获奖名单公布 恭喜以下10位读者朋友获得本次试读员征集的名额,请私信 陈晓猛 将您的QQ号发给小编,以便加入读者VIP群,给您送出图书! 获奖名单 程续缘 悠悠的一杯茶 313150284@qq.com llaomao 落伍特青年 ...

    陈晓猛 2016-12-01
    384 12 0 0