栈结构（Stack）

队列（Queue）

链表（linkedList）

树

满二叉树：深度为 k 且有 个节点的二叉树称为满二叉树。

完全二叉树：符合层次遍历（从左到右，自上而下）的满二叉树，其第 k 层最大的节点数为 个。

二叉搜索树

• 二叉树的节点最多只有两个子节点，左侧节点 < 父节点 < 右侧节点

红黑树

• 根节点为黑色
• 不能有两个相邻的红节点
• 如果一个节点是红的，那么它的两个子节点都是黑的
• 所有叶节点（没有子元素的节点）都是黑的（用NIL引用表示节点）
• 从给定的节点到它的后代节点（NIL叶节点）的所有路径包含相同数量的黑色节点。

二叉堆

• 它是一棵完全二叉树，树的每一层都有左侧和右侧（除最后一层的叶节点），并且最后一层的叶节点尽可能是左侧子节点
• 二叉堆不是最小堆就是最大堆，所有的节点都 >= || <= 每个它的子节点。

排序算法

冒泡排序

描述：相邻元素比较大小，进行交换，第二轮比较完成后，最后的元素将是 (最大 || 最小) 的，下一轮不再参与比较 第一轮比较完成后，最后一个元素是最大的， 因此最后一个元素不再参与比较

	23	13	10	76	7	4	LENGTH - I 次
第一轮	13	10	23	7	4	76	比较 5 次
第二轮	10	13	7	4	23	76	比较 4 次
第三轮	10	7	4	13	23	76	比较 3 次
第四轮	7	4	10	13	23	76	比较 2 次
第五轮	4	7	10	13	23	76	比较 1 次

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

选择排序

描述： 未排序中找到最小（大）元素，存放在排序列表起始位置 然后从剩余未排序元素中继续寻找最小的元素，放到已排序列表的末尾

	23	13	10	76	7	4	LENGTH - I 次
第一轮		13	10	76	7	23	比较 5 次，交换一次
第二轮	4		10	76	13	23	比较 4 次，交换一次
第三轮	4	7		76	13	23	比较 3 次，交换一次
第四轮	4	7	10			23	比较 2 次，交换一次
第五轮	4	7	10	13		76	比较 1 次，交换一次

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i;
    for (let j = min + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) min = j;
    }
    [arr[min], arr[i]] = [arr[i], arr[min]];
  }
  return arr;
}

插入排序

描述：将第一个元素看成是有序的数组与后面无序数组进行比较，比它大则直接放入，比它小则移动数组元素的位置，找到个合适的位置插入

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let preIndex = i - 1;
    let current = arr[i];
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
  return arr;
}

希尔排序

function shellSort(arr) {
  let gap = 1;
  let len = arr.length;
  while (gap < len / 3) gap = gap * 3 + 1;

  for (gap; gap; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < len; i++) {
      let temp = arr[i];
      let j = i - gap;

      while (j >= 0 && arr[j] > temp) {
        arr[j + gap] = arr[j];
        j -= gap;
      }

      // for (; j >= 0 && arr[j] > temp; j -= gap) {
      //   arr[j + gap] = arr[j];
      // }

      // for (; j >= 0; j -= gap) {
      //   if (arr[j] <= temp) break;
      //   arr[j + gap] = arr[j];
      // }
      arr[j + gap] = temp;
    }
  }
  return arr;
}

快速排序

/**
 * 以数组索引为0的值做为基准点(pivot)，两个指针（i index）初始同时指向索引为1的位置。
 * i每次循环加1，index则在索引i的值小于基准点时才进行交换后加1(每次每次值大于pivot时会停下来，等到i找到小于基准点的值进行交换，位置再向前加1)
 * 最后基准点与 index 前一个位置进行交换（ 大于等于index 的都是大于基准点的值）
 */
const arr = [4, 3, 5, 2, 7, 0];
function partition(arr, l = 0, r = arr.length - 1) {
  let pivot = l,
    index = l + 1,
    swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
  for (let i = index; i <= r; i++) {
    const flag = arr[i] < arr[pivot] ? '交换' : '不交换';
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index++);
    }
    /**
     * 1 [4, 3, 5, 2, 7, 0] 2 交换
     * 2 [4, 3, 5, 2, 7, 0] 2 不交换
     * 3 [4, 3, 2, 5, 7, 0] 3 交换
     * 4 [4, 3, 2, 5, 7, 0] 3 不交换
     * 5 [4, 3, 2, 0, 7, 5] 4 交换
     */
    console.log(i, arr, index, flag);
  }
  swap(arr, pivot, index - 1);
  console.log('=====> ', index - 1, arr); // 3 [0, 3, 2, 4, 7, 5]
  return index - 1;
}

// 单向扫描 指针都在索引为1的位置开始
function partition1(arr, l, r) {
  let pivot = l;
  let index = l + 1;
  const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
  for (let i = index; i <= r; i++) {
    if (arr[i] < arr[pivot]) swap(arr, i, index++);
  }
  swap(arr, pivot, --index);
  return index;
}

// 双向扫描 指针分别在索引两端
function partition2(arr, low, high) {
  const pivot = arr[low];
  while (low < high) {
    //注意需要先从左边开始（因为我们从0开始的）
    while (low < high && arr[high] > pivot) high--;
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) low++;
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const partitionIndex = partition2(arr, left, right);
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
  }
  return arr;
}

console.log(quickSort(arr));

归并排序

let count = 0; // 拆分时 先左后右，自上而下 合并时先左后右，自下而上
function mergeSort(arr) {
  console.log(`mergeSort${++count}=====> `, arr);
  if (arr.length < 2) return arr;
  const middle = Math.floor(arr.length / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(l, r) {
  console.log(`merge${++count}=====> `, l, r);
  const result = [];
  while (l.length && r.length) {
    result.push(l[0] > r[0] ? r.shift() : l.shift());
  }
  while (l.length) result.push(l.shift());
  while (r.length) result.push(r.shift());
  return result;
}

堆排序

计数排序

// 通过数组中的最大值max创建一个max+1长度的数组bucket，分别存储各个数组的个数（下标为数组的值），循环bucket进行给数组重新赋值
function countingSort(arr) {
  let maxVal = -Infinity;
  let index = 0;

  for (const el of arr) maxVal = Math.max(maxVal, el);
  const bucket = new Array(maxVal + 1).fill(0);
  for (const el of arr) bucket[el]++;

  for (let i = 0; i < bucket.length; i++) {
    while (bucket[i] > 0) {
      arr[index++] = i;
      bucket[i]--;
    }
  }
  return arr;
}

桶排序

基数排序

力扣

滑动窗口

/**
 * @see {@link https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ | 3. 无重复字符的最长子串}
 * @param {string} s
 * @returns {number}
 * @description 滑动窗口
 */

function lengthOfLongestSubstring(s = 'pwwkew') {
  const set = new Set();
  let ans = 0;
  let rk = -1;
  for (let i = 0; i < s.length; i++) {
    if (i !== 0) set.delete(s.charAt(i - 1));
    while (!set.has(s.charAt(rk + 1)) && rk + 1 < s.length) {
      set.add(s.charAt(rk + 1));
      rk++;
    }
    ans = Math.max(ans, rk + 1 - i);
  }
  return ans;
}

动态规划

爬楼梯

/**
 * @see {@link https://leetcode.cn/problems/climbing-stairs/description/ | 力扣 70. 爬楼梯}
 * @param {number} n
 * @returns {number}
 */

function climbStairs(n, memo = {}) {
  // 递归 + 记忆化搜索
  // if (memo[n]) return memo[n];
  // if (n === 1 || n === 2) return (memo[n] = n);
  // return (memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo));

  // 动态规划
  const dp = [1, 2];
  for (let i = 3; i <= n; i++) {
    [dp[0], dp[1]] = [dp[1], dp[0] + dp[1]];
  }
  console.log('dp :>> ', dp);
  return dp[1];
}

背包问题

function knapsack(weights, values, capacity) {
  const dp1 = [];
  for (let i = 0; i < values.length; i++) {
    for (let j = 0; j <= capacity; j++) {
      dp1[i] ??= [];
      if (weights[i] > j) {
        dp1[i][j] = dp1[i - 1]?.[j] ?? 0;
      } else {
        dp1[i][j] = Math.max(dp1[i - 1]?.[j] ?? 0, (dp1[i - 1]?.[j - weights[i]] ?? 0) + values[i]);
      }
    }
  }
  console.table(dp1);

  const dp2 = [];
  for (let i = 0; i < values.length; i++) {
    for (let j = capacity; j >= weights[i]; j--) {
      dp2[j] = Math.max(dp2[j] ?? 0, (dp2[j - weights[i]] ?? 0) + values[i]);
    }
    console.log('滚动数组=====> ', dp2);
  }
}

function unboundedKnapsack(weights, values, capacity) {
  const dp1 = [];
  for (let i = 0; i < values.length; i++) {
    for (let j = 0; j <= capacity; j++) {
      dp1[i] ??= [];
      dp1[i][j] = dp1[i - 1]?.[j] ?? 0;
      if (j >= weights[i]) {
        dp1[i][j] = Math.max(dp1[i][j], dp1[i][j - weights[i]] + values[i]);
      }
    }
  }
  console.table(dp1);

  const dp2 = [];
  for (let i = 0; i < values.length; i++) {
    for (let j = weights[i]; j <= capacity; j++) {
      dp2[j] = Math.max((dp2[j - weights[i]] ?? 0) + values[i], dp2[j] ?? 0);
    }
    console.log('滚动数组=====> ', dp2);
  }
}

/**
 * w v
 * 2 1
 * 3 3
 * 4 6
 * 8 10
 */

// knapsack([2, 3, 4, 8], [1, 3, 6, 10], 10);
// console.log('======== divide ========');
// unboundedKnapsack([2, 3, 4, 8], [1, 3, 6, 10], 10);

股票问题

/**
 * @see {@link https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/ | 121 && 122. 买卖股票的最佳时机 }
 * @param {number[]} prices
 * @returns {number}
 */
function maxProfit1(prices = [7, 1, 5, 3, 6, 4]) {
  // let ans = 0;
  // 暴力解法
  // for (let i = 0; i < prices.length; i++) {
  //   for (let j = i + 1; prices[i] < prices[j] && j < prices.length; j++) {
  //     ans = Math.max(ans, prices[j] - prices[i]);
  //   }
  // }

  // let minPrice = prices[0];
  // for (let i = 1; i < prices.length; i++) {
  //   if (minPrice > prices[i]) {
  //     minPrice = prices[i];
  //   } else {
  //     ans = Math.max(ans, prices[i] - minPrice);
  //   }
  // }

  // return ans

  // 动态规划 dp[i][j] i 当天 j股票状态  0无 1有
  const dp = Array.from({ length: prices.length }, (_, k) => (k === 0 ? [0, -prices[k]] : [0, 0]));
  for (let i = 1; i < prices.length; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
    //122. 买卖股票的最佳时机 II
    // dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    console.log({
      未持有: { 前一天未持有: dp[i - 1][0], 前一天持有今天卖出: dp[i - 1][1] + prices[i] },
      持有: {
        前一天持有: dp[i - 1][1],
        前一天未持有今天买入: -prices[i]
      }
    });
    // console.log(
    //   `第${i + 1}天未持有  =====>  `,
    //   `前一天未持有${dp[i - 1][0]}`,
    //   `前一天持有今天卖出${dp[i - 1][1] + prices[i]}`,
    //   dp[i][0]
    // );
    // console.log(
    //   `第${i + 1}天持有    =====>  `,
    //   `前一天未持有今天买入${-prices[i]}`,
    //   `前一天持有${dp[i - 1][1]}`,
    //   dp[i][1]
    // );
    console.log('====================');
  }

  console.table(dp);
  return dp.at(-1)[0];

  // 滚动数组
  // const dp = [0, -prices[0]];
  // for (let i = 1; i < prices.length; i++) {
  //   dp[0] = Math.max(dp[0], dp[1] + prices[i]);
  //   dp[1] = Math.max(dp[1], -prices[i]);
  // }
  // return dp[0];
}
// maxProfit();

function maxProfit(prices = [7, 1, 5, 3, 6, 4]) {
  // // 未持有状态0 持有状态1
  // const dp = Array.from({ length: prices.length }, (v, k) =>
  //   k === 0 ? [0, -prices[k]] : [0, 0]
  // );

  // const result = [];
  // for (let i = 1; i < prices.length; i++) {
  //   // 未持有 前一天未持有 || 前一天持有，今天卖出
  //   dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  //   // 持有 前一天持有 || 前一天未持有，今天买入
  //   dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  //   if (dp[i][0] - dp[i - 1][0]) {
  //     result.push(dp[i][0] - dp[i - 1][0]);
  //   }
  // }
  // console.table(dp);
  // console.log(result);
  // console.log(
  //   result
  //     .sort((a, b) => b - a)
  //     .slice(0, 2)
  //     .reduce((sum, v) => sum + v, 0)
  // );

  // 1 买入1  2 卖出1   3 买入2   4 卖出2
  const dp = Array.from({ length: prices.length }, (_, k) =>
    k === 0 ? [0, -prices[0], 0, -prices[0], 0] : [0, 0, 0, 0, 0]
  );
  for (let i = 1; i < prices.length; i++) {
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
    dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
    dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
  }
  return dp.at(-1)[4];
}

// maxProfit([1, 2, 3, 4, 5]);
// maxProfit([3, 3, 5, 0, 0, 3, 1, 4]);

function maxProfit1(k, prices) {
  const dp = Array.from({ length: prices.length }, (_, index) => {
    const arr = Array(2 * k + 1).fill(0);
    return index === 0 ? arr.map((_, i) => (i & 1 ? -prices[0] : 0)) : arr;
  });

  for (let i = 1; i < prices.length; i++) {
    for (let j = 1; j <= 2 * k; j++) {
      if (j & 1) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
      }

      dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + (j & 1 ? -prices[i] : prices[i]));
    }
  }
  console.table(dp);
  return dp.at(-1).at(-1);
}

// maxProfit1(3, [3, 3, 5, 0, 0, 3, 1, 4]);

function maxProfit2(prices) {
  const dp = Array.from({ length: prices.length }, (_, k) =>
    k === 0 ? [0, -prices[k], 0] : [0, 0, 0]
  );
  for (let i = 1; i < prices.length; i++) {
    // 不持有非冷冻  持有   冷冻期
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    dp[i][2] = dp[i - 1][1] + prices[i];
  }
  console.table(dp);
  return Math.max(dp.at(-1)[0], dp.at(-1)[2]);
}

// maxProfit2([1, 2, 3, 0, 2]); // 1 2 0 2

/**
 *@see {@link https://leetcode.cn/problems/Gu0c2T/description/ | LCR 089. 打家劫舍}
 * @param {number[]} nums
 * @returns {number}
 */

function rob(nums = [1, 2, 3, 1]) {
  const dp = Array(nums.length).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  return dp.at(-1);
}
/**
 * @see {@link https://leetcode.cn/problems/longest-increasing-subsequence/description/ | 力扣 300. 最长递增子序列 }
 * @param {number[]} nums
 * @returns number
 */
function lengthOfLIS(nums = [10, 9, 2, 5, 3, 7, 101, 18]) {
  // 递归 + 记忆化搜索
  // let ans = 0;
  // // const memo = {};
  // function len(nums, i) {
  //   // if (memo[i]) return memo[i];
  //   if (i === nums.length - 1) return 1;
  //   let maxLen = 1;
  //   for (let j = i + 1; j < nums.length; j++) {
  //     if (nums[j] > nums[i]) {
  //       maxLen = Math.max(maxLen, len(nums, j) + 1);
  //     }
  //   }
  //   // memo[i] = maxLen;
  //   return maxLen;
  // }
  // for (let i = 0; i < nums.length; i++) {
  //   ans = Math.max(ans, len(nums, i));
  // }

  const dp = Array(nums.length).fill(1);
  // 以每个元素开头的最长递增子序列的长度
  // for (let i = nums.length - 1; i >= 0; i--) {
  //   for (let j = i + 1; j < nums.length; j++) {
  //     if (nums[i] < nums[j]) {
  //       dp[i] = Math.max(dp[i], dp[j] + 1);
  //     }
  //   }
  // }

  // 以每个元素结尾的最长递增子序列的长度
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  console.log('dp :>> ', dp);
  return Math.max(...dp);
}

// console.time('lengthOfLIS');
// const arr = [
//   637, 261, 759, 367, 814, 707, 965, 861, 757, 667, 944, 542, 29, 860, 476, 794, 993, 255, 664, 53, 922, 160, 115, 380,
//   480, 889, 252, 389, 556, 104, 587, 982, 13, 748, 221, 417, 286, 186, 938, 888, 784, 398, 163, 780, 816, 73, 142, 632,
//   952, 455, 129, 135, 1, 892, 5, 214, 792, 220, 169, 893, 170, 296, 321, 203, 552, 897, 694, 640, 209, 962, 994, 201,
//   915, 392, 305, 22, 369, 424, 941, 149, 270, 66, 339, 308, 837, 617, 600, 3, 610, 933, 724, 346, 67, 317, 363, 838,
//   313, 492, 713, 323
// ];
// console.log(lengthOfLIS());

// console.timeEnd('lengthOfLIS');