首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日算法题:Day 29(C/C++)

每日算法题:Day 29(C/C++)

作者头像
算法工程师之路
发布2019-09-05 17:39:24
5250
发布2019-09-05 17:39:24
举报

作者:TeddyZhang,公众号:算法工程师之路

Day 29, C/C++知识点走起~

1

编程题

【剑指Offer】对称的二叉树

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

思路: 首先使用递归得方法,代码非常得简洁,如果l与r都是nullptr,那么就返回真,如果只有其中一个为nullptr,那么一定不是对称二叉树,则返回false,如果都不是nullptr,则需要判断其值是否相等,并且还要递归判断(l.left, r.right)和(l.right, r.left)两组数是否相等!

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot == nullptr)  return true;
        return process(pRoot->left, pRoot->right);
    }
private:
    bool process(TreeNode* l, TreeNode* r){
        if(l == nullptr && r == nullptr)
            return true;
        if(l != nullptr && r != nullptr)
            return l->val == r->val && 
            process(l->left, r->right) &&
            process(l->right, r->left);
        return false;
    }
};

另一种方法,可以使用类似于层次遍历的方式,使用一个队列的方式,每次将成对的元素入堆,然后成对的取出,并进行值得判断,如果相等,则进行下一次判断,不过不相等,返回false。注意,如果两者都是nullptr,则下面不执行,如果只有一个为nullptr,则返回false,因为此时成对元素已经不满足对应相等了!

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot == nullptr)  return true;
        queue<TreeNode*> q;
        q.push(pRoot->left);
        q.push(pRoot->right);
        while(!q.empty()){
            // 成对的取出元素
            TreeNode* left = q.front();
            q.pop();
            TreeNode* right = q.front();
            q.pop();  // 删除头节点
            if(left == nullptr && right == nullptr) continue;
            if(left == nullptr || right == nullptr) return false;
            if(left->val != right->val) return false;
            // 成对的插入元素
            q.push(left->left);
            q.push(right->right);
            q.push(left->right);
            q.push(right->left);
        }
        return true;
    }
};

【剑指Offer】按之字形数据打印二叉树

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

思路: 这道题目与之前有个"二叉树的深度"题目类似,思路的核心是层次遍历,但是在遍历的同时需要处理每一层数据,因此可以使用一个while循环,将每层数据储存到res_tmp中,并且使用even变量来标记层数的奇偶性,如果是奇数的话,那么需要将res_tmp进行反转!

还有一个双栈的做法,效率更高,不过代码写的时候不是那么容易,有细节需要考虑!自己想懂得可以到评论去查看!

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if(pRoot == nullptr) return res;
        queue<TreeNode*> que;
        bool even = false;
        que.push(pRoot);
        while(!que.empty()){
            int size = que.size();
            vector<int> res_tmp;    // 二叉树得高度,层次遍历
            for(int i = ;i < size; i++){
                TreeNode* tmp = que.front();
                res_tmp.push_back(tmp->val);
                que.pop();
                if(tmp->left != nullptr)
                    que.push(tmp->left);
                if(tmp->right != nullptr)
                    que.push(tmp->right);
            }
            if(even){
                reverse(res_tmp.begin(), res_tmp.end());
            }
            res.push_back(res_tmp);
            even = !even;
        }
        return res;
    }
};

2

概念题

【C/C++】const 与 #define 的比较, const有什么优点?

  1. const 常量有数据类型,而宏常量没有数据类型。编译器可以对前者进行类型安全检查。而对后者只进行字符替换,没有类型安全检查,并且在字符替换可能会产生意料不到的错误(边际效应)。
  2. 有些集成化的调试工具可以对 const 常量进行调试,但是不能对宏常量进行调试

【C/C++】全局变量和局部变量有什么区别?是怎么实现的?操作系统和编译器是怎么知道的?

  • 生命周期不同:全局变量随主程序创建和创建,随主程序销毁而销毁;局部变量在局部函数内部,甚至局部循环体等内部存在,退出就不存在;
  • 使用方式不同:通过声明后全局变量程序的各个部分都可以用到;局部变量只能在局部使用;分配在栈区。
  • 操作系统和编译器通过内存分配的位置来知道的,全局变量分配在全局数据段并且在程序开始运行的时候被加载。局部变量则分配在堆栈里面 。

【C/C++】sizeof和strlen的区别是什么?

  • sizeof是一个关键字,而strlen是一个函数,sizeof一般在编译时进行计算,而strlen则是在运行时计算!
  • sizeof可以用来计算数据类型所占内存大小,而strlen只能用来计算字符串的大小,遇到'\0'则停止计算
  • sizeof只关心当前变量的内存大小,并不关心其内容,而strlen并不在意内存大小,只关注字符串内容,计算到'\0'就终止!
  • sizeof和strlen对于指针和数组来说,就会有很大不同!

笔试题目例子:

char str[]="0123456789";
int a=strlen(str);         // a=10; >>>> strlen 计算字符串的长度,以结束符 0x00 为字符串结束。
int b=sizeof(str);         // 而 b=20; >>>> sizeof 计算的则是分配的数组 str[20] 所占的内存空间的大小,不受里面存储的内容改变。

char* ss = "0123456789";
sizeof(ss)  // 结果 4 ===》ss 是指向字符串常量的字符指针,sizeof 获得的是一个指针的之所占的空间,应该是长整型的,所以是 4。
sizeof(*ss) // 结果 1 ===》*ss 是第一个字符 其实就是获得了字符串的第一位 '0' 所占的内存空间,是 char 类型的,占了 1 位
strlen(ss)  // 结果 10 ===》 如果要获得这个字符串的长度,则一定要使用 strlen。strlen 用来求字符串的长度;而 sizeof 是用来求指定变量或者变量类型等所占内存大小。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-09-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法工程师之路 微信公众号,前往查看

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

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

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