算法判断循环链表、数据工程师练级攻略、python 从入门到精通、UML 精粹读后感、John 易筋 ARTS 打卡 Week 22

 关注
发布于: 2020 年 10 月 19 日
1. Algorithm: 每周至少做一个 LeetCode 的算法题笔者的文章：
算法：判断是否是循环链表，并返回循环链表开始节点Linked List Cycle II
题目142. Linked List Cycle II
﻿
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
﻿
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
﻿
Notice that you should not modify the linked list.
﻿
Follow up:
﻿
Can you solve it using O(1) (i.e. constant) memory?
﻿
Example 1:
﻿
﻿
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
﻿
Example 2:
﻿
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
﻿
Example 3:
﻿
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
﻿
Constraints:
﻿
The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.
﻿
解法一，用set存储对象把每个节点存储到不可重复集合set中，判断是否存在即可。但是存储比较多，速度就会稍微慢一点。
﻿
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class LinkedListCycleII:
    def detectCycle(self, head: ListNode) -> ListNode:
        nodeSet = set()
        while head :
            if head in nodeSet:
                return head
            nodeSet.add(head)
            head = head.next
        return Non
﻿
解法二，快慢指针﻿
定义两个指针慢和快。 两者都是从头节点开始的，快是慢的两倍。 如果到达末尾，则表示没有周期，否则最终它将最终赶上周期中某个地方的慢速指针。
﻿
假设从第一个节点到开始循环的节点的距离为A，并且慢速指针行进为A + B。 快速指针必须经过2A + 2B才能赶上。 周期的大小为N。完整的周期也是相交的慢速指针经过的时间比慢速指针经过了多少。
﻿
A + B + N = 2A + 2B
N = A + B
根据我们的计算，慢速指针在遇到快速指针时会精确地经过整个周期，并且由于它最初在循环开始之前就经过了A，因此它必须经过A才能到达循环开始的点！ 我们可以在头节点处启动另一个慢速指针，然后移动两个指针，直到它们在循环开始时相遇为止。
﻿
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    def  detectCycleWithTwoPointer(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
               slow2 = head
               while slow2 != slow:
                   slow = slow.next
                   slow2 = slow2.next
               return slow
        return None
﻿
2. Review: 阅读并点评至少一篇英文技术文章Awesome Data Engineering
﻿
这篇文件列举了数据工程师需要的技能，并列出了需要学习的书和课程。
包括SQL > Python > Big Data > Machine Learning > Security 等。
﻿
3. Tips: 学习至少一个技术技巧笔者的文章：
﻿
Python 3 从入门到精通 Mac OS
说明Python 的 3.0 版本，常被称为 Python 3000，或简称 Py3k。相对于 Python 的早期版本，这是一个较大的升级。为了不带入过多的累赘，Python 3.0 在设计的时候没有考虑向下兼容。
python 安装请参考：
翻译：在Mac上将Python 3设置为默认的正确和错误方法
﻿
Hello World打开命令行 Terminal
# 查看 python 版本
$ python -V
Python 3.8.5
# 进入 python 命令行
$ python
Python 3.8.5 (default, Oct  3 2020, 11:14:07) 
[Clang 11.0.3 (clang-1103.0.32.62)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> print('Hello World')
Hello World
>>> 3+2
5
>>> 
pycharm IDE 安装pycharm 社区开源版本下载 免费
﻿
写一下Hello World 代码，运行快捷键 control + shift + r ， 调试快捷键control + shift + d，或者点击下面绿色的运行按钮。
﻿
学习资源https://www.runoob.com/python3/python3-tutorial.html
﻿
https://wiki.python.org/moin/BeginnersGuide
﻿
如何学习基础教程挨个敲打一遍，再学习一下高级教程多线程编程， 1天左右时间足以。学习完以后，要在于多应用。比如笔者就可以用python写LeetCode算法。
算法：深拷贝链表，其中链表有个随机指向的指针Copy List with Random Pointer
算法：把排好序的链表转换为二叉排序树Convert Sorted List to Binary Search Tree
﻿
再写个爬虫练练手，待续...
﻿
﻿
4. Share: 分享一篇有观点和思考的技术文章笔者写的博客链接
架构师架构蓝图《UML精粹》 UML Distilled读后感
﻿
说明《UML精粹》用统一建模语言(Unified Modeling Language)是面向架构师、开发者、产品、用户通俗易懂的架构语言。因为翻译徐家福老爷爷是在80岁左右的时候才翻译的，所以笔者就直接看了英文原版。
Distill表示蒸馏，过去式表示蒸馏后留下来的精华，所以叫精粹。作者 Martin Fowler 大神作品，110页的书，虽然是出版于2001年，英文原版价格550元。
为什么要有UML？UML类似于高楼大厦的框架，去除了细枝末节，让架构师、产品、开发、客户能够比较明了软硬件的核心。以前是没有UML，也就是瀑布式开发，开发周期比较长，类似IBM这周巨头型公司解决大型系统，周期比较长比如几年，做出来的产品往往不如意，或者做完就被淘汰了。UML大概出现于1988~1992年，因为那个时候SmallTalk面向对象语言的比较火，OO面向对象的语言如雨后春笋般出现，比如python，Java。《UML精粹》是在2001年出版。
﻿
Agile敏捷开发模式替代了瀑布型开发模式：
先实现最小可用模型MVP (Agile敏捷开发模式替代了)；
不断迭代，不断重构；
持续集成等。
﻿
UML 的正确应用：需求分析阶段：用例图分析系统交互，类图描述核心类，活动图描述协作，状态图描述状态转移过程；
设计阶段：类图描述软件领域的类，时序图描述交互场景，包图描述模块间的关系，状态图描述类的生命周期，部署图描述物理服务器关系；
﻿
文档：文档可以描述开发的内容；
老代码逻辑梳理。
﻿
核心UML图本身很大一部分篇幅都在讲类图、时序图；实际上状态图、部署图、用例图也比较重要，作者都只用了2、3页就描述完毕。可见UML图本身就很简单，需要的时候网上查查，照猫画虎就能出来。
﻿
具体请参考文章：极客大学架构师训练营 听课总结 - 架构视图，设计文档 -- 第二课
﻿
UML 图全集
﻿
类图-- 订单类图
时序图 -- 订单时序图
﻿