ARTS打卡：第二十一周

每周完成一个ARTS：

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

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

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

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

Algorithm

14. Longest Common Prefix（Easy）

问题描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

1 2	输入: ["flower","flow","flight"] 输出: "fl"

示例 2:

1
2
3

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。
链接：https://leetcode.com/problems/longest-common-prefix/

解题思路

这个题的目的是找出所给数据组中的最长公共前缀，那我们可以在数组内任选一个字符串，拿它的所有前缀子串分别去匹配剩余的字符串的前缀，最后找出能够匹配所有剩余字符串的最长前缀子串即可。

代码实现

class Solution {
    /**
     * 
     * @param strs 输入的字符串数组
     * @return
     */
    public String longestCommonPrefix(String[] strs){
        // 边界条件
        if(strs == null || strs.length == 0){
            return "";
        }
        // 任选一个字符串，我们这里选择第一个字符串，从最长的前缀子串开始（即字符串本身）
        String s0 = strs[0];
        // 遍历剩余的字符串，拿所选字符串的所有前缀子串去匹配
        for(int i = 1; i < strs.length; i++){
            // 当 strs[i].indexOf(s0) = 0，存在两种情况
            // 1. 当前的 s0 能匹配 str[i]的前缀，所以终止循环，继续匹配下一个字符串
            // 2. 当前的 s0 = "", String.indexOf("") = 0，证明所选字符串的所有前缀子串都不能匹配字符串 str[i] 的前缀，所以终止循环
            while(strs[i].indexOf(s0) != 0){
                // 当前 s0 不能匹配 strs[i]的前缀，拿次长的前缀子串去匹配
                s0 = strs[0].subString(0, s0.length() - 1);
            }
        }
        return s0;
    }
}

执行结果：

Runtime: 0 ms, faster than 100.00% of Java online submissions for Longest Common Prefix.

Memory Usage: 37.5 MB, less than 87.13% of Java online submissions for Longest Common Prefix.

237. Delete Node in a Linked List（Easy）

问题描述

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

4 -> 5 -> 1 -> 9

示例 1:

1
2
3

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

1
2
3

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

链接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

解题思路

根据题意，我们是拿不到给定节点的前驱节点，只能拿到后继节点，那么实现删除节点思路就是将后继节点值覆盖当前节点，以此类推，直至尾节点，最后将尾节点置为null即可，我们可以通过递归来做。

代码实现

public class Solution {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
    
    public void deleteNode(ListNode node) {
        // 从说明中可知：给定的节点为非末尾节点并且一定是链表中的一个有效节点。
        node.val = node.next.val;
        // 终止条件
        if(node.next.next == null) {
            node.next = null;
            return;
        } else {
            // 递归公式
            node = node.next;
            deleteNode(node);
        }
    }
}

执行结果：

Runtime: 0 ms, faster than 100.00% of Java online submissions for Delete Node in a Linked List.

Memory Usage: 36.8 MB, less than 100.00% of Java online submissions for Delete Node in a Linked List.

Review

本周阅读的是：《Understanding Reactor Pattern: Thread-Based and Event-Driven》

作者开头从 thread-base（基于线程）架构和 event-driven（事件驱动）架构切入，然后具体介绍了Reactor Pattern。

基于线程的架构，即一个线程对应一个连接，适用于需要兼容非线程安全的库的程序，同时也指出了 thread-base 架构存在进程过于重量级、上下文切换缓慢和高内存消耗的情况，以及线程与连接一一对应的关系，导致了一旦存在大量的长连接，就会有大量的工作线程处于空闲等待状态，浪费了大量的内存堆栈。

事件驱动结构，可以将线程与连接分隔开来，仅将线程用于特定的回调或处理程序上的事件。

Reactor Pattern 是事件驱动架构的一种实现技术，简单来说，就是用单线程对资源发出的事件进行循环阻塞，并将它们分发给相应的处理程序和回调。只要事件的处理程序和回调被注册了，就不需要阻塞 I/O，这种模式将模块化应用程序级别的代码与可重用的响应式实现解耦。

Reactor 和 Handlers 是 Reactor Pattern 架构的两个重要参与者。

reactor 运行在一个独立的线程中，主要是用于将工作分发给对应的处理程序去处理 I/O 事件。
handler 则是处理与 I/O事件有关的实际工作。
reactor是通过分发适当的 handler 来处理I/O事件。Handlers执行非阻塞操作。

Reactor Pattern 的目的是允许事件驱动的应用程序，可以对来自一个或多的客户端请求进行多路复用和分发。

Tip

本周分享阿里开源的项目：Arthas

最近用的比较多的是 trace 命令，它可以显示方法内部调用路径，并输出方法路径上的每个节点上耗时。

在进行压测的时候，我们可以在后台执行 trace 命令（trace -j class-pattern method-pattern -n xxx > xxx/xxx.log &），等压测完毕后，解析输出的日志文件，可以算出指定方法的平均耗时、最小耗时和最大耗时；我们可以根据耗时情况，查看对应的代码，然后着手进行优化，这对我们在进行性能调优时，有一定的指导作用和帮助。

还有很多其他实用的命令，感兴趣的朋友们可以查看：《Arthas 用户文档》。

本周继续分享 simviso 团队带来的《斯坦福编译原理》译制视频：

【斯坦福编译原理】01 编译器与解释器简介

【斯坦福编译原理】02 编译器结构

【斯坦福编译原理】03 编程语言的性价比

【斯坦福编译原理】04 Cool语言概述

【斯坦福编译原理】05 Cool语言概述 2

ps：知秋大大带领的 simviso 还在不断的更新，感兴趣的小伙伴们赶紧跟上鸭(￣▽￣)”