ARTS是左耳朵耗子提出来的一个打卡任务。每周一个 Algorithm，Review 一篇英文文章，总结一个工作中的技术 Tip，以及 Share 一个传递价值观的东西！我希望这个事可以给大家得到相应的算法、代码、技术和影响力的训练。



这是我的第六周打卡。之前在公司把Jenkins流水线搭起来了，发现在使用的过程中还是有很多问题，比如trigger每次触发的时候，默认会把所有的分支都去构建一遍。这周继续优化Jenkins的流水线，解决了几个比较棘手的问题。



Algorithm



从链表中删去总和值为零的连续节点



描述：





题解：



这道题很关键的地方就是如何判断连续相加等于0，有几种情况要考虑。题目给的示例中Test Case是残缺的，用它去解题会出错的，第一次提交就被坑了。



Case1:

[1,2,-3,3,1]

1+2-3 = 0
所以得到的是[3,1]

还有一种情况就是 -3+3 = 0
所以得到的是[1,2,1]



Case2:

[1,-1,2]
1-1 = 0
所以得到的是[2]



Case3:

[1,-1,1,-1]
1-1+1-1 = 0
所以得到的空



结合这几个Case和题目的示例能得到所有的情况了。



前面说关键点是判断连续相加为0，那么如何判断呢？这里通过累加的方法，遍历整个链表，把每个结点累加的和存到一个哈希表中。还有一个关键点也很重要，就是链表的头结点。



如果不用头结点，很容易出错。我们拿 Case1 来举例子。不用头结点的话



1->2->-3->3->1



初始化一个 sum 变量，值为 0 。我们先累加一下



sum: node
1: 1
3: 2
0: -3
3: 3
4: 1



可以看到，当结点为 2 的时候，sum 为 3 ，然后结点为 3 的时候，sum 又为 3 ，也就是说这两个结点之间的所有结点的和为 0 ，所以我们得到的是 [1,2,4]



这样看起来没什么问题，但是如果是 [1,-1,1,-1] 就出错了。我们分析一下：



sum: node
1: 1
0: -1
1: 1
0: -1



当结点为 1 的时候，sum 为 1 ，然后结点为下一个 1 的时候，sum 又为 1 。那么得到的结果是[1,-1] ，显然是错误。因为 [1,-1] 可以继续消掉。



我们加上头结点的话，再来分析一下这种情况。



head->1->-1->1->-1



sum: node
0: head
1: 1
0: -1
1: 1
0: -1



看，当结点为 head 的时候，sum 为 0，结点为 -1 的时候，sum 又为 0 ，所以得到的结果是 head 。因为 head 的初始值为 0 ，如果结点相加等于 0 的话，后面总会有一个 sum=0 的结点，所以我们返回head.next 就是我们想要的结果。



分析完毕后，我们遍历两次链表就可以得到结果了。第一次把 sum 和 node 存放到哈希表中，第二次根据累加的结果找到值相同的 sum



export default function removeZeroSumSublists(head) {
  const dummy = new ListNode(null)
  dummy.next = head
  const map = new Map()
  let sum = 0
  //首次遍历，生成哈希表，key为当前节点总和，value为当前节点
  for (let p = dummy; p !== null; p = p.next) {
    sum += p.val
    map.set(sum, p)
  }
  //第二次遍历，如果当前节点处sum在下一处出现，表明两节点之间所有节点的和为0，直接删除区间所有节点
  sum = 0
  console.log(dummy)
  for (let q = dummy; q !== null; q = q.next) {
    sum += q.val
    q.next = map.get(sum).next
  }
  return dummy.next
}



时间复杂度：O(n)



Review



Preparing for a Tech Talk, Part 2: What, Why, and How



这是技术演讲系列教程的第二篇。上一篇文章讲了技术演讲的动机，那么这篇文章就开始介绍怎么去做了。



作者把演讲跟《盗梦空间》联系在一起，这部电影是关于在别人睡觉时把想法带入别人的大脑，同样演讲也是如此。



what 是演讲的核心思想，一定要很简洁。why 主要是围绕演讲的主题来解释使用场景，带来的好处等等。how 是关于如何去使用以及实现，通常用一个 Live demo 会比语言更容易让观众明白。

Tip



使用脑图来构建我们的知识体系



这周在使用 Docker 部署项目时经常遇到一个小的问题都要去查半天资料。后来想想，发现自己对Docker 基本上是不熟悉的，虽然公司所有的项目基本都是我用 Docker 搭起来的。



突然感觉工作几年后，接触的东西很多，但都是用的时候才去深入了解的，用完就没有去关心了。虽然说，解决问题的能力很重要，但随着工作年龄的增长，这种能力所占有的优势会越来越小。越往上走，我们越要具备一站式交付的能力，也就是整个产品研发的环节都要很清楚，以最低的成本交付最大的商业价值。这种能力，一方面是要依靠经验；另一方面就是要构建出自己的知识体系，然后查漏补缺，对不熟的地方勤加练习。



为此，我结合了之前收藏的developer-roadmap和architect-awesome用脑图构建了一下自己的知识体系。





根据大的方向分为了基础技能、前端、后端、Devops和软件工程。在细化的过程中，对整个web研发的知识体系又进一步加深了了解，知道自己应该朝着哪方面去深入。有时候方向和目标真的很重要，如果只是每天重复上班下班，很快就会厌倦这样的生活，因为工作对一个人的要求真的不是很高。



Share



分享文章：Jenkins 多分支项目过滤及 when 的高级用法



这周在继续优化Jenkins的发布流程时，又解决了很多人没有搞定的问题，给自己赞一个！