ARTS-1

[blackwuxin]

ARTS，即：每周完成一个ARTS：每周至少做一个 leetcode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章，至少坚持一年。（也就是 Algorithm、Review、Tip、Share 简称ARTS）。

Algorithm

本周算法题：2.两数相加

问题描述：

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

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

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

示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

分析:

1.先定义一个简单链表结构，一个存具体数值，一个存指向的下一个结点。
2.从最低有效位开始相加，由于每位数字处于0...9的范围内，两数相加之和可能会溢出，使用变量保存进位，并带入下一次迭代。

代码：

/**
 * Definition for singly-linked list.
 */
function ListNode(val){
    this.val = val;
    this.next = null;
}
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    var dummyHead = new ListNode(0);
    var p = l1, q = l2, curr = dummyHead;
    var carry = 0;
    while(p != null || q != null){
        var x = (p != null) ? p.val : 0;
        var y = (q != null) ? q.val : 0;
        var sum = carry + x + y;
        carry = parseInt(sum / 10); // 注意取整
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if(p != null) p = p.next;
        if(q != null) q = q.next;
    }
    if(carry > 0){
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
};

复杂度分析:

• 时间复杂度：O(max(m,n))，假设m,n分别表示l1和l2的长度，上面的算法最多重复max(m,n)次。
• 空间复杂度：O(max(m,n))，新列表的长度最多为max(m,n)+1。

Review

介绍浏览器是如何工作的 http://arvindr21.github.io/howBrowserWorks

打开浏览器访问http://google.com会发生什么呢？

• 进行DNS解析
• 请求页面
• 将响应标记化
• 解析HTML
• 构件DOM树
• 构件Render树
• 布局Render树
• 绘制

DNS解析

'域名系统'（Domain Name System）。它作为将域名和IP地址互相映射的一个分布式数据库，能够使人更方便地访问互联网。

www.google.com作为一个域名就和IP地址192.168.1.2相对应。DNS就像一个自动的电话号码簿，我们可以直接拨打192.168.1.2的名字www.google.com来代替电话号码（IP地址）。DNS在我们调用网站的名字以后就会像www.google.com一样便于人类使用的名字转化成像192.168.1.2一样便于机器识别的IP地址。

DNS查询有两种方式：递归和迭代。DNS客户端设置使用DNS服务器一般都是递归服务器，它负责全权处理客户端和DNS查询请求，直到最终返回结果。而DNS服务器之间一般采用迭代查询方法。

以查询www.google.com为了例：

• 客户端发送查询报文query www.google.com至DNS服务器，DNS服务器首先检查自身缓存，如果存在记录则直接返回结果。
• 如果记录老化或者不存在，则：
  1. DNS服务器向根域名服务器发送查询报文query www.google.com，根域名服务器返回顶级域名.com的权威域名服务器地址。
  2. DNS服务器向.com域的权威域名服务器发送查询报文query www.google.com，得到二级域名.goole.com的权威域名服务器地址。
  3. DNS服务器向.google.com域的权威域名服务器发送查询报文query www.google.com，得到主机www的A记录，存入自身缓存并返回给客户端。

Tip

React Native 0.59 component的render() 如果直接返回，写成return;，会红屏报错Invariant Violation:Element type is invaild。

处理办法：render()里面返回修改为return null

Share

React Native inline require分析

配置：

// metro.config.js
module.exports = {
  transformer: {
    getTransformOptions: async () => ({
      transform: {
        experimentalImportSupport: true,
        inlineRequires: true,
      },
    }),
  },
};

测试代码：

import page3 from './src/Page3.js';
import B  from './src/B.js';
const page1 = lazyRequire('./src/Page1');
const page2 = lazyRequire('./src/Page2');

const pages = [
	{
	    component:page1,
	    name:'page1',
	    isInitialPage:true
	},
	{
	    component:page2,
	    name:'page2',
	},
	{
	    component:page3,
	    name:'page3',
	}
];

require bundle:

  var _Page = _interopRequireDefault(_$$_REQUIRE(_dependencyMap[8], "./src/Page3.js"));

  var _B = _interopRequireDefault(_$$_REQUIRE(_dependencyMap[9], "./src/B.js"));

  var page1 = (0, _crn.lazyRequire)(_dependencyMap[10], "./src/Page1");
  var page2 = (0, _crn.lazyRequire)(_dependencyMap[11], "./src/Page2");
  var pages = [{
    component: page1,
    name: 'page1',
    isInitialPage: true
  }, {
    component: page2,
    name: 'page2'
  }, {
    component: _Page.default,
    name: 'page3'
  }];

inline require bundle:

  var page1 = _$$_REQUIRE(_dependencyMap[1], "@ctrip/crn").lazyRequire(_dependencyMap[0], "./src/Page1");

  var page2 = _$$_REQUIRE(_dependencyMap[1], "@ctrip/crn").lazyRequire(_dependencyMap[2], "./src/Page2");

  var pages = [{
    component: page1,
    name: 'page1',
    isInitialPage: true
  }, {
    component: page2,
    name: 'page2'
  }, {
    component: _$$_IMPORT_DEFAULT(_dependencyMap[3], "./src/Page3.js"),
    name: 'page3'
  }];

区别：

1、import B from './src/B.js'; 在后续代码中没有使用B模块，采用inline require方式打的包直接不把B模块打进去，对应引入代码也没有。采用正常打包方式，B模块打包进去，对应也引用执行了。

2、import page3 from './src/Page3.js';在开始导入了page3模块，接着下pages数组中给component赋值使用到了。对应inline require打的包没有开始的导入模块，直接在使用到的地方进行模块加载，component: _$$_IMPORT_DEFAULT(_dependencyMap[3], "./src/Page3.js"),
对比正常打包的效果，在原先import导入模块的是就开始require加载了模块。

总结

采用inline require方式打包，可以把实际代码中没有使用的模块去除，减少size。加载模块的时机在实际真正使用到这个模块的时候，达到懒加载的效果。