ARTS 第十九周（2019.8.5~2019.8.11）

[catcuts]

ARTS 第十九周（2019.8.5~2019.8.11）

• Algorithm 删除链表的倒数第N个节点
• Review 谷歌 JavaScript 代码风格规范的 13 个值得注意的要点
• Tip Nedb 在 JSON 对象数组的批量 $pull 上的问题
• Share [极客专栏] Git协同工作流，你该怎么选？

Algorithm 删除链表的倒数第N个节点

题目：

删除链表的倒数第N个节点

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    // first 和 second 分别表示第一个和第二个指针
    // last 表示指向 first 前一个节点的指针
    // 它在当需要删除的节点为最后一个节点时使用
    let last = head, first = head, second = head;
    // 先移动第二个指针，与第一个指针错开 n - 1 个节点
    // 也就是让第二个指针和第一个指针之间的节点个数为 n - 1 个
    // 比如，假设 n = 2：
    // f
    // O - O - O - O - O - O -... - O - O
    //         s
    // （last 总是指向 first 之前一个节点，故不展示）
    while(n--) {
        second = second.next;
    }
    // 错开后，再同时移动 first 和 second 指针
    // 直到 second 指针指向 null，也就是最后一个节点的下一个节点（不存在这个节点，也就是 null）
    // 延续上例，此时：
    //                              f
    // O - O - O - O - O - O -... - O - O - null
    //                                      s
    // 可以看出，此时 f 就是我们要删除的节点（倒数第 n=2 个节点）
    while(second) {
        last = first;
        first = first.next;
        second = second.next;
    }
    // 剩下的就是对目标节点的边界判断了
    // 此时目标节点就是 first 指向的节点
    if (first === head) {  // 若目标节点时首节点
        head = first.next || null;  // 首节点的下一个节点顶上作为新的首节点
        first.next = null;
    } else if (first.next) {  // 若目标节点是非首非末节点
        first.val = first.next.val;
        first.next = first.next.next;
    } else {  // 若目标节点是末节点（此时 last 派上用场）
        last.next = null;
    }
    return head;  // 最后返回首节点
};

思路：
思路见注释。
一次遍历，故时间复杂度 = O(1)；
不占用额外空间，故空间复杂度 = O(1)。
这里解释一下：
虽然代码上用了两个循环，看起来是两次遍历，
但“一次遍历”是对链表长度而言的，
也就是说，如果一个循环并没有遍历完整个列表所有元素，那就不算“一次遍历”；
所以这里我们可以看到，
两个循环对链表遍历的总元素个数为 n + L - n = L，其中 L 为链表长度
也就是两个循环的实际效果是一次遍历，达到了题目的要求。

对比：
与高分对比：
本代码运行 208 个测试用例花费约 68ms，平均一个测试用例约 0.33ms；
高分代码运行 208 个测试用例花费约 68ms，平均一个测试用例约 0.33ms。

思路一致代码略。
实际上我也是受到评论区的思路点拨才用的双指针，
不过这些思路还引入了“哑节点”，我觉得也可以不用就没有使用。

一开始我的思路是，题目要一次遍历是吧，那就把所有遍历过的节点缓存到一个 map，于是。。。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    // 定义 map
    let nodeMap = { "1": head }, curNode = head, len = 1;
    // 一次遍历
    while(curNode.next) {
        curNode = curNode.next;
        nodeMap[++len] = curNode;
    }
    // 边界处理
    if (n === len) {
        head.next = null;
        return nodeMap[2] || null;
    } else if (n === 1) {
        nodeMap[len - 1].next = null;
    } else {
        let node = nodeMap[len - n + 1];
        node.val = node.next.val;
        node.next = node.next.next;
    }
    // 返回首节点
    return head;
};

时间复杂度 O(1) 但空间复杂度 O(n)。
运行 208 个测试用例花费约 88ms，平均一个测试用例约 0.43ms；

Review 谷歌 JavaScript 代码风格规范的 13 个值得注意的要点

阅读：
13 Noteworthy Points from Google’s JavaScript Style Guide

点评：
文章对谷歌 JS 代码规范中的 13 个比较值得注意的条目进行了引用和点评：

1. 用空格代替制表符（Tab）
2. 代码末尾使用分号（;）
3. 暂时不要使用 ES6 的模块化规范（export 和 import）
4. 不建议对代码进行垂直对齐
5. 用 const 和 let 彻底代替 var（为啥呢，见拓展阅读）
6. 首选使用箭头函数，除非需要命名函数如递归时，因为它不对 this 产生任何影响
7. 使用模板字符串代替拼接字符串（好处显而易见：便于阅读而且不易出错）
8. 使用加号（+）拼接多行字符串，而不是使用反斜杠（\）来声明多行字符串（因为反斜杠兼容性不好）
9. 首选使用 for-of 来遍历数组，对于 JSON 对象可以使用 for-in（for-of 的性能与 for 相当，而且更美观）
10. 不要使用 eval()
11. 使用大写名称的变量来接收全局的常量，也就是如果一个常量是位于函数内部的局部变量则可以用小写名称变量来接收
12. 一个萝卜一个坑，一行一个变量声明（也就是不推荐用 let a, b, c, ... = xxx）
13. 使用单引号（'）代替双引号（"），若单引号中还需要单引号，则外层使用反引号（```）

对于代码规范，仁者见仁智者见智，除了 Google 规范，还有 Airbnb 规范，两套规范经常打架。

对于我们的项目，需参考已有大公司的实践，有针对性地摘取并在必要的时候扩展，以制定符合我们团队的代码规范。

拓展阅读：
Google JavaScript Style Guide
Why don’t we use var anymore?
Get around tslint: one-variable-per-declaration

Tip Nedb 在 JSON 对象数组的批量 $pull 上的问题

比如下面是一个例子，运行结果是：

测试 JSON 对象数组的批量 $push：成功
测试 JSON 对象数组的批量 $pull：错误：Unknown logical operator $in
测试非 JSON 对象数组的批量 $push：成功
Waiting for the debugger to disconnect...
测试非 JSON 对象数组的批量 $pull：成功

准备提个 issue 但不指望能得到解决因为 Nedb 似乎不被维护很久了。。。
我们项目用它主要是历史遗留，后面会更换成 MongoDB
但也不排除在一些嵌入式产品上继续使用 Nedb

const data = [
    {
        _id: 'id1',
        planets: [
            { name: 'Mars', system: 'solar', inhabited: false },
            { name: 'Earth', system: 'solar', inhabited: true },
            { name: 'Jupiter', system: 'solar', inhabited: false },
            { name: 'Omicron Persia 8', system: 'futurama', inhabited: true }
        ],
        planetNames: [
            'Mars',
            'Earth',
            'Jupiter',
            'Omicron Persia 8'
        ]
    }
]

const Datastore = require('nedb'),
    db = new Datastore({ filename: './test_nedb_pull_push.dat', autoload: true });

db.remove({}, { multi: true }, (err, numRemoved) => {
    db.insert(data, async (err, newDocs) => {

        // 测试 JSON 对象数组的批量 $push 和 $pull
        await new Promise((resolve, reject) => {
            let newPlanets = [
                { name: 'Omicron Persia 8', system: 'futurama', inhabited: true },
                { name: 'Pluto', system: 'solar', inhabited: false, distance: 37 }
            ];
            let planetsToBeRemoved = [
                { name: 'Mars' },
                { name: 'Earth' },
            ]
            db.update(
                { _id: 'id1' },
                { $push: { 'planets': { $each: newPlanets } } },
                { returnUpdatedDocs: true },
                (err, numAffected, updatedDocs) => {
                    let message = err ? `错误：${err.message}` : '成功'
                    console.log(`测试 JSON 对象数组的批量 $push：${message}`);
                    db.update(
                        { _id: 'id1' },
                        { $pull: { 'planets': { $in: planetsToBeRemoved } } },
                        { returnUpdatedDocs: true },
                        (err, numAffected, updatedDocs) => {
                            let message = err ? `错误：${err.message}` : '成功'
                            console.log(`测试 JSON 对象数组的批量 $pull：${message}`);
                            resolve();
                        }
                    )
            });
        });

        // 测试非 JSON 对象数组的批量 $push 和 $pull
        await new Promise((resolve, reject) => {
            let newPlanetNames = [
                'Omicron Persia 8',
                'Pluto',
            ];
            let planetNamesToBeRemoved = [
                'Mars',
                'Earth',
            ]
            db.update(
                { _id: 'id1' },
                { $push: { 'planetNames': { $each: newPlanetNames } } },
                { returnUpdatedDocs: true },
                (err, numAffected, updatedDocs) => {
                    let message = err ? `错误：${err.message}` : '成功'
                    console.log(`测试非 JSON 对象数组的批量 $push：${message}`);
                    db.update(
                        { _id: 'id1' },
                        { $pull: { 'planetNames': { $in: planetNamesToBeRemoved } } },
                        { returnUpdatedDocs: true },
                        (err, numAffected, updatedDocs) => {
                            let message = err ? `错误：${err.message}` : '成功'
                            console.log(`测试非 JSON 对象数组的批量 $pull：${message}`);
                            resolve();
                        }
                    )
            });
        })
    });
});

Share [极客专栏] Git协同工作流，你该怎么选？

分享一篇极客“左耳听风”专栏文章（据说可限10位免费阅读哦）
20 | Git协同工作流，你该怎么选？