澳门威利斯人_威利斯人娱乐「手机版」

来自 澳门威利斯人 2019-04-23 20:50 的文章
当前位置: 澳门威利斯人 > 澳门威利斯人 > 正文

奥门泥斯人别人家的面试题,的扩展方法集合

countBits 的时日复杂度

考虑 countBits, 上边的算法:

  • “版本1” 的小运复杂度是 O(N*M),M 取决于 Number.prototype.toString 和 String.prototype.replace 的复杂度。
  • “版本2” 的时刻复杂度是 O(N*logN)
  • “版本三” 的日子复杂度是 O(N*M),M 是 N 的2进制数中的“一”的个数,介于 一 ~ logN 之间。

上边多个版本的 countBits 的时刻复杂度都高于 O(N)。那么有未有时间复杂度 O(N) 的算法呢?

实际,“版本三”已经为大家提醒了答案,答案就在上边的不得了定律里,小编把尤其等式再写一回:

countBit(n & (n - 1)) === countBit(n) - 1

1
countBit(n & (n - 1)) === countBit(n) - 1

也等于说,若是我们精晓了 countBit(n & (n - 1)),那么大家也就了解了 countBit(n)

而大家领略 countBit(0) 的值是 0,于是,我们得以不会细小略的递推:

版本4

function countBits(nums){ var ret = [0]; for(var i = 1; i <= nums; i ){ ret.push(ret[i & i - 1] 1); } return ret; }

1
2
3
4
5
6
7
function countBits(nums){
   var ret = [0];
   for(var i = 1; i <= nums; i ){
       ret.push(ret[i & i - 1] 1);
   }
   return ret;
}

原来就这么轻便,你想到了吧 ╮(╯▽╰)╭

上述正是负有的始末,轻易的主题素材思量起来很有意思吗?程序猿就活该追求完美的算法,不是啊?

那是 leetcode 算法面试题种类的第1期,下1期大家谈谈别的1道题,那道题也很有趣:判断二个非负整数是还是不是是 四 的整数十一回方,别告诉自身你用循环,想想更抢眼的章程呢~

打赏支持小编写出越来越多好文章,多谢!

打赏小编

旁人家的面试题:一个整数是不是是“肆”的N次幂

2016/05/30 · 基本功技巧 · 2 评论 · 算法

正文笔者: 伯乐在线 - 10年踪迹 。未经笔者许可,禁止转发!
接待到场伯乐在线 专辑作者。

这是 leetcode.com 的第1篇。与上一篇平等,大家探讨共同相对简便易行的主题素材,因为学习总强调鲁人持竿。而且,就到底轻易的难点,追求算法的极致的话,在那之中也是有高校问的。

//获取字符数组
String.prototype.ToCharArray=function()
{
         return this.split("");
}
//获取N个一样的字符串
String.prototype.Repeat=function(num)
{
    var tmpArr=[];
    for(var i=0;i<num;i )    tmpArr.push(this);
    return tmpArr.join("");
}
//逆序
String.prototype.Reverse=function()
{
     return this.split("").reverse().join("");
}
//测试是还是不是是数字
String.prototype.IsNumeric=function()
{
    var tmpFloat=parseFloat(this);
    if(isNaN(tmpFloat))    return false;
    var tmpLen=this.length-tmpFloat.toString().length;
    return tmpFloat "0".Repeat(tmpLen)==this;
}
//测试是或不是是整数
String.prototype.IsInt=function()
{
    if(this=="NaN")    return false;
    return this==parseInt(this).toString();
}
// 合并八个空白为一个空白
String.prototype.resetBlank = function()
{
    return this.replace(/s /g," ");
}
// 除去右边空白
String.prototype.LTrim = function()
{
    return this.replace(/^s /g,""); 

// 除去右侧空白
String.prototype.RTrim = function()
{
    return this.replace(/s $/g,""); 
}
// 除去两边空白
String.prototype.trim = function()
{
    return this.replace(/(^s )|(s $)/g,""); 
}
// 保留数字
String.prototype.getNum = function()
{
    return this.replace(/[^d]/g,"");
}
// 保留字母
String.prototype.getEn = function()
{
    return this.replace(/[^A-Za-z]/g,""); 
}
// 保留汉语
String.prototype.getCn = function()
{
    return this.replace(/[^u4e00-u9fa5uf900-ufa2d]/g,"");
}
// 获得字节长度
String.prototype.getRealLength = function()
{
    return this.replace(/[^x00-xff]/g,"--").length;
}
// 从左截取钦定长度的字串
String.prototype.left = function(n)
{
    return this.slice(0,n);
}
// 从右截取钦点长度的字串
String.prototype.right = function(n)
{
    return this.slice(this.length-n);
}
// HTML编码
String.prototype.HTMLEncode = function()
{
    var re = this;
    var q1 = [/x26/g,/x3C/g,/x3E/g,/x20/g];
    var q2 = ["&","<",">"," "];
    for(var i=0;i<q1.length;i )
    re = re.replace(q1[i],q2[i]);
    return re;
}
// Unicode转化
String.prototype.ascW = function()
{
    var strText = "";
    for (var i=0; i<this.length; i ) strText  = ""   this.charCodeAt(i)   ";";
    return strText;

统计“1”的个数

给定八个非负整数 num,对于任性 i,0 ≤ i ≤ num,计算 i 的值对应的二进制数中 “一” 的个数,将那么些结果重回为二个数组。

例如:

当 num = 伍 时,重回值为 [0,1,1,2,1,2]。

/** * @param {number} num * @return {number[]} */ var countBits = function(num) { //在此间达成代码 };

1
2
3
4
5
6
7
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
    //在此处实现代码
};

打赏协助本身写出更加多好小说,多谢!

任选一种支付方式

奥门泥斯人 1 奥门泥斯人 2

1 赞 7 收藏 2 评论

您或许感兴趣的篇章:

  • 详解JS中Array对象扩张与String对象扩展
  • Javascript string 扩张库代码
  • Javascript String对象扩张HTML编码和解码的艺术
  • JavaScript 字符串数字左补位,右补位,取固定长度,截位增加函数代码
  • JavaScript中ES陆字符串扩充方法
  • JavaScript常用字符串与数组扩大函数小结
  • js完毕prototype扩展的艺术(字符串,日期,数组扩充)
  • javascript框架布署读书笔记之字符串的恢弘和修补
  • JS字符串函数扩大代码
  • JavaScript兑现替换字符串中最后多个字符的主意
  • JavaScript利用正则表明式替换字符串中的内容
  • js replace(a,b)之替换字符串中持有钦命字符的不二秘技
  • JavaScript基于扩张String完结替换字符串中index处字符的法子

打赏协助小编写出越来越多好小说,多谢!

任选一种支付格局

奥门泥斯人 3 奥门泥斯人 4

3 赞 8 收藏 5 评论

永不内置函数

本条标题标显要思路和上一道题类似,先思量“四”的幂的二进制表示:

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

相当于各类数比上贰个数的2进制前面多四个零嘛。最器重的是,“4”的幂的二进制数只有1 个“一”。假设条分缕析翻阅过上一篇,你就会领会,推断二个贰进制数唯有 二个“壹”,只必要:

JavaScript

(num & num - 1) === 0

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

而是,二进制数唯有 一个“一”只是“4”的幂的要求非充裕规范,因为“2”的奇数次幂也只有 三个“一”。所以,大家还索要增大的剖断:

JavaScript

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

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

何以是 num & 0xAAAAAAAA === 0? 因为那么些保证 num 的二进制的不胜 “壹” 出现在“奇数位”上,也就确定保障了那一个数确实是“4”的幂,而不光只是“二”的幂。

最后,大家取得完整的版本:

版本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 & -一) === 0 也是 true


本文由澳门威利斯人发布于澳门威利斯人,转载请注明出处:奥门泥斯人别人家的面试题,的扩展方法集合

关键词: 澳门威利斯人 JavaScript 基础技术