基础算法练习及相关技巧

本文包括js学习中简单功能的算法
包括对js以及DOM和BOM的研究过程中一些有意思的代码实现
本文还包括公司面试相关算法问题的代码段，但不会指出是哪个公司出的题

数据结构及基本排序、查找算法

这个部分内容比较多，请查看一下博客：

递归实现斐波那契数列

function reFib(n){
  if (n < 2) return n;
  else return reFib(n - 1) + reFib(n - 2);
}

动态规划实现斐波那契数列

function dynFib(n){
  var val = [];

  for(var i = 0; i <= n; i++)
    val.push(0);
  if (n == 1 || n == 2) return 1;
  else{
    val[1] = 1;
    val[2] = 2;
    for (var i = 3; i <= n; ++i)
      val[i] = val[i - 1] + val[i - 2];
    return val[n - 1];
  }
}

迭代实现斐波那契数列

function iterFib(n){   //得到第n个数列值
  var a = 1, b = 1, temp;
  for(var i = 2; i <= n; i++){
    temp = b;
    b = a + b;
    a = temp;
  }
  return a;
}

迭代实现斐波那契数列 ES6

function* fibs(){
  let a = 1;
  let b = 1;
  while(1){
    yield a;
    [a, b] = [a, a + b];
  }
}

var [first, second, third, forth, fifth, sixth] = fibs();

数组元素去重复

function unique(arr) {
return arr.filter(function(item, index){
  return arr.indexOf(item) === index;
});
}   //除去所以 undefined

//以下是 ES6 方法
 function unique(arr){
   return Array.from(new Set(arr));
 }  //保留数组中的 undefined

Fisher Yates Shuffle

Array.prototype.shuffle = function(){
  var len = this.length;
  for(var i = len - 1; i > 0; i--){
    var j = Math.round(Math.random() * i);
    // debugger;
    [this[i],this[j]] = [this[j],this[i]];
  }
  return this;
}

查找2个字符串的最长公共子串

function lcs(word1, word2){
  var max = 0;
  var index = 0;
  var lcsarr = [];
  var str = "";

  for(var i = 0; i <= word1.length + 1; ++i){
    lcsarr[i] = [];
    for(var j = 0; j <= word2.length + 1; ++i)
      lcsarr[i][j] = 0;
  }

  for(var i = 1; i <= word1.length; ++i){
    for(var j = 1; j <= word2.length; ++j){
      if(word1[i - 1] === word2[j - 1])
        lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;
      if(max < lcsarr[i][j]){
        max = lcsarr[i][j];
        index = i;
      }
    }
  }
  if(max === 0)
    return "";
  else {
    for(var i = index - max; i < index; ++i)
      str += word1[i];
    return str;
  }
}

背包问题 递归

/**
 * [knapsack description]
 * @param  number capacity 背包容量（最大承重）
 * @param  array weights 背包内物品重量
 * @param  array value 物品对应的价值
 * @param  number n 物品数量
 * @return number  求的的最大价值
 */
function knapsack(capacity, weights, value, n){
  if(n === 0 || capacity === 0) return 0;
  if(weights[n -1] > capacity) return knapsack(capacity, weights, value, n - 1);
  else return Math.max(value[n - 1] + knapsack(capacity - weights[n - 1], weights, value, n - 1), knapsack(capacity, weights, value, n - 1));
}

背包问题 动态规划

/**
 * [knapsack description]
 * @param  number capacity 背包容量（最大承重）
 * @param  array weights 背包内物品重量
 * @param  array value 物品对应的价值
 * @param  number n 物品数量
 * @return number  求的的最大价值
 */
function dKnapsack(capacity, weights, value, n){
  var K = [];   //价格矩阵
  for(var i = 0; i <= n; i++)
    K[i] = [];

  for(var i = 0; i <= n; i++){
    for(var w = 0; w <= capacity; w++){
      if(i == 0 || w == 0)
        K[i][w] = 0;
      else if(weights[i - 1] <= w)
        K[i][w] = Math.max(value[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]);
      else
        K[i][w] = K[i - 1][w];
      console.log(K[i][w] + " ");
    }
    console.log();
  }
  return K[n][capacity];
}

背包问题 贪心法

/**
 * [knapsack description]
 * @param  number capacity 背包容量（最大承重）
 * @param  array weights 背包内物品重量
 * @param  array value 物品对应的价值
 * @return number  求的的最大价值
 */
function dKnapsack(capacity, weights, values){
  var load = 0;
  var i = 0;
  var w = 0;

  while(load < capacity && i < 4){
    if(weight[i] <= (capacity - load)){
      w += value[i];
      load += weight[i];
    } else {
      var r = (capacity - load) / weight[i];
      w += r * value[i];
      load += weights[i];
    }
    ++i;
  }
  return w;
}

找零问题 贪心法

function makeChange(origAmt, coins){
  var remainAmt = 0;
  if(origAmt % .25 < origAmt){
    coins[3] = parseInt(origAmt / .25);
    remainAmt = origAmt % .25;
    origAmt = remainAmt;
  }
  if(origAmt % .1 < origAmt){
    coins[2] = parseInt(origAmt / .1);
    remainAmt = origAmt % .1;
    origAmt = remainAmt;
  }
  if(origAmt % .05 < origAmt){
    coins[1] = parseInt(origAmt / .05);
    remainAmt = origAmt % .05;
    origAmt = remainAmt;
  }
  coins[0] = parseInt(origAmt / .01);
}
function showChange(coins){
  if(coins[3] > 0) console.log("25美分数量- " + coins[3] + " - " + coins[3] * .25);
  if(coins[2] > 0) console.log("10美分数量- " + coins[2] + " - " + coins[2] * .1);
  if(coins[1] > 0) console.log("5美分数量- " + coins[1] + " - " + coins[1] * .05);
  if(coins[0] > 0) console.log("1美分数量- " + coins[0] + " - " + coins[0] * .01);
}

最大公约数 辗转相除法

function gcd(a, b){
  return b === 0 ? a : gcd(b, a%b);
}

最大公约数 更相减损术

function gcd(a, b){
  return a === b ? a : a < b ? gcd(a, b-a) : gcd(b, a-b);
}

hanoi塔 递归

function re_hanoi(n, a, b, c){
  if(n !== 0){
    re_hanoi(n - 1, a, c, b);
    console.log(a + " => " + b + "\n");
    re_hanoi(n - 1, c, b, a);
  }
}

hanoi塔 非递归

function hanoi(n){ //0 1 2 共3个塔
  for(var t = 1; t < 1 << n; t++){
    var first, second;
    switch((t & t - 1) % 3){
      case 0: first = 'a'; break;
      case 1: first = 'b'; break;
      case 2: first = 'c'; break;
      default: break;
    }
    switch(((t | t - 1) + 1) % 3){
      case 0: second = 'a'; break;
      case 1: second = 'b'; break;
      case 2: second = 'c'; break;
      default: break;
    }
    console.log(first + " => " + second + "\n")
  }
}

查找n以内的最大质数(埃拉托色尼法)

function maxPrime(n){
  var a = new Array(n + 1);
  var max = Math.floor(Math.sqrt(n));
  var p = 2;
  while(p <= max){
    for(var i = 2 * p; i <= n; i += p)
      a[i] = 1;
    while(a[++p]) /* empty */;
  }
  while(a[n]) n--;
  return n;
}

身份证号码末尾校验码

/**
 * [indentify description]
 * @param  String str 身份证号码
 * @return Boolean 是否合法身份证号
 */
function indentify(str)
  {
    var weight = [7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2];
    var check = ["1", "0", "X", "9", "8", "7", "6", "5", "4", "3", "2"];
    if(str.length !== 18) {
      alert("input error");
      str="";
    } else {
      var substr = str.slice(0, 17);
      var last = str.slice(-1);
      var S = 0;
      for(var i = 0; i < 17; i++) {
        S += substr[i] * weight[i];
      }
      S = S % 11;
      if(check[S] === last.toUpperCase()) {
        return true;
      } else {
          str="";
          return false;
      }
    }
  }

青蛙跳台阶 动态规划

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

function jumpFloor(number){
    if(number < 1){
        return 0;
    }
    if(number === 1){
        return 1;
    }
    if(number === 2){
        return 2;
    }
    var temp = 0, a = 1, b = 2;
    for(var i = 3; i <= number; i++){
        temp = a + b;
        a = b;
        b = temp;
    }
    return temp;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,530评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 86,403评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,120评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,770评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,758评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,649评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,021评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,675评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,931评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,659评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,751评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,410评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,004评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,969评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,042评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,493评论 2赞 343

推荐阅读更多精彩内容