ARTS打卡：第四周

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

ARTS打卡：第四周

每周完成一个ARTS：

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

Algorithm

本周记录如下：

104. Maximum Depth of Binary Tree（Easy）

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

undefined

return its depth = 3.

题目大致意思：
给一个二叉树，找到它的最大深度，最大深度是指从根节点到最远叶节点的最长路径上的节点数。

思路：使用DFS（深度优先遍历）

解法一：

1
2
3
4
5
6
7
8
9
class Solution {
   public int maxDepth(TreeNode root) {
        // root == null 时返回 0，是边界条件
        // root != null 时，必有一个节点
        // 假设 maxDepth(root.left) 能求出左子树的最大深度，maxDepth(root.right) 能求出右子树的最大深度，那么只需比较左右子树的最大深度，取max，再加上根节点的 1，就是二叉树的最大深度了
        // 其实就是利用深度优先遍历求最大深度
        return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

解法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    // 记录最大深度
    private int max = 0;
    public int maxDepth(TreeNode root) {
         dsf(root, 0);
         return max;
    }
    public void dsf(TreeNode root, int depth){
        // 当前 root 为 null 时，要么根结点为 null，那么已经到达底部
        if (root == null){
            // 每次达到底部时，比较当前深度和当前记录的最大深度，取两者最大值
            max = Math.max(max, depth);
            return;
        }
        // 深度 + 1
        depth++;

        dsf(root.left, depth);
        dsf(root.right, depth);
    }
}

21. Merge Two Sorted Lists（Easy）

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

题目：
合并两个已排序的链表，并将其作为一个新列表返回。新列表应该通过将前两个列表的节点拼接在一起来创建。

思路：
需要正确理解题意，这道题给出的例子，其实很容易误导做题者，一开始我就被误导了，直至后面才发现，这道题要的新列表是要有序。

我们可以用递归来解这道题，解决递归的流程一般有四步：

  1. 定义一个递归方法
  2. 推导出递归方法和基本情况（base case）
  3. 如果递归方法存在重复计算的问题，使用记忆化技术进行优化
  4. 尽可能的使用尾递归

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 终止条件
    if (l1 == null){
        return l2;
    }else if (l2 == null){
        return l1;
    }else if (l1.val > l2.val){
        // 当 l1 的值大于 l2 时，将 l2 当做头结点，并将头结点的下一个后继节点指向 mergeTwoLists 方法返回的节点
        l2.next = mergeTwoLists(l1, l2.next);
        // 返回头结点
        return l2;
    }else{
        // 同理
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }
}

运行结果：
Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Sorted Lists.
Memory Usage: 37 MB, less than 97.90% of Java online submissions for Merge Two Sorted Lists.

779. K-th Symbol in Grammar（Medium）

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

Note:

N will be an integer in the range [1, 30].
K will be an integer in the range [1, 2^(N-1)].

题目：

在第一行，我们写一个0。现在，在后面的每一行中，查看前面一行，并将每个出现的0替换为01，将每个出现的1替换为10。给定第N行和索引K，返回第N行中的第K个索引符号(K的值为1个索引)(1个索引)。

解题思路：

从 Example 中，我们可以得出一个规律：

假设 row(N) 表示第 N 行，currLen 表示当前行的长度，preLen 表示上一行的长度，row(N)[K] 表示第 N 行，下标为 k 的值。

当 K 值小于等于 currLen/2，即 row(N-1) 的长度时，row(N)[K] 等于 row(N-1)[k]， 当 K 值大于 currLen/2 时，row(N)[K] 等于 row(N-1)[K - preLen] 与 1 的异或值。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int kthGrammar(int N, int K) {
    // 以已有的条件可得
    if (N == 1){
        return 0;
    }
    // 当前 N 行的长度
    int currMaxLength = (int)Math.pow(2, N-1);
    // 当前 N 行的一半长度，即上一行的长度
    int midLength = currMaxLength / 2;
    // 当 K 值小于等于 currLen/2，即 row(N-1) 的长度时，row(N)[K] 等于 row(N-1)[k]
    if (K <= midLength){
        return kthGrammar(N - 1, K);
    }else{
        //  当 K 值大于 currLen/2 时，row(N)[K] 等于 row(N-1)[K - preLen] 与 1 的异或值
        return kthGrammar(N-1, K- midLength) ^ 1;
    }
}

Review

本周阅读的是以下三篇文章，都是与异步 I/O 模型有关的：

  1. Thousands of Threads and Blocking l/O:The Old Way to Write Java Servers Is New Again（and Way Better）
  2. Scalable IO in Java
  3. Boost application performance using asynchronous I/O

Tip

感觉这周没学到什么小技巧Orz，就分享一个小发现吧，IDEA 自带的一个功能， View -> Show ByteCode，效果如下：
View -> Show ByteCode

Share

本周分享知秋大佬的有关 NIO 的系列文章：