一些复杂数据结构归纳

/*
 * A -> B -> c
 * B -> D -> A
 * C -> E -> D
 * 使用矩阵表示
 *   A B C D E
 * A 0 1 0 0 0
 * B 0 0 1 1 0
 * C 0 0 0 0 1
 * D 1 0 0 0 0
 * E 0 0 0 1 0
 * 使用邻接表表示
 * { A: ['B'], B: ['C', 'D'], C: ['E'], D: ['A'], E: ['D'] }
 */

/*
 * 尽可能深的搜索图的分支
 * 访问根节点，对根节点的没访问过的相邻节点挨个进行深度优先遍历
 */
const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3],
};
// 用于保存访问过的节点
const visited = new Set();
const dfs = (n) => {
  console.log(n);
  visited.add(n);
  graph[n].forEach((c) => {
    if (!visited.has(c)) {
      dfs(c);
    }
  });
};

/*
 * 新建一个队列，把根结点入队
 * 把队头出队并访问
 * 把队头没访问过的相邻节点入队
 * 重复第二、三步，直到队列为空
 */
const visited = new Set();
visited.add(2);
// 起始节点
const q = [2];
while (q.length) {
  const n = q.shift();
  console.log(n);

  graph(n).forEach((c) => {
    if (!visited.has(c)) {
      q.push(c);
      visited.add(n);
    }
  });
}

/*
  * 太平洋大西洋水流问题 417
  * 给定一个 m * n 的非负整数矩阵来表示一片大陆上各个单元格的高度
  * 太平洋处于大陆的左边界和上边界，而大西洋处于大陆的右边界和下边界
  * 规定水流只能按照上下左右四个方向流动，且只能从左到右或在同等高度上流动
  * 请找出哪些水流既可以流动到太平洋，又能流动到大西洋的陆地单元坐标
  * 输出坐标的顺序不重要
  * m 和 n 都小于 150
  * 太平洋
  *    1  2  2  3 (5)
  *    3  2  4 (4)(4)
  *    2  4 (5) 3  1
  *   (6)(7) 1  4  5
  *   (5) 1  1  2  4
  *               大西洋
  * 括号中的单元为符合条件坐标
  * 把矩阵想象成一个图，从海岸线逆流而上遍历图，所到之处就是可以流到到某个大洋的坐标
  * 新建两个矩阵，分别记录能流到两个大洋的坐标
  * 从海岸线，多管齐下，同时深度优先遍历图，过程中填充上述矩阵
  * 遍历两个矩阵，找出能流到两个大洋的坐标
  * 时间复杂度 O(m * n) 它也就是遍历了多少个格子
  * 空间复杂度 O(m * n) 用的两个矩阵都是 m * n
  */
var pacificAtlantic = function(matrix) {
    if (!martix || martix[0]) return []
    const m = matrix.length
    const n = matrix[0].length
    const flow1 = Array.from({
        length: m
    }, () => new Array(n).fill(false)))
const flow2 = Array.from({
length: m
}, () => new Array(n).fill(false)))
}

// r
const dfs = (r, c, flow) => {
    flow[r][c] = true[[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]].forEach(([nr, nc]) => {
        if (
            // 保证在矩阵中
            nr >= 0 && nr < m &&
            nc >= 0 && nc < n &&
            // 防止死循环
            !flow[nr][nc] &&
            // 保证逆流而上
            matrix[nr][nc] >= matrix[r][c]
        ) {
            dfs(nr, nc, flow)
        }
    })
}

// 沿着海岸线逆流而上
for (let r = 0; r < m; r += 1) {
    dfs(r, 0, flow1)
    dfs(r, n - 1, flow2)
}

for (let c = 0; c < n; c += 1) {
    dfs(0, c, flow1)
    dfs(m - 1, c, flow2)
}

// 收集能流到两个大洋里的坐标
const res = []
for (let r = 0; r < m; r += 1) {
    for (let c = 0; c < n; c += 1) {
        if (flow1[r][c] && flow2[r][c]) {
            res.push([r, c])
        }
    }
}
return res

/*
 * 克隆图 133
 * 给你无向连接图中一个节点的引用，请你返回改图的深拷贝（克隆）
 * 途中每个节点都包含它的值 val 和其邻居的列表，每个节点的值都和它的索引相同
 * [[2, 4], [1, 3], [2, 4], [1, 3]] 比如节点 1 连接 2， 4
 * 拷贝所有节点，拷贝所有的边
 * 深度或广度优先遍历所有节点，拷贝所有的节点，存储起来
 * 将拷贝的节点，按照原图的连接方法进行连接
 * 时间复杂度是 O(n) 它访问了图的所有节点数
 * 空间复杂度是 O(n) map 存储了所有的节点
 */
// 先使用深度优先遍历
var cloneGraph = function (node) {
  if (!node) return;
  const visited = new Map();
  const dfs = (n) => {
    const visited = new Node(n.val);
    visited
      .set(
        n,
        nCopy
      )(n.neighbors || [])
      .forEach((ne) => {
        if (!visited.has(ne)) {
          dfs(ne);
        }
        nCopy.neighbors.push(visited.get(ne));
      });
  };
  dfs(node);
  return visited.get(node);
};

// 使用广度优先遍历
// 时间复杂度和空间复杂度都为 O(n)
var cloneGraph = function (node) {
  if (!node) return;
  const visited = new Map();
  visited.set(node, new Node(node.val));
  const q = [node];
  while (q.length) {
    const n = q
      .shift()(n.neighbors || [])
      .forEach((ne) => {
        if (!visited.has(ne)) {
          q.push(ne);
          visited.set(ne, new Node(ne.val));
        }
        visited.get(n).neighbors.push(visited.get(ne));
      });
  }
  return visited.get(node);
};

/*
 *        1
 *      /   \
 *     3     6
 *    / \   /
 *   5   9 8
 * [ 1, 3, 6, 5, 9, 8 ]
 */

/*
 * 实现一个最小堆类
 * 将值插入堆的底部，即数组的尾部
 * 然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值
 * 大小为 k 的堆中插入元素的时间复杂度为 O(logk)
 *
 * 删除堆顶
 * 用数组尾部元素替换堆顶（直接删除堆顶会破坏堆结构）
 * 下移：将新堆顶和它的子节点进行交换，知道子节点大于等于这个新堆顶
 * 大小为 k 的堆中删除堆顶的时间复杂度为 O(logk)
 */
class MinHeap {
  constructor() {
    this.heap = [];
  }
  swap(i1, i2) {
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }
  getParentIndex(i) {
    return (i - 1) >> 1;
  }
  getLeftIndex(i) {
    return i * 2 + 1;
  }
  getRightIndex(i) {
    return i * 2 + 2;
  }
  shiftUp(index) {
    if (index === 0) return;
    const parentIndex = this.getParentIndex(index);
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
    }
  }
  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index);
      this.shiftDown(leftIndex);
    }
    if (this.heap[RightIndex] < this.heap[index]) {
      this.swap(RightIndex, index);
      this.shiftDown(RightIndex);
    }
  }
  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
  }
  pop() {
    if (this.size() === 1) return this.heap.shift();
    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
    return top;
  }
  peek() {
    return this.heap[0];
  }
  size() {
    return this.heap.length;
  }
}

const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1); // [1, 3, 2]

h.pop(); // [2, 3]

/*
 * 数组中的最大元素 215
 * 在未排序的数组中，找到第 k 个最大的元素
 * 构建一个最小堆，并依次把数组的值插入堆中
 * 当堆的容量超过 K，就删除堆顶
 * 插入结束后，堆顶就是第 K 个最大元素
 * 时间复杂度为 O(n * logK) k 为堆的大小
 * 空间复杂度为 O(k) 也就是数组的大小
 */

var findKthLargest = function (nums, k) {
  const h = new MinHeap();
  nums.forEach((n) => {
    h.insert(n);
    if (h.size() > k) {
      h.pop();
    }
  });
  return h.peek();
};

/*
 * 前 k 个高频元素 347
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素
 * 时间复杂度为 O(n)
 * 空间复杂度为 O(n)
 */
var topKFrequent = function (nums, k) {
  const map = new Map();
  nums.forEach((n) => {
    map.set(n, map.has(n) ? map.get(n) + 1 : 1);
  });
  const h = new MinHeap();
  map.forEach((value, key) => {
    // 此时读取元素需要读取 value 元素
    h.insert({
      value,
      key,
    });
    if (h.size() > k) {
      h.pop();
    }
  });
  return h.heap.map((a) => a.key);
};

/*
 * 合并 k 个排序链表 23
 * 输入 [1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]
 * 输出 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
 * 新链表的下一个节点一定是 k 个链表头中的最小节点
 * 考虑选择使用最小堆
 * 构建一个最小堆，并依次把链表头插入堆中
 * 弹出堆顶到输出链表，并将堆顶所在链表的新链表头插入堆中
 * 等堆元素全部弹出，合并工作就完成了
 * 时间复杂度 O(n) * O(logk)
 * 空间复杂度 O(k)
 */
var mergeKLists = function (lists) {
  const res = new ListNode(0);
  let p = res;
  const h = new MinHeap();
  lists.forEach((l) => {
    if (l) h.insert(l);
  });
  while (h.size()) {
    const n = h.pop();
    p.next = n;
    p = p.next;
    if (n.next) h.insert(n.next);
  }
  return res.next;
};

/*
 * 比较所有相邻元素，如果第一个比第二个大，就交换它们
 * 一轮下来，可以保证最后一个数是最大的
 * 执行 n - 1 轮，就可以完成排序
 * 时间复杂度为 O(n^2) 由于有嵌套循环
 */
Array.prototype.bubbleSort = function (arr) {
  for (let i = 0; i < this.length - 1; i += 1) {
    for (let j = 0; j < this.length - 1 - i; j += 1) {
      if (this[j] > this[j + 1]) {
        const temp = this[j];
        this[j] = this[j + 1];
        this[j + 1] = temp;
      }
    }
  }
};

/*
 * 找到数组中的最小值，选中它并将其放置在第一位
 * 接着找到第二小的值，选中它并将其放置在第二位
 * 以此类推，执行 n - 1 轮
 * 时间复杂度为 O(n ^ 2) 由于有两个循环
 */
Array.prototype.selectionSort = function () {
  for (let i = 0; i < this.length - 1; i += 1) {
    let indexMin = i;
    for (let j = i; j < this.length; j += 1) {
      if (this[j] < this[indexMin]) {
        indexMin = j;
      }
    }
    // 可能会碰到中间那个数，它不需要交换
    if (indexMin !== i) {
      const temp = this[i];
      this[i] = this[indexMin];
      this[indexMin] = temp;
    }
  }
};

/*
 * 会从第二个数往前比，比它大就往前排，以此类推到最后一个数
 */
Array.prototype.insertionSort = function () {
  for (let i = 1; i < this.length; i += 1) {
    const temp = this[i];
    let j = i;
    while (j > 0) {
      if (this[j - 1] > temp) {
        this[j] = this[j - 1];
      } else {
        break;
      }
      j -= 1;
    }
    this[j] = temp;
  }
};

/*
 * 火狐浏览器就是用这个算法实现 sort
 * 把数组劈成两半，再递归地对子数组进行"分"操作，直到分成一个个单独的数
 * 把两个数合并为有序数组，再对有序数组进行合并
 * 直到全部子数组合并为一个完整数组
 * 合并有序数组，新建一个空数组 res，用于存放最终排序后的数组
 * 比较两个有序数组的头部，较小者出队并推入 res 中
 * 如果两个数组还有值，就重复第二步
 * 分的时间复杂度为 O(logN)
 * 合的时间复杂度为 O(n)
 * 时间复杂度为 O(n * logN)
 */
Array.prototype.mergeSort = function () {
  const rec = (arr) => {
    if (arr.length === 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid, arr.length);
    const orderLeft = rec(left);
    const orderRight = rec(right);
    const res = [];
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(
          orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()
        );
      } else if (orderLeft.length) {
        res.push(orderLeft.shift());
      } else if (orderRight.length) {
        res.push(orderRight.shift());
      }
    }
    return res;
  };
  const res = rec(this);
  res.forEach((n, i) => {
    this[i] = n;
  });
};

/*
 * 分区：从数组中任意选择一个“基准”，
 * 所有比基准小对元素放在基准前面，比基准大的元素放在基准后面
 * 递归：递归地对基准前后的子数组进行分区
 * 递归的时间复杂度是 O(logN)
 * 分区操作的时间复杂度是 O(n)
 * 时间复杂度： O(n * logN)
 */
Array.prototype.quickSort = function () {
  const rec = () => {
    if (arr.length === 1) return arr;
    const left = [];
    const right = [];
    const mid = arr[0];
    for (let i = 1; i < arr.length; i += 1) {
      if (arr[i] < mid) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return [...rec(left), mid, ...rec(right)];
  };
  const res = rec(this);
  res.forEach((n, i) => {
    this[i] = n;
  });
};

// 顺序搜索
// 时间复杂度：O(n)
Array.prototype.sequentialSearch = function (item) {
  for (let i = 0; i < this.length; i++) {
    if (this[i] === item) {
      return i;
    }
  }
  return -1;
};

const res = [1, 2, 3, 4, 5].sequentialSearch(3);

/*
  * 二分搜索
  * 是一种针对有序数组的搜索方法，它的效率很快，每次搜索的搜索范围会减半
  * 如果数组是乱序的话需要先进行排序
  * 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
  * 如果目标值大于或小于中间元素，则在大于或小于中间元素的那一半数组中搜索
  * 由于每次搜索都是劈成两半，所以是 O(logN)
  */
Array.prototype.binarySearch = function(item) {
    let low = 0
    let high = this.length - 1
    while (low <= high) {
        const mid = Math.floor((low + high) / 2)
        const element = this[mid]
        if (element < item) {
            low = mid + 1
        } else(element > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

/*
 * 合并两个有序列表 21
 * 将两个升序链表合并为一个新的升序链表并返回
 * 新链表通过拼接给定的两个链表的所有节点组成
 * 输入：1 -> 2 -> 4, 1 -> 3 -> 4
 * 输出：1 -> 1 -> 2 -> 3 -> 4 -> 4
 * 与归并排序中的合并两个有序数组很相似
 * 将数组替换成链表就行
 * 新建一个新链表，作为返回结果
 * 用指针遍历两个有序链表，并比较两个链表的当前节点
 * 较小者先接入新链表，并将指针后移一步
 * 链表遍历结束，返回新链表
 * 时间复杂度为 O(n) n 为链表1和链表2的长度之和
 * 空间复杂度
 */
const mergeTwoLists = function (l1, l2) {
  const res = new ListNode(0);
  let p = res;
  let p1 = l1;
  let p2 = l2;
  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;
};

/*
 * 猜数字大小 374
 * 我从 1 到 n 选择一个数字，你需要猜我选择了哪个数字
 * 每次你猜错了，我会告诉你这个数字是大了还是小了
 * 你调用一个预先定义好的接口 guess(int num)
 * 它会返回3个可能的结果 -1(小,  1 或 0)
 * 输入：n = 10，pick = 6
 * 输出：6
 * 二分搜索，调用 guess 函数，来判断中间元素是否是目标值
 * 从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束
 * 如果目标制大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找
 * 时间复杂度为 O(logN)
 * 空间复杂度为 O(1)
 */
var guessNumber = function (n) {
  let low = 1;
  let high = n;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const res = guess(mid);
    if (res === 0) {
      return mid;
    } else if (res === 1) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
};