ARTS打卡：第三周

发表于 | 分类于 | 本文总阅读量 次

ARTS打卡：第三周

每周完成一个ARTS：

  1. Algorithm：每周至少做一个 leetcode 的算法题
  2. Review：阅读并点评至少一篇英文技术文章
  3. Tip：学习至少一个技术技巧
  4. Share：分享一篇有观点和思考的技术文章

Algorithm

本周记录如下：

206. Reverse Linked List（Easy）

Reverse a singly linked list.

Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

题目：反转单链表，示例如上所示。

思路1： 首先让单链表的头结点的前驱节点指向NULL，然后遍历链表节点，改变当前节点的后继节点为前驱节点，直至循环结束，返回尾结点。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode reverseList(ListNode head) {
    // 用于记录上一个节点（一开始为null，是为了让单链表的头结点的前驱节点指向NULL）
    ListNode prev = null;
    // 当前节点
    ListNode curr = head;
    // 循环遍历至尾结点
    while(curr != null){
        // 临时节点，保存当前节点的后继节点
        ListNode nextTemp = curr.next;
        // 改变当前节点的后继节点为前驱节点
        curr.next = prev;
        // 移动节点
        prev = curr;
        curr = nextTemp;
    }
    // 返回旧单链表的尾结点（即反转后的新单链表的头结点）
    return prev;
}

复杂度分析：

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

运行结果：
Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
Memory Usage: 37.7 MB, less than 29.48% of Java online submissions for Reverse Linked List.

思路2：
使用递归，来自官方的解法：

The recursive version is slightly trickier and the key is to work backwards. Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let’s assume the list is: n1 → … → nk-1 → nk → nk+1 → … → nm → Ø

Assume from node nk+1 to nm had been reversed and you are at node nk.

n1 → … → nk-1 → nk → nk+1 ← … ← nm

We want nk+1’s next node to point to nk.

So,

nk.next.next = nk;

Be very careful that n1’s next must point to Ø. If you forget about this, your linked list has a cycle in it. This bug could be caught if you test your code with a linked list of size 2.

大致意思：

我们可以假设单链表是这样的：n1 → … → nk-1 → nk → nk+1 ← … ← nm，现在想要 nk+1 的后继节点指向nk，即 （nk+1.next = nk）。

所以我们的 Base Case 是： nk.next.next = nk。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode reverseList(ListNode head) {
    // 当头结点为 null，直接返回 null（边界条件）
    // head.next == null，递归终止的条件 
    if (head == null || head.next == null){
        return head;
    }
    // 获取当前节点的后继节点，即 nk+1
    ListNode p = reverseList(head.next);
    // base case
    head.next.next = head;
    // 因为 n1 的前驱节点要指向 null
    head.next = null;
    return p;
}

复杂度分析：

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

运行结果：
Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
Memory Usage: 37.7 MB, less than 41.78% of Java online submissions for Reverse Linked List.

509. Fibonacci Number（Easy）

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

Given N, calculate F(N).

Example 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note:

0 ≤ N ≤ 30.

题目：
斐波纳契数，哈哈哈，大家是不是很眼熟呐，一道很经典的题目，这里不解释题目意思了。

解题思路：
这里先要引入一个概念，Memoization（记忆化）。

Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. (Source: wikipedia)

简单来说，记忆化技术是用来解决递归方法中出现重复计算的问题，使用缓存保存之前计算过的结果，使得相同输入，无需重复计算，直接从缓存中获取值。

在这道题中，我们可以看出，有很多次的重复计算，比如：F(4) = F(3) + F(2) = F(2) + F(2) + F(1) = F(1) + F(0) + F(1) + F(0) + F(1)。

所以我们可以引入记忆化技术。从上述的例子中，可以推导出递归公式为：F(n) = F(n-1) + F(n-2)。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    // 使用一个map集合，作为缓存
    private Map<Integer, Integer> cacheMap = new HashMap<>();
    public int fib(int N) {
        // 判断输入的值 N ，在缓存中是否存在计算结果，有的话直接返回
        if(cacheMap.containsKey(N)){
            return cacheMap.get(N);
        }
        int result;
        // F(1) = 1, F(0) = 0，所以当 N < 2 时，可以直接返回 N 。
        if (N < 2) {
            result =  N;
        }else {
            result = fib(N - 1) + fib(N - 2);
        }
        // 把计算结果放到缓存中
        cacheMap.put(N, result);
        return result;
    }
}

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

运行结果：
Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
Memory Usage: 31.7 MB, less than 100.00% of Java online submissions for Fibonacci Number.

我在 submissions 中发现一个有趣的答案，使用 Java 8 特性解题的，分享给大家：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int fib(int N) {
         // F(1) = 1, F(0) = 0，所以当 N < 2 时，可以直接返回 N 。
        if ( N == 0 || N == 1){
            return N;
        }
        // .limit(N + 1)： 循环 N + 1 次，每次生成一个数组为[f[1], f[0]+f[1]]，f 为上一个数组，new int[]{0, 1}为初始值，.mapToInt(f -> f[0])：获取每个数组的f[0]，形成IntStream；.max()：获取流中数值最大的元素，.getAsInt()： 转成 int 数值。
        return Stream.iterate(new int[]{0, 1}, f -> new int[]{f[1], f[0] + f[1]})
                .limit(N + 1)
                .mapToInt(f -> f[0])
                .max()
                .getAsInt();
    }
}

运算结果：
Runtime: 38 ms, faster than 5.57% of Java online submissions for Fibonacci Number.
Memory Usage: 32.3 MB, less than 100.00% of Java online submissions for Fibonacci

70. Climbing Stairs(Easy)

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

undefined

Example 2:

undefined

题目大致意思：
你正在爬楼梯，需要n步才能达到楼顶。 每次你可以爬1或2步。那可以通过多少不同的方式登顶？ 注意：给定n将是一个正整数。

核心思路：
把握一个核心思想，就是达到楼顶的最后步数，要么是1，要么是2。
我们假设当 n = 4 时， 可能的方式为 F(3) + 1 或者 F(2) + 2，即 F(4) = F(3) + F(2)，所以我们可以推导出公式为：F(n) = F(n-1) + F(n -2)。

解法一：递归 + 记忆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int climbStairs(int n) {
        // 缓存数组，用于存储F(n)的值，下标对应 n 值。
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

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

解法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
public int climbStairs(int n) {
    // 创建一个 n+1 的数组
    int[] result = new int[n + 1];
    // 有0下标的值，是为方便F(2)的计算
    result[0] = 1;
    result[1] = 1;
    // 循环 n 次
    for (int i = 2; i <= n; i++) {
        // 根据 f(i -1) 和 f(i -2) 的值动态计算 f(i)的值
        result[i] = result[i -1] + result[i - 2];
    }
    return result[n];
}

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

解法三：Fibonacci Number
不知你们发现没，这题跟我们上一题斐波纳契数是一样，都是F(n) = F(n-1) + F(n-2)，代码跟解法二基本一样，只是数组换成了整形，在空间消耗上进行了优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

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

LeetCode上还有几种解法，在时间复杂度上有了进一步的优化，感兴趣的小伙伴们，可以自行查看：https://leetcode.com/problems/climbing-stairs/solution/

Review

本周阅读的是 LeetCode Recursion I 上的三篇文章：Time Complexity - Recursion 、 Space Complexity - Recursion 和 Tail Recursion。

《Time Complexity - Recursion》，作者在这篇文章中介绍了如何对递归方法的时间复杂度进行分析。文中写了一种 Execution Tree（执行树）的方法， 并提到使用了 Memoization（记忆化）技术的递归方法，进行时间复杂度分析时，需要减去这部分节省的时间花销。

《Space Complexity - Recursion》，作者在文中介绍了递归函数的空间复杂度分析方法，其中提到空间复杂度的分析，主要分为两部分：递归相关和非递归相关的空间消耗。

《Tail Recursion》，这篇文章介绍一种特殊的递归方法，尾递归，并结合实例和图进行了讲解。

Tail recursion is a recursion where the recursive call is the final instruction in the recursion function. And there should be only one recursive call in the function.
(尾递归是一种递归，它的递归调用是递归函数中的最后一条指令，且尾递归函数中应该只有一个递归调用。)

Tip

最近有在摆弄 docker，在这里简单罗列下使用到的一些命令：

镜像相关的命令:

  • docker search image：搜索可用的镜像

  • docker pull image：拉取镜像

容器相关的命令：

  • docker run [OPTIONS] IMAGE [COMMAND] [ARG…]：创建一个新的容器并运行一个命令。
  • docker start/stop/restart CONTAINER：启动或停止或重启指定的容器。
  • docker rm [OPTIONS] CONTAINER [CONTAINER…]：删除一个或多少容器。
  • docker ps [OPTIONS]：列出容器。
  • docker logs [OPTIONS] CONTAINER：获取容器的日志。
  • docker exec [OPTIONS] CONTAINER COMMAND [ARG…]：在运行的容器中执行命令。

更多的命令可以到Docker 命令大全或者到官网上查看。

Share

本周分享几篇梁大的文章：
保持自己的技能不落伍 | 认知升级
构造知识反馈闭环
技术探讨的正确姿势