树的笔记
##
- 0 树
- 1 二叉树
- 2 二叉查找树
- 3 平衡二叉树
0.树
树有多个节点(node),用以储存元素。某些节点之间存在一定的关系,用连线表示,连线称为边(edge)。边的上端节点称为父节点,下端称为子节点。树像是一个不断分叉的树根。
树的深度和高度的定义:
基数为1时 树的深度=树的高度=最大层数
1.二叉树
二叉树是数据结构中重要的数据结构,也是树家族最为基础的结构。
二叉树的定义
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点).
二叉树的子树有左右之分,次序不能颠倒。
二叉树的第i层至多有2^(i-1)个结点.
深度为k的二叉树至多有2^k-1个结点.
对任何一棵二叉树T,如果其终端结点数为N,度为2的结点数为M,则N=M+1。1.1 满二叉树
就是满树呗。
1.2完全二叉树
高度为h的完全二叉树。前h-1层为满树,最后一层元素全部集中在左侧。
2.二叉查找树
定义
又称二叉排序树(Binary Sort Tree)或二叉搜索树。二叉排序树是一颗空树或者是具有以下性质的树。
- 若左子树不为空 则左子树上的所有值均小于根节点的值。
- 若右子树不为空 则右子树所有值大于根节点的值。
- 以上性质完全适用于左右子树(左右子树均为二叉查找树)。
- 没有键值相等的节点。
3.平衡二叉树
平衡二叉树的定义
Balance Binary Tree又称为AVL树。它具有以下性质:
- 1.它是一颗空树或者它的左右两个子树的高度差绝对值不超过1。
- 2.它的左右子树均是一颗平衡二叉树。
在平衡二叉搜索树中,我们可以看到,其高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。
python的类
0 坑的实例
1 | class A: |
1 | class A: |
这俩啥区别?
做该题目时遇到了坑Binary Tree Path.
注意到init方法的第一个参数永远是self,表示创建的实例本身,因此,在init方法内部,就可以把各种属性绑定到self,因为self就指向创建的实例本身。
有了init方法,在创建实例的时候,就不能传入空的参数了,必须传入与init方法匹配的参数,但self不需要传,Python解释器自己会把实例变量传进去:
1 python的对象删除
1 | a = [1,2,3] |
del删除的是变量,而不是数据,解除了变量和数据的联系。
以上现象说明了:
- 1.’=’赋值的两个对象具有相同的内存地址。
- 2.修改其中一个 另外一个值也会受到影响.(类似于C++中的指针)
- 3.del其中一个 另外一个却不受影响.(类似于C++中引用
看网上的总结:
- 1.首先介绍python的对象引用
- a. python不允许程序员选择采用传值还是传引用。Python参数传递采用的肯定是传对象引用的方式。实际上,这种方式相当于传值和传引用的一种综合。如果函数收到的是一个可变对象(比如字典或者列表)的引用,就能修改对象的原始值——相当于通过传引用来传递对象。如果函数收到的是一个不可变对象(比如数字、字符或者元组)的引用,就不能直接修改原始对象——相当于通过传值来传递对象。
- b. 当人们复制列表或字典时,就复制了对象列表的引用同,如果改变引用的值,则修改了原始的参数。
- c . 为了简化内存管理,Python通过引用计数机制实现自动垃圾回收功能,Python中的每个对象都有一个引用计数,用来计数该对象在不同场所分别被引用了多少次。每当引用一次Python对象,相应的引用计数就增1,每当消毁一次Python对象,则相应的引用就减1,只有当引用计数为零时,才真正从内存中删除Python对象.
- del函数。删除引用,而不是删除对象。对象由自动垃圾回收机制删除。解释了删除掉a之后 b还有值的缘故。
{.line-numbers} 1
2
3
4
5a = 2
b = a
b = 3
print(a)
#2
- del函数。删除引用,而不是删除对象。对象由自动垃圾回收机制删除。解释了删除掉a之后 b还有值的缘故。
- 1.首先介绍python的对象引用
python字符串相关操作
Momenta World Cup比赛小结
北京时间2018.08.07 20:07
刚从五道口吃饭回来,到今天,二十多天的Momenta无人车足球赛算是告一段落,论文明天再写,先写此文做个小总结。
此次比赛规则很简单:类似于世界杯,双方各执一车,上下半场各20分钟,进球多者为胜者。
比赛物力&人力:
- turtlebot3智能小车一台
- 运算平台: 树莓派*2
- 传感器:camera*2
- 控制器与电机
- 其他结构部件
- 数据集:带标签图片10W张
- 算力:每组TITANX * 8
- 队友:程煜钧-北交博三 冯昊-清华大二 余唯民-清华大三 闫坤-北航大二 本人-北邮研一
我扮演角色:类似酱油
比赛结果:第五名
收获及感想:
1. 关于Momenta
这家公司真的技术好牛逼。
这家公司的Mentor真的好年轻。
这家公司真的好人性化。
这家公司福利真的好。
Dinner talker 分别见到了创始人旭东 Faster-RCNN作者 少卿。
旭东很年轻,但是有这个年龄不该有的深邃,无论是言谈与对话上。
少卿腼腆,书生气质很重。说话比较轻 谈起NN比较话多。
各种Mentor 其中底层至芯片代码,应用至NN的大牛 与我同龄。
拿过各种机器学习的冠军的李翔 比我大三年而已,问其本科事迹,10年已经在玩AI。那时我在写51。
总之 Momenta人才年轻 很有创造力 假以时日 定能执国内无人驾驶行业牛耳。
2. 关于自己
好菜。
真的好菜。
这次比赛,队里代码主要由低年级的小兄弟写的,我就在旁边给点how to的建议,想起自己大二那年全国电赛写无人机C代码了场景了,非常类似。
小兄弟们码力很强,至少比同时的我强。也让我认识到自己码力的不足,我比他们大三届啊 这三年我写都了啥代码?为何码力长进这么差?
这次深刻认识到了自己的不足之处 同龄的他们已经在Momenta做Mentor了 而我还在搬着砖。
3. 关于未来:
就要研二了,研三就要实习。充电时间就剩一年,到时如何让把自己卖出一个好价钱是个大问题。
研二Todolist:
- 刷算法。Java Python。提高码力。
- 刷Linux。熟悉生产环境。
- 多写blog 多做总结。
- 认真做事。每一件小事。
- 多刷leetcodee 年入百万。。。
- 看书。
先这样吧
1 | #define TRUE FALSE |
Ubuntu16.04 + CDH5.14 + saprk2 踩坑实录
1.配置Java环境。
2.修改主机hosts。
3.免密登陆。
4.下载安装包.
5.坑.
- JAVA_HOME.即使设置的很对还是报错。 改链接。 http://www.aboutyun.com/thread-23764-1-1.html
mkdir –p /usr/java
ln -s /usr/lib/jdk/jdk1.8.0_181 /usr/java/default
- JAVA_HOME.即使设置的很对还是报错。 改链接。 http://www.aboutyun.com/thread-23764-1-1.html
- hue数据库访问。 python的锅。需要装东西 https://stackoverflow.com/questions/5178292/pip-install-mysql-python-fails-with-environmenterror-mysql-config-not-found
apt install python-dev
apt install python-mysqldb
- hue数据库访问。 python的锅。需要装东西 https://stackoverflow.com/questions/5178292/pip-install-mysql-python-fails-with-environmenterror-mysql-config-not-found
- 创建失败 no user cloudera-scm。新开用户。
- ACL问题
改ACL
- ACL问题
- permissions 问题
hdfs 用户修改所有权限777
- permissions 问题
- spark2
安装最新版本即可。- java 包错误。Error: A JNI error has occurred, please check your installation and try again
Exception in thread “main” java.lang.NoClassDefFoundError: org/slf4j/Logger
修改spark-env.sh
https://www.jianshu.com/p/6acd6419f697
- java 包错误。Error: A JNI error has occurred, please check your installation and try again
- spark2
总结:多google 多看官方文档.
tensorflow 模型保存
1. tensorflow模型保存
1 | import tensorflow as tf |
以上代码生成了3个文件
- 1.my-model.ckpt.data-00000-of-00001
- 2.my-model.ckpt.index
- 3.my-model.ckpt.meta
2.模型加载
1 | with tf.Session() as sess: |
尽管以上代码中指定的文件名字并没有声明,但是通过saver还是可以自动加载出模型的。
Ubuntu系统磁盘相关命令
1.swap分区大小.
- 内核空间交换区分利用参数查看命令
{.line-numbers} 1
cat /proc/sys/vm/swappiness
cat /proc/sys/vm/swappiness
2.调整分区大小.
通过gparted 软件
3.查看磁盘命令.
1 | df -hl |
4.显示隐藏文件
1 | ctrl+h |
5.adduser useradd
adduser 会自动创建用户目录。
6.fork()函数
只需记住一点:fork()函数调用一次返回两次。
在父进程中 根据返回值(子进程PID)继续执行
在子进程中 根据返回值(0) 再继续执行。
如下例子 根据短路原则 main作为父进程 会创建子进程1 子进程1创建子进程2。
子进程保存了父进程前的代码状态 并直接运行。{.line-numbers}
1
2
3
4 int main()
{
fork()||fork();
}
7.进程与线程
进程是操作系统进行资源分配和调度的一个独立单位。线程是CPU调度和分派的基本单位,是比进程更小的能独立进行的基本单位。线程是进程的一个实体,一个进程中包含多个线程,线程是共享进程的地址空间。
8.标准输入输出
0,1,2叫文件描述符;Linux中,每打开一个文件都有一个小的整数与之对应,就是文件描述符!
0 是标准输入的 (stdin)
1 是标准输出的 (stdout)
2 是标准报错输出的 (stderr)
‘<’是输入重定向符
‘>’是输出重定向符
9.reboot和shutdown init
reboot是重新启动 删除一切进程。shutdown是立即停止然后重新启动。shutdown命令可以安全地关闭或重启Linux系统,它在系统关闭之前给系统上的所有登录用户提示一条警告信息。该命令还允许用户指定一个时间参数,可以是一个精确的时间,也可以是从现在开始的一个时间段。
init是所有进程的祖先,其进程号始终为1。init用于切换系统的运行级别,切换的工作是立即完成的。init 0命令用于立即将系统运行级别切换为0,即关机;init 6命令用于将系统运行级别切换为6,即重新启动。
shell 变量含义
1.shell变量
linux中shell变量$#,$@,$0,$1,$2的含义解释
| 参数形式 | 含义 |
| ——- | ——- |
|$0| 当前脚本文件名|
|$n| 传递给脚本或函数的参数。代表第n个参数。n不能大于10。
|$#| 传递给脚本或者函数的参数个数。|
|$| 传递给脚本或函数的所有参数。|
|$@| 同上。被双引号(“ “)包含时,与 $ 稍有不同。|
|$?| 上个命令的退出状态或者函数返回值。 |
|$$| 当前shell进程ID。|1
2
3
4
5
6
7
8
9
10
11
12
13
14
15#!/bin/bash
echo "File Name: $0"
echo "First Parameter : $1"
echo "First Parameter : $2"
echo "Quoted Values: $@"
echo "Quoted Values: $*"
echo "Total Number of Parameters : $#"
###
./test.sh one two
# File Name : ./test.sh
# First Parameter : one
# Second Parameter : two
# Quoted Values: one two
# Quoted Values: one twp
# Total Number of Parameters : 2
2.提取文件名
${}用于字符串的读取,提取和替换功能,可以使用${} 提取字符串1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
321、提取文件名
# var=/dir1/dir2/file.txt
# echo ${var##*/}
file.txt
2、提取后缀
# var=/dir1/dir2/file.txt
# echo ${var##*.}
txt
3、提取不带后缀的文件名,分两步
# var=/dir1/dir2/file.txt
# tmp=${var##*/}
# echo $tmp
file.txt
# echo ${tmp%.*}
file
5、提取目录
# var=/dir1/dir2/file.txt
# echo ${var%/*}
/dir1/dir2
6、
# var=/dir1/dir2/file.txt
# echo ${var%%.*}
/dir1/dir2/file
7、
# var=/dir1/dir2/file.tar.gz
# echo ${var#*.}
tar.gz
8、${}总结
${}的使用是变量的提取和替换等操作;
#:表示从左边算起第一个
%:表示从右边算起第一个
##:表示从左边算起最后一个
%%:表示从右边算起最后一个
换句话来说,#总是表示左边算起,%总是表示右边算起。
:表示要删除的内容,对于#和##的情况,它位于指定字符(例子中的’/‘和’.’)的左边,表于删除指定字符及其左边的内容;对于%和%%的情况,它位于指定字符(例子中的’/‘和’.’)的右边,表示删除指定字符及其右边的内容。这里的’‘的位置不能互换,即不能把*号放在#或##的右边,反之亦然。
使用文件目录的专有命令basename和dirname
1、提取文件名,注意:basename是一个命令,使用$(), 而不是${}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18# var=/dir1/dir2/file.txt
# echo $(basename $var)
file.txt
2、提取不带后缀的文件名
# var=/dir1/dir2/file.txt
# echo $(basename $var .txt)
file
3、提取目录
# var=/dir1/dir2/file.txt
# dirname $var
/dir1/dir2
# echo $(dirname $var)
/dir1/dir2
# dir=/dir1/dir2/
# dirname $dir
/dir1
python常识基础
To be added:目录
1.python求整
1 | a = 4//3 |
2.位操作
1 | a = 0011 1100 |
4.lambda
lambda 表达式通常在需要一个函数,但是又不想费神(233)去命名一个函数时使用,也就是匿名函数。1
2
3
4
5
6
7add = lambda x,y : x+y
add(1,2)
#3
#-----------
a = [1,-3,2,4]
# key -- 主要是用来进行比较的元素,只有一个参数,具体的函数的参数就是取自于可迭代对象中,指定可迭代对象中的一个元# 素来进行排序。
b = sorted(a,key =lambda x:abs(x)
5.enumerate
- python 内置函数
- 对于一个可迭代的(iterable)/可遍历的对象(如列表、字符串),enumerate将其组成一个索引序列,利用它可以同时获得索引和值
{.line-numbers} 1
2
3
4
5
6
7
8
9a =[1,3,4,6]
for index,item in enumerate(a):
print(index,item)
'''
0 1
1 3
2 4
3 6
'''
6.set 求交 并 差集
set的遍历是无序的。
不同机器 不同时间跑出的结果都不一样。
- 交集 : x&y
- 并集 : x|y
- 差集 : x-y
7.filter 函数
filter函数用于过滤序列,过滤掉不符合条件的元素,python2中返回新列表,python3中返回可迭代对象。
用法
filter(function,iterable)
1 | a = filter(lambda x: x % 2 ==0,range(10)) |
8.python 中的None True False
1 | list1 = [] |
判断对象是否为None 主要由以下写法:1
2
3
4
5
6
7if X is None:
pass
if not X:
pass
# 当X为None, False, 空字符串"", 0, 空列表[], 空字典{}, 空元组()这些时,not X为真,即无法分辨出他们之间的不同。
if not X:
pass
在Python中,None、空列表[]、空字典{}、空元组()、0等一系列代表空和无的对象会被转换成False。除此之外的其它对象都会被转化成True。
- None是一个特殊的常量.
- None和False不同。
- None不是0。
- None不是空字符串。
- None和任何其他的数据类型比较永远返回False。
- None有自己的数据类型NoneType。
- 你可以将None复制给任何变量,但是你不能创建其他NoneType对象。
9.牛逼的sum函数。
sum()的语法是:
sum(iterable,start)
The sum() function adds start and items of the given iterable from left to right.
sum()参数:
iterable- iterable (list, tuple, dict etc) whose item’s sum is to be found. Normally, items of the iterable should be numbers.
可以是list 元组 字典等可迭代对象。
start (optional) - this value is added to the sum of items of the iterable. The default value of start is 0 (if omitted)
默认为0.也可以是[]等。1
2
3
4a = [[1,3,5,7,9],[2,4,6,8]]
x = sum(a,[])
print(x)
# [1 3 5 7 9 2 4 6 8]
10. 单引号 双引号 三引号
- 1.单引号和双引号是通用的。
- 2.在要表达的字符串中有单引号出现时使用双引号方便。
- 3.在要表达的字符串中有单引号出现时使用单引号方便。
- 4.三引号的出现是直接可以做在引号内回车。当然还可以做注释块啦。
- 5.1234均体现了python的任性化。
{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 str1 = " I'm OK, thank u"
str2 = 'Hello,MI "Fans"'
str3 = ''' Are
You
OK
'''
print(str1,str2,str3)
'''
I'm OK, thank u
Hello,MI "Fans"
Are
You
OK
'''
11. python 赋值 浅拷贝 深拷贝
1.直接赋值。其实就是对象的引用。(别名)。赋值引用,都指向同一个对象。
2.浅拷贝。拷贝父对象,不会拷贝父对象的内部子对象。两者是一个独立的对象,但他们的子对象还是指向统一对象(是引用)。
3.深拷贝。copy模块的deepcopy()方法,完全拷贝了父对象个其子对象。两者是完全独立的。{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11 import copy
a = [1,2,3,[4,5,6]]
b = a.copy()
a[3].append(7)
c = copy.deepcopy(a)
print(a,b,c)
print(id(a),id(b),id(c))
# [1, 2, 3, [4, 5, 6, 7]] [1, 2, 3, [4, 5, 6, 7]] [1, 2, 3, [4, 5, 6, 7]]
# 2164258934920 2164258672008 2164258840008
print(id(a[1]),id(b[1]))
1616669792 1616669792
4.关于*
{.line-numbers}
1
2
3
4
5 a = [[]] * 2
id(a[0])
#2653548226632
id(a[1])
#2653548226632
12.装饰函数
参见装饰函数。写的是真好。
13.map/reduce函数。起源于Google鼎鼎大名 Map/Reduce论文。
python中map()、filter()、reduce()这三个都是应用于序列的内置函数。
map(function, iterable, …)
map()函数接收两个参数,一个是函数,一个是序列,map将传入的函数依次作用到序列的每个元素,并把结果作为新的list(python2.7) Iterator(python3 使用之前需要list化)返回。
stackoverflow上有人说可以这样理解map():{.line-numbers}
1
2
3
4
5
6
7
8
9
10 map(f, iterable)
#基本上等于:
[f(x) for x in iterable]
def f(x):
return abs(x)
for item in map(f,[1,-2,3,-4]):
print(item)
# 1 2 3 4
14.赋值
多重赋值:x=y=z=1
多元赋值:x,y,z=1,3,’a string’
增量赋值:x+=1
15.
sys.argv是传递给python脚本的命令行参数【字符串】列表
argv[0]为该脚本自身路径,其余为命令行参数。
和shell脚本的 $0 $1 $2 $3 $4一样。
16.zip 函数
zip()函数用于将可迭代的对象(如list dict )作为参数,将对象中对应元素进行打包成一个个元组,然后返回由这些元组组成的对象。返回组成的对象节省了内存可以使用list()俩将输出对象那个转换为列表.如果各个迭代器元素个数不一样 则返回列表长度于最短对象相同。zip(*zipped) 解压缩。
{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 zipped = zip([1,2,3],[4,5,6])
zipped
#<zip at 0x16fd026dbc8>
list(zipped)
[(1, 4), (2, 5), (3, 6)]
a,b = zip(*zipped) #error 了 很奇怪
zipped = zip([1,2,3],[4,5,6]) ##这样就可以 很奇怪
a,b = zip(*zipped)
a
(1,2,3)
b
(4,5,6)
17 .join()函数
用于将序列中的元素以指定的字符连接生成一个新的字符串。参数可以是元组 列表 字典 字符串。
语法:str.join(sequence){.line-numbers}
1
2
3
4
5
6
7
8
9
a = ['1','2','3']
st = ''.join(a)
#'123'
#对于字典类型 只会将key进行连接
seq = {'hello':'nihao','good':2,'boy':3,'doiido':4}
print('-'.join(seq))
# hello-good-boy-doiido
18 可迭代对象。
可以直接作用于for循环的数据类型有以下几种:
一类是集合数据类型,如list、tuple、dict、set、str等;
一类是generator,包括生成器和带yield的generator function。
这些可以直接作用于for循环的对象统称为可迭代对象:Iterable。
可以使用isinstance()判断一个对象是否是Iterable对象:
19.python中的元组。
元组数据结构类似于list 但是元素不能修改类似于string 但是又可以进行拼接 截取操作。
20.为什么的大部分语言都是0-based索引。
首先明确索引脚标表示的是对首元素的偏移量。基于0-based的脚标表示 这个在汇编语言时代可以直接使用MOV指令比较方便。即下标可以直接等价成MOV值到偏移寄存器里,而基址寄存器里面保存的是数组头的地址,结合这两个就可以寻址取值。在python中 据python之父介绍 使用0-based的原因主要是python的半开区间切片语法与0-based完美契合。Fortan使用1-based。
21.python 字符串拼接
简介两种:
- 1 str1 + str2
- 2 ‘’.join([‘1’,’2’])
{.line-numbers}
1
2
3
4
5
6
7
8 str1 = "abc"
str2 = 'def'
print(str1 + str1)
# ""abcdef
print(''.join(['1','2']))
# '12'
print('a'.join(['1','2']))
#'1a2'
22.python 格式化输出
- 整数输出
- %o 八进制
- %d 十进制
- %x 十六进制
1 | print('%d'%20) |
- 浮点数输出
- %f 默认保留小数点后六位。默认进行了四舍五入
%.3f 保留三位小数点
%e 保留小数点后六位 以指数形式
- %.3e 保留三位小数 科学计数法
1 | print('%f'%20) |
- 字符串输出。
%s
{.line-number} 1
2
3
4
5
6
7
8
9
10print('%s'% 'hello world')
#hello world
print('%20s'% 'hello world') #右对齐20位
# hello world
print('%-20s'% 'hello world') #左对齐20位
#hello world
print('%10.2s' % 'hello world') # 右对齐,取2位
# he
print('%-10.2s' % 'hello world') # 左对齐,取2位
#heformat用法。相对基本格式化采用的%方法,format功能更为强大。
- 不带编号,即“{}”
- 带数字编号,可调换顺序,即“{1}”、“{2}”
- 带关键字,即“{a}”、“{tom}”
1 |
|