小江的前端之路

外观

返回顶部
本页目录

数据结构与算法

Hello 算法https://www.hello-algo.com/ 我的第一本算法书 算法图解

数据结构

所有数据结构都是基于数组、链表或二者的组合实现的。

链表

alt

数组

alt

栈

alt

队列

alt

哈希表

alt

二叉树

alt

二叉查找树

「二叉搜索树 Binary Search Tree」满足以下条件：

1.对于根节点，左子树中所有节点的值<根节点的值< 右子树中所有节点的值； 2.任意节点的左、右子树也是二叉搜索树，即同样满足条件 alt

堆

「堆 Heap」是一种满足特定条件的完全二叉树，可分为两种类型：

  • 「大顶堆 Max Heap」，任意节点的值 >=其子节点的值；
  • 「小顶堆 Min Heap」，任意节点的值 <=其子节点的值； alt

图

「图 Graph」是一种非线性数据结构，由「顶点 Vertex」和「边 Edge」组成 alt

算法

搜索

排序

选择排序

在未排序序列找到最小的数,存放到排序序列的起始位置,再从剩余未排序元素中继续寻找最小然后放到已排序序列的末尾。

alt

顺序排序

顺序排序（又称直接插入排序）和插入排序是同一种排序算法

顺序排序是一种极简单的排序算法，它的工作原理是：通过比较两个数的大小来决定他们的相对次序，然后通过交换位置来改变两个数的相对次序.

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置

alt

冒泡排序

算法步骤: 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 alt

dotnetcli
做

  swapped = false

  从 i = 1 到 最后一个没有排序过元素的索引-1

    如果 左边元素 > 右边元素

      交换（左边元素，右边元素）

      swapped = true; ++swapCounter（交换计数器）

while swapped

快速排序

1.从数列中挑出一个元素，称为 "基准"（pivot）;

2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序； alt

JavaScript
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    
    var pivot = arr[Math.floor(arr.length / 2)];
    var left = [];
    var right = [];
    
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else if (arr[i] > pivot) {
            right.push(arr[i]);
        }
    }
    
    return quickSort(left).concat(pivot, quickSort(right));
}

// 示例用法
var unsortedArray = [5, 3, 8, 4, 2, 1, 10, 9];
var sortedArray = quickSort(unsortedArray);
console.log(sortedArray);  // 输出：[1, 2, 3, 4, 5, 8, 9, 10]

检索算法

1.最大最小值

如何在数组中查找最小值，算法如下。 (1) 将数组第一个元素赋值给一个变量，把这个变量作为最小值。 (2) 开始遍历数组，从第二个元素开始依次同当前最小值进行比较。 (3) 如果当前元素小于最小值，则把当前元素赋值给最小值。

JavaScript
function  findMin(arr) {
  let min =arr[0];
  for(let i=1;i<arr.length;i++){
    if (arr[i]<min) {
      min = arr[i]
    }
  }
  return min;
  
}

2.二分查找

二分查找算法，也称折半查找算法，是一种在有序数组中查找某一特定元素的搜索算法。 alt

  • (1) 将数组的第一个位置设置为下边界（0）
  • (2) 将数组最后一个元素所在的位置设置为上边界（数组的长度减 1）。
  • (3) 若下边界等于或小于上边界，则做如下操作。
    • a. 将中点设置为（上边界加上下边界）除以 2。
    • b. 如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加 1。
    • c. 如果中点的元素大于查询的值，则将上边界设置为中点元素所在下标减 1。
    • d. 否则中点元素即为要查找的数据，可以进行返回。
javaScript
function binSearch(arr,data){
  let low = 0;
  let high = arr.length-1;
  while (low <= high) {
    let min = Math.floor((low+high)/2)
    if (arr[min] < data) {
      low = min + 1
    }else if (arr[min] > data) {
      high = min -1
    }else{ 
      return min
    }
    return -1;
  }
}

动态规划

将原问题分解成若干子问题，通过解决子问题来求解原问题

斐波那契数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

递归方法

javaScript
function recurFib(n) {
  if(n<2){
    return n;
  }
  else{
    return recurFib(n-1) + recurFib(n-2);
  }
}
print(recurFib(10))

递归函数的问题是它的执行效率非常低

使用动态规划的技巧去计算斐波那契数列来展示

javaScript
function dynFib(n) {
  let val = [];
  for ( let i = 0; i <= n; ++i; ){
    var[i] = 0;
  }
  if (n==1 || n==2) {
    return 1;

  }
  else{
    val[1] = 1;
    val[2] = 2;
    for(let i = 3; i <= n; ++i;){
      val[i] = val[i-1] + val[i-2];
    }
    return val[n-1];
  }
}

最长公共子串

javaScript
 function lcs (word1, word2) {
      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
        }
      }
      // 的第二部分代码
      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
          }
        }
      }
      var str = ""
      if (max == 0) {
        return ""
      } else {
        for (var i = index - max; i <= max; ++i) {
          str += word2[i]
        }
        return str
      }
    }

该函数的第一部分初始化了两个变量以及一个二维数组 第二部分构建了用于保存字符匹配记录的表

背包问题

使用动态规划来解决背包问题的关键思路是计算装入背包的每一个物品的最大价值，直到背包装满

javaScript
    function max (a, b) {
      return (a > b) ? a : b
    }
    function dKnapsack (capacity, size, value, n) {
      var K = []
      for (var i = 0; i <= capacity + 1; 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 (size[i - 1] <= w) {
            K[i][w] = max(value[i - 1] + K[i - 1][w - size[i - 1]],
              K[i - 1][w])
          }
          else {
            K[i][w] = K[i - 1][w]
          }
          putstr(K[i][w] + " ")
        }
        print()
      }
      return K[n][capacity]
    }
    var value = [4, 5, 10, 11, 13]
    var size = [3, 4, 7, 8, 9]
    var capacity = 16
    var n = 5
    print(dKnapsack(capacity, size, value, n));

贪心算法

贪心算法总是会选择当下的最优解

找零问题

用最少数量的硬币来找零钱

  • 1.初始化一个空的结果列表，用于存储所需的硬币。
  • 2.对于每一种硬币面额，从最大面额开始（通常是从大到小排列的），重复以下步骤：
    • 计算当前面额的硬币可以用多少个，即 硬币数量 = 总金额 / 当前面额。
    • 将这些硬币添加到结果列表中。
    • 减去已经添加的硬币总额，更新剩余的总金额。
    • 如果剩余总金额为0，则找零结束；否则，继续下一个面额的硬币。
javaScript
function makeChange(coins, amount) {
  // 首先将硬币按面额从大到小排序
  coins.sort((a, b) => b - a);

  const change = [];
  let remainingAmount = amount;

  for (const coin of coins) {
    while (remainingAmount >= coin) {
      change.push(coin);
      remainingAmount -= coin;
    }
  }

  if (remainingAmount === 0) {
    return change;
  } else {
    return "无法找零";
  }
}

// 示例用法
const coins = [25, 10, 5, 1];  // 美元面额
const amount = 63;
const result = makeChange(coins, amount);
console.log(result);  // 输出：[25, 25, 10, 1, 1, 1]