Arts 第二十四周(8/26 ~ 9/1)

106 阅读9分钟

ARTS是什么?
Algorithm:每周至少做一个leetcode的算法题;
Review:阅读并点评至少一篇英文技术文章;
Tip:学习至少一个技术技巧;
Share:分享一篇有观点和思考的技术文章。

Algorithm

LeetCode 864. Shortest Path to Get All Keys

题目解析

非常有意思的一道搜索问题,在一个矩阵内,给定初始点,要你取得图中所有的钥匙,并输出取得所有钥匙所需要的 最小步数,门只有对应的钥匙才能开,另外图中还会有墙阻断路线。看到最小步数,脑袋里面马上反应是使用 广度优先搜索。之前说过,其实我们可以把矩阵看成是一个图,矩阵中的对应的位置就是图上的节点,每个位置和其上下左右四个位置相连,这样图上的边也就有了。

难点在于细节的把控上面,还有就是你怎么解决 “对应钥匙开对应门”,我们来看看下面这个例子:

. . . . . . . . . . B
. . . . # . . . . . .
. @ . A b # . . . . a
. . . . # . . . . . .

对于图上的遍历,不管是使用深度优先搜索,还是使用广度优先搜索,我们都会使用一个数据结构用来记录我们走过的点,根据具体的要求,这个数据结构可以是数组,也可以是 Set,目的是防止走之前的老路,如果没有这样一个数据结构,程序会无休止地运行下去。但是你看到上面的例子,我们必须去到远处拿到钥匙 a 之后,我们才可以拿钥匙 b,你会发现如果要遵循 “访问过的节点不能再继续访问” 这么一个要求,那么我们的实现思路在这里会遇到阻碍。一开始,遇到这个问题,我使用了一些数据结构去记录门还有点和点的距离,最后发现设计太复杂,程序没法写下去了。看到 discuss 里面有一个思路非常好,我们判断一个点是不是被访问过,不仅仅看其二维坐标,还要看第三维的东西,这里的第三维的东西就是钥匙,如果我们之前到一个位置上面只拿了两把钥匙,这时我们手里有三把钥匙,那么我们依然可以到这个位置上面去,钥匙在这里就好像是第三维的坐标一样。

因为题目里面说到最多只会出现 6 把钥匙,对于每把钥匙只有两种状态,获得和没有获得,这里还有一个技巧就是用一个整数去表示当前我们获得的钥匙,再次体会到了位运算的强大之处,发现如果一类东西的可能的个数并不是特别大,并且每个东西只有两种状态的时候,可以考虑使用整形去表示,并用位运算进行处理


参考代码

private class Pair {
    int x, y, steps, keys;
    Pair(int x, int y, int steps, int keys) {
        this.x = x;
        this.y = y;
        this.steps = steps;
        this.keys = keys;
    }
    
    @Override
    public boolean equals(Object obj) {
        Pair o = (Pair)obj;
        if (this == o) {
            return true;
        }
        
        return (this.x == o.x && this.y == o.y && this.keys == o.keys);
    }
    
    @Override
    public int hashCode () {
        return x * 100 + y * 10 + keys;
    }
}

private int[] dirX = {0, 0, -1, 1};
private int[] dirY = {-1, 1, 0, 0};

public int shortestPathAllKeys(String[] grid) {
    if (grid == null || grid.length == 0 || grid[0].equals("")) {
        return -1;
    }
    
    int m = grid.length, n = grid[0].length();
    
    Queue<Pair> queue = new LinkedList<>();
    
    Set<Pair> visited = new HashSet<>();
    
    int totalKeysNum = 0;
    
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            char cur = grid[i].charAt(j);
            if (cur >= 'a' && cur <= 'f') {
                totalKeysNum++;
            }
            
            if (cur == '@') {
                Pair startPoint = new Pair(i, j, 0, 0);
                queue.offer(startPoint);
                visited.add(startPoint);
            }
        }
    }

    while (!queue.isEmpty()) {
        Pair cur = queue.poll();

        if (cur.keys == (1 << totalKeysNum) - 1) {
            return cur.steps;
        }
        
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.x + dirX[i];
            int nextY = cur.y + dirY[i];
            
            if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) {
                continue;
            }
            
            char c = grid[nextX].charAt(nextY);
            
            Pair nextInfo = new Pair(nextX, nextY, cur.steps + 1, cur.keys);

            if (c == '#' || (c >= 'A' && c <= 'F' && ((cur.keys >> c - 'A') & 1) == 0)) {
                continue;
            }
            
            if (visited.contains(nextInfo)) {
                continue;
            }
            
            if (c >= 'a' && c <= 'f') {
                nextInfo.keys |= (1 << c - 'a');
            }
            
            queue.offer(nextInfo);
            visited.add(nextInfo);
        }
    }
    
    return -1;
}

Review

7 Reasons Why JavaScript Async/Await Is Better Than Plain Promises (Tutorial)

经常使用 node 的人,应该对 async/await 不会陌生,虽然它只是 JavaScript 中的一个语法糖,背后的实现依然是 Promise,但是相比于 Promise,它还是有很多的过人之处。这其实就和 JSX 是一样的,在 react 中虽然你可以使用函数调用的方式去写 HTML,但是 JSX 的出现会让程序的可读性增加不少。这篇文章讲述了 async/await 的几点过人之处:

  • 让代码更加的简洁,使用过 Promise 的人都会知道,对于稍微复杂一点的逻辑,Promise 实现起来需要依靠 then 函数级联和嵌套传递变量,这么一来会让代码的可读性降低,但是 async/await 的出现改变了这一点,你不需要使用 then,只需要在异步运行的代码的前面加上 await 即可。
  • 相对于 Promise,async/await 的错误处理会更加的直接和简洁,普通的 try...catch 包裹并不能检测 Promise 里面的异常。Promise 的异常处理需要使用 .catch() 函数,当级联和嵌套非常多的时候,出现错误我们也很难定位错误,而 async/await 的话,普通的 try...catch 依然有效,这其实最符合我们对程序代码的直观认识。
  • async/await 不仅对异步代码有效,对于同步执行的代码,使用 async/await 也不会受到任何的影响,这个有什么用呢?现在 NPM 上面的开源库函数非常的多,有些库函数是异步执行的,有些则是同步,当你调用这些库函数的时候,你可能并不知道这个函数是异步执行的还是同步执行的,如果是异步执行的函数,它是会返回 promise,这时你可以对 promise 进行 .then() 之类的操作,但是如果是同步函数的话,你直接使用 .then() 是会报错的,你还必须将其转换成 promise 类型。async/await 完美解决了这个问题,不管是同步还是异步,async/await 都预先会将其转成 promise 的形式,并达到同步的效果,你需要做的事情其实就是在需要调用的函数前面加上 async/await 即可。

但是这里我想说的是 async/await 是很好用,但是 Promise 也不能被完全舍弃,在有些情况下我们还是得借助 Promise 里面的函数,比如需要执行一组不相干的函数,我们可以使用 Promise.all(),这样可以大大缩短程序运行的时间。遇到具体的问题依然要具体分析,不能过分依赖某项技术,平时的思考以及好奇心才是兴趣和能力提升的关键


Tip

这周依旧积累了不少关于 JavaScript 的知识,首先是关于 JavaScript 的上下文环境变量的:

  • JavaScript 中只有 全局上下文函数上下文eval 函数上下文
  • 上下文变量是存在栈当中,上下文变量在栈中的位置是由函数的位置决定
  • 在执行上下文变量中有四个重要的东西
    • 词法环境 - 使用 const 和 let 定义的东西
    • 变量环境 - 使用 var 定义的东西
    • this 变量
    • 表示外部环境的变量
  • 使用 const 和 let 的时候,如果使用在声明之前,会导致 暂时性死区(Temporal dead zone),另外就是 暂时性死区会导致 typeof 不再是一个安全的操作,总之记住先声明,再使用
  • JavaScript 是通过 词法作用域链 去寻找变量的,词法作用域链是由代码声明的位置决定的,它是静态作用域链,在代码阶段就决定好了,和函数怎么调用没有关系
  • 根据词法作用域,内部函数可以访问外部函数声明的变量,当通过调用一个外部函数返回一个内部函数后,即使外部函数调用结束了,但是内部函数引用外部函数的变量依然保存在内存中,我们把这些变量的集合称之为闭包,JavaScript 引擎会依照 当前执行上下文 -> 闭包 -> 外部词法作用域 的顺序来查找变量
  • 函数闭包如果作为全局变量,那么它会一直存在;可以考虑将函数闭包在局部内使用,这样可以避免不必要的内存泄漏

另外就是 JavaScript 中的 this 变量:

  • 和执行上下文一样,this 也分为 3 种,全局中的 this,函数中的 this,以及 eval 函数中的 this
  • 全局上下文中的 this 指向的是 window 变量,如果函数中的 this 不进行绑定的话,也指向的是 window 变量,有 3 种方式绑定函数中的 this:
    • 使用 call、apply、bind 函数进行绑定,这 3 个函数在使用上面稍有区别,可以参考下面的例子:
      let obj = { number: 3 };
      let addTogether = function(a, b, c){
       return this.number + a + b + c;
      };
      
      // call
      console.log(addTogether.call(obj, 1,4,6));  // 14
      
      // apply
      console.log(addTogether.apply(obj, [1,4,6]); // 14
      
      // bind
      console.log(addTogether.bind(obj, 1,4,6)()); // 14
      // or
      console.log(addTogether.bind(obj)(1, 4, 6)); // 14
      
    • 使用对象调用其内部的一个方法,这个方法中的 this 会指向对象本身
    • 通过构造函数来设置
  • 嵌套函数中的 this 并不会继承其外部函数中的 this,这其实是 JavaScript 中的一个设计缺陷,解决这个问题有两种方法:
    • 使用箭头函数,箭头函数区别于一般的函数,其并不会创建单独的执行上下文变量
    • 在外层函数中,将外层函数的 this 变量赋值给其他的变量,在嵌套函数中通过词法作用域链来访问获得

Share

这周在 medium 上面发表了自己的第一篇英文文章,相对中文,感觉英文表达起来还是比较地生疏,希望自己以后多加练习

“this” in JavaScript