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



这是我的第二周打卡。这周比较大的收获就是解决了 Jenkins 中使用代理来执行 npm install 的问题，对 docker 的网络加深了一些认识。



Algorithm



两数相加

描述：



给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。



如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。



您可以假设除了数字 0 之外，这两个数都不会以 0 开头。



示例：



输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

题解：



思路一：链表遍历



这道题首先想到的思路跟官方的一致，就是遍历链表，对每个节点进行求和。需要注意的有几点：



1. 两个链表的长度不一定是相等的

2. 相加的过程中会产生进位

3. 链表尾结点产生的进位会导致链表的长度加1



注意到以上几点之后，代码写起来其实是蛮简单的。



/**
 * 两数相加
 * @param {ListNode} l1 
 * @param {ListNode} l2 
 * @return {ListNode}
 */
export function addTwoNumbers(l1, l2) {
  //声明一个head节点
  const head = new ListNode(null);
  //当前节点
  let curr = head;
  //进位
  let carry = 0;
  //当两个链表都不为空时，每位相加
  while (l1 != null || l2 != null) {
    //链表长度不一致，缺位补0
    let x = l1 != null ? l1.val : 0;
    let y = l2 != null ? l2.val : 0;
    let sum = x + y + carry;
    carry = Number.parseInt(sum / 10);
    curr.next = new ListNode(sum % 10);
    curr = curr.next;
    if (l1 != null) {
      l1 = l1.next;
    }
    if (l2 != null) {
      l2 = l2.next;
    }
  }
  if (carry > 0) {
    curr.next = new ListNode(carry);
  }
  return head.next;
}



时间复杂度：O(n)



Tips:



由于我是用 vscode 来写的，发现一个有趣的问题就是 leetcode 的 javascript 版本默认是做了数组转链表的操作。这个实现起来也比较容易，用对象来模拟一个链表即可。



//声明一个单链表结点
class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
/**
 * 数组转链表
 * @param {Array} arr 
 * @return {ListNode} 
 */
export function array2List(arr) {
  if (arr.length === 0) {
    return null;
  }
  const head = new ListNode(null);
  let i = 0, curr = head;
  for (i; i < arr.length; i++) {
    curr.next = new ListNode(arr[i]);
    curr = curr.next;
  }
  return head.next;
}



上面这段代码有点难理解的就是下面这三句



curr = head
curr.next = new ListNode(arr[i]);
curr = curr.next;



对于这几行代码，如果理解了 js 的引用类型就比较容易看懂，或者画一下堆栈图就更好理解。

Review



2020 and Beyond Programming Trend Predictions



这篇文章是去年在 infoq 上看到的，然后一直躺在我的收藏夹中。对于这种技术趋势的文章，虽然很多时候都只是当成一个资讯来看，但仔细阅读还是可以挖掘出一些有用的内容的。特别是回过头再去看的时候。



文章主要介绍的技术是：Rust、GraphQL、PWA、WebAssembly 和 React



PWA 和 WebAssembly 在19年出现的频率特别高。WebAssembly 应该算是一个比较超前的概念了，对于这种技术，一出来马上就会出现WebAssembly 的出现是否会取代 JavaScript？这样的文章。



作者在文章中更多地强调 WebAssembly 是一种将 JavaScript 技术与更高级的技术相结合的方法。短期内一个技术取代另一个技术的可能性是比较低的，尤其是这种更偏向于底层的实践。作为普通的技术开发者，没必要杞人忧天，整天活在技术焦虑之中。我们更应该把时间花在学习当下的技术上，学会区分知识和资讯很重要。



PWA 作为一个偏应用层的技术，感觉跟我们的相关度其实是更高一些的。因为解决用 web 去开发 app 的尝试从来都没停过，如果 web 能够达到媲美原生 app 的效果，最直接的优势就是省钱。国内外的很多厂商已经开始做了尝试：有哪些使用 PWA 的 app ？



GraphQL 放到2020年来说，已经不是一个新奇的玩具了。在19年我就开始尝试了用apollo 来构建新的API，因为传统的 REST API 已经满足不了前端日益庞大的数据交互了，有了痛点再来主动地搜寻解决方案对自己的成长是比较迅速的。



React 在 2020 好像没有什么颠覆性的改变了，倒是 Vue3.0 做出了很多重大的改变来帮助开发者面对大型前端项目，比如 Composition API

Tip



解决 Jenkins 中使用代理来执行 npm install 的问题



这周工作中最大的收获应该是解决了在 Jenkins 中使用代理的问题。之前一直没怎么去关心 docker 的网络问题，Jenkins 的 pipeline 使用的 agent 环境是 docker，然后 Jenkins 也是使用 docker 来安装的，其实是一个 docker in docker 的问题。



由于篇幅可能比较大，这里开了一篇新的文章来介绍。

Share



分享文章：Clean Frontend Architecture：整洁前端架构



《Clean Architecture》这本书是 Robert C. Martin 很早之前写的。当我们谈到架构的时候，基本都是指后端的系统架构。但是在2020年的今天，前端已经变得很复杂了，由一个 View 层变成了一个端，很多后端的架构思想已经开始在前端的开发设计中慢慢浮现出来。这篇文章是把 《Clean Architecture》里的思想借鉴到前端来实现，当然这只是作者的一个 idea 。是否真的要在项目中使用，还是要斟酌一下的，毕竟过于复杂和过度设计。