这篇文章重点记录二叉树的一些不入流的题目，但是很有意思。
题目的大意是给你一个二叉树，然后输出它的遍历字符串，就比如；
Input: Binary tree: [1,2,3,4]
1
/ \
2 3
/
4
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".
Input: Binary tree: [1,2,3,null,4]
1
/ \
2 3
\
4
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example,
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
这个题目有意思在，有一点 tip 在里面，也就是需要在你写程序之前进行一些观察。看着那些括号和数字是一些杂乱无章的符号，实际有固定套路的。
通过第二个例子，假设根节点有右子节点，而没有左子节点的话，需要在根节点后面添加一个”()”,当然这个”()”你也可以看成一个空节点。此时，一般还是看不出的， 这时候，你把output的首位和末尾分别用”()”进行包裹起来，则这个结果就有规律了。
class Solution {
public:
string tree2str(TreeNode* t) {
string res = "";
if(!t) return res;
tree2str_helper(t, res);
return string(res.begin()+1, res.end()-1);
}
private:
void tree2str_helper(TreeNode* t, string& res){
if (!t) return;
res += "(";
if (t) res += to_string(t->val);
if(!t->left && t->right) res += "()";
tree2str_helper(t->left, res);
tree2str_helper(t->right, res);
res +=")"; // 这个语句为什么放在这里，把我搞蒙了
}
};
主要参考这篇文章做的笔记， here
简单的说，容器是独立运行的一个或一组应用，以及它们的运行态环境。对应的，虚拟机可以理解为模拟运行的一整套操作系统（提供了运行态环境和其他系统环境）和跑在上面的应用。
启动容器有两种方式，一种是基于镜像新建一个容器并启动，另外一个是将在终止状态（stopped）的容器重新启动。 因为 Docker 的容器实在太轻量级了，很多时候用户都是随时删除和新创建容器。
cmd: docker run
只运行一个程序:
vimer@host:~$ docker run ubuntu /bin/echo “Hello, vimer” Hello, vimer
当利用 docker run 来创建容器时，Docker 在后台运行的标准操作包括：
检查本地是否存在指定的镜像，不存在就从公有仓库下载 利用镜像创建并启动一个容器 分配一个文件系统，并在只读的镜像层外面挂载一层可读写层 从宿主主机配置的网桥接口中桥接一个虚拟接口到容器中去 从地址池配置一个 ip 地址给容器 执行用户指定的应用程序 执行完毕后容器被终止
通过 -d参数来指定docker后天运行。
vimer@host:~/src/trustedStorage$ docker run ubuntu /bin/sh -c "while true; do echo hello,world; sleep 1; done"
hello,world
hello,world
hello,world
hello,world
...
使用容器无限执行，在伪终端输出以上内容。
vimer@host:~/src/trustedStorage$ docker run -d ubuntu /bin/sh -c "while true; do echo hello,world; sleep 1; done"
544a5eb8567694e882474064ec081869f8df3aefce9e3ad3619755a72bb04899
加了-d参数，所以docker把容器放在后台运行了。使用 -d 参数启动后会返回一个唯一的 id，也可以通过 docker container ls 命令来查看容器信息。
vimer@host:~/src/trustedStorage$ docker container ls
CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES
544a5eb85676 ubuntu "/bin/sh -c 'while t…" About a minute ago Up About a minute heuristic_euclid
vimer@host:~/src/trustedStorage$ docker container logs 544a5
hello,world
hello,world
...
可以查看正在运行的container跑的是什么内容（假设有打印输出的话）。
vimer@host:~/src/trustedStorage$ docker container ls
CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES
544a5eb85676 ubuntu "/bin/sh -c 'while t…" 7 minutes ago Up 7 minutes heuristic_euclid
vimer@host:~/src/trustedStorage$ docker container stop 544a5
544a5
vimer@host:~/src/trustedStorage$ docker container ls -a
//所有的image都在这里面， 包括已经终止的container
可以将一个终止的container重新激活。restart是首先关闭docker，然后再打开docker。
在使用 -d 参数时，容器启动后会进入后台。 某些时候需要进入容器进行操作，包括使用 docker attach 命令或 docker exec 命令，推荐大家使用 docker exec 命令，原因会在下面说明。
vimer@host:~/src/trustedStorage$ docker container start 544a5
544a5
vimer@host:~/src/trustedStorage$ docker attach 544a5
hello,world
hello,world
^Zhello,world
hello,world
hello,world
^Cvimer@host:~/src/trustedStorage$
也就是这样，使用attach的方式，可以在伪终端下使用 Ctrl + C的方式关掉container。
docker exec 后边可以跟多个参数，这里主要说明 -i -t 参数。
vimer@host:~/src/trustedStorage$ docker run -dit ubuntu
05e1d23b8876d24fae0a324681652fa54145e2baf17edc994b12d91da7f8b43d
-i 只是交互，但是输出呢，是那种原来一行一行的。 -t 是模拟出来一个终端。
vimer@host:~/src/trustedStorage$ docker exec -i 05e1d bash
ls
bin
boot
dev
etc
home
lib
lib32
lib64
libx32
media
mnt
opt
proc
root
run
sbin
srv
sys
tmp
usr
var
exit
这里你就可以放心使用exit退出容器，但是原容器还是存在的。 加上 -t 的参数后:
root@05e1d23b8876:/# ls
bin dev home lib32 libx32 mnt proc run srv tmp var
boot etc lib lib64 media opt root sbin sys usr
我们首先将上面的container stop。然后使用export命令导出:
vimer@host:~/src/trustedStorage$ docker export 05e1d23b8876 > test_ubuntu.tar
vimer@host:~/src/trustedStorage$ ls
test_ubuntu.tar
vimer@host:~/src/trustedStorage$ du test_ubuntu.tar -h
72M test_ubuntu.tar
vimer@host:~$ cat test_ubuntu.tar | docker import - test/ubuntu:v1.0
sha256:02b96a5671af165755c27b9690edbd4836338425a0147ecd8f986572cc632386
这个时候，你使用container ls是看不到该container的，首先得激活才有可能看到，类似实例化吧。
这块还有一点问题，后面再补充吧。
import可以直接在URL上导入过来，而且在这个过程中可以继续打tags info。
docker container rm ID
该命令必须删除终止状态的容器。如果是运行中的，则添加-f参数。
docker container prune 则会清除所有的已终止的container，慎用。
vimer@host:~$ docker container prune
WARNING! This will remove all stopped containers.
Are you sure you want to continue? [y/N] y
Deleted Containers:
d31e1b77c7798c12d63742d7ec5210dd625ea89754d91e1022b6ef3f368eaf3b
d8f8aa5613744b77960d5459ffbd087c329b17506bca45b7cd6927d0acb1495d
11ba0ac4d76afe40da5b077a53c725c536b6d0687eaa2404730591df9a1f1015
e5530c2e24488944ffdb89a341c8fd649d8b0df55c1ffe1ec8cdd62318908086
f3548a71e9f896897b03dea2bc55ab3075015db46c0735e14a6997f2ead773ec
f4439eba7ee40eafa711019eb00d2a8c119bc17047a9771c0fb74a41fdb2ac17
013060b7e65dacffa181390c7977f3caa1e98838baef1b74e937f6b314e0509d
Total reclaimed space: 4.504MB
通过最下面的提示，我们可以发现， container占用的资源的真的很少的，至少在占用物理空间这个层面来说。
docker diff container_name
在大师的帮助下，初步有一个对docker的认识，
镜像构建时，会一层层构建，前一层是后一层的基础。每一层构建完就不会再发生改变，后一层上的任何改变只发生在自己这一层。比如，删除前一层文件的操作，实际不是真的删除前一层的文件，而是仅在当前层标记为该文件已删除。在最终容器运行的时候，虽然不会看到这个文件，但是实际上该文件会一直跟随镜像。因此，在构建镜像的时候，需要额外小心，每一层尽量只包含该层需要添加的东西，任何额外的东西应该在该层构建结束前清理掉。
镜像（Image）和容器（Container）的关系，就像是面向对象程序设计中的 类 和 实例 一样，镜像是静态的定义，容器是镜像运行时的实体。容器可以被创建、启动、停止、删除、暂停等。 容器的实质是进程，但与直接在宿主执行的进程不同，容器进程运行于属于自己的独立的 命名空间。因此容器可以拥有自己的 root 文件系统、自己的网络配置、自己的进程空间，甚至自己的用户 ID 空间。容器内的进程是运行在一个隔离的环境里，使用起来，就好像是在一个独立于宿主的系统下操作一样。这种特性使得容器封装的应用比直接在宿主运行更加安全。也因为这种隔离的特性，很多人初学 Docker 时常常会混淆容器和虚拟机。 前面讲过镜像使用的是分层存储，容器也是如此。每一个容器运行时，是以镜像为基础层，在其上创建一个当前容器的存储层，我们可以称这个为容器运行时读写而准备的存储层为 容器存储层。 容器存储层的生存周期和容器一样，容器消亡时，容器存储层也随之消亡。因此，任何保存于容器存储层的信息都会随容器删除而丢失。 按照 Docker 最佳实践的要求，容器不应该向其存储层内写入任何数据，容器存储层要保持无状态化。所有的文件写入操作，都应该使用 数据卷（Volume）、或者 绑定宿主目录，在这些位置的读写会跳过容器存储层，直接对宿主（或网络存储）发生读写，其性能和稳定性更高。 数据卷的生存周期独立于容器，容器消亡，数据卷不会消亡。因此，使用数据卷后，容器删除或者重新运行之后，数据却不会丢失。
以上概念太重要了， 摘抄自下面的文章:
https://yeasy.gitbook.io/docker_practice/basic_concept/image
docker pull [选项] [Docker Registry 地址[:端口号]/]仓库名[:标签]
一般Docker Registry 地址不指定，默认为官方的Docker Hub，标签不指定，默认为latest
例如：docker pull ubuntu:16.04
可以提前使用docker docker search ubuntu命令查看Docker Hub上的所有可利用的镜像。
使用该命令查看下载的镜像
查看指定镜像
查看镜像id
vimer@host:~$ docker image ls ubuntu -q
d70eaf7277ea
docker image rm 镜像1 镜像2 …
通常可用镜像id（前3位就行），镜像名，摘要删除
批量删除
docker image rm $(docker image ls -q ubuntu)
docker run -it –rm ubuntu bash
-it: -i 交互式操作 -t 终端
–rm: 容器退出时做清理工作
bash: 交互式shell
我们以这个镜像启动并运行一个容器，执行如下命令可以启动ubuntu里面的bash并进行交互操作. 具体操作就是:
vimer@host:~$ docker pull ubuntu
Using default tag: latest
latest: Pulling from library/ubuntu
6a5697faee43: Pull complete
ba13d3bc422b: Pull complete
a254829d9e55: Pull complete
Digest: sha256:fff16eea1a8ae92867721d90c59a75652ea66d29c05294e6e2f898704bdb8cf1
Status: Downloaded newer image for ubuntu:latest
docker.io/library/ubuntu:latest
vimer@host:~$ docker image ls
REPOSITORY TAG IMAGE ID CREATED SIZE
ubuntu latest d70eaf7277ea 3 weeks ago 72.9MB
tinylab/linux-lab next d9b4a01fd5eb 3 months ago 3.55GB
vimer@host:~$ docker run -it --rm ubuntu bash // rm 清理容器退出时的资源
root@dc09804ce242:/# ls
bin dev home lib32 libx32 mnt proc run srv tmp var
boot etc lib lib64 media opt root sbin sys usr
# 注意这里：
root@dc09804ce242:/# uname -a
Linux dc09804ce242 5.3.0-42-generic #34~18.04.1-Ubuntu SMP Fri Feb 28 13:42:26 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
root@dc09804ce242:/# exit
exit
vimer@host:~$ uname -a
Linux host 5.3.0-42-generic #34~18.04.1-Ubuntu SMP Fri Feb 28 13:42:26 UTC 2020 x86_64 x86_64 x86_64 GNU/L
看到没有，docker（容器里的Ubuntu其实就是用的）使用的kernel其实就是host的kernel，现在就有个疑问，docker的 这个交互是怎么做到的，好像用到了namespace和cgroup这两个特性。
docker commit最好用来保存现场，而不是制作镜像，定制镜像应该使用 Dockerfile 来完成。 基本的作用就是: 在一个容器中新改动了某个特性，并以此为镜像，以方便下次使用。这个命令就是干这个的，。
注意，我们还是 慎用 这个命令，看这里的。 https://yeasy.gitbook.io/docker_practice/image/commit
https://yeasy.gitbook.io/docker_practice/image/build 大神写的非常完整，忍不住赞，这也是我之前没用docker考虑到的问题，这篇文章里基本上都有涉及。
总结几点就是：在构建docker镜像时尽量压缩层数，一般来说一个RUN指令完成一个事情，还有一个问题是， 要把不需要的东西不要加进存储层。
在 Shell 中，连续两行是同一个进程执行环境，因此前一个命令修改的内存状态，会直接影响后一个命令；而在 Dockerfile 中，这两行 RUN 命令的执行环境根本不同，是两个完全不同的容器。这就是对 Dockerfile 构建分层存储的概念不了解所导致的错误。
https://zhuanlan.zhihu.com/p/41123740
这篇文章其实就是一篇杂记，讲开源代码中的有意思wiki记录下来。
该命令是判断shell中的各种关键字的类型， 现在可以记住一个用法， type -t.
vimer@host:~$ type -t ls
alias
vimer@host:~$ type -t date
file
vimer@host:~$ type -t if
keyword
使用if test 代替”[“或者“[[”。
if test "$E1" = 0; then
fi
if test "0$FF" -lt 0; then
...
fi
这个test可以单独使用：
test $name = vimer
判断的结果会存放在”$?”中。 记住，0代表成功1代表失败。
if [ -z "${VAR}" ]; # another way:
if [ ! -z "$VAR" ];
不过需要注意的是，”[“和”[[“的用法在某些shell中是无法使用的，所以就会导致这样的一种代码:
if [ X$1 = X ]; then
echo "the first argu is empty"
else
echo "the first argu is $1"
fi
什么意思呢？ 我们想一想，这样的，如果参数1为空的话， 是不是两个”X”就是相等的，这个技巧就是利用了这个原理。在android中，经常使用的一种的代码是：
if [ "x$1" = "x--host" ]; then
target_mode="no"
DEX_LOCATION=$tmp_dir
run_args="${run_args} --host"
shift
这里，注意这个”x”的巧妙用法，就是这样的有趣，也就是说，如果，你想一个个解析参数列表，x后面要补全我们的参数形式。
上面的这个参数形式就是./exe --host.
那么，很明显的是， 关键字shift就是移动参数列表。
while true; do
if [ "x$1" = "x--host" ]; then
echo "something"
shift
elif [ "x$1" = "x--quit" ]; then
echo "quit"
shift
elif expr "x$1" : "x--" >/dev/null 2>&1; then
echo "unknown $0 option: $1" 1>&2
usage="yes"
break
else
break
fi
done
这个代码重要的一部分是unknown选项的处理，需要后面吸收一下。
git reset的作用对象就是 .git/refs/head/master, 类似一个游标，可以改变（往前或者往后），
4bb86dd506 (HEAD -> dongchuan_11-11-xiawu) Support compilation
f632f6757b (origin/d_art, m/d_art, vimer_dev) Merge
afd74582ac Merge "READ_BARRIER_MARK_REG" into d_art
上面的log我做了一些处理，可以有差别的看一下。
git reset 有两种用法:
git reset --flags paths_file
git reset [--soft | --hard]
先来介绍第二种用法。
vimer@host:~/src/aosp_art/art$ git reset --hard HEAD^
HEAD 现在位于 f632f6757b Merge "Integration testing of Arithmetic/Condition IR." into d_art
vimer@host:~/src/aosp_art/art$ git log --oneline
f632f6757b (HEAD -> dongchuan_11-11-xiawu, origin/d_art, m/d_art, vimer_dev) Merge "Integration ...." into d_art
afd74582ac Merge "READ_BARRIER_MARK_REG" into d_art
这里开始涉及以前没有注意到的知识了， 比如’HEAD^’. HEAD^代表了HEAD的父提交，在上面的log日志找中， 我们很容易的知道
4bb86dd506是HEAD，但是呢， 该HEAD是由下面的git log诞生出来的: f632f6757b. 那么， HEAD^也就是寻找当前HEAD的父提交。
这个操作的作用是（慎用），直接把版本库、暂存区和工作区的原HEAD指向的commit清除了，假设如果你的commit没有upload到服务器上， 那么，你的原HEAD在本地是找不到了。下面就是使用上述命令后引用里面的值。
cat .git/refs/heads/dongchuan_11-11-xiawu
f632f6757b12a
git reset --soft 只会把引用的HEAD给替换成原来的父id， 不会影响工作区和暂存区的内容， 另外一个意思就是这个操作只会把
版本库的commit重置到HEAD的前一个（HEAD^）。结果如下：
vimer@host:~/src/aosp_art/art$ git status
位于分支 dongchuan_11-11-xiawu
要提交的变更：
（使用 "git reset HEAD <文件>..." 以取消暂存）
新文件： Main.java
有时候经常使用git diff去展示目前的工作区与版本库之间的差异(肯定不对)， 其实就差了一个HEAD, 加上HEAD标签就是告诉git， 工作区的文件与谁
做对比:
vimer@host:~/src/aosp_art/art$ git diff HEAD
diff --git a/Main.java b/Main.java
new file mode 100644
index 0000000000..7705266642
--- /dev/null
+++ b/Main.java
@@ -0,0 +1,79 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Proje
这个命令仅是把工作区和暂存区之间的内容做对比。
后面的paths就是文件， 这个命令直接将暂存区的内容回退回去。比如上面的提示就只这个意思，
vimer@host:~/src/aosp_art/art$ git reset Main.java
vimer@host:~/src/aosp_art/art$ git status
位于分支 dongchuan_11-11-xiawu
未跟踪的文件:
（使用 "git add <文件>..." 以包含要提交的内容）
这个命令是拯救git误失误的一个利器，之前也听说过，问题还是出现在HEAD或者分支上的理解上。
也就是使用这个命令时， 比如，你前面使用了git reset --hard命令，接下来使用这个命令一定
要将二者保持在同一分支上。比如， 文章开始我就使用了git reset --hard命令演示。
也就是我的HEAD原本是 4bb86dd506。
vimer@host:~/src/aosp_art/art$ git reflog show dongchuan_11-11-xiawu | head -5
f632f6757b dongchuan_11-11-xiawu@{0}: reset: moving to HEAD^
3459ab0be8 dongchuan_11-11-xiawu@{1}: commit: add java test
f632f6757b dongchuan_11-11-xiawu@{2}: reset: moving to HEAD^
4bb86dd506 dongchuan_11-11-xiawu@{3}: reset: moving to dongchuan_11-11-xiawu@{1}
f632f6757b dongchuan_11-11-xiawu@{4}: reset: moving to HEAD^
4bb86dd506在git reflog的展示中位于第4个（从上到下）。我之前的操作是使用checkout, 这个操作的逻辑是产生新的
分支，然后如何如何怎么怎么样。现在可以直接使用git reset --hard命令。
vimer@host:~/src/aosp_art/art$ git reflog show dongchuan_11-11-xiawu | head -5
f632f6757b dongchuan_11-11-xiawu@{0}: reset: moving to HEAD^
3459ab0be8 dongchuan_11-11-xiawu@{1}: commit: add java test
f632f6757b dongchuan_11-11-xiawu@{2}: reset: moving to HEAD^
4bb86dd506 dongchuan_11-11-xiawu@{3}: reset: moving to dongchuan_11-11-xiawu@{1}
f632f6757b dongchuan_11-11-xiawu@{4}: reset: moving to HEAD^
vimer@host:~/src/aosp_art/art$ git reset --hard dongchuan_11-11-xiawu@{5}
HEAD 现在位于 4bb86dd506 Support compilation of a method if all of its IRs can be compiled.
注意branch名字后的@{n},这个n需要数清 id 从上往下 数位于第几位然后再加1。接着再看一下这个命令:
vimer@host:~/src/aosp_art/art$ git reflog show dongchuan_11-11-xiawu | head -6
4bb86dd506 dongchuan_11-11-xiawu@{0}: reset: moving to dongchuan_11-11-xiawu@{5}
f632f6757b dongchuan_11-11-xiawu@{1}: reset: moving to HEAD^
3459ab0be8 dongchuan_11-11-xiawu@{2}: commit: add java test
f632f6757b dongchuan_11-11-xiawu@{3}: reset: moving to HEAD^
4bb86dd506 dongchuan_11-11-xiawu@{4}: reset: moving to dongchuan_11-11-xiawu@{1}
f632f6757b dongchuan_11-11-xiawu@{5}: reset: moving to HEAD^
看，上面的 git reset命令也这么记录进去了。
这个需求应该很容易的使用python实现，但是如果什么东西都用python去完成， 未免大材小用了(其实是真菜)
# cat IR_lists.txt
HAbove
HAboveOrEqual
HLessThan
HLessThanOrEqual
现在的需求是， 在每一条IR的前面添加HInstruction::, 最后形成比如HInstruction::HAbove的形式。
由于这个IR_lists.txt文件是不断变化的， 所以直接写死不太灵活。
现在先用这个命令， 之前用的都忘记了。
awk '{print "HInstruction::"$0}' IR_lists.txt
HInstruction::HAbove
HInstruction::HAboveOrEqual
HInstruction::HLessThan
HInstruction::HLessThanOrEqual
sed的分隔符有很多种， 大家只要统一风格就行。
sed 's#^#HInstruction::#' IR_lists.txt
# or
sed 's/^/HInstruction::/' IR_lists.txt
HInstruction::HAbove
HInstruction::HAboveOrEqual
HInstruction::HLessThan
HInstruction::HLessThanOrEqual