每日算法题：Day 29（C/C++）
每日算法题：Day 29（C/C++）
作者：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有什么优点?
- const 常量有数据类型，而宏常量没有数据类型。编译器可以对前者进行类型安全检查。而对后者只进行字符替换，没有类型安全检查，并且在字符替换可能会产生意料不到的错误（边际效应）。
- 有些集成化的调试工具可以对 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 是用来求指定变量或者变量类型等所占内存大小。
完
腾讯云开发者
