Algorithm

题目描述

给定一个链表，判断链表中是否有环。

Example

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

题目解答

首先能想到的解法是使用一个Set存储已经遍历过的节点，如果在遍历中节点已经存在于Set中，则说明链表是有环的，这种解法额外使用了其它的数据结构。另一种更好的方法就是使用快慢指针的方式，类似于跑道上的套圈，如果快的人追上了慢的人则说明是有环的，否则就是快的人先到达终点（即访问到最后的Null）

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

public class CycleSolution {
    public static boolean hasCycle(ListNode node) {
        ListNode slow = node;
        ListNode fast = node;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

快慢指针的解法的时间复杂度为O(n)，空间复杂度为O(1)，因为只使用了两个指针。

Review

Code Smells: Iteration 本文是Idea作者代码味道系列的第三篇。作者对第二篇中的使用不太恰当的for循环进行了优化。

Set替换List

就是使用Set来替换List的for循环判断元素是否存在，这样可以直接使用Set.contains()一行代码来进行判断了，更加简洁。这种替换的前提是list中的元素是唯一的且重复元素不影响执行结果。

Map替换List

使用Map来替换List中的for循环查找匹配的元素。这种情况对于Java8中的findFirst和findAny等语句也是有效的。

更多的建议

  1. 多使用Java核心库中提供的方法，如List.contains()方法。还有就是集合的工具类Collections，这个类在1.8版本后新增很多的实用方法。
  2. 方法的命名很重要，确实，起个好名字很难。

留言区的热烈讨论

这一次的代码味道感觉引起了读者的不赞同，有的说是为了宣传Idea的重构而写的，有的说这种重构只是把代码逻辑交给了更底层的实现，但是for循环是一直都存在的，例如对于数组的for循环。作者最后也说明了自己的文章意图，就是设计的代码味道，对于不同需求使用不同的数据结构来实现，对于那些可能重构的代码可以对其进行更优的处理。但是还有一句名言叫不要做提前的性能优化。写出简洁易懂的代码是最好的，毕竟代码被人看的次数很多，尤其是你手上项目是好几手的情况下，好的代码结构与命名会对后来者更友好。

Tip

打印指定文件夹的树目录

使用exa

1

exa -T -L 3 > tree.md

此方法只能输出结构，不能进行查看文件内容操作

使用tree命令

1

tree --charset utf8 -H file:///Users/tomyli/Downloads ~/Downloads -o ~/tmp.html

这样可以生成一个html文件，支持点击文件进行内容的预览了。

Share

今天分享的是git-commit-message这篇文章（从阮一峰老师那获取的），主要描述了angular项目中提交代码的git信息规范，信息提交的格式分为页头，消息体，页脚三部分。提交的信息中又分成不同的类型来表示是生产环境的改动还是测试环境的改动，这样在对修改进行查询时会准确的查找到信息。而且这种语义式的提交还可以用在自动化的发布上。文中还提到使用emoji更能提高信息的意图。另外对于这种实践文中提到了两个开源工具commitlint和cz-cli 。