Skip to main content

算法基础

1、 冒泡排序​

先来个常规思路

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

console.log(bubbleSort([2, 45, 1, 23, 55, 21, 44, 53, 7, 26]));

1.1、 优化点一​

  • 第二层循环，思考下循环次数: arr.length - 1;
  • 冒泡排序的基本逻辑是从左往右滑动窗口，将大的元素移动到右边。
  • 第一次循环执行下来，最大的元素已经到了最右边了，第二次循环其实不需要再考虑最后一个元素了
  • 同样的，第三次循环也不需要比较倒数第二个了

优化之后的代码如下：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

console.log(bubbleSort([2,45,1,23,55,21,44,53,7,26]));

1.2、 优化点二​

  • 考虑一个场景，第二层循环执行下来，并没有做过元素互换，说明什么
  • 说明数组排序已经是从小到大排序的了
  • 这样的话，我们直接结束循环即可
function bubbleSort(arr) {
  let swapped = true;
  for (let i = 0; i < arr.length - 1 && swapped; i++) {
    swapped = false;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }
  }

  return arr;
}

console.log(bubbleSort([2,45,1,23,55,21,44,53,7,26]));

1.3、 优化点三​

其实第一个循环完全也是没有必要的。

function bubbleSort(arr) {
  let swapped = true;
  while(swapped) {
    swapped = false;
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }
  }

  return arr;
}

console.log(bubbleSort([2,45,1,23,55,21,44,53,7,26]));

1.4、 优化点四​

// 数组元素互换，可以使用 array destructuring
// example 
const [first, second, third] = ["Laide", "Gabriel", "Jets"];
const arr = [1, 2, 3];
[arr[1], arr[2]] = [arr[2], arr[1]];
console.log(arr);
//  [1, 3, 2]
function bubbleSort(arr) {
  let swapped = true;
  while(swapped) {
    swapped = false;
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
  }

  return arr;
}

console.log(bubbleSort([2,45,1,23,55,21,44,53,7,26]));

2、 快速排序​

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const middleIndex = Math.floor(arr.length / 2);
  const middleIndexValue = arr[middleIndex];

  const left = [];
  const right = [];

  for (let i = 0; i < arr.length; i++) {
    if (i === middleIndex) continue;
    if (arr[i] < middleIndexValue) {
      left.push(arr[i]);
	  } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), middleIndexValue, ...quickSort(right)];
}

console.log(quickSort([1, 3, 5, 7, 9, 2, 4, 6]));

3、 插入排序​

插入排序的核心思路是：每次从原数组往新数组插入，插入的位置要求大于左边，小于右边。

边界条件：

  1. 小于第一个，直接往左边插入
  2. 比新数组最后一个元素大，没有后边了，运行右边为 undefined
function insertSort(arr) {
  const res = [arr.shift()];

  while(arr.length) {
    const value = arr.shift();
    for (let i = 0; i < res.length; i++) {
      const current = res[i];
      const next = res[i + 1];
      if (i === 0 && value <= current) {
        res.unshift(value);
      } else if (value > current && (value <= next || next === undefined)) {
        res.splice(i + 1, 0, value);
        break;
      }
    }
  }

  return res;
}

function rang(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

let count = 100;
while (count--) {
  const list = Array(10).fill(0).map(() => rang(1, 500));
  const a = insertSort(list);
  console.log(a.length, JSON.stringify(a));
}

4、 选择排序​

选择排序：核心思想就是选择一个最大的元素，往新的数组去执行 push 操作。

function selectSort(a) {
  const sortedArr = [];
  while (a.length > 0) {
    let max = a[0];
    let markIndex = 0;
    for (let i=1; i < a.length; i++) {
      if (a[i] < max) {
        max = a[i];
        markIndex = i;
      }
    }
    sortedArr.push(max);
    a.splice(markIndex, 1);
  }
  return sortedArr;
}

function rang(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

let count = 100;
while (count--) {
  const list = Array(10).fill(0).map(() => rang(1, 500));
  const a = selectSort(list);
  console.log(a.length, JSON.stringify(a));
}

5、 算法：动态规划​

1块、4块、5块，求总数n块的最小硬币数

function minCoins(coins, target) {
  // 创建一个数组存储最小硬币数
  const dp = new Array(target + 1).fill(Infinity);
  
  // 初始化 0 元的硬币数为 0
  dp[0] = 0;
  
  // 遍历每个目标金额
  for (let i = 1; i <= target; i++) {
    // 遍历每种硬币面额
    for (let j = 0; j < coins.length; j++) {
      // 如果当前硬币面额小于等于目标金额
      if (coins[j] <= i) {
        // 更新最小硬币数
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }
  
  // 如果无法凑成目标金额,返回 -1
  return dp[target] === Infinity ? -1 : dp[target];
}

// 示例用法
const coins = [1, 4, 5];
const target = 10;
const result = minCoins(coins, target);
console.log(result); // 输出 2

这个解决方案使用动态规划的方法来求解最小硬币数。它首先创建一个数组 dp,存储每个目标金额所需的最小硬币数。初始化 dp[0] 为 0,因为 0 元不需要任何硬币。

然后,它遍历每个目标金额,并对于每个目标金额,遍历所有可用的硬币面额。如果当前硬币面额小于等于目标金额,则更新 dp[i] 为 dp[i - coins[j]] + 1,这样就可以得到最小硬币数。

最后,如果无法凑成目标金额,则返回 -1,否则返回 dp[target]。

这个解决方案的时间复杂度是 O(n * m),其中 n 是目标金额,m 是硬币种类数。空间复杂度是 O(n),用于存储 dp 数组。

6、 数据转换​

// 问题：
// {a:1,b:{c:2,d:{e:3},g:[4,{h:5}]}}
// 转成
// {
// "a":1,
// "b.c":2,
// "b.d.e":3,
// "b.g[0]":4,
// "b.g[1].h":5,
// }
function dataTransform(obj, path = '', data = {}) {
  if (Array.isArray(obj)) {
    obj.forEach((item, index) => {
      if (typeof item === 'object') {
        dataTransform(item, `${path}[${index}].`, data);
      } else {
        data[`${path}[${index}]`] = item;
      }
    });
  } else if (typeof obj === 'object') {
    for (let key in obj) {
      const item = obj[key];
      if (typeof item === 'object') {
        dataTransform(item, `${path}${key}${Array.isArray(item) ? '' : '.'}`, data);
      } else {
        data[`${path}${key}`] = item;
      }
    }
  }
  return data;
}

console.log(dataTransform({a:1,b:{c:2,d:{e:3},g:[4,{h:5}]}, x: [
  3,
  { y: 4, z: [45] }
]}));

7、 数组转树型结构​

// const arr = [
//   { id: 1, name: "i1" },
//   { id: 2, name: "i2", parentId: 1 },
//   { id: 4, name: "i4", parentId: 3 },
//   { id: 3, name: "i3", parentId: 2 },
//   { id: 8, name: "i8", parentId: 7 },
// ];

const arr = [
  { id: 1, name: 'i1'},
  { id: 2, name: 'i2', parentId: 9},
  { id: 3, name: 'i3', parentId: 5},
  { id: 4, name: 'i4', parentId: 1},
  { id: 5, name: 'i5', parentId: 1},
  { id: 6, name: 'i6', parentId: 2},
  { id: 7, name: 'i7', parentId: 3},
];

function transformArrayToTree(arr) {
  const tree = {};
  const result = [];

  for (const node of arr) {
    tree[node.id] = node;
  }

  for (const node of arr) {
    if (node.parentId) {
      const parent = tree[node.parentId];
      if (parent) {
        parent.children = parent.children || [];
        parent.children.push(node);
        delete node.parentId;
      }
    } else {
      result.push(node);
    }
  }

  return result;
}

console.log(JSON.stringify(transformArrayToTree(arr), null, 2));