ARTS 第二十周（2019.11.11~2019.11.17）

[catcuts]

ARTS 第二十周（2019.11.11~2019.11.17）

• Algorithm 只出现一次的数字 II（中等难度）
• Review 使用 JavaScript Map（非 JSON） 对象存储键值对
• Tip Windows 批处理中路径的空格
• Share [极客专栏：设计模式之美] 07 | 哪些代码设计看似是面向对象，实际是面向过程的？

Algorithm 只出现一次的数字 II（中等难度）

题目

只出现一次的数字 II（中等难度）

解法参考的是 只出现一次的数字 II （数字电路设计思想）

该解法采用数字电路设计的思路，设计了一个运算符（或加法逻辑），
使三个相同的数字运算后得到 0，于是运算的最后结果就是这个只出现一次的数字。
从而达到了时间复杂度和空间复杂度都为 O(1) 的要求。

在思考过程中，自己也想到要使用这么一个运算符，但是没想到用数字电路设计的方法来实现。
（自己是电气工程专业的，也学过数字电路设计，然而太久没用了一时间没想到。。）

这里放出参考代码，思路我参照参考自己重演了一遍。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let a = 0, b = 0, temp = 0;
    for (let num of nums) {
        temp = (b & num) | (a & ~num);
        b = (~a & ~b & num) | (b & ~num);
        a = temp;
    }
    return b;
};

执行结果：通过
执行用时：64 ms，在所有 javascript 提交中击败了 95.32% 的用户
内存消耗：36.4 MB，在所有 javascript 提交中击败了 46.25% 的用户

思路：
一种思路是，找到一个逻辑，使得三个相同的数字在这个逻辑的运算下结果为 0，
并且这个逻辑满足交换律，从而最终留下的就是我们所求的只出现一次的数字。

这样一种逻辑可以转化为设计一个不进位的三进制加法器，
因为不进位三进制加法器中，执行三次加法 0 + 1 + 1 + 1 = 0。

又因为三进制数字需要用 2 个 bit 来表示，而加数 1 则用 1 个 bit 表示，
所以可以得到真值表或转换方程如下：
其中：

• a 和 b 分别用于表示三进制的 2 位，c 表示加数
• a' 和 b' 分别表示加数之后的结果

a	b	c	a'	b'
0	0	1	0	1
0	1	1	1	0
1	0	1	0	0
0	0	0	0	0
0	1	0	0	1
1	0	0	1	0

（因为是三进制，所以剩下的状态 11 不用关心）

那么可以得到 a' 和 b' 的卡诺图如下：

a'
 \________________________
 | ab | 00 | 01 | 11 | 10 |
 |_c__|____|____|____|____|
 | 0  | 0  | 0  |( x | 1 )|
 |____|____|____|____|____|
 | 1  | 0  |( 1 | x )| 0  |
 |____|____|____|____|____|
 
 b'
 \________________________
 | ab | 00 | 01 | 11 | 10 |
 |_c__|____|____|____|____|
 | 0  | 0  |(1  | x )| 0  |
 |____|____|____|____|____|
 | 1  |(1  | 0 )| x  | 0  |
 |____|____|____|____|____|

画圈后，得到表达式：
（图中以括号表示圈，式中以~表示非）

• a' = a(~c) + bc
• b' = b(~c) + (~a)c

所以一次次的迭代后，最终的结果是：a'b' + x = 01
其中 a'b' = 0，x 为所求，即 01，也就是 b'
所以最后返回 b' 即为结果。

对比：
与高分对比：
本代码运行 11 个测试用例花费约 64ms，平均一个测试用例约 5.82ms；
高分代码运行 11 个测试用例花费约 64ms，平均一个测试用例约 5.82ms。
最高分代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let m = 0, n = 0;
    for(let i = 0; i < nums.length; i++) {
        m = m ^ nums[i] & ~n;
        n = n ^ nums[i] & ~m;
    }
    return m;
};

Review 使用 JavaScript Map（非 JSON） 对象存储键值对

阅读：
Storing Key-Value Pairs With JavaScript Maps

点评：
本文介绍并展示了如何使用 JavaScript Map 对象来保存、索引、修改、删除键值对。

Map 对象与 JSON 对象的区别在于：

• Map 对象存储的键可以是任意数据类型，
  而 JSON 对象存储的键只能是字符串类型。
  因此 Map 对象对键的索引采取严格匹配的模式（0 !== "0"）

• Map 对象是一个 Iterator 对象，
  可以直接使用 for...of 和 forEach 遍历，
  也可以使用对象展开符（...）
  而 JSON 对象不行。
  比如：

    for (let [key, value] of numMap) {
        console.log(`${key} - ${value}`);
    }

  又如：

    // 其中后者存储的键值对会混合覆盖前者存储的键值对
    const combinedArray = [...numMap1, ...numMap2, ...numMap3];
    const combinedNumMap = new Map(combinedArray);

• Map 对象的 size 属性可以直接获得键值对的个数，
  而 JSON 对象需要用 Object.keys() 转换后取其 length 属性

• Map 对象保存的键名称不会与其原型链上的属性键名冲突，
  而 JSON 对象则存在这种问题。
  比如：

    let o = {};
    o.constructor = 666;  // 覆盖了对象的构造函数
    let m = new Map();
    m.set('constructor', 666);  // 没有覆盖 Map 对象的构造函数

创建一个 Map 对象保存键值对：

const arrayOfKeysAndValues = [
  ['a', 1],
  ['b', 2],
  ['c', 3],
  ['d', 4],
  ['e', 5],
  ['f', 6],
  ['g', 7],
  [8, 'h'],
  [9, 'i'],
  [10, 'j'],
  [11, 'k'],
  [12, 'l'],
  [13, 'm'],
  [14, 'n'],
  [15, 'o'],
]
let numMap = new Map(arrayOfKeysAndValues);

从一个 Map 对象中索引键对应的值：

numMap.get('a');  // 1
numMap.get('8');  // undefined
numMap.get(8);    // "h"

修改一个 Map 对象中某个键对应的值：

numMap.set('a', 666);  // numMap
numMap.set(999, 666);  // numMap

从一个 Map 对象中删除一个键值对：

numMap.delete(15);  // true
numMap.delete(15);  // false

参考阅读：
JavaScript 标准内置对象 Map - MDN Web docs

Tip Windows 批处理中路径的空格

Windows 批处理中，当某条语句依赖的文件（夹）路径包含空格时，

需要对包含空格的这一段路径用双引号引起来，否则可能无法正确识别。

如：node D:\Program Files (x86)\start.js

应改为：node D:\"Program Files (x86)"\start.js

注意不能改为：node "D:\Program Files (x86)\start.js"

Share [极客专栏：设计模式之美] 07 | 哪些代码设计看似是面向对象，实际是面向过程的？

分享一篇极客专栏《设计模式之美》
07 | 理论四：哪些代码设计看似是面向对象，实际是面向过程的？

总的来说，使用面向对象风格编写的面向过程代码有如下特点：

1. 使用了类，但是
2. 要么完全没有封装（比如数据和操作分离的贫血模式）
3. 要么破坏了封装（比如滥用 getter 或 setter）
4. 要么完全没有抽象（大而全的 Constants 或 Utils 类）
5. 要么封装或抽象不完全（比如类实例化后，或者子类继承后，需要自己管理其内部某些属性或状态）

平时应该多留心代码是否存在上述特征。

文中没有举封装或抽象不完全的例子，这里举一个。

比如一个实现某种业务需求（如与某种类型设备通讯的应用协议）的 tcp 或 udp 服务器；

实例化后还需要自己管理其协议相关的就绪状态（ready属性）；使你不得不对其再封装一层，并抽象其连接、断开等方法使其自动进行就绪状态的管理；

每个继承都这么封装一遍，就会有大量重复的代码，而且其实类的实例化者或继承者并不需要也不应该关心就绪状态的管理，所以没有达到就绪状态管理的封装。

这就是一种不完全的封装。