Skip to content

Latest commit

 

History

History
298 lines (212 loc) · 13.7 KB

2019-04-15.md

File metadata and controls

298 lines (212 loc) · 13.7 KB
Raw

一. Algorithm

做了算法训练营中的一道作业题目 236. Lowest Common Ancestor of a Binary Tree ，求二叉树中两个节点的最近的一个共同祖先节点。

做题过程遇到了一些问题，最终是参考 discuss 中的答案才最终捋清楚，代码如下：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        //  1. 递归终止条件：到达叶节点或者目标节点
        if(root == null || root == p || root == q) {
            return root;
        }  


        // 2. 递归公式：当前节点是否为 p、q 两个节点的祖先节点
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 3. 基于递归结果求解
        if (left == null) {
            return right;
        }

        if (right == null) {
            return left;
        }

        return root;
    }
}

题目要求是求 p、q 节点的最近的祖先节点，这里有两种情况

    1. p、q 有共同的祖先节点，那么返回结果就是最低的祖先节点

    1. 一个节点为另一个节点的祖先节点，那么返回的就是 p、q 中的那个祖先节点

对于树相关的题目，一个很重要的做题原则就是：

只关注一个节点

回到 第 236 题，如果确定一个节点是否为 p、q 两个节点的祖先节点，判断依据就是

  • 其左右子树中包含两个节点

那么我们要做的就是查看其左子树、右子树是否包含 p、q 两个节点。同样对于左右子节点，依然是采用相同的逻辑判断，这里完全符合递归的求解方式：大问题拆分为逻辑相同的子问题。代码如下：

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

对于一个节点计算完成后，我们得到了其左右子树包含 p、q 节点的结果，此时再基于上面提到的两种情况进行结果返回

拥有共同祖先节点

该种其结果一定是左右子树都可能查找到对应的节点，因此只要某个节点的查找结果满足

left != null && right !=null

就说明该节点就是 p、q 的共同祖先节点。

一个节点为另一个节点的祖先节点

此时，计算的结果会如图所示：

x 为 y 的节点父节点， x 的父节点在计算时，left 为空，right 则返回了 x 节点自身。因此对于这种情况，当 left 或 right 有一个为 null 一个不为 null 时， 不为 null 的节点即为共同祖先节点。

采用递归的解法，最快的情况下每个节点都要遍历一遍，时间复杂度为 O(N)，空间上只有节点的空间占用，因此空间复杂度也为 O(N)。

二. Review

读了 Medium 上的一篇文章：The most important skill a programmer can learn 。

作者提到，作为一个程序员，我们需要学会的最重要的一项技能是「学会说不」。

The best code is no code at all, and the most effective programmer is the one who knows when not to code. 最好的代码就是没有代码，最卓有成效的程序员应该知晓什么时候不要去写代码。

作者提到，编程是解决问题的艺术，当我们需要通过编程来解决问题时，也应该意识到，新的代码也可能会增加系统的复杂性、引入潜在的 BUG，需要更全面的测试、debug 和维护，因此对写代码前应该认真想想，是否真的必须通过增加代码来解决问题。

关于如何确定不写代码，作者提到了两点：

  • 只关心最重要的核心功能。做项目时一个常见的问题就是在核心功能之外还想要很多其实不大么紧要的功能，并且因为这些功能反而耽误了核心功能的开发。优秀的开发者应该时刻明白什么才是最最重要的，做到要事第一，避免编写无关紧要的代码。
  • 尽可能的避免代码变得臃肿。当代码量持续增加时，应该权衡新增代码带来的收益和风险，避免因为代码过度臃肿导致了各种依赖问题，维护问题。

以上就是作者文章的简要总结。作者想表达的意思应该是谨慎的对待代码，时刻保持代码的简洁，保持其可维护性，避免随着代码量的增加引发各种 BUG 和提高运维难度。这是每个程序员在日常工作中都应该注意的事情，因为现实工作中，往往因为赶项目上线采取各种「凑合」的解决方式，长期来看这会极大的破坏项目的可维护性，优秀的程序员应该尽可能避免该种情况的发生。

三. Tips

分享一下利用 kubeadm 搭建 k8s 集群的过程

1. 环境准备

  • 三台可以互相 ping 通的机器

这里建议用国外的云厂商开三台服务器，这样可以省去很多网络上的麻烦。

  • 安装 Docker

2. 安装 kubeadm

我用的系统是 Ubuntu18.04，这里采用官网提供的安装方式即可：

apt-get update && apt-get install -y apt-transport-https curl
curl -s https://packages.cloud.google.com/apt/doc/apt-key.gpg | apt-key add -
cat <<EOF >/etc/apt/sources.list.d/kubernetes.list
deb https://apt.kubernetes.io/ kubernetes-xenial main
EOF
apt-get update
apt-get install -y kubelet kubeadm kubectl
apt-mark hold kubelet kubeadm kubectl

安装完成后就可以准备启动主节点了，编辑配置文件如下：

3. 启动主节点

编辑配置文件如下：

apiVersion: kubeadm.k8s.io/v1beta1  
kind: ClusterConfiguration # 指明资源类型
kubernetesVersion: "v1.14.0" # 指明 k8s 版本
# 如果使用的是阿里云等服务可能某些镜像是无法访问的，可以通过该配置手动修改镜像仓库的地址
# imageRepository: registry.cn-hangzhou.aliyuncs.com/imooc

然后采用下面命令启动主节点：

kubeadm init --config kubeadm.yaml

整个过程因为要下载镜像可能需要耗时几分钟，完成后出现如下提示：

Your Kubernetes control-plane has initialized successfully!

To start using your cluster, you need to run the following as a regular user:
  # 启动成功后需要手动进行的操作
  mkdir -p $HOME/.kube
  sudo cp -i /etc/kubernetes/admin.conf $HOME/.kube/config
  sudo chown $(id -u):$(id -g) $HOME/.kube/config

You should now deploy a pod network to the cluster.
Run "kubectl apply -f [podnetwork].yaml" with one of the options listed at:
  https://kubernetes.io/docs/concepts/cluster-administration/addons/

Then you can join any number of worker nodes by running the following on each as root:
# 添加工作节点的命令
kubeadm join 111.111.111.111:6443 --token 6dgktp.s21p4tucxc395i5u \
    --discovery-token-ca-cert-hash sha256:068b6c03cf59217b8343179237766a9367fc9a529e7266aa54cbee60bb0c51b6

将上面提到的三条命令手动执行，完成后就可以查看集群状态了：

$ kubectl get nodes
NAME           STATUS     ROLES    AGE   VERSION
my-server-01   NotReady   master   50s   v1.14.1

如果没有执行上面的三条命令将会报如下错误：

# root @ my-server-01 in ~ [17:04:22]
$ kubectl get nodes
The connection to the server localhost:8080 was refused - did you specify the right host or port?

执行成功后可以看到 master 节点已经启动了，但是其状态 status 还是 NotReady，这是因为我们没有配置网络插件的原因，查看其 pod 信息展示如下：

$ kubectl get pods --all-namespaces
NAMESPACE     NAME                                   READY   STATUS    RESTARTS   AGE
kube-system   coredns-fb8b8dccf-snk96                0/1     Pending   0          117s
kube-system   coredns-fb8b8dccf-x9x76                0/1     Pending   0          117s
kube-system   etcd-my-server-01                      1/1     Running   0          69s
kube-system   kube-apiserver-my-server-01            1/1     Running   0          51s
kube-system   kube-controller-manager-my-server-01   1/1     Running   0          73s
kube-system   kube-proxy-gvqz9                       1/1     Running   0          117s
kube-system   kube-scheduler-my-server-01            1/1     Running   0          62s

可以看到 coredns 两个 pod是 Pending 状态的，接下来安装网络插件。

安装 Calio 网络插件

该插件的安装非常简单，按照其官网指示操作即可：

# 下载配置
curl https://docs.projectcalico.org/v3.7/manifests/calico.yaml -O

# 安装插件
$ kubectl apply -f calico.yaml
configmap/calico-config created
customresourcedefinition.apiextensions.k8s.io/felixconfigurations.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/ipamblocks.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/blockaffinities.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/ipamhandles.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/ipamconfigs.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/bgppeers.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/bgpconfigurations.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/ippools.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/hostendpoints.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/clusterinformations.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/globalnetworkpolicies.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/globalnetworksets.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/networkpolicies.crd.projectcalico.org created
customresourcedefinition.apiextensions.k8s.io/networksets.crd.projectcalico.org created
clusterrole.rbac.authorization.k8s.io/calico-kube-controllers created
clusterrolebinding.rbac.authorization.k8s.io/calico-kube-controllers created
clusterrole.rbac.authorization.k8s.io/calico-node created
clusterrolebinding.rbac.authorization.k8s.io/calico-node created
daemonset.extensions/calico-node created
serviceaccount/calico-node created
deployment.extensions/calico-kube-controllers created
serviceaccount/calico-kube-controllers created

网络插件安装完成后就可以看到 master 节点可以正常工作了，

$ kubectl get pods --all-namespaces
NAMESPACE     NAME                                      READY   STATUS    RESTARTS   AGE
kube-system   calico-kube-controllers-9b4ff7697-t5btf   1/1     Running   0          68m
kube-system   calico-node-5lr9v                         1/1     Running   0          67m
kube-system   calico-node-847x4                         1/1     Running   0          68m
kube-system   calico-node-czn8q                         1/1     Running   0          67m
kube-system   coredns-fb8b8dccf-nnmtb                   1/1     Running   0          71m
kube-system   coredns-fb8b8dccf-vnj64                   1/1     Running   0          71m
kube-system   etcd-yingjie01                            1/1     Running   0          70m
kube-system   kube-apiserver-yingjie01                  1/1     Running   0          70m
kube-system   kube-controller-manager-yingjie01         1/1     Running   0          70m
kube-system   kube-proxy-j89pm                          1/1     Running   0          71m
kube-system   kube-proxy-spsvs                          1/1     Running   0          67m
kube-system   kube-proxy-xjxkk                          1/1     Running   0          67m
kube-system   kube-scheduler-yingjie01                  1/1     Running   0          70m
kube-system   kubernetes-dashboard-5bd4bfc87-mqbzd      1/1     Running   0          50m

# root @ yingjie01 in ~/k8s [9:08:18]
$ kubectl get nodes
NAME        STATUS   ROLES    AGE   VERSION
yingjie01   Ready    master   71m   v1.14.1

4. 启动工作节点

工作节点的启动是非常简单的，看上面我们启动成功主节点后打印出的信息，里面有一条 kubeadm join 命令，复制该命令到对应的机器上执行即可，当然前提是这台机器上已经安装了 kubeadm 了。

kubeadm join 111.111.111.111:6443 --token 6dgktp.s21p4tucxc395i5u \
    --discovery-token-ca-cert-hash sha256:068b6c03cf59217b8343179237766a9367fc9a529e7266aa54cbee60bb0c51b6

安装完成后，在主节点查看节点信息如下：

$ kubectl get nodes
NAME        STATUS   ROLES    AGE     VERSION
yingjie01   Ready    master   4h45m   v1.14.1
yingjie02   Ready    <none>   4h41m   v1.14.1
yingjie03   Ready    <none>   4h41m   v1.14.1

可以看到集群搭建已经可以了，整个过程基本没遇到什么问题，希望对大家有帮助。

四. Share

最近看的一篇文章，里面提到了一个人工智能西瓜书的 10 周的学习打卡群，群里成员都是搞 AI 方向的创业者、清北斯坦福等顶尖高校的学生，但坚持情况如下：

3月18日 第一天任务 364人完成打卡
3月19日 264人完成打卡
3月22日 184人完成打卡
3月25日 125人完成打卡
4月1日 84人完成打卡
4月6日 26人完成打卡

可见哪怕参与人员已经是非常优秀的人了，能坚持下来的人依旧寥寥无几，而坚持下来并且保质保量完成的可能 10 人都不到。坚持下来，就已经可以比大多数人优秀了，我们所面临的竞争远比我们想象的要小得多，你只要稍微坚持下其实可以超过大多数人。