前端数据结构与算法总结＜week three＞

标题没有错哈哈
还多了零，想概括得更全面一点~

零、String 字符串

0.1 验证回文串

0.1.1 思路

• 将原始字符串转化为只有小写字母和数字字符串，利用双指针进行比对

0.1.2 步骤

1. 设置正则表达式进行匹配
2. 将不符合正则表达式的去掉
3. 头尾比较

0.1.3 代码

var isPalindrome = function (s) {
  let pattern = /[^a-z0-9]/gi;
  s = s.replace(pattern, "").toLocaleLowerCase();
  if (!s.length) {
    return true;
  }

  let j = s.length - 1;
  for (let i = 0; i <= j; i++) {
    if (i === j) return true;
    if (s[i] === s[j]) {
      j--;
    } else {
      return false;
    }
  }
  return true;
};

三、LinkList 链表

3.7 合并两个有序链表

3.7.1 思路

• 有种归并排序合并的意思

3.7.2 步骤

1. 创建新链表
2. 设置 p1，p2
3. 比较俩链表大小

3.7.3 代码

var mergeTwoLists = function (list1, list2) {
  const res = new ListNode(0);
  let p = res;
  let p1 = list1;
  let p2 = list2;
  while (p1 && p2) {
    if (p1.val < p2.val) {
      p.next = p1;
      p1 = p1.next;
    } else {
      p.next = p2;
      p2 = p2.next;
    }
    p = p.next;
  }
  if (p1) {
    p.next = p1;
  }
  if (p2) {
    p.next = p2;
  }
  return res.next;
};

七、Heap 堆

7.2 二叉堆

7.2.1 思路

• 封装 ***pare 函数，判断是否需要最大堆
• 在 constructor 中构建，默认为 true

7.2.2 步骤

• 传入 i，j
• 比较对应位置大小，返回 true or false

7.2.3 代码

class Heap {
  data = [];
  length = 0;
  isMax;
  constructor(arr, isMax = true) {
    this.isMax = isMax;
    this.buildHeap(arr);
  }
  ***pare(i, j) {
    if (this.isMax) {
      return this.data[i] >= this.data[j];
    } else {
      return this.data[i] <= this.data[j];
    }
  }
  swap(i, j) {
    const temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }
  insert(value) {
    this.data.push(value);
    this.length++;
    this.heapify_up();
  }
  heapify_up() {
    const index = this.data.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.***pare(parentIndex, index)) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }
  extract() {
    if (this.length === 0) return undefined;
    if (this.length === 1) {
      this.length--;
      return this.data.pop();
    }
    const topValue = this.data[0];
    this.length--;
    this.heapify_down(0);
    return topValue;
  }
  heapify_down(index) {
    while (2 * index + 1 < this.length) {
      let leftindex = 2 * index + 1;
      let rightIndex = 2 * index + 2;
      let largerIndex = leftindex;
      if (rightIndex <= this.length && this.***pare(leftindex, rightIndex)) {
        largerIndex = rightIndex;
      }
      if (this.***pare(index, largerIndex)) break;
      this.swap(largerIndex, index);
      index = largerIndex;
    }
  }
  buildHeap(arr) {
    this.data = arr;
    this.length = arr.length;
    const start = Math.floor((this.length - 1) / 2);
    for (let i = start; start >= 0; start--) {
      this.heapify_down(i);
    }
  }
  peek() {
    return this.data[0];
  }
  size() {
    return this.length;
  }
  isEmpty() {
    return this.length === 0;
  }
}

7.3 数组中的第 K 个最大元素

7.3.1 思路

• 构建最小堆
• 只保留 k 个元素
• 堆顶就是第 k 个最大元素

7.3.2 步骤

1. 遍历数组元素，依次插入最小堆中
2. 当 size 大于 k 的时候，就提取堆顶
3. 最后返回堆顶元素

7.3.3 代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
class Heap {
  data = [];
  length = 0;
  swap(i, j) {
    const temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }
  insert(value) {
    this.data.push(value);
    this.length++;
    this.heapify_up();
  }
  heapify_up() {
    let index = this.data.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.data[parentIndex] <= this.data[index]) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }
  extract() {
    if (this.length === 0) return undefined;
    if (this.length === 1) {
      this.length--;
      return this.data.pop();
    }
    const topValue = this.data[0];
    this.data[0] = this.data.pop();
    this.length--;
    this.heapify_down(0);
    return topValue;
  }
  heapify_down(index) {
    while (2 * index + 1 < this.length) {
      let leftindex = 2 * index + 1;
      let rightIndex = 2 * index + 2;
      let largerIndex = leftindex;
      if (rightIndex <= this.length && this.data[leftindex] > this.data[rightIndex]) {
        largerIndex = rightIndex;
      }
      if (this.data[index] <= this.data[largerIndex]) break;
      this.swap(largerIndex, index);
      index = largerIndex;
    }
  }
  buildHeap(arr) {
    this.data = arr;
    this.length = arr.length;
    const start = Math.floor((this.length - 1) / 2);
    for (let i = start; start >= 0; start--) {
      this.heapify_down(i);
    }
  }
  peek() {
    return this.data[0];
  }
  size() {
    return this.length;
  }
  isEmpty() {
    return this.length === 0;
  }
}

var findKthLargest = function (nums, k) {
  const heap = new Heap();
  nums.forEach((n) => {
    heap.insert(n);
    if (heap.size() > k) {
      const res = heap.extract();
      console.log(res);
    }
  });
  return heap.peek();
};

7.4 前 K 个高频元素

7.4.1 思路

• 构建最小堆
• 插入元素和频率

7.4.2 步骤

1. 记录数组中每个元素和对应的频率
2. 创建最小堆
   • 插入元素
   • 保持堆中只有 k 的元素
3. 返回所有的元素

7.4.3 代码

class Heap {
  data = [];
  length = 0;
  swap(i, j) {
    const temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }
  insert(value) {
    this.data.push(value);
    this.length++;
    this.heapify_up();
  }
  heapify_up() {
    let index = this.data.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.data[parentIndex] && this.data[parentIndex].value <= this.data[index].value) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }
  extract() {
    if (this.length === 0) return undefined;
    if (this.length === 1) {
      this.length--;
      return this.data.pop();
    }
    const topValue = this.data[0];
    this.data[0] = this.data.pop();
    this.length--;
    this.heapify_down(0);
    return topValue;
  }
  heapify_down(index) {
    while (2 * index + 1 < this.length) {
      let leftindex = 2 * index + 1;
      let rightIndex = 2 * index + 2;
      let largerIndex = leftindex;
      if (this.data[rightIndex] && rightIndex <= this.length && this.data[leftindex].value > this.data[rightIndex].value) {
        largerIndex = rightIndex;
      }
      if (this.data[index].value <= this.data[largerIndex].value) break;
      this.swap(largerIndex, index);
      index = largerIndex;
    }
  }
  buildHeap(arr) {
    this.data = arr;
    this.length = arr.length;
    const start = Math.floor((this.length - 1) / 2);
    for (let i = start; start >= 0; start--) {
      this.heapify_down(i);
    }
  }
  peek() {
    return this.data[0];
  }
  size() {
    return this.length;
  }
  isEmpty() {
    return this.length === 0;
  }
}
var topKFrequent = function (nums, k) {
  const map = new Map();
  nums.forEach((num) => {
    map.set(num, map.has(num) ? map.get(num) + 1 : 1);
  });
  const heap = new Heap();
  map.forEach((value, key) => {
    heap.insert({ key, value });
    if (heap.size() > k) {
      heap.extract();
    }
  });
  return heap.data.map((item) => item.key);
};

7.4 合并k个排序链表

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

7.4.1 思路

• 构建最小堆
• 把堆中所有元素放在新链表上

7.4.2 步骤

1. 创建新节点和指针
2. 构建最小堆
3. 将所有链表的头部节点放入最小堆
4. 弹出堆中的元素
5. 放在新的链表上面

7.4.3 代码

class Heap {
  data = [];
  length = 0;
  swap(i, j) {
    const temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }
  insert(value) {
    this.data.push(value);
    this.length++;
    this.heapify_up();
  }
  heapify_up() {
    let index = this.data.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.data[parentIndex] && this.data[parentIndex].val <= this.data[index].val) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }
  extract() {
    if (this.length === 0) return undefined;
    if (this.length === 1) {
      this.length--;
      return this.data.pop();
    }
    const topValue = this.data[0];
    this.data[0] = this.data.pop();
    this.length--;
    this.heapify_down(0);
    return topValue;
  }
  heapify_down(index) {
    while (2 * index + 1 < this.length) {
      let leftindex = 2 * index + 1;
      let rightIndex = 2 * index + 2;
      let largerIndex = leftindex;
      if (this.data[rightIndex] && rightIndex <= this.length && this.data[leftindex].val > this.data[rightIndex].val) {
        largerIndex = rightIndex;
      }
      if (this.data[index].val <= this.data[largerIndex].val) break;
      this.swap(largerIndex, index);
      index = largerIndex;
    }
  }
  buildHeap(arr) {
    this.data = arr;
    this.length = arr.length;
    const start = Math.floor((this.length - 1) / 2);
    for (let i = start; start >= 0; start--) {
      this.heapify_down(i);
    }
  }
  peek() {
    return this.data[0];
  }
  size() {
    return this.length;
  }
  isEmpty() {
    return this.length === 0;
  }
}
var mergeKLists = function (lists) {
  const res = new ListNode(0);
  let p = res;
  const heap = new Heap();
  lists.forEach((l) => {
    if (l) heap.insert(l);
  });
  while (heap.size()) {
    const n = heap.extract();
    p.next = n;
    p = p.next;
    if (n.next) heap.insert(n.next);
  }
  return res.next;
};

八、Set 集合

8.1 求两个数组的交集和并集

8.1.1 思路

• 交集
  • 将其中一个数组转成集合，遍历另外一个数组，判断集合中是否有这个元素，有就加入新的集合中
• 并集
  • 将其中一个数组转成集合，再将另外一个数组的元素加入

8.1.2 步骤

• 交集
  1. 创建 res 接收元素（集合）
  2. 将 nums1 转成集合
  3. 遍历 nums2 是否元素是否在集合中
  4. 加入 res
  5. 返回 res（转成数组）
• 并集
  1. 将 num1s 转成集合
  2. 遍历 nums2 加入到集合中
  3. 返回集合（转成数组）

8.1.3 代码

// 交集
var intersection = function (nums1, nums2) {
  const res = new Set();
  const arr1 = new Set(nums1);
  nums2.forEach((num) => {
    if (arr1.has(num)) res.add(num);
  });
  return Array.from(res);
};
// 并集
var getUnion = function (nums1, nums2) {
  const arr1 = new Set(nums1);
  nums2.forEach((num) => {
    arr1.add(num);
  });
  return Array.from(arr1);
};

九、Map 字典

9.1 两数之和

9.1.1 思路

• 利用 map 存储 num 和对应的下标，找到另一半就返回，没有就存储

9.1.2 步骤

1. 创建 map
2. 遍历数组
3. 找到返回
4. 没有就存储 set

9.1.3 代码

var twoSum = function (nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const num1 = nums[i];
    const num2 = target - num1;
    if (map.has(num2)) {
      return [i, map.get(num2)];
    }
    map.set(num1, i);
  }
};

9.2 无重复字符的最长子串

9.2.1 思路

• 双指针维护滑动窗口，不断移动右指针，记录最大窗口的长度

9.2.2 步骤

1. 创建左指针
2. 记录最长 res
3. 创建 map
4. 遍历字符串
   • 遇到重复的并且在滑动窗口内，左指针就右移到下一个重复的元素的下一个
   • 更新 res
   • 记录索引
5. 返回 res

9.2.3 代码

var lengthOfLongestSubstring = function (s) {
  let l = 0;
  let res = 0;
  const map = new Map();
  for (let r = 0; r < s.length; r++) {
    if (map.has(s[r]) && map.get(s[r]) >= 1) {
      l = map.get(s[r]) + 1;
    }
    res = Math.max(res, r - l + 1);
    map.set(s[r], r);
  }
  return res;
};

9.3 最小覆盖子串

9.3.1 思路

• 利用双指针维护一个滑动窗口，找到包含 t 的子串之后，移动左指针缩小包含 t 的范围

9.3.2 步骤

1. 创建左指针和右指针
2. 创建 set 记录需要的字符和个数，创建 needType 记录需要字符的种类
3. 设置 res 记录答案
4. while 循环移动右指针
   • 获取当前字符开始筛选
     • 判断 set 中是否有
     • 判断是否满足了所有的种类
       • 否
       • 是
         • substring 获取到当前子串
         • 更新 res
         • 左指针移动需要的字符种类可能会增加
         • l++
   • r++
5. 返回 res

9.3.3 代码

var minWindow = function (s, t) {
  let l = 0;
  let r = 0;
  const need = new Map();
  let res = "";
  for (const c of t) {
    need.set(c, need.has(c) ? need.get(c) + 1 : 1);
  }
  let needType = need.size;
  while (r < s.length) {
    if (need.has(s[r])) {
      need.set(s[r], need.get(s[r]) - 1);
      if (need.get(s[r]) === 0) {
        needType -= 1;
      }
    }
    while (needType === 0) {
      const newStr = s.substring(l, r + 1);
      if (!res || newStr.length < res.length) res = newStr;
      if (need.has(s[l])) {
        need.set(s[l], need.get(s[l]) + 1);
        if (need.get(s[l]) === 1) {
          needType += 1;
        }
      }
      l+=1;
    }
    r+=1;
  }
  return res
};

9.4 实现 URL 缓存

9.4.1 思路

• 使用类实现
• 存储 key 和 value
• 根据 key 取出 value

9.4.2 步骤

1. 属性
   • length
   • data
2. 方法
   • get
     • 之前有
       • 取出删除重新设置
     • 之前无
       • 直接设置
     • 发现容量超出移除最后一个
   • set
     • 取出删除重新设置

9.4.3 代码

class URLCache {
  length = 0;
  data = new Map();
  constructor(length) {
    this.length = length;
  }
  set(key, value) {
    const data = this.data;
    if (data.has(key)) {
      data.delete(key);
    }
    data.set(key, value);
    if (data.size > this.length) {
      const delKey = data.keys().next().value;
      data.delete(delKey);
    }
  }
  get(key) {
    const data = this.data;
    if (!data.has(key)) {
      return null;
    }
    const value = data.get(key);
    data.delete(key);
    data.set(key, value);
    return value;
  }
}

十、Array 数组

10.1 三数之和

10.1.1 思路

• 从小到大排序，去重

10.1.2 步骤

1. 创建数组
2. 不满足条件
3. 从小到大排序
4. 遍历数组
   • 不符合直接 return
   • 对第一个数去重：num[i] num[i-1]
   • 定义左右指针
   • while 循环条件（L<R）L 和 R 不能相等
     • sum === 0
       • 去重条件

10.1.3 代码

function threeSum(nums) {
  const ans = [];
  if (nums.length < 3 || nums == null) return ans;
  const n = nums.length;
  nums.sort((a, b) => a - b);
  for (let i = 0; i < n; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let L = i + 1;
    let R = n - 1;
    while (L < R) {
      const sum = nums[i] + nums[L] + nums[R];
      if (sum === 0) {
        ans.push([nums[i], nums[L], nums[R]]);
        while (L > 0 && nums[L] === nums[L + 1]) L++;
        while (R < n - 1 && nums[R] === nums[R - 1]) R--;
        L++;
        R--;
      } else if (sum < 0) {
        L++;
      } else {
        R--;
      }
    }
  }
  return ans;
}

十二、动态规划

• vue3 的 diff 算法中，最长自增子序列（贪心 + 二分查找）
• 需要用到子问题的解，选择最优的，从而知道整个问题的解
• 核心思想
• 将问题划分为若干个子问题，在子问题的基础上初步构建出原问题的解
• 求解步骤
  • 定义状态
  • 确定状态转移方程
  • 初始化状态
  • 计算最终的结果

12.1 斐波那契

• F0 = 0，F1 = 1
• F2 = F0 + F1

12.1.1 思路

• 递归求解
• 动态规划
• 状态压缩

12.1.2 步骤

• 递归求解
  1. 递归结束条件
• 动态规划
  1. dp 保留斐波那契数列中每一个位置对应的值（状态）
  2. dp[i] = dp[i-1]+dp[i-2]
  3. dp[0]/dp[1]
  4. 直接计算最终的结果
• 状态压缩
  1. 定义状态和初始化状态：prev cur
  2. 循环记录值
  3. 返回当前值

12.1.3 代码

// 一、递归求解
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// 二、动态规划
function fib(n) {
  const dp = [];
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

// 三、状态压缩
function fib(n) {
  if (n <= 1) return n;
  let prev = 0;
  let cur = 1;
  for (let i = 2; i <= n; i++) {
    const newValue = prev + cur;
    prev = cur;
    cur = newValue;
  }
  return cur;
}

12.2 爬楼梯

12.2.1 思路

• 使用 dp

12.2.2 步骤

1. 定义状态
2. 得到状态转移方程
3. 初始化状态
4. 最终答案

12.2.3 代码

function jump(n){
  const dp = [];
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

12.3 买卖股票的最佳时机

只能买卖一次

12.3.1 思路

• 定义状态
• 转移方程
• 初始化
• 最终结果

12.3.2 步骤

1. 定义状态：dp[i]：在这一天卖出能获取的最大收益
2. 状态转移方程
   • dp[i] = price - minPrice + 遍历得到结果
   • dp[i] = max(dp[i-1],price-minPrice)
3. 初始化状态：dp[0] = 0
4. 最终结果

12.3.3 代码

function maxProfit(price) {
  if (price.length <= 1) return 0;
  const n = price.length;
  const dp = [];
  dp[0] = 0;
  let minPrice = price[0];
  for (let i = 1; i <= n; i++) {
    dp[i] = Math.max(dp[i - 1], price - minPrice);
    minPrice = Math.min(minPrice, price[i]);
  }
  return dp[n - 1];
}

function maxProfit(price) {
  const n = price.length;
  if (n <= 1) return 0;
  let prev = 0;
  let minPrice = price[0];
  for (let i = 1; i <= n; i++) {
    prev = Math.max(prev, price[i] - minPrice);
    minPrice = Math.min(minPrice, price[i]);
  }
    return prev
}

12.4 最大子数组和

12.4.1 思路

• 子数组是数组中连续的部分

12.4.2 步骤

1. 定义状态：dp[i] 以 i 位置结尾的连续数组能获取到的最大值
2. 状态转移方程：dp[i] = max(num[i],dp[i-1]+num[i])
3. 初始化状态：dp[0] = num[0]
4. 返回最终结果：遍历 dp 获取到最大值

12.4.3 代码

var maxSubArray = function (nums) {
  const n = nums.length;
  if (n <= 1) return nums[0];
  const dp = [];
  dp[0] = nums[0];
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
  }
  return Math.max(...dp);
};

var maxSubArray = function (nums) {
  const n = nums.length;
  if (n <= 1) return nums[0];
  let max = nums[0];
  let prev = max;
  for (let i = 1; i < n; i++) {
    prev = Math.max(prev + nums[i], nums[i]);
    max = Math.max(prev, max);
  }
  return max;
};

12.5 打家劫舍

相邻房间不能偷

12.5.1 思路

• 和前两个房间有关系

12.5.2 步骤

1. 定义状态：dp[i] 在 i 之前的房间偷到的最大钱数
2. 状态转移方程：dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]) 偷和不偷的两种情况
3. 初始化状态：dp[0] = nums[0] dp[1] =Math.max(dp[0],nums[1] )
4. 返回最终结果

12.5.3 代码

var rob = function(nums) {
  const n = nums.length
  if (n < 0) return 0
  const dp = []
  dp[0] = nums[0]
  dp[1] = Math.max(dp[0], nums[1])
  for (let i = 2; i < n; i++){
    dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i])
  }
  return dp[n-1]
};

12.6 打家劫舍 二

房间围成了一个环

12.6.1 思路

• 首和尾只能选择一个
• 两种情况
  • 不考虑尾元素
  • 不考虑首元素

12.6.2 步骤

1. 两种结果取最大值
   • 定义状态：dp[i] 在 i 之前的房间偷到的最大钱数
   • 状态转移方程：dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]) 偷和不偷的两种情况
   • 初始化状态：dp[0] = nums[0] dp[1] =Math.max(dp[0],nums[1] )
   • 返回最终结果

12.6.3 代码

var rob = function (nums) {
  const n = nums.length;
  if (n < 0) return 0;
  if (n === 1) return nums[0];
  const result1 = robRange(nums, 0, n - 1);
  const result2 = robRange(nums, 1, n);
  return Math.max(result1, result2);
};
var robRange = function (nums, start, end) {
  if (start === end) return nums[start];
  const dp = [];
  dp[start] = nums[start];
  dp[start + 1] = Math.max(dp[start], nums[start + 1]);
  for (let i = start + 2; i < end; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[end - 1];
};

十三、排序算法

13.1 冒泡排序

13.1.1 思路

• 大的元素每次浮动到数组尾端

13.1.2 步骤

1. 两层循环
2. 判断前者是否比后者大
3. 前一轮没有交换后面就不需要扫描了

13.1.3 代码

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    let swaped = false;
    for (let j = 0; j < n - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swaped = true;
      }
    }
    if (!swaped) break;
  }
  return arr;
}

13.2 选择排序

13.2.1 思路

• 在未排序的数组中找到最小元素，将其放在数组的起始位置

13.2.2 步骤

1. 双层遍历
2. 刚开始设置第一个为最小
3. 从后面开始找，找到最小的 index
4. 当前 index 不等于 最小的 index 就交换

13.2.3 代码

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

13.3 插入排序

13.3.1 思路

• 类似于打牌，每次从未排序的数组中获取元素放在已经排序后的数组中

13.3.2 步骤

1. for（未排好序的元素） ＋ while 循环（每次跟前面的比较）
2. 每次比较从排好序数组的倒数第一个开始

13.3.2 代码

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

13.4 归并排序

13.4.1 思路

• 分解 Divide(分解 logn 次)：使用递归算法
  • 如果待排序数组长度为一，认为数组已经有序，直接返回
  • 将待排序数组分成两个长度相等的子数组，分别对这两个子数组进行递归排序
  • 将两个排好序的子数组合并成一个有序数组，返回这个有序数组
• 合并 Merge：合并过程中需要比较每个子数组的元素并将他们有序地合并成一个新的数组
  • 使用双指针:使用 i 和 j 分别指向两个子数组的开头,比较它们的元素大小,并将小的元素插入到新的有序数组中
  • 如果其中一个子数组已经遍历完,就将另一个子数组的剩余部分直接插入到新的有序数组中
  • 最后返回这个有序数组
• 递归终止条件
  • 当子数组的长度为一时,认为这个子数组已经有序,递归结束

13.4.2 步骤

1. 递归结束条件
2. 开始划分数组递归
3. 合并过程

13.4.3 代码

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  let leftArr = arr.slice(0, mid);
  let rightArr = arr.slice(mid);
  const newLeftArr = mergeSort(leftArr);
  const newRightArr = mergeSort(rightArr);
  let i = 0;
  let j = 0;
  let newArr = [];
  while (i < newLeftArr.length && j < newRightArr.length) {
    if (newLeftArr[i] <= newRightArr[j]) {
      newArr.push(newLeftArr[i]);
      i++;
    } else {
      newArr.push(newRightArr[j]);
      j++;
    }
  }
  if (i < newLeftArr.length) {
    newArr.push(...newLeftArr.slice(i));
  }
  if (j < newRightArr.length) {
    newArr.push(...newRightArr.slice(j));
  }
  return newArr;
}

13.5 快速排序

13.5.1 思路

• 在里面写一个递归

• 基本思路是将一个大数组分成两个小数组，然后递归地对两个小数组进行排序

• 通过选择一个基准元素，将数组分成左右两个部分，左部分的元素都小于或等于基准元素，右部分的元素都大于基准元素

  • 利用双指针算法，i找到比基准元素大的元素，j找到比基准元素小的元素
  • 直到 j 越过 i，基准元素和i交换

• 对左右两部分分别进行递归调用快速排序，最终将整个数组排序

13.5.2 步骤

1. 内部封装 partition 函数
2. 递归结束条件

13.5.3 代码

function quickSort(arr) {
  partition(0, arr.length);
  function partition(left, right) {
    if (left >= right) return;
    const pivot = arr[right];
    let i = left;
    let j = right - 1;
    while (i <= j) {
      while (arr[i] < pivot) {
        i++;
      }
      while (arr[j] < pivot) {
        j--;
      }
      if (i <= j) {
        const temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
        i++;
        j--;
      }
    }
    const temp = arr[i];
    arr[i] = arr[right];
    arr[right] = temp;
    partition(left, j);
    partition(i + 1, right);
  }
  return arr;
}

13.6 堆排序

13.6.1 思路

• 先原地建堆
• 然后对最大堆进行排序（升序）

13.6.1 步骤

1. 获取长度
2. 从第一个非叶子节点开始下滤操作
3. 将最大值交换到最后，从堆顶元素开始下滤

13.6.2 代码

function heapSort(arr) {
  const n = arr.length;
  const start = Math.floor(n / 2 - 1);
  for (let i = start; i >= 0; i--) {
    heapifyDown(arr, n, i);
  }
  for (let i = 0; i < n; i++) {
    swap(arr, i, n - 1);
    heapifyDown(arr, n, i);
  }
  return arr;
}

function heapifyDown(arr, n, index) {
  while (2 * index + 1 < n) {
    let leftIndex = 2 * index + 1;
    let rightIndex = 2 * index + 2;
    let largerIndex = leftIndex;
    if (rightIndex && arr[rightIndex] > arr[leftIndex]) {
      largerIndex = rightIndex;
    }
    if (arr[index] >= arr[largerIndex]) {
      break;
    }
    swap(arr, index, largerIndex);
    index = largerIndex;
  }
}
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

十四、贪心算法

14.1 买卖股票的最佳时机二

支持多次买卖

14.1.1 思路

• 贪心算法，每次有利润就卖出

14.1.2 步骤

1. 定义利润进行记录
2. 遍历数组进行累加

14.1.3 代码

function maxProfit(price) {
  let profit = 0
  for (let i = 1; i < price.length; i++){
    if (price[i] > price[i - 1]) {
      profit += price[i]-price[i-1]
    }
  }
  return profit
}

14.2 分发饼干

g 胃口 = [1,2,3], s 饼干 = [1,1]

14.2.1 思路

• 从小到大排序，累计分发的值

14.2.2 步骤

1. 定义排序函数
2. 进行排序
3. 遍历饼干看能满足多少个孩子的胃口

14.2.3 代码

var findContentChildren = function (g, s) {
  const sortFunc = (a, b) => {
    return a - b;
  };
  s.sort(sortFunc);
  g.sort(sortFunc);
  let count = 0;
  s.forEach((n) => {
    if (n >= g[count]) {
      count++;
    }
  });
  return count;
};