时间复杂度

可以理解为进行了多少次常数操作的指标（加、减、乘、除、数组寻址），只会取通项公式系数最高

常数操作为 O(1)

冒泡排序为类似于等差数列，等差数列通项公式 Sₙ=na₁+n(n-1)d/2 即为 O(n^2)

二分查找为 O(logN)

异或

1、异或满足结合律与分配律

2、相同数字异或为0，任何数异或0 都为任何数

3、可以理解为无进位相加

代码值的相互替换可以不生成新的变量（内存地址不可以相同，如果相同则为自己异或自己结果为0）

let a = 10;
let b = 9;

a = a ^ b;
b = a ^ b;
a = a ^ b;
// a = 9 , b = 10
/*
a => 1001
b => 1010 
第一次异或 a => 0011 b => 1010
第二次异或 b => 1001 a => 0011
第三次异或 a => 1010 b => 1001
*/

题目：有一个数组有N个数出现偶数次、1个数出现奇数次

let arr = [1,2,3,3,4,2,1,1,1,3,4];
let eor = 0;
arr.forEath(item => {
  eor ^= item;
})
// 由于满足交换律 => [1,1,1,1,2,2,3,3,3,4,4] 
// 由于满足结合律 => [(1,1),(1,1),(2,2),(3,3),3,(4,4)]
// 由于自己异或自己结果为0，0异或任何数都为任何数 可知结果为3

console.log("出现奇数次的数",eor)

题目：有一个数组有N个数出现偶数次、2个数出现奇数次

let arr = [1,2,3,3,4,2,1,1,1,3,4,5];
let eor = 0;
arr.forEath(item => {
  eor = eor ^ item; // 此时eor 肯定有一个位置为1 (3 ^ 5)
})
// 获取一个数二进制最右侧的1
// eor = 0011 ^ 0101 => 0110
// ~eor = 1001；~eor + 1 = 1010
// eor & ~eor + 1 => 0010

// eor 此时结果为 a ^ b 且会有一个二进制位为1 取到为1的值 0010
// 由于偶数次位的值异或为0
let rightOne = eor & (~eor + 1);
// 获取两个出现奇数的值得其中一个
let onlyOne = 0;
arr.forEath(item => {
  // 0001 & 0010 为 0 可知item 都是为 二进制第二位都是0的数
  if(item & rightOne === 0){
    // onlyOne最终结果为 二进制第二位是0的奇数
    onlyOne ^= item; 
  }
})
let b = eor ^ onlyOne;

排序

选择排序

第一步，0 到n-1 获取最小值

第二步，将最小值索引与索引0交换

第三步，1到n - 1 获取最小值

第四步，重复步骤二交换索引为1

const arr = [1,7,5,2,0,3,6,4]

let index = 0;
const selectSort = (arr:number[],index:number) => {
  if(arr === null || arr.length < 2) return arr;
  let minIndex = index;
  for(let i = index; i < arr.length; i++){
    if(arr[i] < arr[minIndex]){
      minIndex = i;
    }
  }
  let temp = arr[index];
  arr[index] = arr[minIndex];
  arr[minIndex] = temp;
  if(index + 1 < arr.length){
    return selectSort(arr,index += 1)
  }else{
    return arr;
  }
}
console.log(selectSort(arr,index));


const selectSort1 = () => {
  for(let i = 0; i < arr.length; i++){
    let minIndex = i;
    for(let j = i + 1;j < arr.length; j++){
      minIndex = arr[minIndex] > arr[j] ? j : minIndex;
    }
    let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}

冒泡排序

第一步：将0与arr.length位置进行比较判断，如果n小于n+1，就进行交换，第一轮交换结束后，数组的最后一位为最大值

第二步：将0与arr.length - 2重复步骤一

插入排序

第一步、判断0,1位置是否有序，1位置小于0位置，则互换

第二步、判断0,2位置是否有序，无序则比对1位置小则交换，大则结束；比较0位置小则交换，大则结束；索引小于0则结束

第n步、判断0,n位置是否有序

const arr = [1,7,5,2,0,3,6,4]

const insertSort = () => {
    for(let i = 1; i < arr.length; i++){
        // 要时刻记录当前最后的索引位，便于每次计算
        let index = i;
        while(index - 1 >= 0 && arr[index - 1] > arr[index]){
            let temp = arr[index];
            arr[index] = arr[index -1];
            arr[index - 1] = temp;
            index --;
        }
    }
}
insertSort();
console.log(arr);

归并排序

第一步、将数组根据中间索引进行拆分，将拆分后的左右两数组继续进行拆分直至数组长度为1

第二步、合并两个数组按两个被拆分的数组进行处理，定义L指针、R指针分别执行左右两个数组，将数据保存到temp临时数组中，做一下两个数组的越界处理，将temp数组中的内容替换到arr数组中

function merge(arr: number[],left: number,right: number,middle: number,temp: number[]) {
  let index = 0;
  let R = middle + 1; // 右数组指针
  let L = left; // 左数组指针
  while (L <= middle && R <= right) {
    // 将小的值赋值给temp
    temp[index++] = arr[L] < arr[R] ? arr[L++] : arr[R++];
  }
  // 防止右数组越界 左数组还有
  while (L <= middle) {
    temp[index++] = arr[L++];
  }
  // 防止左数组越界 右数组还有
  while (R <= right) {
    temp[index++] = arr[R++];
  }
  // 将temp数组中的值赋值给arr
  // left + index <= right 防止越界 
  for (index = 0; left + index <= right; index++) {
    arr[left + index] = temp[index];
  }
}
function mergeSort(arr: number[]) {
  const temp: number[] = [];
  // 递归二等分数组
  const process = (arr: number[],left: number,right: number,temp: number[]) => {
    if (left >= right) return;
    let middle = parseInt(`${(left + right) / 2}`);
    process(arr, left, middle, temp);
    process(arr, middle + 1, right, temp); 
    merge(arr, left, right, middle, temp);
  };
  process(arr, 0, arr.length - 1, temp);
}


const arr = [1, 5, 2, 6, 8, 4, 7, 9, 3, 99, -1];
mergeSort(arr);
console.log(arr);

快速排序

第一步、找一个基准值

第二步、从剩余数组中区分出大于基准值与小于基准值的数组

第三步、拼接递归大于小于基准值的数组与原基准值

function quickSort(arr:number[]):number[]{
  if(arr.length < 2) return arr;
  const flag = arr[0];
  let maxArr = arr.slice(1).filter(item => item > flag);
  let minArr = arr.slice(1).filter(item => item < flag);
  return quickSort(minArr).concat([flag]).concat(quickSort(maxArr));
}

const arr = [1, 5, 2, 6, 8, 4, 7, 9, 3, 99, -1]; 
console.log(quickSort(arr));

前置问题

// 问题1 给定一个数组，给定一个值a 左边都为小于等于a的，右边都是大于a的
// 解题步骤 
//  1、设置L为-1 即为小于指定值的区域，遍历数组
//  2、当值大于指定值 跳过
//  3、当值小于等于指定值使，使小于指定值区域的下一个与当前值互换，并移动小于指定值的区域
const arr = [1, 5, 2, 6, 8, 4, 7, 9, 3, 99]; 
const num = 5; 
function generatorArr (arr,num) {
  let L = -1; // 小于num的区域索引
  for(let i = 0; i < arr.length; i++){
    if(arr[i] <= num){ 
      let temp = arr[i];
      arr[i] = arr[L + 1];
      arr[L + 1] = temp;
      L++;
    }
  }
}
generatorArr(arr,num)
console.log(arr);

// 问题2 荷兰国旗问题给定一个数组，给定一个值a。使数组左边都是小于a，中间等于a，右边大于a
// 解题步骤
//  1、设置L为-1 即为小于指定值的区域，遍历数组
//  2、如果arr[i] < a 让小于区域的下一个与i位置的值互换，小于区域右扩 i++
//  3、如果arr[i] == a 跳过不处理 i++
//  4、如果arr[i] > a 让大于区域的前一个与i位置的值互换，大于区域左扩 i不变
const arr1 = [1, 5, 2, 6, 8, 4, 7, 9, 3, 99, 5]; 
const num1 = 5; 
function netherlandsFlag(arr:number[],num:number){
  let index = 0;
  let L = -1;
  let R = arr.length;
  while(arr[index] !== arr[R]){
    if(arr[index] < num){
      let temp = arr[index];
      arr[index] = arr[L + 1];
      arr[L + 1] = temp;
      index++;
      L++;
    }else if(arr[index] === num){
      index++;
    }else{
      let temp = arr[index];
      arr[index] = arr[R - 1];
      arr[R - 1] = temp;
      R--;
    }
  }
}
netherlandsFlag(arr1,num1)
console.log(arr1);

通过问题1可推出快速排序1版本，设置数组中最后一个值为指定值，将剩余数组进行左右划分，再将右侧数组的第一个与指定值互换，递归左右数组
通过问题2可推出快速排序2版本，设置数组中最后一个值为指定值，利用荷兰国旗问题，找到右侧数组的第一个与指定值互换，然后再递归左右数组，中心数组不变(指定值的集合)

堆排序

桶排序

题目1：数组X中每一位的值都在【0，100】区间内，进行排序

解题思路：计数排序

步骤一、生成一个长度为101,每一位都是0的数组Y，遍历X数组根据X数组的值，使Y数组对应索引加一

步骤二、根据Y索引的对应的值如 index 存在 Y[index]个值

解题思路：奇数排序

步骤一、找到最大值的位数，将小于该位数的值，前面补0直至满足最值大位数如最大值100，其他数075

步骤二、生成桶，并将数组每一位个位数放到对应尾数值得桶中

步骤三、根据桶的索引依次将数组倒出、再根据每一位值得十位数放到桶中

步骤四、根据桶的索引依次将数组倒出、再根据每一位值得百位数放到桶中

………

直至将最大值得第一位放入桶中再从左到右再倒出

function getDigit(num: number): number {
  let index = 0;
  while (num > 1) {
    num /= 10;
    index++;
  }
  return index;
}
function bucketSort(arr: number[]) {
  let index = 0;
  const digit = getDigit(Math.max(...arr));
  const temp: number[] = [];
  while (index <= digit) {
    let bucket: number[][] = [[], [], [], [], [], [], [], [], [], []];
    let tempIndex = 0;
    for (let i = 0; i < arr.length; i++) {
      const bucketIndex =
        arr[i].toString()[arr[i].toString().length - index - 1] ?? 0;
      bucket[bucketIndex].push(arr[i]);
    }
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i].length > 0) {
        bucket[i].forEach((item) => {
          temp[tempIndex++] = item;
        });
      }
    }
    arr = temp;
    index++;
  }
  return temp;
}
const arr = [10, 5, 7, 24, 16, 50, 13, 46, 100];

console.log(bucketSort(arr));

查找

二分查找

从有序数组中找到对应的数值，或者是无序但是可以肯定某一侧肯定存在查找的值，就可以二分

function binarySearch (arr,num) {
    let start = 0;
    let end = arr.length - 1;
    let middle = parseInt((arr.length - 1) / 2);
    while(start < end){
        middle = parseInt((end + start) / 2)
        if(arr[middle] < num){
            start = middle + 1;
        }else if (arr[middle] > num){
            end = middle - 1;
        }else{ 
            return true;
        }
    }
    if(start === end) {
        return arr[start] == num ? true : false;
    }
}
// arr.length > 1;
const arr = [1,2,3,3,4,5,6,7,9];
const num = 0
console.log(binarySearch(arr,num))

递归查找

master公式求解递归时间复杂度（子问题规模一致）

N 表示数据量

a 表示调用函数次数

T(N/b) 表示子问题规模

d 表示其他代码时间复杂度

数据结构

1、数组：便于寻址，不便于增删数据

2、链表：便于增删数据，不便于寻址

链表结构

// 方案1
const next = (head) => {
  // 有停止条件 如果没有元素或者有一个元素的情况下
  if(head === null || head.next === null) return head;
  let newHead = next(head.next);
  head.next.next = head;
  // 将当前head的next 置为空
  head.next = null;
  return newHead
}
this.head = next(this.head)
return this.head;


// 方案2
if(this.head&&this.head.next){
    let head = this.head;
    let newHead = null;
    while(head!= null){
        let tem = head.next; // B
        head.next = newHead;
        newHead = head;
        head = tem;
    }
    this.head = newHead
    return newHead;
}else{
    return this.head;
}

堆结构

在逻辑概念上可以理解为是一个完全二叉树( 树的层级都是满的，如果不满也是从左往右依次变满 )

堆结构就是用数组实现的完全二叉树结构
完全二叉树中如果每颗子树的最大值都在顶部就是大跟堆
完全二叉树中如果每颗子树的最小值都在顶部就是小跟堆
堆结构具有insert操作、heapify堆化操作
优先级队列结构就是堆结构

因此节点的左节点满足 2 * i + 1、右节点满足2 * i + 2、父节点满足 ( i - 1 )/ 2

大根堆

class Heap{
  private size = 0;
  private heapList = [];
  constructor(list?:[]){
    if(list){ 
      // 将数组进行堆化
      for(let i in list){
        this.add(i);
      }
    }
  }
  private compareParent(index){
    // 当前元素与他父比
    while(this.heapList[index] > this.heapList[(index - 1) / 2]){
      let temp = this.heapList[index];
      this.heapList[index] = this.heapList[(index - 1) / 2]
      this.heapList[(index - 1) / 2] = temp;
      index = (index - 1) / 2;
    }
  } 
  add(num) {
    this.heapList.push(num);
    if(this.heapList.length > 1){
      this.compareParent(this.size)
    }
    this.size += 1;
  }
  getSize(){
    return this.size;
  }
  getAllNode(){
    return [...this.heapList];
  }
  peek(){
    return this.heapList[0];
  }
  // 取出第一个值 并从heapList中删掉
  // 1、取出第一个值。 2、将heapList的最后一个放到第一个位置
  // 3、将size减少
  pop(){
    let retValue = this.peek();
    this.size -= 1;
    this.heapList[0] = this.heapList[this.heapList.length - 1];
    this.heapList.pop();
    this.heapify(0);
    return retValue;
  }
  
  heapify(index){
    // 找到当前左子节点下表
    let left = index * 2 + 1;
    while(left < this.size){ // 判断左子节点 是否越界了
      // 判断右孩子是否越界 如果不越界并且右子节点大于左子节点 返回右节点的索引
      let largest = left + 1 < this.size && this.heapList[left] < this.heapList[left + 1] 
        ? left + 1 
        : left;
      largest = this.heapList[index] < this.heapList[largest] ? largest : index;
      // 如果二者相同 表示index大 则不需要变化了 跳过循环
      if(index === largest){
        break;
      }
      //否则二者进行交换（子节点大于当前的节点）
      let temp = this.heapList[index];
      this.heapList[index] = this.heapList[largest]
      this.heapList[largest] = temp;
      // 将当前节点的索引置为子节点索引
      index = largest;
      // 获取left的索引 进行下一次循环
      left = index * 2 / 1;
    }
  }
  sort(){
    if(this.heapList.length < 2) return this.heapList;
    let temp = this.heapList[0];
    this.heapList[0] = this.heapList[this.size - 1];
    this.heapList[this.size - 1] = temp;
    this.size -= 1;
    while(this.size > 0){
      this.heapify(0);
      let temp = this.heapList[0];
      this.heapList[0] = this.heapList[this.size - 1];
      this.heapList[this.size - 1] = temp;
      this.size -= 1;
    }
  }
}

随机数

Math.random 会等概率生成 [0,1) 之间的一个小数

Math.random() * N 会等概率生成 [0,N)之间的一个小数

parseInt(Math.random() * N) 会等概率生成 [0,N - 1]之间的一个整数

等概率发生器

我们可以通过等概率发生器将1-5 随机生成的函数转为 0 - 1 等概率随机生成函数

const f1 = parseInt((Math.random() * 5)) +1
// 等概率发生器
const f2 = () => {
  let c = 0;
  do{
    c = f1()
  }while(c === 3)
  // 1、2 => 0    4、5 => 1
  return c > 3 ? 1 : 0;
}

// 转为 1 到 7 随机生成数字 
// 可以转为 0 -> 6 + 1 或者 1 -> 7
const f3 = () => {
  let c = 0;
  do{
    c = f2();
  }while(c === 0)
  return c;
}
// 此时 f3 即随机产生1 到 7之间的数字 

将01不等概率转为等概率

假设 fn为不等概率的产生0,1 ，将fn执行两次 1、0 返回 1；0、1返回0；去除0、0与1、1

const f =Math.random() < 0.77 ? 0 : 1;


const f1 = () => {
  let c = 0;
  do{
    c = f()
  }while(c === fn()) // 去除 0、0；1、1等相等条件
  return c;
}

对数器

function generatorArr(maxSize: number, maxValue: number) {
  const arr = [];
  const length = parseInt(`${Math.random() * (maxSize + 1)}`);
  for (let i = 0; i < length; i++) {
    arr.push(parseInt(`${Math.random() * (maxValue + 1)}`));
  }
  return arr;
}

function copyArr(arr: number[]) {
  if (arr && arr.length === 0) return arr;
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr[i] = arr[i];
  }
  return newArr;
}

function defaultValidtor(arr: number[]) {
  return arr.sort((a, b) => a - b);
}

interface LogarithmProps {
  maxSize?: number;
  maxValue?: number;
  validtorSort: (arr: number[]) => void;
  debug?: boolean;
}

function logarithm(options: LogarithmProps) {
  const debug = options.debug ? options.debug : false;
  const testCount = debug ? 10 : 500000;
  const maxSize = debug ? 10 : options.maxSize ?? 100;
  const maxValue = debug ? 10 : options.maxValue ?? 100;
  let complete = true;
  for (let i = 0; i < testCount; i++) {
    let arr1 = generatorArr(maxSize, maxValue);
    let arr2 = copyArr(arr1);
    debug && console.log(`arr1 : ${arr1} \n arr2 : ${arr2}`);
    options.validtorSort(arr1);
    defaultValidtor(arr2);
    debug && console.log(`排序后 arr1 : ${arr1} \n 排序后 arr2 : ${arr2}`);
    let i = 0;
    while (i < arr1.length && complete) {
      if (arr1[i] !== arr2[i]) {
        complete = false;
      }
      i++;
    }
    if (!complete) break;
  }
  return complete;
}
const insertSort = (arr: number[]) => {
  for (let i = 1; i < arr.length; i++) {
    // 要时刻记录当前最后的索引位，便于每次计算
    let index = i;
    while (index - 1 >= 0 && arr[index - 1] > arr[index]) {
      let temp = arr[index];
      arr[index] = arr[index - 1];
      arr[index - 1] = temp;
      index--;
    }
  }
};

logarithm({
  validtorSort: insertSort,
  debug: true,
});

前缀数组

假设有一个数组arr,用户总是频繁查询数组中某一段的累加和，如何设计数据结构更加方便

let arr = [2,1,7,5,8,6,4,3]

前缀和数组

const preSumArr = [];

const RangeSum = (arr:number[]) => {
  for(let i = 0; i < arr.length; i++){
    preSumArr[i] = preSumArr[i-1] + arr[i]
  }
}

const preSum = (L:number,R:number) => {
  return L === 0 ? preSumArr[R] : preSumArr[R] - preSumArr[L]
}

算法技巧

单链表结构常用处理

快慢指针
哈希表 Map

1、判断一个链表是否为回文结构

题目：给定一个单链表的头节点head，请判断是否为回文结构

例子：1->2->1 返回true，1->2->2->1 返回true，1->2->3 返回false

快慢指针：

// 方案1：使用栈结构，遍历链表使其入栈，再次遍历链表与栈pop进行对比，如果都一直返回true
// 方案2：使用栈结构，存储链表的一半右侧值，遍历链表一半位置与栈pop的值进行对比
// 方案3：使用快慢指针，使用慢指针找到中点位置，将中点位置next指向null,中点位置右侧逆序使用
//变量记录，循环链表head.next !== null，比对head与变量记录位置value是否相同，比对结束后回复
//原链表位置

class Node {
  public value:number;
  public next:Node|null;
  constructor(value:number,next:Node|null){
    this.value = value;
    this.next = next;
  }
}
// 使用栈结构
function isPalindrome1(head:Node){
  const stack:Node[] = [];
  let cur = head;
  while(cur !== null){
    stack.push(cur);
    cur = cur.next;
  }
  while(head !== null){
    if(head.value !== stack.pop().value){
      return false;
    }
    head = head.next;
  }
  return true;
}
// 使用快慢指针 存储右侧一半链表到栈结构
function isPalindrome2(head:Node){
  if(head == null || head.next == null) return true;
  let right = head.next; // 慢指针
  let cur = head; // 快指针
  while(cur.next!==null && cur.next.next !== null){
    right = right.next;
    cur = cur.next.next;
  }
  const stack:Node[] = [];
  while(right !== null){
    stack.push(rigth);
    rigth = right.next;
  }
  while(stack.length > 0){
    if(head.value !== stack.pop().value){
      return false;
    }
    head = head.next;
  }
  return true;
}
// 
function isPalindrome3(head:Node){
  if(head == null || head.next == null) return true;
  let n1 = head;
  let n2 = head;
  while(n2.next !== null && n2.next.next !== null){
    n1 = n1.next;
    n2 = n2.next.next;
  }
  n2 = n1.next; // 将n2置为中间位置的下一个
  n1.next = null; // 将中间位置的node.next = null
  let n3 = null; //记录右侧最后一个位置
  while(n2 != null){ // 将右侧逆序
    n3 = n2.next; // 记录n位置
    n2.next = n1; // 修改n2.next;
    n1 = n2; // 将n1 指向n2;
    n2 = n3; // n2 指向原n2.next
  }
  n3 = n1; // n3,n1 存储的右侧最后一个位置
  n2 = head; // n2 存储左侧第一个位置
  let result = true; // 返回状态
  while(n1 !== null && n2 !== null && result){
    if(n1.value != n2.value){
      result = false;
    }
    // 从两侧往中间走
    n1 = n1.next; 
    n2 = n2.next;
  }
  // 将右侧逆序回来
  n1 = n3.next; // 将右侧指向为n1
  n3.next = null;
  while(n1 !== null){
    n2 = n1.next;
    n1.next = n3;
    n3 = n1;
    n1 = n2;
  }
  return res;
}

2、将单向链表按某值划分为左侧小于、中间等于、右侧大于结构

题目：给定一个单链表的头节点head，节点的值类型是整数，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部门都是值小于pivot的节点，中间部门都是值等于pivot的节点，右部门都是值大于pivot的节点

【进阶】：在实现原问题功能的基础上增加如下的要求

【要求】：调整后所有小于、大于、等于pivot的节点之间的相对顺序和调整前一样

【要求】：时间复杂度O(N)，额外空间复杂度O(1)

// 方案1：将链表转为Node数组，将数组进行partition，类似于快排形式，定义小于指定值范围L:-1，
//大于指定值范围R:数组长度，遍历数组，小于则与L的后一个做交换i++,等于i++，大于则与R的前一个
//做交换i不变，继续执行新索引i的值,遍历数组重新连接起来
// 方案2：定义6个遍历，小于头、小于尾、等于头、等于尾、大于头、大于尾，遍历链表，将value与
//对应值比较，放到对应大于、小于、等于区域，构建成3个链表，最后将3个链表next
//小于尾 -> 等于头 -> 等于尾-> 大于头

class Node {
  public value:number;
  public next:Node|null;
  public rand:Node|null;
  constructor(value:number,next:Node|null,rand:Node|null){
    this.value = value;
    this.next = next;
    this.rand = rand;
  }
}

function listPartition(head:Node,pivot:number){
  let startH:Node|null = null;
  let startE:Node|null = null;
  let middleH:Node|null = null;
  let middleE:Node|null = null;
  let endH:Node|null = null;
  let endE:Node|null = null;
  let next:Node|null = null;
  while(head !== null){
    next = head.next;
    head.next = null;
    if(head.value < pivot){
      if(startH === null){
        startH = head;
        startE = head;
      }else{
        startE.next = head;
        startE = head;
      }
    }else if(head.value === pivot){
      if(middleH === null){
        middleH = head;
        middleE = head;
      }else{
        middleE.next = head;
        middleE = head;
      }
    }else{
      if(endH === null){
        endH = head;
        endE = head;
      }else{
        endE.next = head;
        endE = head;
      }
    }
    head = next;
  }
  if(startE !== null){
    startE.next = middleH;
    middleE = middleE === null ? startE : middleE;
  }
  if(middleE !== null){
    middleE.next = endH;
  }
  return startH !== null ? startH : (middleH !== null ? middleH : endH)
}

3、复制含有随机指针节点的链表

题目：一种特殊的单链表节点类描述如下

class Node{ next:Node,rand:Node,value:number }

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。

【要求】：时间复杂度O(N)，空间复杂度O(1)

// 方案1：使用Map<Node,Node>结构存储新旧Node，key为旧Node，value为新Node，遍历链表Node1的
//next 可以通过Map找到对应的新节点，rand同样可以
// 方案2：生成新节点使旧节点的next指向新节点，新节点的next指向旧节点的next,
class Node {
  public value:number;
  public next:Node|null;
  constructor(value:number,next:Node|null){
    this.value = value;
    this.next = next;
  }
}
function copyListWithRand(head:Node){
  let map = new Map<Node,Node>();
  let cur = head;
  while(cur !== null){
    map.set(cur,new Node(cur.value,null));
    cur = cur.next;
  }
  cur = head;
  while(cur !== null){
    map.get(cur).next = map.get(cur.next);
    map.get(cur).rand = map.get(cur.rand);
    cur = cur.next;
  }
  return map.get(head);
}
function copyListWithRand2(head:Node){
  if(head === null) return null;
  let cur = head;
  let next:Node|null = null;
  // 生成 旧Node1 -> 新Node1 -> 旧Node2
  while(cur !== null){
    next= cur.next;
    cur.next = new Node(cur.value,next);
    cur = next;
  }
  cur = head;
  let curCopy = null;
  while(cur !== null){
    next = cur.next.next;
    curCopy = cur.next;
    curCopy.rand = cur.rand != null ? cur.rand.next : null;
    cur = next;
  }
  let result = head.next;
  cur = head;
  // 拆分新Node与旧Node
  while(cur !== null){
    next = cur.next.next;
    curCopy = cur.next;
    cur.next = next;
    curCopy.next = next !== null ? next.next : null;
    cur = next;
  }
  return res;
}

4、两个单链表相交的一系列问题

题目：给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交返回null

【要求】：如果两个链表长度之和为N，时间复杂度O(N)，空间复杂度O(1)

// 判断有环并找到入环第一个
// 方案1：通过快慢指针找到是否存在环，如果存在将快指针移动到链表头部，快慢指针每次走一个，
//当快慢指针再次相遇时就是入环前的第一个
// 方案2：通过Map<Node,Node>结构 如果链表走到最后Map每次都是新增则无环，否则获取Map
//第一个的值Node为入环第一个Node

// 该题方案1：遍历两条无环单链表 获取end1，end2，size1，size2，如果end1===end2将长链表遍历到
//与短链表同样长后，两条链表一起遍历，直到两条其中一个Node相同是停止，记录Node并返回，
//end1 !== end2 则表示二则无相交
// 该题方案2：两条链表一个有环一个无环，这种情况不会出现相交情况
// 该题方案3：两条链表都有环，
//    情况1：记录入环前节点为end1、end2判断二者是否相等，
//    情况2：二者都无环，或者相交节点在环内，使loop1、loop2都继续向下走，在回到loop1与loop2
//节点前相遇则存在，否则则不存在

function getLoopNode(head:Node){
  if(head === null || head.next === null) return null;
  let n1 = head.next; // 慢指针
  let n2 = head.next.next; // 快指针
  // 使用快慢指针重合确保存在环
  while(n1 !== n2){
    if(n2.next === null || n2.next.next === null) return null;
    n2 = n2.next.next;
    n1 = n1.next;
  }
  n2 = head; // 将快指针置为head;
  // 每次走一步 n1与n2再次相遇则为入环的第一个节点
  while(n1 != n2){
    n1 = n1.next;
    n2 = n2.next;
  }
  return n1;
}
function noLoop(head1:Node,head2:Node){
  if(head1 === null || head2 === null) return null;
  let cur1 = head1;
  let cur2 = head2;
  let n = 0; // 记录head1与head2相差多少
  while(cur1.next !== null){
    n++;
    cur1 = cur1.next;
  }
  while(cur2.next !== null){
    n--;
    cur2 = cur2.next;
  }
  if(cur1 != cur2) return null;
  cur1 = n > 0 ? head1 : head2; // 记录为长链表
  cur2 = cur1 === head1 ? head2 :head; // 短链表
  n = Math.abs(n); // 有可能是负数 转为整数
  while(n !== 0){
    n--;
    cur1 = cur1.next;
  }
  while(cur1 !== cur2){
    cur1 = cur1.next;
    cur2 = cur2.next;
  }
  return cur1;
}


function bothLoop(head1:Node,head2:Node,loop1:Node,loop2:Node){
  let cur1:Node|null = null;
  let cur2:Node|null = null;
  if(loop1 === loop2){
    cur1 = head1;
    cur2 = head2;
    let n = 0;
    while(cur1 != loop1){
      n++;
      cur1 = cur1.next;
    }
    while(cur2 != loop2){
      n--;
      cur2 = cur2.next;
    }
    cur1 = n > 0 ? head1 : head2; // 记录为长链表
    cur2 = cur1 === head1 ? head2 :head; // 短链表
    n = Math.abs(n); // 有可能是负数 转为整数
    while(n !== 0){
      n--;
      cur1 = cur1.next;
    }
    while(cur1 !== cur2){
      cur1 = cur1.next;
      cur2 = cur2.next;
    }
    return cur1;
  }else{
    cur1 = loop1.next;
    while(cur1 !== loop1){
      if(cur1 == loop2){
        return loop1
      }
      cur1 = cur1.next;
    }
    return null;
  }
}
// 主函数
function getIntersetcNode(head1:Node,head2:Node){
  if(head1 === null || head2 === null) return null;
  let loop1 = getLoopNode(head1);
  let loop2 = getLoopNode(head2);
  if(loop1 === null && loop2 === null){
    return noLoop(head1,head2);
  }
  if(loop1 !== null && loop2 !== null){
    return bothLoop(head1,head2,loop1,loop2);
  }
  return null;
}

二叉树

class Node<T> { value:T,left:Node|null,right:Node|null }

用递归与非递归方式实现二叉树的先序、中序、后序遍历
如何直观的打印二叉树
如何完成宽度有限的二叉树遍历

先序遍历

先进入头节点，再进入左子树，返回头节点进入右子树

头 -> 左 -> 右

function preorder(head:Node){
  if(head === null){
    return null;
  }
  console.log(head);
  preorder(head.left);
  preorder(head.right);
} 
// 步骤1：先将head进行压栈
// 步骤2：将栈中head弹出，进行处理
// 步骤3：再将head的right、left压栈，(先右后左)

function preorder(head:Node|null){
  if(head === null) return null;
  const stack:Node[] = [head];
  while(stack.lenght > 0){
    let cur = stack.pop();
    console.log("处理Node ：",cur.value);
    cur.right && stack.push(cur.right);
    cur.left && stack.push(cur.left);
  }
}

中序遍历

先进入左子树，然后头节点，然后再进入右子树

function middleOrder(head:Node){
  if(head === null){
    return null;
  }
  preorder(head.left);
  console.log(head);
  preorder(head.right);
}
// 定义：左 -> 右 -> 头的执行顺序
// 步骤1：先将head进行压栈
// 步骤2：将栈中head弹出，放到辅助栈中
// 步骤3：再将head的left、right压栈，(先左后右)

function middleOrder(head:Node){
  if(head !== null){
    const stack:Node[] = [head];
    while(stack.lenght > 0 || head !== null){
      if(head !== null){
        stack.push(head);
        head = head.left;
      }else{
        head = stack.pop();
        console.log(head.value);
        head = head.right;
      }
    }
  }
}

后序遍历

先进入左子树，然后右子树，然后打印头节点

function postOrder(head:Node){
  if(head === null){
    return null;
  }
  preorder(head.left);
  preorder(head.right);
  console.log(head);
}
// 定义：头 -> 右 -> 左的执行顺序 并将处理节点放入辅助栈，最后辅助栈pop弹出
// 步骤1：先将head进行压栈
// 步骤2：将栈中head弹出，放到辅助栈中
// 步骤3：再将head的left、right压栈，(先左后右)

function postOrder(head:Node|null){
  if(head === null) return null;
  const stack:Node[] = [head];
  const auxiliary:Node[] = [];
  while(stack.lenght > 0){
    let cur = stack.pop();
    auxiliary.push(cur);
    cur.left && stack.push(cur.left);
    cur.right && stack.push(cur.right);
  }
  while(auxiliary.lenght > 0){
    let cur = auxiliary.pop();
    console.log("处理cur ：",cur.value)
  }
}

宽度优先遍历

使用队列（先进先出）先放head 弹出head，然后先放左再放右

function widthFirstOrder(head:Node){
  const queue:Node[] = [head]; // 先进先出
  while(queue.lenght > 0){
    let cur = queue.shift();
    console.log("需要处理的value ：",cur.value)
    cur.right && queue.unshift(cur.right);
    cur.left && queue.unshift(cur.left); // 头 [left,right] 尾
  }
}

获取二叉树的最大宽度节点个数

function getMaxWidthNodeSize(head:Node) {
  if(head === null) return;
  const queue:Node[] = [head];
  const levelMap = new Map<Node,number>();
  levelMap.set(head,1);
  let curLevel = 1; // 记录当前层数
  let curLevelNodes = 0; // 记录当前层Node数
  let max = -1; //  max 为最大宽度节点个数
  while(queue.lenght > 0){
    let cur = queue.shift();
    let curNodeLevel = levelMap.get(cur);
    if(curNodeLevel === curLevel){ // 如果是当前节点就讲当前层数节点Node数++
      curLevelNodes++;
    }else{ // 记录上一个层数个数
      max = Math.max(max,curLevelNodes);
      curLevel++;
      curLevelNodes = 0;
    }
    // 将left、right存储到Map
    if(cur.left){
      levelMap.set(cur.left,curNodeLevel + 1);
      queue.unshift(cur.left);
    } 
    if(cur.right){
      levelMap.set(cur.right,curNodeLevel + 1);
       queue.unshift(cur.right);
    }
  }
}

搜索二叉树

满足一棵树左子树都比当前Node小，右子树都比当前Node大

问题：如何判断一棵树是搜索二叉树

使用中序遍历，左 -> 中 -> 右可以只知道是都是升序的

// 方案1：
let preValue = Number.MIN_VALUE; // 用于记录上次的Node value值便于比对
function isBST(head:Node){
  if(head === null) return true; // 如果head没有了则返回true 表示是搜索二叉树
  let isLeftBst = isBST(head.left); // 递归左树，判断是否为搜索二叉树 
  if(!isLeftBst) return false; // 如果不是返回false
  if(head.value < preValue) { // 如果上次值大于当前值 表示不是搜索二叉树
    return false 
  }else{
    preValue = head.value // 否则记录当前值
  }
  return isBst(head.right); // 判断右树是否为搜索二叉树 如果是则是搜索二叉树，否则不是
}

// 方案2：
function isBST1(head:Node){
  const temp:Node[] = []
  const process = (head:Node) => {
    if(head === null) return;
    precess(head.left);
    temp.push(head);
    precess(head.right);
  }
  process(head);
  for(let i = 1; i < temp.length; i++){  
    if(temp[i].value < temp[i - 1].value){
      return false
    }
  }
  return true;
}

// 使用递归方式处理 
// 找到判断条件 左/右子树都是搜索二叉树,且左子树的最大值小于当前值，右子树的最小值大于当前值
// 1.左树需要给我 最大值和左树是搜索二叉树
// 2.右树需要给我 最小值和右树是搜索二叉树

function isSearchBinaryTree(head:Node) {
  return process(head:Node).isBST;
}

function process(head:Node){
  if(head === null){ // 为null时可以知道isBST是true，但是不知道最大值还是最小值
    return null;
  }
  let leftInfo = process(head.left);
  let rightInfo = process(head.right);
  let max = Number.MIN_VALUE;
  let min = Number.MIN_VALUE;
  // 因为是递归行为 左右两棵树的操作是一致的，预期是左子树取最大，右子树取最小
  // 但是无法做到区分效果，所以取左子树的最大值、最小值，右子树的最大值、最小值
  if(leftInfo !== null){
     max = Math.max(head.value,leftInfo.max);
     min = Math.min(head.value,leftInfo.min);
  }
  if(rightInfo !== null){
     max = Math.max(head.value,rightInfo.max);
     min = Math.min(head.value,rightInfo.min);
  }
  
  let isBST = (leftInfo !== null ? (leftInfo.isBST || head.value > leftInfo.max) : true) && 
    (rightInfo!== null ? (rightInfo.isBST || head.value < rightInfo.min) : true);
  return {max,min,isBST}
}

完全二叉树

二叉树从左到右存在节点，或者是个满二叉树

问题：如何判断二叉树是否是满的

二叉树按宽度遍历，

如果存在有右子树没有左子树则返回false

如果不满足上述问题时，且左右节点不全的情况下，接下来遇到的所有节点都必须是叶子节点(度为0的节点)

function CompleteBinaryTree(head:Node){
  if(head === null) return true;
  const queue:Node[] = [head];
  let leaf = false; // 判断是否遇到过左右子节点其中一个不存在的情况
  let l:Node|null = null;
  let r:Node|null = null;
  while(queue.length > 0){
    head = queue.shift();
    l = head.left;
    r = head.right;
    // leaf 为true表示后续节点只能为叶子结点 或者是 没有左子节点有右子节点
    if((leaf && (l!==null||r!==null))||(l!==null||r!==null)){
      return false;
    }
    if(l !== null) queue.unshift(l);
    if(r !== null) queue.unshift(r);
    if(l == null || r== null){
      leaf = true;
    }
  }
  return true;  
}

满二叉树

满二叉树满足 L为深度，N为节点个数满足

问题：求满二叉树

可以先求出L深度，N二叉树的节点个数，然后判断是否满足

// 判断满二叉树条件 需要知道二叉树的深度，需要知道二叉树的总节点个数
function fullBinaryTree(head:Node){
  const {deep,count} = process(head:Node);
  let targetCount = 2 ** deep - 1;
  return targetCount === count;
}
function process(head:Node){
  if(head === null){
    return {deep:0,count:0};
  }
  let leftInfo = process(head.left);
  let rightInfo = process(head.right);
  // 深度为自身高度 + 左右子树最高高度
  let deep = Math.max(leftInfo.deep,rightInfo.deep) + 1;
  // 当前树的所有node = 左右子树相加 + 自身
  let count = leftInfo.deep + rightInfo.deep + 1;
  return {deep,count};
}

平衡二叉树

满足左子树的高度与右子树的高度差都不超过1

问题：判断是否为平衡二叉树

// 解题思路，假设一X为头的子树，如果是平衡二叉树的话，左子树与右子树分别都是平衡二叉树，且
//左子树与右子树的高度差不能超过一，因此可以定义一个info : {height:number,isbalance:boolean}

function isBalanceTree(head:Node){
   return process(head).isbanlance;
}

function process(head:Node){
  if(head === 0){
    return {height:0,isbanlance:true}
  }
  let leftInfo = process(head.left);
  let rightInfo = process(head.right);
  // 判断当前节点 
  let height = Math.max(leftInfo.height,rightInfo.height) + 1;// 取左右子树高度 + 自身高度
  let isbanlance = leftInfo.isbanlance && 
      rightInfo.isbanlance &&
      Math.abs(leftInfo.height - rightInfo.height) <= 1
  return {height,isbanlance}
  
}

解决树形DP问题

使用递归方式，找到需要使用的共用属性递归返回，类似于事件冒泡，从叶子结点开始往上收集，收集到根时进行处理

找到O1、O2节点的公共祖先

问题1、O1是O2的祖先或者O2是O1的祖先

问题2、O1与O2存在共同祖先

function getCommonAncestor(head:Node,O1:Node,O2:Node){
  if(head === null || head === O1 || head === O2){ // 如果节点为null或者等于O1或者O2
    return head;
  }
  let leftInfo = getCommonAncestor(head.left,O1,O2);
  let rightInfo = getCommonAncestor(head.left,O1,O2);
  if(leftInfo !== null && rightInfo !== null){
    return head;
  }
  return leftInfo !== null ? left : right;
}

前缀树

例子：

一个arr1:string[],另一个arr2:string[]。arr2中有哪些字符是arr1中出现的？并打印。arr2中有哪些字符是作为arr1中某个字符串前缀出现的请打印，arr2中有哪些字符是作为arr1中某个字符串前缀出现的请打印，arr2中出现次数最大的前缀。

// abc 结构 => {"a":{"b":{"c":{isEnd:true}}}}
/**
* Initialize your data structure here.
*/
var Trie = function() {
  this.tree = {};
};

/**
* Inserts a word into the trie. 
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
  let tree = this.tree;
  for(const w of word){
    if(tree[w] == undefined){
      tree[w] = {};
    }
    tree = tree[w];
  }
  tree.isEnd = true;
};

/**
* Returns if the word is in the trie. 
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
  let tree = this.tree;
  for(const w of word){
    if(tree[w] == undefined){
      return false;
    }
    tree = tree[w];
  }
  return tree.isEnd == true;
};

/**
* Returns if there is any word in the trie that starts with the given prefix. 
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
  let tree = this.tree;
  for(const w of prefix){
    if(tree[w] == undefined){
      return false;
    }
    tree = tree[w];
  }
  return true;
};


var obj = new Trie()
obj.insert(word)
var param_2 = obj.search(word)
var param_3 = obj.startsWith(prefix)

贪心算法

题目1：有一间会议室，同时被n个团队进行预约，已知每个团队的开始与结束时间，求出一天时间(9点到18点)中最大可以安排多少个团队

interface Program{
  start:number,
  end:number,
}

/*
*  programs 团队数量
*  timePoint 会议室开门时间
*/
function bestArrange(programs:Program[],timePoint:number){
  programs = programs.sort((a,b)=> a.end - b.end); // 安装最小结束时间排序
  let result = 0; // 会议室接受团队个数
  for(let i = 0; i < programs.lenght; i++){ // 遍历团队数组
    if(timePoint <= programs[i].start){ // 判断团队开始时间是否小于会议可使用时间
      result++; // 开启了一个会议
      timePoint = programs[i].end;
    }
  }
  return result;
}

学习算法