ARTS打卡：第七周

每周完成一个ARTS：

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

Algorithm

189. Rotate Array(Easy)

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

题意：
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
需要注意是只允许使用 O(1)的额外空间，效果如 Example 所示。

解题思路1：使用暴力破解。
循环 K 次，每次遍历数组，让数组的每一位元素往前移动一位。

解题代码如下：

1
2
3
4
5
6
7
8
9

public void rotate(int[] nums, int k) {
    for (int i = 0; i < k; i++) {
        for (int j = 1; j < nums.length; j++) {
            int temp = nums[j];
            nums[j] = nums[0];
            nums[0] = temp;
        }
    }
}

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

解题思路2：
仔细观察 Example ，我们可以发现一个事实，旋转数组 K 次，K 个元素从数组后端挪动到前端，其余元素从前端挪到后端。
在这种方法中，我们首先翻转数组，然后再次翻转数组前 k 个元素，最后翻转 n - k 个元素，即其余的元素，n 为数组长度；这样就能得出答案。
例子：

1
2
3
4

原始数组                           : 1 2 3 4 5 6 7
首先翻转整个数组                    : 7 6 5 4 3 2 1
其次翻转数组前 k 个元素             : 5 6 7 4 3 2 1
最后翻转数组后 n - k 个元素         :5 6 7 1 2 3 4 --> Result

解题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public void rotate(int[] nums, int k) {
    k = k % nums.length;
    // 翻转整个数组
    reverse(nums, 0, nums.length - 1);
    // 翻转数组前 k 个元素
    reverse(nums, 0, k - 1);
    // 翻转数组后 n - k 个元素
    reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

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

217. Contains Duplicate(Easy)

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

题意：
给一个 int 类型的数组，如果数组内有重复的元素，返回 true，无则返回 false。

思路1：结合set集合进行判重。

代码如下：

1
2
3
4
5
6
7
8
9
10

public boolean containsDuplicate(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (set.contains(num)){
            return true;
        }
        set.add(num);
    }
    return false;
}

复杂度：
时间复杂度：O(n)，set的查找和插入消耗的时间都是常量。
空间复杂度：O(n)，额外消耗的空间就是set的大小，取决于有多少元素加入到集合中。

思路2：先对数组进行排序，然后遍历进行判重。

代码如下：

1
2
3
4
5
6
7
8
9

public boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

复杂度：
时间复杂度：O(nlogn)。Array.sort() 时间复杂度是 O(nlogn)，遍历是 O(n)，不过遍历的次数是基于排序的情况来决定的，所以时间复杂度是 O(nlogn)。
空间复杂度：O(1)。空间复杂度取决于 Arrays.sort()的内部实现，如果是使用heapsort，通常会花费 O(1) 的辅助空间。

思路3：利用 Java 8 的 distinct() 和 count() 来做。

代码如下：

1
2
3
4

public boolean containsDuplicate(int[] nums) {
    long count = Arrays.stream(nums).distinct().count();
    return nums.length == count;
}

这种方法从 leetcode 给出结果上来看，消耗时间最长，空间消耗也最大，时间和空间的复杂度不知如何分析(:з」∠)，不过代码更简洁易懂。

Review

本周阅读的是《UNIX® Network Programming Volume 1, Third Edition: The Sockets Networking 》中的 6.2 I/O Models。

作者 Stevens 在这节中详细说明了五种 IO Model 的特点和区别。

这五种 IO Model 分别是：BIO（blocking IO）、NIO（non-blocking IO）、 IO multiplexing、signal driven IO 和 AIO（asynchronous IO）。

Tip

分享一篇我在学习《左耳听风》专栏做的笔记，有关于如何高效学习的：97 - 高效学习：深度，归纳和坚持实践

Share

本周分享梁大组织维护的一个知识仓库：服务端思维，里面有每周答疑周报、每月精读等内容，非常值得小伙伴们关注~

ARTS打卡：第六周

每周完成一个ARTS：

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

Algorithm

这周的 LeetCode 记录如下：

26. Remove Duplicates from Sorted Array（Easy）

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn’t matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn’t matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

大致题意：
删除排序数组中的重复项，要求给定一个排序数组，在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

解题思路：
这道题，我们可以借鉴快慢指针的思想来做，不过不是用链表，是用数组进行模拟：
假设 slow 为慢指针，fast 为快指针，因为 nums 数组是已经排好序的升序数组，所以当 nums[slow] = nums[fast]，我们让快指针前进一步，跳过重复的数据，即 fast++；若 nums[slow] != nums[fast]时，让慢指针前进一步，即 slow++，然后交换快指针与慢指针的值，将新数据替换掉重复数据，即 nums[slow] = nums[fast]；重复步骤直至快指针走到数组尾部，即 fast == nums.length时，输出结果 slow + 1，这就是去重后的数组长度了。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public int removeDuplicates(int[] nums) {
    // 当是空数组时，直接返回 0，边界条件
    if (nums.length == 0) {
        return 0;
    }
    // slow 为慢指针
    int slow = 0;
    // fast 为 快指针
    for (int fast = 1; fast < nums.length; fast++
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

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

运行结果：
Runtime: 1 ms, faster than 99.98% of Java online submissions for Remove Duplicates from Sorted Array.
Memory Usage: 40.8 MB, less than 84.56% of Java online submissions for Remove Duplicates from Sorted Array.

122. Best Time to Buy and Sell Stock II(Easy)

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation:
Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.

Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

题意：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路：
这道题是看答案才明白过来的，感觉挺有趣的，虽然挺多人认为这道题就是拿来搞笑的。
有三种解决方法，详情请查看：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/solution/
第三种解法，着实我眼前一亮。
先暂时忽略题目的限制，那么我们就可以得出这个结果：只要我们每次买进股票的价格比我们卖出的价格低的机会，就能实现利润最大化。

代码实现：

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i - 1] < prices[i]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
}

Review

本周阅读的是这篇文章：Lazy Asynchronous I/O For Event-Driven Servers

文中详细介绍了LAIO的概念，LAIO 的 API，并将其与 NIO、AIO 进行了多方面多角度的比较。

部分笔记如下图所示：

Tip

这周 VS Code 用的比较多，就分享下快捷键的使用吧。

windows 版的快捷键说明文档，可以直接通过快捷键 Ctrl + K，Ctrl + R 获取，也可以通过这个网址获取：https://code.visualstudio.com/shortcuts/keyboard-shortcuts-windows.pdf

中文版的可以参看这个博客：VS Code折腾记 - (2) 快捷键大全，没有更全

Share

本周分享：一个NullPointerException，竟然有这么多花样！

文章来自肥朝大佬的公众号，文风一如既往的幽默风趣，知识点讲解条理清晰。

ARTS打卡：第五周

每周完成一个ARTS：

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

Algorithm

这周将 Recursion I 剩余部分完成了，记录如下：

96. Unique Binary Search Trees(Medium)

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST’s:

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

题目意思：给定n值，求出有多少结构上唯一的存储值1 … n的BST（二叉搜索树）？

首先我们要了解二叉搜索树（BST binary search trees）是什么?

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

思路来源：
DP Solution in 6 lines with explanation. F(i, n) = G(i-1) * G(n-i)-G(i-1)-*-G(n-i))

这个帖子说的很详细，建议小伙伴们都看看。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int numTrees(int n) {
        // 为了方便理解，申请长度为 n+1 的数组，便于最后直接返回 g[n]
        int[] g = new int[n + 1];
        // base case
        g[0] = g[1] = 1;
        // 从g(2)出发
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // g(n) = f(1, n) + ... + f(n, n)
                // f(i, n) = g(i -1) * g(n - i)
                // g(n) = g(0) * g(n - 1) + ... + g(n - 1) * g(0)
                g[i] += g[j -1] * g[i - j];
            }
        }
        return g[n];
    }
}

95. Unique Binary Search Trees II(Medium)

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST’s shown below:

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

题目意思：给定整数n，生成存储值1 … n的所有结构上唯一的BST（二叉搜索树）。

思路：
其实跟上面那道题的思路很相像，这里大致说下：

1. 我们从 Example 可得出如果 n 是输入值的话，那么根节点可能就是 1-n 中任何一个。
2. 我们可以先假设 G(n) = G(start, end) 能获取生成存储值1 … n的所有结构上唯一的BST，start是 1-n 范围内的起点，end 是终点，即 n。
3. 因为是BST，所以当i为根节点时，左子树的所有结果集可以假设为 G(start, i - 1)，，右子树的所有结果集可以假设为 G(i+1, n)。
4. 确认 base case，能确认最底部的根节点，然后关联有可能的左子树和右子树，最后返回一个包含了所有的情况的集合，当 start > end 的时候，返回一个空集合，表示没有左/右子树。
5. 确认边界条件，当 n == 0，直接返回空集合。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public List<TreeNode> generateTrees(int n) {
    // 边界条件
    if (n == 0) {
        return new ArrayList<>();
    }
    return genTrees(1, n);
}
private List<TreeNode> genTrees(int start, int end) {
    List<TreeNode> treeNodes = new ArrayList<>();
    //  base case
    if (start > end) {
        treeNodes.add(null);
        return treeNodes;
    }
    for (int i = start; i <= end; i++) {
        List<TreeNode> leftTreeNodes, rightTreeNodes;
        // 获取左子树的所有可能-递归公式
        leftTreeNodes = genTrees(start, i - 1);
        // 获取右子树的所有可能-递归公式
        rightTreeNodes = genTrees(i + 1, end);
        // base case
        for (TreeNode leftTreeNode :
                leftTreeNodes) {
            for (TreeNode rightTreeNode :
                    rightTreeNodes) {
                TreeNode root = new TreeNode(i);
                root.left = leftTreeNode;
                root.right = rightTreeNode;
                treeNodes.add(root);
            }
        }
    }
    return treeNodes;
}

Review

本周阅读的是：Tutorial For Dynamic Programming

是一篇很好的动态规划的学习资料。

Tip

这周分享从梁大的知识星球中学到的 tip：

Share

本周分享的是小灰大大的文章：漫画：什么是动态规划？

这篇文章以漫画的形式，生动形象的介绍了动态规划，让算法学起来不再那么的枯燥无味。

小灰的公众号还有其他以漫画形式介绍算法的文章，感兴趣的小伙伴们可以关注走一波。

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，效果如下：

Share

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

• BIO到NIO源码的一些事儿之BIO
• BIO到NIO源码的一些事儿之NIO 上
• BIO到NIO源码的一些事儿之NIO 中
• BIO到NIO源码的一些事儿之NIO 下 之 Selector
• BIO到NIO源码的一些事儿之NIO 下 Buffer解读 上
• BIO到NIO源码的一些事儿之NIO 下 Buffer解读 下

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

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

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

前言

这篇是身为技术菜鸟的博主写的第一篇技术文章，新手上路，文笔粗糙，还请大家多多担待。

之所以写这篇文章，起因是我看完《Java 8 in Action》 也有一段时间了，在日常工作中，也经常使用 Java 8 的语法，就打算写下有关 Java 8 的一系列文章，用于自我复习和总结，加深自己对 Java 8的理解和使用，好了，言归正传，下面就让我们进入主题吧。

你是否曾经被 NullPointerException 异常折磨的苦不堪言？你是否曾为复杂的POJO 类写非空判断，为那多个 if xxx != null 或多层嵌套 if xxx != null 的代码感到烦恼心累？

呐，程序猿们，我们是时候用Java 8 的 Optional 类进行优雅的判空啦，当然，如果你用的是 Java 8 的话(:з」∠)。

Optional 是什么？

java.util.Optional 类是 Java 8 引入的一个新的类，是一个容器，可以保存类型为T的值，也可以保存null值，它提供了许多有用的方法，使得我们可以不用显示进行空值检查。

Optional 的类方法

Optional 的应用实例

上面基本上列出了 Optional 类的所有方法，下面挑几个常用的方法进行介绍：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

public class OptionalTest {

    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    private static class Basket {
        private Apple apple;
    }

    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    private static class Apple {
        private String color;

        private Double weight;
    }

    public static void main(String[] args) {
        Apple apple = new Apple("red", 20.00);
        Basket basket = new Basket(apple);
        try {
            // 返回一个包含指定 apple 的 Optional，如果 apple 为空，则抛出 NullPointerException
            Optional<Apple> optionalApple1 = Optional.of(apple);
        } catch (NullPointerException e) {
            e.printStackTrace();
        }

        // 将 apple 用 Optional 封装之后返回，如果 apple 为null，则返回一个空的 Optional 对象
        // 推荐采用这种方式
        Optional<Apple> optionalApple2 = Optional.ofNullable(apple);

        try {
            // 如果 optionalApple 包含有值，则返回该值，否则抛出 NoSuchElementException 异常
            Apple apple1 = optionalApple2.get();
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }

        // 如果不想get()抛出异常，可以使用 orElse() 方法
        // 如果 optionalApple2 有值，则将其返回，否则返回指定 null 值
        Apple apple1 = optionalApple2.orElse(null);

        // 如果 optionalApple2 有值存在，就对该值执行提供的mapping 函数调用
        Optional<Double> weightOptional = optionalApple2.map(Apple::getWeight);

        // 可以与 get() 一起使用，或者与 orElse() 一起使用
        Double weight1 = optionalApple2.map(Apple::getWeight).get();
        Double weight2 = optionalApple2.map(Apple::getWeight).orElse(00.00);

        // 从 Basket 中 获取 Apple 的 weight
        Double appleWeight1 = Optional.ofNullable(basket)
                .map(Basket::getApple)
                .map(Apple::getWeight)
                .orElse(00.00);

        // 使用 orElseThrow
        Double appleWeight2 = Optional.ofNullable(basket)
                .map(Basket::getApple)
                .map(Apple::getWeight)
                .orElseThrow(NullPointerException::new);
    }
}

使用 Optional 进行优雅判空

还是用上面列举的类，如果不用使用 Optional，想要获取 Basket 类内的 Apple 类的 weight 值，得这样写：

1
2
3
4
5
6
7
8
9
10
11
12

public double getAppleWeight(Basket basket){
    if (basket != null){
        Apple apple = basket.getApple();
        if (apple != null){
            Double weight = apple.getWeight();
            if (weight != null){
                return weight;
            }
        }
    }
    return 0.0;
}

看看这个 if 嵌套，emm…，这还是较为简单的 pojo 类，如果是复杂的，简直不堪入目啊。
而在 Optional 的加持下，只需这样写：

1
2
3
4
5
6

public double getAppleWeight(Basket basket){
    return Optional.ofNullable(basket)
            .map(Basket::getApple)
            .map(Apple::getWeight)
            .orElse(0.0);
}

瞬间代码就清爽了，嘻嘻，人也跟着欢快起来了。

当然 Optional 不止能进行优雅的判空，还可以利用 Optional 的其它的API，进行一些神奇的操作，比如使用 filter 进行参数校验之类的。

参考：

1. 《Java 8 in Action》
2. Java8 如何正确使用 Optional

ARTS 第二周分享

每周完成一个ARTS：

1. Algorithm：每周至少做一个 leetcode 的算法题
2. Review：阅读并点评至少一篇英文技术文章
3. Tip：学习至少一个技术技巧
4. 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:

1
2
3
4
5
6
7
8
9

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

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

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

1
2
3
4
5

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

 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?

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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答案，答案如下：

1
2
3
4
5
6
7
8
9
10
11

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小时理论”等。

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

1. 对编程感兴趣，从编程中获取乐趣，这样才能坚持10000小时或10年。
2. 动手编程，边学边做，实践出真知。
3. 和其他的程序猿交流，能比培训或看书收获更多。
4. 在大学期间或加上研究生期间，深入计算机领域学习；如果不喜欢读书，那直接通过工作获取经验也可以，但不能死读书，计算机科学并不能让你成为编程专家，正如学习颜料和画笔不能让你成为一个画家一样。
5. 与其他程序猿一起参与一些项目，在一些项目中成为最好的程序猿，尽自己最大的能力去带领团队，用自己的视野去启发别人；在一些项目中当最差的程序猿，当你是最差的时候，学习其他大牛。
6. 接收他人项目时，理解他人写的代码，修复他人的BUG；思考设计自己的软件，让其容易被他人维护。
7. 至少学会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插件，如下图所示：

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

1
2
3
4
5
6
7
8
9
10
11
12

@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();
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

Share

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

ARTS 第一周分享

ARTS 是耗子叔发起的一次活动，感兴趣的小伙伴们可以到知乎上查看极客时间《左耳听风》发起的ARTS挑战怎么参加？

每周完成一个ARTS：

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

Algorithm

LeetCode 的萌新用户，这周做的几道题是 Recursion 1 里面的题目，记录如下：

#344. Reverse String（Easy）

Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1 ：
Input: [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]
Example 2 ：
Input: [“H”,”a”,”n”,”n”,”a”,”h”]
Output: [“h”,”a”,”n”,”n”,”a”,”H”]

这道题的大致意思是写一个方法，用于反转输入的字符数组，不允许额外分配多一个数组，要求只能使用O(1)的额外内存来实现。
解法简单，就直接上代码了:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public void reverseString(char[] s) {
        char temp;
        int midIndex = s.length / 2;
        for (int i = 0; i < midIndex; i++) {
            temp = s[i];
            s[i] = s[s.length - 1 -i];
            s[s.length - 1 - i] = temp;
        }
    }
}

贴一个在 Discuss 里看到的答案，利用 ascii 来实现的，是我想不到的思路(:з」∠)：[Java] two pointer solution without temp var ：

1
2
3
4
5
6
7
8
9

class Solution {
    public void reverseString(char[] s) {
        for (int i=0,j=s.length-1;i<j;i++,j--){
            s[i]=(char)(s[j]-s[i]);
            s[j]=(char)(s[j]-s[i]);
            s[i]=(char)(s[j]+s[i]);
        }
    }
}

#24. Swap Nodes in Pairs（Medium）

Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.

题目的大致意思：给定一个链表，交换每两个相邻节点并返回其头部。 只能更改节点本身。

解题思路：这道题可以当做是递归问题，解决递归问题两大关键点：

• recurrence relation：the relationship between the result of a problem and the result of its subproblems.（即大问题分解为小问题的规律，基于这个规律写出递推公式）
• base case：the case where one can compute the answer directly without any further recursion calls. （即递归的终止条件）

所以我们第一步，就是先找出递归关系，将大问题分解为小问题。

以 Example 提供的数据为例，将两个节点划分为一组来看，会发现（1->2），交换位置后为（2->1），即将 2 作为头部节点，并指向 1，且 1 节点要指向下一组的头部节点，然后返回头部2；下一组（3->4），通过同样的操作，变为（4->3），3 指向了下一组的头部节点，然后返回头部节点 4。

你看，递归关系就出来了，都是把原头结点的下一个节点当做当前头结点，把原头结点指向下一组的头结点，然后把当前头节点的下一个节点指向原头结点，最后返回当前头结点。（表述能力有点渣，请见谅(:з」∠) ）。

把递归关系写成方法，如下：

1
2
3
4
5
6
7
8
9
10
11
12

public ListNode swapPairs(ListNode head) {
    // 临时变量保存原先的头结点
    ListNode tmp = head;
    // 把原先头结点的下一个节点当做当前头结点
    head = head.next;
    // 把原头结点指向下一组的头结点
    tmp.next = swapPairs(head.next);
    // 把当前节点的下一个节点指向原先头结点
    head.next = tmp;
    // 返回当前头结点
    return head;
}

当然，还没完，我们还需要找到递归的终止条件，即当：

• 假设传入的是一个空节点时，直接返回空节点。
• 假设传入的节点没有下一个节点时，直接返回当前节点。

这时答案就出来了：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
        public ListNode swapPairs(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode tmp = head;
            head = head.next;
            tmp.next = swapPairs(head.next);
            head.next = tmp;
            return head;
        }
    }

Review

本周阅读了一篇在《左耳听风》第71讲中推荐阅读的文章：《The Key To Accelerating Your Coding Skills》。

作者在这篇文章中讲述了如何有效地快速提高自己的编程能力，认为在学习编程的过程中，存在着编码拐点，一旦通过这个拐点，作为一个开发人员的操作方式，将会有很大的不同。通过拐点之前，将可能是一段令人沮丧的经历，但一旦它过去了，它就会让你变得无比强大。

Tip

分享一个关于 Intellij IDEA Debug的小技巧：
有时候我们进入方法体之后，还想退回到方法体外时，如果手速过快，点多了几下F8/F9，这时，只需点击 Drop Frame，即可退回方法体外，如下图所示：

这里附上在Github上找到的IntelliJ IDEA 简体中文专题教程

Share

分享一个在阿里技术公众号上看到的一篇文章《工程师男友如何反窃听？趣聊密码学入门科普》，文章生动有趣，非常值得一看，妈妈再也不担心如何向别人介绍我所处的行业了(:з」∠) 。