Algorithm

解法一

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Stack<TreeNode> pstack = new Stack<TreeNode>();//维持节点p对应的父节点
    Stack<TreeNode> qstack = new Stack<TreeNode>();//维持节点q对应的父节点
    boolean findp = false;//找到p节点的状态
    boolean findq = false;//找到q节点的状态
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        int r = pstack.size()- qstack.size();
        if (r>0) {
            while (r>0) {
                pstack.pop();
                r--;
            }
        }else if (r<0) {
            while (r<0) {
                qstack.pop();
                r++;
            }
        }
        while (!pstack.empty()) {
            TreeNode temp = pstack.pop();
            if (temp.val == qstack.pop().val) {
                return temp;
            }
        }
        return null;
    }
    public void dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null||(findp && findq)) return;
            
        if (!findp) pstack.add(root);
        if (!findq) qstack.add(root);
        
        if (root.val == p.val) findp =true; 
        if (root.val == q.val) findq =true;
            
        if (root.left != null) dfs(root.left, p, q);
        if (root.right != null) dfs(root.right, p, q);

        if (!findp) pstack.pop();
        if (!findq) qstack.pop();
    }
}

基于解法一的优化，细节参考官方描述

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        dfs2(root,  p, q);
        return ans;
    }
    public boolean dfs2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return false;
        boolean lson = dfs2(root.left, p, q);
        boolean rson = dfs2(root.right, p, q);
        if ((lson && rson)|| ((root.val == p.val || root.val == q.val)||(lson || rson))) {
            ans = root;
        }
            
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

Review

Data Structures - Asymptotic Analysis
算法的渐近分析是指定义其运行时性能的数学边界/框架。使用渐近分析，我们可以很好地推测出算法的最佳情况、平均情况和最坏情况。
渐近分析是输入边界的分析，也就是说，如果该算法没有输入，则可以得出在常数时间内完成工作的结论。除了“输入”，所有其他因素都被认为是常数。
渐近分析是指以数学计算单位计算任何运算的运行时间。例如，一个操作的运行时间计算为f(n)，另一个操作的运行时间计算为g(n2)。这意味着第一个操作的运行时间会随着n的增加而线性增加，第二个操作的运行时间会随着n的增加而呈指数增长。同样，如果n非常小，两种操作的运行时间几乎相同。
通常，算法所需的时间分为三种类型：

最佳情况-程序执行所需的最小时间。
平均情况-程序执行所需的平均时间。
最坏情况-程序执行所需的最大时间。

渐近符号

下面是常用的渐近符号来计算算法的运行时间复杂度。

Ο Notation
Ω Notation
θ Notation

Big Oh Notation, Ο
符号Ο(n)是正式的方式来表达一个算法的运行时间的上界。它衡量的是最坏情况下的时间复杂度，或者是一个算法可能需要完成的最长时间。

例如，对于函数f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

Omega Notation, Ω
Ω(n)的符号是正式的方式来表达一个算法的运行时间的下界。它度量了最佳情况的时间复杂度或一个算法可能需要完成的最佳时间量。

例如，对于函数f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Theta Notation, θ
θ(n)符号是正式的方式表达一个算法运行时间的上下界。它的表现形式如下：

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

常见的渐近符号

下面是一些常见渐近符号的列表-

Tips

鲁棒性
所谓“鲁棒性”，是指控制系统在一定（结构，大小）的参数摄动下，维持其它某些性能的特性。根据对性能的不同定义，可分为稳定鲁棒性和性能鲁棒性。

从软件系统角度来讲：

如果这样抽象定义软件系统的任务处理流程，它是一个接收输入，进行相应运算处理后，输出相应正确结果的过程。在这个过程中接收和运算处理会存在一定的“摄动”，如：在查询输入时大写字母和小写字母是同样的意思，希望系统能识别并兼容这类输入；在运算处理过程中，如果磁盘故障，IO过高，一些攻击时，系统能不崩溃，能自行进行有效恢复。
总结来讲，因为一些特殊原因，在偏离正常“运行轨道”时，系统自行恢复到正常运行轨道的能力。

从算法角度来讲：

以分类算法为例进行说明，某类实体在正常情况都表现很类似，通过我们的算法很容易区分出来，但在某些特殊情况下同一类的实体的个别会出现异常表现，这时算法能会区分出来，这就体现了算法的鲁棒性。在SVN等算法中针对鲁棒性会明确的数值度量。

从实际意义角度来讲：

针对系统稳定性而提出的研究方向，或一个度量指标。
通信网络的鲁棒性鲁棒性/抗变换性（英文：robustness）原是统计学中的一个专门术语，20世纪70年代初开始在控制理论的研究中流行起来，用以表征控制系统对特性或参数扰动的不敏感性。鉴于中文“鲁棒性”的词义不易被理解，“robustness”又被翻译成了语义更加易懂的“抗变换性”，“抗变换性”和“鲁棒性”在译文中经常互相通用。

在实际问题中，系统特性或参数的摄动常常是不可避免的。产生摄动的原因主要有两个方面，一个是由于量测的不精确使特性或参数的实际值会偏离它的设计值（标称值），另一个是系统运行过程中受环境因素的影响而引起特性或参数的缓慢漂移。因此，鲁棒性已成为控制理论中的一个重要的研究课题，也是一切类型的控制系统的设计中所必须考虑的一个基本问题。对鲁棒性的研究主要限于线性定常控制系统，所涉及的领域包括稳定性、无静差性、适应控制等。

沟通-引导
本周分享一个真实故事的感悟：
教儿子用竖算式加法：
儿子之前一直是用数手指头进行加法运算，今晚想教儿子用竖算式方法做两位数的加法题。
对话如下：
我：爸爸今晚教你一种新的方法算加法，怎么样？
儿子：好呀
我：在纸上写了几道竖算式加法题，开始给他讲解，个位和个位相加，十位和十位相加。。。。一两分钟后...
儿子：向我提了一堆问题，并表示听不懂，什么是个位，为什么要写成这样子（上下写的方式）。

随着我讲的越多，他越不爱听，带着哭腔打断我说话，用手捂着我嘴不让我讲了，不要学这种方式了。这时我很想发火，也在想怎么讲，他愿意学也能学会。

思考片刻后，我打算用提问的方法引起他的兴趣，所以做出如下改善：
我问：为什么数到数字9之后，10会变成2个数字组成呢？
儿子：突然之间好像来兴趣了，就反问我为什么？还说1000是4个数字组成，这又是为什么？（小孩天然的好奇心）
我：很认真的给他解释了一会，不过我能看出，他没听懂，但他没打断的讲话。这时我意识到当前讲这些可能超过他的认知了。再次改变策略，用奖励和死记操作步骤的方式：
我：爸爸给你演示一遍，你按爸爸的方式，做完这二道题，就奖励你看ipad(ipad上面有动画片)。
儿子：好，然后很认真的看我演示了一遍。
接下来由他自己去做其他两道题，第一道题目是34+7。他先算4+7等于11，直接把11全部写到竖算式的下面，然后算3加1等于4，最终算完结果是411，他自己也感觉不对，就问我，这时我告诉他哪里不对，并给他一些鼓励。接下来的一题，到是做对了，与他击掌庆祝。我想看他是否理解了进位思想，再给他出了一道题34+5（他愿意再做一题，可能是做对了一题，有成就感了），他做出来的结果是49，我就问他4是怎么算出来的，给他解释了这道题不用进位。做完后很开心的去看ipad，第二天还很开心跟他姥姥讲学会了竖算式加法。

第二天晚上：
他竟然主动问我昨天提到的10为什么由2个数字组成（看来小孩的好奇心很重）。晚上我们继续练习了竖算式，这次没有排斥，按我教的操作方式连续算出了3道题，每算一道题进行一次give me five 庆祝。

感想：

抽象的认知需要自己去感悟，如：小到数字之间的规律，大到世界万物的运行规律。我认为认知的建立是在其他认知的基础之上，我没办法把我高维的抽象认知直接讲给他。人类都是从模仿之中获取知识(认知)，所以我直接教他操作方法，让他按方法多练习，我觉得一段时间后，他自然能明白这套方法里面的奥秘。
沟通需要共同参与，不能只是我讲，尤其是在我讲的东西，对方听不懂的时候，对听讲者来说是一种折磨，需要立即停止讲述，采用引导提问的方式让其参与进来，共同去解决一个隐形问题的目标来展开。
小孩其实有很强的好奇心，也需要鼓励，同时模仿能力也不差。

ARTS第5周