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 条评论
登录 后参与评论

相关文章

来自专栏安恒网络空间安全讲武堂

护网杯REFINAL——write up

根据前面的一些信息,判断出长度为0x30,经过如下设置,我们可以很快开始进行动态调试。

1552
来自专栏WindCoder

异步JavaScript:从回调地狱到异步和等待

这是一个典型的异步编程挑战,您如何选择处理异步调用,在很大程度上,会导致或破坏您的应用程序,并且可能是您的整个启动。

5661
来自专栏java一日一条

如何写出漂亮的 React 组件

在Walmart Labs的产品开发中,我们进行了大量的Code Review工作,这也保证了我有机会从很多优秀的工程师的代码中学习他们的代码风格与样式。在这篇...

1183
来自专栏腾讯IVWEB团队的专栏

响应式编程中 Stream 对象的实现原理

这篇文章介绍一种编程泛型,叫做响应式编程。将响应式称作“编程泛型”可能有些夸大其作用范畴,不过通过引入响应式确实会改变我们对特定问题的思考方法,就像刚接触red...

5140
来自专栏GreenLeaves

C# 多线程五之Task(任务)

为什么MS要推出Task,而不推Thread和ThreadPool,以下是我的见解:

1931
来自专栏有趣的Python和你

千里之行,始于足下变量字符串

1003
来自专栏听雨堂

数据库范式

关系数据库设计之时是要遵守一定的规则的。尤其是数据库设计范式 现简单介绍1NF(第一范式),2NF(第二范式),3NF(第三范式)和BCNF,另有第四范式和第五...

1936
来自专栏racaljk

关于llvm kaleidoscope: 记一次Debug血泪之路

简而言之,慎(bu)用(yong)全局变量!                                

1231
来自专栏牛客网

51信用卡前端凉面

1720
来自专栏前端知识分享

Angular中ui-grid的使用详解

  在项目开发的过程中,产品经理往往会提出各种需求,以提高用户体验。最近,项目中用到的表格特别多,而且表格的列数和行数也超多。为了让用户浏览更爽,产品经理提出,...

1842

扫码关注云+社区

领取腾讯云代金券