20180930_ARTS_week14

第十四周,算法题 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 并不会动原来的数组,而是返回一个新的数组,计算开销小了很多,所以比较快。

Share

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

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

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

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


碎碎念

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CSS3动画-抛物线运动

    今天来说下CSS3动画,目标是让一个方块做抛物线运动。主要用到的CSS3属性有animation,transform,@keyframes,transition...

    Bob.Chen
  • 20180708_ARTS_week02

    Add Two Numbers You are given two non-empty linked lists representing two non-ne...

    Bob.Chen
  • 20180902_ARTS_week10

    这周因为有些事情忙,挑了条 easy 难度的题。整个思路比较简单,算面积嘛,然后左右两边分别有两个游标,哪个低了哪个就往中间移动一格。复杂度 O(n)。

    Bob.Chen
  • 小述JavaScript数组的增删改查

    操作数组一直以来都是很头疼的问题,特别是我这样的比较菜的码农,我个人是很排斥数组这个东西的,但是很多的时候不用数组还是不行的,毕竟很多的数据只靠一个变量是远远不...

    何处锦绣不灰堆
  • 数组中的方法

    河湾欢儿
  • JavaScript 数组纯函数

    forEach 遍历所有元素,item 对应的是元素的值,index 对应的是元素的位置

    Nian糕
  • PHP To Go 转型手记 (二)

    作为一名PHP程序员,我感到荣幸。但在时代不断的变迁中,要具备足够的知识才可生存。

    CrazyCodes
  • JavaScript中的这些骚操作,你都知道吗?

    写这篇文章的缘由是上周在公司前端团队的code review时,看了一个实习小哥哥的代码后,感觉一些刚入行不久的同学,对于真实项目中的一些js处理不是很熟练,缺...

    前端森林
  • 算法系列(三)

      那么接下来就是选择排序:   选择排序就是先选数组中最大的一个,再选剩下中的最大一个,如此反复直到最后一个,其思想就是平时我们的一般正常的排序思想。 接下来...

    欢醉
  • Java冒泡排序法升级版

    指尖改变世界

扫码关注云+社区

领取腾讯云代金券