读后感：数据结构与算法JavaScript描述

本书看完，对常见的数据结构与算法从概念上有了更深入的理解。

书中关于数组、栈和队列、链表、字典、散列、集合、二叉树、图、排序、检索、动态规划、贪心算法都有详细的介绍。算是一本不错的学习书籍。

栈和队列：都可以通过数组来模拟。栈的规则是先进后出，队列的规则是先进先出。

链表：有双向与单向链表之分，默认有一个头指针，指向下一个节点，就像链条一样。

数组 vs 链表：

数组查找速度快：数组能够通过索引快速找到一个元素，高效快速。而链表没有索引，查找不是很便捷。
链表增加、删除性能高：数组增加、删除一个元素，后面的元素都需要移动一个位置，数据量大时，改前面的数据，很耗性能。而链表只需改动节点的指向索引，非常高效。

字典：简单理解就是key/value的键值对存储的对象。

散列：基于数组设计，长度预定。借助散列函数将每个键值映射为一个唯一的数组索引。

集合：js中的map、set。

二叉树：非线性的数据结构，以分层的方式存储。用来存储具有层级关系的数据。比如文件系统。具有根节点、左子树、右子树、叶子节点。树的层数就是树的深度。树的遍历：

中序：按照节点上的键值，升序访问所有节点
先序：先访问根节点，然后以同样的方式访问左子树和右子树。
后序：先访问叶子节点，从左子树到右子树，再到根节点。

图：由边的集合及顶点的集合组成。地图就是一种图。如果一个图的顶点是有序的，则称之为有向图，反之为无向图。

常见的排序：冒泡排序、选择排序、插入排序

高级排序：希尔排序、归并排序。

检索：二分查找算法，比排序查找算法高效。

动态规划

使用递归方案能解决的问题，都能够使用动态规划技巧来解决。

动态规划：解决相似子问题，并保存子问题的解，通过子问题的解从而解决整个问题。子问题的解通常存储在数组中便于访问

动态规划，听过它的鼎鼎大名，但一直没深入了解过。

书中的例子：

1.计算裴波那契数列

斐波那契数列：0,1,1,2,3,5,8,13...

该序列是由前两项数值相加而成的

递归实现：效率低，有太多值在递归调用中被重新计算。

function recurFib (n) {

  if (n < 2) {

    return n;

  }

  return recurFib(n - 1) + recurFib(n - 2);

}

动态规划实现：将数组的每个元素赋值为前两个元素之和，循环结束，最后一个元素值即为最终计算得到的斐波那契数值

function dynFib(n) {

  var val = [];

  for (var i = 0; i <= n; i++) { // 0 - n：含 n+1 个

    val[i] = 0;

  }

  if (n == 1 || n == 2) {

    return 1;

  }

  val[1] = 1;

  val[2] = 2;

  for (var i = 3; i <= n; i++) {

    val[3] = val[i-1] + val[i-2];

  }

  return val[n-1];

}

迭代实现：不保存中间结果

function iterFib (n) {

  var last = 1;

  var nextLast = 1;

  var result = 1;

  for (var i = 2; i < n; i++) {

    result = last + nextLast;

    nextLast = last;

    last = result;

  }

  return result;

}

2.寻找两个字符串的最长公共子串

动态规划：使用一个二维数组存储两个字符串相同位置的字符比较结果。初始数组每一个元素被设置为0，每次在这两个数组的相同位置发现了匹配，就将该数组对应行和列的元素加1，否则保持为0

function lcs (word1, word2) {

  // 初始化二维数组，每项为0

  var max = 0;

  var index = 0;

  var lcsarr = new Array(word1.length + 1);

  for (var i = 0; i <= word1.length + 1; i++) {

    lcsarr[i] = new Array(word2.length + 1);

    for (var j = 0; j <= word2.length + 1; j++) {

      lcsarr[i][j] = 0;

    }

  }

  // 保存字符匹配的记录，如果两个字符串相应位置的字符进行了匹配，当前数组元素的值将被设置为前一次循环中数组元素保存的值加1，最后如果变量max的值比现在存储在数组中的当前元素小，max的值将被赋值给这个元素，变量index的值将被设置为i的当前值。这两个变量将在函数的最后一部分用于确定从哪里开始获取最长公共子串。

  for (var i = 0; i <= word1.length; i++) {

    for (var j = 0; j <= word2.length; j++) {

      if (i == 0 || j == 0) {

        lcsarr[i][j] = 0;

      } else {

        if (word1[i - 1] == word2[j - 1]) {

          lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;

        } else {

          lcsarr[i][j] = 0;

        }

      }

      if (max < lcsarr[i][j]) {

        max = lcsarr[i][j];

        index = i;

      }

    }

  }

  // 确认从哪里开始构建这个最长公共子串。以变量index减去变量max的差值作为起始点，以变量max的值作为终点。

  var str = '';

  if (max == 0) {

    return '';

  } else {

    for (var i = index - max; i <= max; i++) {

      str += word2[i];

    }

    return str;

  }

}

console.log(lcs('raven', 'havoc')); // av

关于第二部分，记录字符串匹配结果，可以优化，减少遍历次数

 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;

      }

    }

  }

书中还有关于如何用递归与动态规划解决背包问题，甚至用贪心算法解决部分背包问题。

背包问题：有一个保险箱，保险箱中的物品规格和价值不同。你需要将保险箱中的宝物放入一个你的背包，希望背包装进的宝贝价值最大。如：保险箱中有5件物品，尺寸：3,4,7,8,9，价值：4,5,10,11,13，背包的容积为16。最优解是：选取第三件和第五件，总尺寸是16，总价值是23。

如果感兴趣的，可以翻开此书看看。

巴特西

读后感：数据结构与算法JavaScript描述

动态规划

最新文章

热门文章