每日算法题：Day 30（Python）
作者：TeddyZhang，公众号：算法工程师之路
Day 30, Python知识点走起~
1
编程题
【剑指Offer】把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路： 层次遍历，层次遍历，层次遍历，然后使用队列的size，用于判断每一行的个数，然后，一次遍历一次直接遍历一行，更多用法参考Day29(" 之字形打印二叉树 " 和 " 二叉树的深度 ")
/*
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;
que.push(pRoot);
while(!que.empty()){
int size = que.size();
vector<int> res_tmp;
while(size--){
TreeNode* tmp = que.front();
que.pop();
res_tmp.push_back(tmp->val);
if(tmp->left != nullptr)
que.push(tmp->left);
if(tmp->right != nullptr)
que.push(tmp->right);
}
res.push_back(res_tmp);
}
return res;
}
};
【剑指Offer】序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
思路：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
char* Serialize(TreeNode *pRoot) {
string s;
if (!pRoot)
return nullptr;
deque<TreeNode*> q;
q.push_back(pRoot);
while (!q.empty()) {
int n = q.size();
for (int i = ; i < n; ++i) {
if (q.front()) {
q.push_back(q.front()->left);
q.push_back(q.front()->right);
s += to_string(q.front()->val) + ' ';
} else {
// 如果是nullptr，则使用# 表示
s += "# ";
}
q.pop_front();
}
}
char* chr = strdup(s.c_str());
return chr;
}
TreeNode* Deserialize(char *str) {
if (!str)
return nullptr;
int k = ;
auto ret = nextNode(str, k);
deque<TreeNode*> q;
q.push_back(ret);
while (!q.empty()) {
int n = q.size();
for (int i = ; i < n; ++i) {
q.front()->left = nextNode(str, k);
q.front()->right = nextNode(str, k);
if (q.front()->left)
q.push_back(q.front()->left);
if (q.front()->right)
q.push_back(q.front()->right);
q.pop_front();
}
}
return ret;
}
TreeNode* nextNode(char *str,int &i) {
string s;
while (str[i] != '\0'&&str[i] != ' ') {
if (str[i] == '#') {
i += ;
return nullptr;
}
s += str[i];
i++;
}
if (str[i] == ' ')
i++;
if (!s.empty())
return new TreeNode(stoi(s));
return nullptr;
}
};2
概念题
【Python】装饰器@property的作用是什么？
由于我们对一个实例的属性进行操作时，有时候不希望属性暴露出来，因此一般使用getter和setter成员函数来获取或者修改该属性，而Python内置的装饰器@property可以很好的辅助实现这个功能！并且可以很快速的讲一个类方法变成一个属性！并且其还内置了setter属性用来修改属性的值！注意@property和@score.setter下的函数名尽量保持一致！
class Student(object):
def __init__(self):
super(Student).__init__()
@property
def score(self):
return self.__score
@score.setter
def score(self, value):
self.__score = value
Student.score =
print(Student.score
【Python】python中的dict属性是做什么的？
一个类的__dict__存放着类的静态函数，类函数，成员函数，全局变量和内置变量等，而一个对象示例的__ dict__存放着self.xxx的东西
class A(object):
a =
b =
def __init__(self):
self.a =
self.b =
def test(self):
print('a normal func.')
@staticmethod
def static_test(self):
print('a static func.')
@classmethod
def class_test(self):
print('a calss func.')
a = A()
print(A.__dict__)
print(a.__dict__)
# {'__module__': '__main__', 'a': 0, 'b': 1, '__init__': <function A.__init__ at 0x000001BB42445510>, 'test': <function A.test at 0x000001BB434AAE18>, 'static_test': <staticmethod object at 0x000001BB422AC438>, 'class_test': <classmethod object at 0x000001BB42452FD0>, '__dict__': <attribute '__dict__' of 'A' objects>, '__weakref__': <attribute '__weakref__' of 'A' objects>, '__doc__': None}
# {'a': 2, 'b': 3}
【Python】在python中没有const关键字，怎么实现一个常量呢？
python常规情况下没有常量，在python中通常使用类来构造const类型，具体原理为：重载内置函数（self.__setattr__和self.__getattr__）, 在定义的时候运行setattr, 将常量放入到__dict__中，后面如果再次进行设置就会报错！获取则正常执行！ 代码为：
class Const:
class ConstError(TypeError): # 自定义异常函数
pass
def __setattr__(self, name, value):
if name in self.__dict__:
raise self.ConstError("Can't change const.%s" % name)
else:
self.__dict__[name] = value
self.__dict__[name] = value
def __getattr__(self, name):
if name in self.__dict__:
return self.__dict__[name]
else:
return None
con = Const() # 实例化
con.PI = 3.14
print(con.PI) # 输出3.14
con.PI = 4.8
print(con.PI) # 会出现ConstError的错误，并终止程序完