面试中常见算法问题详解,一个整数是否是

JavaScript 面试中常见算法问题详解

2017/02/20 · JavaScript · 1 评论 · 算法

原文出处: 王下邀月熊_Chevalier   

JavaScript 面试中常见算法问题详解 翻译自 Interview Algorithm Questions in Javascript() {…} 从属于笔者的 Web 前端入门与工程实践。下文提到的很多问题从算法角度并不一定要么困难,不过用 JavaScript 内置的 API 来完成还是需要一番考量的。

Chrome控制台 如何调试Javascript

2015/01/12 · JavaScript · Chrome

原文出处: ctriphire   

上面的文章已经大致介绍了一下console对象具体有哪些方面以及基本的应用,下面简单介绍一下如何利用好chrome控制台这个神器好好调试javascript代码(这个才是我们真正能用到实处的地方)

1、先说一下源码定位

大家打开测试网页   看到页面右下方有一个推荐的图标吗?右击推荐图标,选择审查元素,打开谷歌控制台,如下图所示

图片 1

我们现在想知道votePost方法到底在哪?跟着我这样做,在Console面板里面输入votePost然后回车

图片 2

直接点击上图标红的链接,控制台将定位到Sources面板中,展示如下图所示

图片 3

大家看了上面这个图片之后估计头都要晕了吧,这么多js都整在一行,让人怎么看呀,不用担心,按下图操作即可(也就是点击中间面板左下方的Pretty print就行了)

图片 4

这时我们再回到Console面板时会惊奇的发现原来的链接后面的1现在变成91了(其实这里的数字1或者91就是代表votePost方法在源码中的行号 )现在看出Pretty print按钮的强大之处了吧

知道了怎么样查看某一个按钮的源码,那接下来的工作便是调试了,调试第一步需要做的便是设置断点,其实设置断点很简单,点击一下上图所示的92即可,这时你会发现92行号旁边会多了一个图标,这里解释一下为什么不在91处设置断点,你可以试下,事实上根本就没法在91处上设置断点,因为它是函数的定义处,所以没法在此设置断点。

图片 5

设置好了断点后,你就会在右边Breakpoints方框里看到刚刚设置的断点。

我们先来介绍一下用到的调试快捷键吧(事实上我们也可以不用下表所示的快捷键,直接点击上图所示右侧栏最上层的一排按钮来进行调试,具体用哪个按钮,把鼠标放到按钮上方一会就会显示它相应的提示)

 

快捷键 功能
F8 恢复运行
F10 步过,遇到自定义函数也当成一个语句执行,而不会进入函数内部
F11 步入,遇到自定义函数就跟入到函数内部
Shift + F11 步出,跳出当前自定义函数

其中值得一提的是,当我们点击“推荐”按钮进行调试的时候会发现,不管我们是按的F10进行调试还是按F11进行逐步调试,都没法进行$.ajax函数内部,即使我们在函数内部设置了断点也没有办法进入,这里按F8才是真正起效果的,不信你试试。

当我们在调试的时候,右侧Scope Variables里面会显示当前作用域以及他的父级作用域,以及闭包。你不仅能在右侧 Scope Variables(变量作用域) 一栏处看到当前变量,而且还能把鼠标直接移到任意变量上,就可以查看该变量的值。

用图说话(哈哈)

图片 6

 

刚刚我们介绍的只是在html里面能够看得到它绑定了onclick事件,这样我们就找到它绑定的js函数,如果它是在jQuery页面加载完成函数里面绑定的,这时候我们怎么知道它绑定的是哪个js函数呢,如果我们不知道绑定的js函数就更加不用说调试进去了

下面介绍一下如何查看,还是以刚刚那个测试网页为例子吧,但是这次我们来看“提交评论”作说明吧,

右击“提交评论”–>审核元素,我们可以清楚的看到在这个按钮上未绑定任何事件。在Console面板内输入如下代码

JavaScript

function lookEvents (elem) { return $.data ? $.data( elem, "events", undefined, true ) : $._data( elem, "events" ); } var event = lookEvents($("#btn_comment_submit")[0]); // 获取绑定的事件

1
2
3
4
function lookEvents (elem) {
    return $.data ? $.data( elem, "events", undefined, true ) : $._data( elem, "events" );
}
var event = lookEvents($("#btn_comment_submit")[0]); // 获取绑定的事件

如下图所示:

图片 7

按照上述介绍的方法定位到具体的blog-common.js里面,找到postComment  然后一层层的找到具体的代码,再设置断点就好了。

最后介绍一下一个神器,很好用的debugger

如果你自己写的代码,你执行的时候想让它在某一处停下来,只要写上的debugger就好了,不信你试试!哈哈

赞 1 收藏 评论

图片 8

别人家的面试题:一个整数是否是“4”的N次幂

2016/05/30 · 基础技术 · 2 评论 · 算法

本文作者: 伯乐在线 - 十年踪迹 。未经作者许可,禁止转载!
欢迎加入伯乐在线 专栏作者。

这是 leetcode.com 的第二篇。与上一篇一样,我们讨论一道相对简单的问题,因为学习总讲究循序渐进。而且,就算是简单的问题,追求算法的极致的话,其中也是有大学问的。

JavaScript Specification

“4”的整数次幂

给定一个32位有符号整数(32 bit signed integer),写一个函数,检查这个整数是否是“4”的N次幂,这里的N是非负整数。

例如:

  • 给定 num = 16,返回 true,因为 16 = 42
  • 给定 num = 5,返回 flase

附加条件: 你能够不用循环和递归吗?

阐述下 JavaScript 中的变量提升

所谓提升,顾名思义即是 JavaScript 会将所有的声明提升到当前作用域的顶部。这也就意味着我们可以在某个变量声明前就使用该变量,不过虽然 JavaScript 会将声明提升到顶部,但是并不会执行真的初始化过程。

解题思路

如果忽略“附加条件”,这题还挺简单的对吧?简直是信手拈来:

版本1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num /= 4; } return num === 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
        num /= 4;
    }
    return num === 1;
}

版本1 好像很简单、很强大的样子,它的时间复杂度是 log4N。有同学说,还可以做一些微小的改动:

版本1.1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num >>>= 2; } return num === 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
      num >>>= 2;
    }
    return num === 1;
}

上面的代码用位移替代除法,在其他语言中更快,鉴于 JS 通常情况下非常坑的位运算操作,不一定速度能变快。

好了,最关键的是,不管是 版本1 还是 版本1.1 似乎都不满足我们前面提到的“附加条件”,即不使用循环和递归,或者说,我们需要寻找 O(1) 的解法。

按照惯例,大家先思考10秒钟,然后往下看 ——


阐述下 use strict; 的作用

use strict; 顾名思义也就是 JavaScript 会在所谓严格模式下执行,其一个主要的优势在于能够强制开发者避免使用未声明的变量。对于老版本的浏览器或者执行引擎则会自动忽略该指令。

JavaScript

// Example of strict mode "use strict"; catchThemAll(); function catchThemAll() { x = 3.14; // Error will be thrown return x * x; }

1
2
3
4
5
6
7
8
// Example of strict mode
"use strict";
 
catchThemAll();
function catchThemAll() {
  x = 3.14; // Error will be thrown
  return x * x;
}

不用循环和递归

其实这道题真心有好多种思路,计算指数之类的对数学系学霸们完全不是问题嘛:

版本2

JavaScript

const log4 = Math.log(4); function isPowerOfFour(num){ var n = Math.log(num) / log4; return n === (0|n); }

1
2
3
4
5
const log4 = Math.log(4);
function isPowerOfFour(num){
    var n = Math.log(num) / log4;
    return n === (0|n);
}

嗯,通过对数公式 logm(n) = log(n) / log(m) 求出指数,然后判断指数是不是一个整数,这样就可以不用循环和递归解决问题。而且,还要注意细节,可以将 log4 当做常量抽取出来,这样不用每次都重复计算,果然是学霸范儿。

不过呢,利用 Math.log 方法也算是某种意义上的犯规吧,有没有不用数学函数,用原生方法来解决呢?

当然有了!而且还不止一种,大家可以继续想30秒,要至少想出一种哦 ——


解释下什么是 Event Bubbling 以及如何避免

Event Bubbling 即指某个事件不仅会触发当前元素,还会以嵌套顺序传递到父元素中。直观而言就是对于某个子元素的点击事件同样会被父元素的点击事件处理器捕获。避免 Event Bubbling 的方式可以使用event.stopPropagation() 或者 IE 9 以下使用event.cancelBubble

不用内置函数

这个问题的关键思路和上一道题类似,先考虑“4”的幂的二进制表示:

  • 40 = 1B
  • 41 = 100B
  • 42 = 10000B
  • 43 = 1000000B
  • ……

也就是每个数比上一个数的二进制后面多两个零嘛。最重要的是,“4”的幂的二进制数只有 1 个“1”。如果仔细阅读过上一篇,你就会知道,判断一个二进制数只有 1 个“1”,只需要:

JavaScript

(num & num - 1) === 0

1
(num & num - 1) === 0

但是,二进制数只有 1 个“1”只是“4”的幂的必要非充分条件,因为“2”的奇数次幂也只有 1 个“1”。所以,我们还需要附加的判断:

JavaScript

(num & num - 1) === 0 && (num & 0xAAAAAAAA) === 0

1
(num & num - 1) === 0 && (num & 0xAAAAAAAA) === 0

为什么是 num & 0xAAAAAAAA === 0? 因为这个确保 num 的二进制的那个 “1” 出现在“奇数位”上,也就确保了这个数确实是“4”的幂,而不仅仅只是“2”的幂。

最后,我们得到完整的版本:

版本3

JavaScript

function isPowerOfFour(num) { return num > 0 && (num & (num-1)) === 0 && (num & 0xAAAAAAAA) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    return num > 0 && (num & (num-1)) === 0
                   && (num & 0xAAAAAAAA) === 0;
};

上面的代码需要加上 num > 0,是因为 0 要排除在外,否则 (0 & -1) === 0 也是 true


== 与 === 的区别是什么

=== 也就是所谓的严格比较,关键的区别在于=== 会同时比较类型与值,而不是仅比较值。

JavaScript

// Example of comparators 0 == false; // true 0 === false; // false 2 == '2'; // true 2 === '2'; // false

1
2
3
4
5
6
// Example of comparators
0 == false; // true
0 === false; // false
 
2 == '2'; // true
2 === '2'; // false

其他版本

上面的版本已经符合了我们的需求,时间复杂度是 O(1),不用循环和递归。

此外,我们还可以有其他的版本,它们严格来说有的还是“犯规”,但是我们还是可以学习一下这些思路:

版本4:用 Math.sqrt

JavaScript

function isPowerOfFour(num) { num = Math.sqrt(num); return num > 0 && num === (0|num) && (num & (num-1)) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    num = Math.sqrt(num);
    return num > 0 && num === (0|num) && (num & (num-1)) === 0;
};

版本5:用正则表达式

JavaScript

function isPowerOfFour(num) { return /^1(00)*$/g.test(num.toString(2)); };

1
2
3
function isPowerOfFour(num) {
    return /^1(00)*$/g.test(num.toString(2));
};

以上就是所有的内容,这道题有非常多种思路,相当有趣,也比较考验基本功。如果你有自己的思路,可以留言参与讨论。

下一期我们讨论另外一道题,这道题比这两道题要难一些,但也更有趣:给定一个正整数 n,将它拆成至少两个正整数之和,对拆出的正整数求乘积,返回能够得到的乘积最大的结果

想一想你的解法是什么?你能够尽可能减少算法的时间复杂度吗?期待你的答案~~

打赏支持我写出更多好文章,谢谢!

打赏作者

解释下 null 与 undefined 的区别

JavaScript 中,null 是一个可以被分配的值,设置为 null 的变量意味着其无值。而 undefined 则代表着某个变量虽然声明了但是尚未进行过任何赋值。

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

图片 9 图片 10

1 赞 7 收藏 2 评论

解释下 Prototypal Inheritance 与 Classical Inheritance 的区别

在类继承中,类是不可变的,不同的语言中对于多继承的支持也不一样,有些语言中还支持接口、final、abstract 的概念。而原型继承则更为灵活,原型本身是可以可变的,并且对象可能继承自多个原型。

关于作者:十年踪迹

图片 11

月影,奇舞团团长,热爱前端开发,JavaScript 程序猿一枚,能写代码也能打杂卖萌说段子。 个人主页 · 我的文章 · 14 ·     

图片 12

数组

本文由澳门新葡亰平台官网发布于web前端,转载请注明出处:面试中常见算法问题详解,一个整数是否是

TAG标签:
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。