20180930_ARTS_week14

Posted on 2018-09-30 in ARTS by yucongchen

第十四周，算法题 Valid Parentheses，看了一篇介绍 chrome dev tools 的文章，其中关于代码使用率的检测工具十分实用，记录 JavaScript 数组操作的小 tip，分享对于记录解决问题思路的看法。

Algorithm

/**
 * Valid Parentheses
 * https://leetcode.com/problems/valid-parentheses/description/
 * 
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    if (s == "") {
        return true;
    }

    var stack = [];
    var dict = {
        ')' : '(',
        ']' : '[',
        '}' : '{'
    }

    for (var i=0; i<s.length; i+=1) {
        if( dict[s[i]] ) { // find right silde, try to match
            var beforeItem = stack.pop();
            if ( dict[s[i]] === beforeItem) {
                continue
            }
            return false;
        } else {
            stack.push(s[i])
        }
    }

    return stack.length == 0;
};

console.log(isValid("()"))
console.log(isValid("()[]{}"))
console.log(isValid("(]"))
console.log(isValid("([)]"))
console.log(isValid("{[]}"))

这个算法就是利用了栈。

想到这个的思路是因为解的过程中，发现如果遇到左边的，需要存起来，后面可能有用（类似入栈），遇到右边的，需要比对前一个值，并且比完如果匹配就没用了（这类似出栈）。这整个就是栈的工作模式，突然就恍然大悟，用栈就好了。

中间发现有不匹配的就直接返回 false 了，最后再检查一下栈里面是否为空，空就是都匹配完了，返回 true，不然就是没匹配完，返回 false。

Review

Mastering Chrome Developer Tools: Next Level Front-End Development Techniques

https://medium.freecodecamp.org/mastering-chrome-developer-tools-next-level-front-end-development-techniques-3ac0b6fe8a3

作者介绍了 Chrome Developer Tools 中几个功能。

Dark Theme，暗黑主题，你懂的，酷酷的。
Store as global variable，可以把 console.log 打出来的变量右键存为全局变量，方便查看。
Animation Tools，这个工具应该很多都熟悉，可以调节动画各种参数，以及暂停动画。
Simulate Element Pseudo State，这个很熟悉了，就是各种 :hover :active 等。
Prettify CSS and JavaScript，对于压缩过的 js 和 css 特别好用，方便查看。
Code Coverage，这个功能我觉得最赞了，可以查看页面上 js 文件和 css 文件的使用率，对用来清理积攒的不用代码特别有参考价值。使用的时候需要 Chrome 59 版本以上，dev tools 中选择 Coverage tab，没有就调出来，和 console 在同一行的，之后单击 record 然后开始用网页，用完点完成就能看到分析结果了。

大致介绍了这几个功能，其中 Code Coverage 是我觉得最实用的，推荐你也试试。

Tip

JavaScript 中对数组做操作可以说是家常便饭，插在末尾用 push，插在开头用 unshift，插在中间用 splice。

然而这些系统提供的方法性能是不是就是最好呢？并不全是。

比如插在末尾：

var arr = [1,2,3,4,5];
var arr2 = [];

arr[arr.length] = 6;     // with an average of 5 632 856 ops/sec
arr.push(6);             // 35.64 % slower
arr2 = arr.concat([6]);  // 62.67 % slower

arr[arr.length] = 6 的方式会更快。

比如插在开头：

var arr = [1,2,3,4,5];

[0].concat(arr);    // with an average of 4 972 622 ops/sec
arr.unshift(0);     // 64.70 % slower

[0].concat(arr) 的方式会更快。

不过插在中间使用 splice 是性能最好的。

var items = ['one', 'two', 'three', 'four'];
items.splice(items.length / 2, 0, 'hello');

以上来源 http://www.jstips.co/en/javascript/insert-item-inside-an-array/

这里重点看下 unshift 方法，比较中可以看到 unshift 相比 [0].concat(arr) 的方式要慢上不少，

其原因是使用 unshift 每次添加一个元素都要在原有的数组上把已有的元素往下移一个位置，而用 concat 并不会动原来的数组，而是返回一个新的数组，计算开销小了很多，所以比较快。

这次的算法题和前面有些不同，我多记录了一些我是怎么想到这个思路的，因为最近看《暗时间》一书，里面说到记录并说清楚解题思路往往比最后的解题结果更为重要，于是我就尝试了记录思路。

不过这个思路记录的还是比较简单，因为真的梳理了一下这个流程，然后恍然大悟这里是栈的工作模式。

最近也的确体会到解题思路的重要性，常常看一本书，作者说可以怎么怎么样做，ok，我知道可以这样做，但是我更想知道是怎么找到可以这样做的。

解题思路才是线条，把一个个独立的点串联起来。

碎碎念

记录一些所思所想，写写科技与人文，写写生活状态，写写读书心得，主要是扯淡和感悟。欢迎关注，交流。

微信公众号：程序员的诗和远方

公众号ID : MonkeyCoder-Life

程序员的诗和远方

Algorithm

Review

Tip

Share

碎碎念