每周 ARTS 第 10 期

2019-06-10 本文已影响0人落英坠露

1. Algorithm

226. 翻转二叉树（简单）

描述：

翻转一棵二叉树

示例：

思路：

递归法：翻转一个二叉树，就是把根节点的左子树翻转一下，同样的把右子树翻转一下，再交换左右子树就可以了。
迭代法：类似广度优先遍历的方式，使用队列存储尚未交换的节点，每次从队列取出一个结点，交互其左右子结点，直到队列为空。

class Solution {
    public TreeNode invertTreeRecursively(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTreeRecursively(root.left);
        invertTreeRecursively(root.right);
        return root;
    }

    public TreeNode invertTreeIteratively(TreeNode root) {
        if (root == null) {
            return null;
        }

        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (list.isEmpty()) {
            TreeNode current = list.poll();
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;

            if (current.left != null) {
                list.add(current.left);
            }
            if (current.right != null) {
                list.add(current.right);
            }
        }
        return root;
    }
}

分析：

递归和迭代法一样：

时间复杂度：O(n)
空间复杂度：O(n)

326. 3 的幂（简单）

描述：

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

示例：

输入: 27
输出: true

思路：

解法一：累乘法
解法二：3的幂次质因子只有3，而整数范围内的3的幂次最大是1162261467

解法：

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        long m = 1;
        while (m < n) {
            m *= 3;
            if (m == n) {
                return true;
            }
        }
        return false;
    }

    public boolean isPowerOfThree2(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

分析：

解法一：

时间复杂度：O(n)
空间复杂度：O(1)

解法二：

时间复杂度：O(1)
空间复杂度：O(1)

2. Review

Goodbye, Object Oriented Programming 再见，面向对象编程

作者是个有着多年经验的老程序员，他毫不留情地指出了面向对象编程的问题，分别从封装、继承和多态这三大支柱来阐述。

继承最大的好处就是复用。但是出现了「猴子香蕉丛林」问题，我只想要一根香蕉，得到的却是香蕉丛林。钻石问题，继承关系的结构图就像钻石一样，这样容易造成调用混乱。还有基类问题，子类不知道基类的实现，从而引发操作错误。解决办法就是用组合替代继承，原意是包含和委托。
封装使得对象保证内部的变量受保护，然而它却带来了一下问题。引用问题，给构造方法传参时，对象存在多个应用，这样对象就不安全了。解决办法是对象深拷贝，但不是所有对象都支持克隆。
面向对象编程不需要多态，它完全可以基于接口来实现。

最后作者告别了面向对象编程，转向函数式编程。

虽然作者举出这么多 OOP 的问题，但是面向对象的思想依然非常流行。软件开发没有银弹，能够实现功能、解决问题的思想都是值得采用的。

3. Tip

日常的琐事都用软件记录，比如有道云笔记、滴答清单、LastPass。大脑是用来思考的，不是用来记东西的，它充当的更多是 CPU 的角色，而不是硬盘。所以，让大脑轻松一下，用工具记录吧。

4. Share

关于线程和I/O模型的极简知识主要讲述了线程和 I/O 模型的演化历史，问题驱动模型的演化，每种模型都有各自的使用场景。