ARTS 第二周分享

每周完成一个ARTS：

Algorithm：每周至少做一个 leetcode 的算法题

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

Share：分享一篇有观点和思考的技术文章

Algorithm

本周记录如下：

118. Pascal’s Triangle（Easy）

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

题目大致意思：给定一个负整数，生成一个帕斯卡三角形，如Example所示。

思路：这里的动图非常形象，我们可以从动图中看出，每个数组的首尾元素是 1，且数组长度与深度一致，紧接着我们将动图转换成阶梯型，代入二维数组的概念来看，如下所示：

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]

就可以很容易看出除首尾元素为 1 外，其余元素等于上一个数组对应下标的值加上上一个数组对应下标-1的值，即curr[n] = prev[n] + prev[n-1]。

 class Solution {
    public List<List<Integer>> getPascalsTriangle(int numRows) {
        List<List<Integer>> pascalsTriangle = new ArrayList<>();
        if (numRows == 0) {
            return pascalsTriangle;
        }
        // 首个数组一定是 1
        ArrayList<Integer> firstArray = new ArrayList<>();
        firstArray.add(1);
        pascalsTriangle.add(firstArray);
        for (int i = 1; i < numRows; i++) {
            List<Integer> temp = new ArrayList<>();
            // 上一个数组
            List<Integer> preList = pascalsTriangle.get(i - 1);
            // 每个数组头部元素总是 1
            temp.add(1);
            for (int j = 1; j < i; j++) {
                temp.add(preList.get(j) + preList.get(j - 1));
            }
            // 每个数组尾部元素总是 1
            temp.add(1);
            pascalsTriangle.add(temp);
        }
        return pascalsTriangle;
    }
}

结果：
Runtime: 0 ms, faster than 100.00% of Java online submissions for Pascal’s Triangle.
Memory Usage: 32.7 MB, less than 100.00% of Java online submissions for Pascal’s Triangle.

119. Pascal’s Triangle II

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.

Example:
Input: 3
Output: [1,3,3,1]
Follow up:

Could you optimize your algorithm to use only O(k) extra space?

@DevDocsleetcode.com/problems/pascals-triangle-ii

题目大致意思：跟题118差不多，要求只使用O（k）额外空间，如Example所示。

思路：跟题118差不多一致，可以用递归实现。

class Solution {
    public List<Integer> getRow(int rowIndex) {
            // 终止条件
            if (rowIndex == 0) {
                List<Integer> result = new ArrayList<>(rowIndex + 1);
                result.add(1);
                return result;
            }
            // 获取上一个数组，利用递归获取
            List<Integer> prevList = getRow(rowIndex - 1);
            // 从后往前遍历
            for (int i = rowIndex - 1; i > 0; i--) {
                // 即 curr[i] = prev[i] + prev[i - 1]
                prevList.set(i, prevList.get(i) + prevList.get(i - 1));
            }
            // 加入尾部元素 1
            prevList.add(1);
            return prevList;
    }
}

结果：
Runtime: 1 ms, faster than 84.50% of Java online submissions for Pascal’s Triangle II.
Memory Usage: 32.3 MB, less than 100.00% of Java online submissions for Pascal’s Triangle II.

从结果上来看，运行时间上，还可以进行优化，最后脑细胞不够，想不出如何优化，查看了下Runtime：0ms答案，答案如下：

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        long nk = 1;
        for(int i = 0; i <= rowIndex; i++){
            res.add((int)nk);
            nk = nk * (rowIndex - i) / (i + 1);
        }
        return res;
    }
}

Review

本周阅读的是专栏里推荐的两篇文章：《Teach Yourself Programming in Ten Years》（中英对照）和《What are some of the most basic things every programmer should know?》

作者在这篇《Teach Yourself Programming in Ten Years》（十年学会编程）文章中提出了当前人们急于求成这种不好的风气，批判了诸如24小时或天学会XXX的书籍的无用，并举了诸多著名的例子来证明“十年”学会编程的观点，比如“10000小时理论”等。

作者还列出自己编程成功的秘笈，以下列出我印象比较深的几点：

对编程感兴趣，从编程中获取乐趣，这样才能坚持10000小时或10年。
动手编程，边学边做，实践出真知。
和其他的程序猿交流，能比培训或看书收获更多。
在大学期间或加上研究生期间，深入计算机领域学习；如果不喜欢读书，那直接通过工作获取经验也可以，但不能死读书，计算机科学并不能让你成为编程专家，正如学习颜料和画笔不能让你成为一个画家一样。
与其他程序猿一起参与一些项目，在一些项目中成为最好的程序猿，尽自己最大的能力去带领团队，用自己的视野去启发别人；在一些项目中当最差的程序猿，当你是最差的时候，学习其他大牛。
接收他人项目时，理解他人写的代码，修复他人的BUG；思考设计自己的软件，让其容易被他人维护。
至少学会6种编程语言，一种支持抽象类的语言（例如 C++ 或 Java ）,一种支持函数的语言（例如 Lisp，ML 或 Haskell），一种支持语义抽象的语言（例如 Lisp ）,一种支持声明性规范的语言（例如 Prolog 或 C++ templates ），一种强调并行性的语言（例如 Go 或 Clojure ）。

小结

学习编程是一件漫长且要持续投入的事情，不存在任何的捷径，想要一蹴而就无疑是痴人说梦，是需要一步一个脚印，脚踏实地的努力才行，就如上一周分享的文章所说，跨越编程拐点之前，将可能是一段令人沮丧的经历，所以我们要进行有针对性的日复一日年复一年的训练，并且要有合理的反馈渠道，根据反馈做出相对的改进，需要多一点正向反馈，这样才能坚持下去，跨越一个接一个的拐点，最后达成“十年学习编程”的成就。

《What are some of the most basic things every programmer should know?》，这篇文章不长，感兴趣的小伙伴们可以自行查看。

Tip

介绍一个开发利器 Lombok，以注解的形式，简化消除getter、setter、equals、hashcode、toString等代码。

官方地址：https://projectlombok.org/
github地址：https://github.com/rzwitserloot/lombok

具体使用方法，可以参看JAVA奇技淫巧简化代码之lombok这篇博客。

上面那篇博客只介绍了 Eclipse，如果是InteliJ IDEA 的用户，需在安装一个Lombok插件，如下图所示：
lombok

这里介绍一下 @Builder 这个注解，可以很容易生成建造者模式的代码，效果如下：

@Builder
public class Apple {

    private String color;

    private Double wight;


    public static void main(String[] args) {
        Apple apple = Apple.builder().color("Red").wight(100.0).build();
    }
}

可以通过链式设置类的属性值，尤其是当类属性很多时，这样非常方便，且代码看起来很优雅。通过注解生成代码如下：

public class Apple {
    private String color;
    private Double wight;

    Apple(String color, Double wight) {
        this.color = color;
        this.wight = wight;
    }

    public static Apple.AppleBuilder builder() {
        return new Apple.AppleBuilder();
    }

    public static class AppleBuilder {
        private String color;
        private Double wight;

        AppleBuilder() {
        }

        public Apple.AppleBuilder color(String color) {
            this.color = color;
            return this;
        }

        public Apple.AppleBuilder wight(Double wight) {
            this.wight = wight;
            return this;
        }

        public Apple build() {
            return new Apple(this.color, this.wight);
        }

        public String toString() {
            String var10000 = this.color;
            return this.wight;
        }
    }
}

更多详情请查看https://projectlombok.org/features/Builder

使用 Java 8 的 Optional 类进行优雅的判空