数据结构和算法

说说时间复杂度和空间复杂度？

时间复杂度和空间复杂度是算法分析中常用的两个概念，用于衡量算法的效率和资源消耗情况。

• 时间复杂度（Time Complexity）：

时间复杂度描述了算法运行时间随输入规模增长的趋势，即算法执行所需的时间。

通常用大 O 表示法（Big O notation）表示时间复杂度，如 O(n)、O(log n)、O(n^2) 等。

时间复杂度分析的是算法运行时间与输入规模之间的关系，而不是具体的运行时间。

• 空间复杂度（Space Complexity）：

空间复杂度描述了算法在运行过程中所需的额外空间随输入规模增长的趋势，即算法执行所需的内存空间。

通常也用大 O 表示法表示空间复杂度，如 O(1)、O(n)、O(n^2) 等。

空间复杂度分析的是算法在运行过程中所需的额外空间与输入规模之间的关系。

数组和链表的区别？它们的应用场景？

• 数组 （Array）：

数组是一种线性数据结构，元素在内存中是连续存储的。

数组的元素可以通过索引直接访问，时间复杂度为 O(1)。

数组的大小固定，一旦创建后大小不可变。

插入和删除操作可能涉及元素的移动，时间复杂度为 O(n)。

适用于需要随机访问元素、知道元素索引的情况，以及对内存占用有明确要求的情况。

• 链表 （Linked List）:

链表是一种非连续存储的线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。

链表的插入和删除操作效率较高，时间复杂度为 O(1)，只需调整指针即可。

链表不支持随机访问，访问元素需要从头节点开始顺序查找，时间复杂度为 O(n)。

链表有单向链表、双向链表和循环链表等不同类型。

适用于频繁插入和删除操作，对内存占用没有严格要求的情况，以及不需要随机访问元素的情况。

• 应用场景：

数组适合需要快速随机访问元素的场景，例如索引数组、堆栈、队列等。

链表适合需要频繁插入和删除元素的场景，例如实现链表、LRU缓存等。

如何再JS中实现栈和队列？

• 栈

class Stack {
    constructor(){
        this.items = [];
    }

    push(element) {
        this.items.push(element);
    }

    pop() {
        if(this.isEmpty()){
            return "Stack is empty.";
        }
        return this.items.pop();
    }

    peek(){
        return this.items[this.items.length-1];
    }

    isEmpty(){
        return this.items.length === 0;
    }

    size(){
        return this.items.length;
    }
}

• 队列

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

什么是哈希表？它是如何工作的？

哈希表（Hash Table）是一种数据结构，用于实现关联数组或映射数据结构。它通过将键（key）映射到值（value）的方式来存储和检索数据。哈希表通常通过哈希函数将键转换为对应的存储位置（索引）来实现快速的数据访问。

工作原理：

• 哈希函数（Hash Function）：哈希表使用哈希函数将键转换为数组中的索引。哈希函数应该能够将不同的键映射到不同的索引，同时尽量减少碰撞（多个键映射到同一个索引）的发生。

• 存储数据：哈希表内部通常是一个数组，每个元素称为桶（bucket），每个桶可以存储一个键值对。通过哈希函数计算键的哈希值，并将值存储在对应的桶中。

• 解决冲突：由于哈希函数的映射不可避免地会导致碰撞，即多个键映射到同一个索引。哈希表通常采用解决冲突的方法，如链地址法（Separate Chaining）或开放寻址法（Open Addressing）来处理碰撞。

• 快速访问：通过哈希函数计算键的哈希值，然后找到对应的索引，从而可以快速访问存储在哈希表中的值。在理想情况下，哈希表的查找、插入和删除操作的时间复杂度为 O(1)。

说说二叉树并用JS表示一个二叉树？

二叉树是一种常见的树状数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

应用场景：

• 数据库索引：数据库中的索引通常使用B树或B+树来实现，而B树和B+树都是一种特殊的二叉树。

• 表达式求值：二叉树可以用来表示表达式，通过遍历二叉树可以求出表达式的值。

• 文件压缩：哈夫曼树是一种特殊的二叉树，可以用来实现文件压缩。

• 人工智能：决策树是一种特殊的二叉树，可以用来实现人工智能中的决策过程。

遍历方式：

• 前序遍历（Pre-order Traversal）：先访问根节点，然后访问左子树，最后访问右子树。

• 中序遍历（In-order Traversal）：先访问左子树，然后访问根节点，最后访问右子树。

• 后序遍历（Post-order Traversal）：先访问左子树，然后访问右子树，最后访问根节点。

• 层序遍历（Level-order Traversal）：按照从上到下、从左到右的顺序访问每个节点。

JS实现二叉树：

class TreeNode {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 创建二叉树
const root = new TreeNode(1)
root.left = new TreeNode(2)
root.right = new TreeNode(3)
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

实现二叉搜索树/二叉排序树（BST）的查找、插入和删除？

BST特性：

1. 若左子树非空，则左子树上所有节点的值均小于根节点的值。

2. 若右子树非空，则右子树上所有节点的值均大于根节点的值。

3. 左右子树分别是一棵BST。

4. 对BST进行中序遍历可以得到一个递增的有序序列。

5. 查找效率取决于树的高度，最好情况是一个二叉平衡树，最坏情况是只有左（右）孩子的单支树，类似于有序的链表，其平均查找长度为O(n)。

使用JavaScript实现如下：

class TreeNode {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BST {
  constructor() {
    this.root = null;
  }
  //插入，成功返回整棵树，失败返回undefined
  insert(value){
    const node = new TreeNode(value)

    if(!this.root){
      this.root = node;
      return this;
    }

    let current = this.root;

    while(true){
      if(value === current.value){
        return undefined; // 相同节点值，插入失败
      }
      if(value < current.value){
        if(!current.left){
          current.left = node;
          return this;
        }
        current = current.left;
      }else {
        if(!current.right){
          current.right = node;
          return this;
        }
        current = current.right;
      }
    }
  }
  // 查找，如果成功则返回对应节点，否则返回false
  find(value){
    if(!this.root){
      return false;
    }
    let current = this.root;
    let found = false;
    while(current && !found){
      if(value < current.value){
        current =current.left;
      }else if(value > current.value){
        current = current.right;
      }else {
        found = true
      }
    }
    if(!found){
      return false
    }
    return current
  }
  // 删除
  remove(value){
    const removeNode = (node,value) => {
      if(!node){
        return null;
      }
      if(value === node.value){
        if(!node.left && !node.right){
          return null;
        }
        if(!node.left){
          return node.right;
        }
        if(!node.right){
          return node.left;
        }
        // 如果左右子树都存在，则找到右子树中序遍历的第一个子节点替换node
        let tempNode = node.right;
        while(tempNode.left){
          tempNode = tempNode.left;
        }
        node.value = tempNode.value;
        node.right = removeNode(node.right,tempNode.value)
        return node;
      }else if(value < node.value) {
        node.left = removeNode(node.left,value)
        return node;
      }else {
        node.right = removeNode(node.right.value)
        return node;
      }
    }
    this.root = removeNode(this.node,value)
  }
}

普通的二叉树有什么问题？如何解决？说说AVL树、红黑树？

普通的二叉树在某些情况下可能会出现不平衡的情况，导致其操作的时间复杂度退化为 O(n)，其中 n 是二叉树中节点的数量。这种不平衡可能会发生在节点的插入、删除操作频繁的情况下，使得树的高度过高，从而影响了二叉树的性能。解决方案就是二叉平衡树和红黑树：

二叉平衡树（AVL树）：

• AVL 树是一种自平衡二叉搜索树，它要求任何节点的两棵子树的高度差的绝对值不超过1。如果在插入或删除操作后破坏了这一条件，AVL 树会通过旋转操作来重新平衡树的结构。

• AVL 树的平衡性较好，查找、插入和删除操作的时间复杂度都是 O(log n)，其中 n 是节点的数量。

• 由于 AVL 树要求更为严格的平衡条件，所以在频繁插入、删除操作的场景下，会有更多的旋转操作，可能会导致性能略低于红黑树。

红黑树：

• 红黑树是一种近似平衡的二叉搜索树，它通过一些特定的规则保持树的大致平衡，而不要求严格的平衡。

• 红黑树的特点包括：每个节点要么是红色，要么是黑色；根节点是黑色；每个叶节点（NIL 节点）是黑色；不能有相邻的两个红色节点；从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

• 红黑树的插入、删除操作相对 AVL 树来说更加灵活，旋转操作相对较少，因此在实际应用中更为常见。

• 红黑树的查找、插入和删除操作的时间复杂度也是 O(log n)。

什么是红黑树？它在实际应用中有什么优势？

红黑树是一种自平衡的二叉搜索树，它在普通二叉搜索树的基础上引入了一些额外的规则来保持树的平衡。红黑树具有以下特点：

1. 节点颜色：每个节点都被标记为红色或黑色。

2. 根节点：根节点是黑色的。

3. 叶子节点：叶子节点（NIL 节点或空节点）是黑色的。

4. 红色节点规则：红色节点的子节点必须是黑色的（即不存在两个相邻的红色节点）。

5. 黑色节点规则：从任一节点到其每个叶子节点的路径上，黑色节点的数量必须相同。

这些规则确保了红黑树保持平衡，从而保证了在最坏情况下的时间复杂度为 O(log n)，其中 n 是树中节点的数量。红黑树通常用于需要高效插入、删除和查找操作的数据结构，比如在编程语言的编译器实现、数据库系统、操作系统中的调度算法等场景中广泛应用。

红黑树相对于普通的二叉搜索树的优势包括：

1. 平衡性：红黑树通过自平衡的性质保持了树的平衡，避免了出现极端不平衡的情况，保证了较稳定的查找、插入和删除性能。

2. 高效性：红黑树的平衡性保证了操作的时间复杂度稳定在 O(log n) 的水平，相比于普通的二叉搜索树，在最坏情况下的性能更可控。

3. 广泛应用：由于红黑树具有高效的插入、删除和查找操作，它被广泛应用于各种领域，包括编程语言的编译器实现、数据库系统、操作系统中的调度算法等。

说说深度优先搜索（DFS）和广度优先搜索（BFS） ? 如何在树和图中实现它们？

深度优先搜索（DFS）:

DFS是一种用于遍历或搜索树或图的算法，它从根节点开始沿着一条路径直到无法再继续，然后回溯到前一节点，继续探索下一条路径，直到所有节点都被访问过为止。DFS通常使用栈来实现。

在树中，DFS可以分为三种主要方式：

• 前序遍历（Preorder）：先访问根节点，然后递归地前序遍历左子树和右子树。

• 中序遍历（Inorder）：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。

• 后序遍历（Postorder）：先递归地后序遍历左子树和右子树，然后访问根节点。

广度优先搜索（BFS）:

BFS是另一种用于遍历或搜索树或图的算法，它从根节点开始，先访问当前节点的所有邻居节点，然后逐层向下访问。BFS通常使用队列来实现。

在树中，BFS按照层级顺序逐层遍历，从根节点开始，然后是第二层节点，第三层节点，以此类推，直到所有节点都被访问过。

堆的概念和应用场景？

堆（Heap）是一种特殊的树形数据结构，通常用于实现优先队列。堆分为最大堆和最小堆两种类型，最大堆中父节点的值大于或等于子节点的值，最小堆中父节点的值小于或等于子节点的值。

堆的应用场景包括但不限于以下几个方面：

1. 优先队列（Priority Queue）：堆可以用来实现优先队列，其中具有较高优先级的元素可以更快地被访问和处理。

2. 堆排序（Heap Sort）：堆排序是一种基于堆的排序算法，通过构建最大堆或最小堆来实现排序。

3. 实时系统中的调度：堆可以用于实时系统中的任务调度，确保高优先级任务得到及时处理。

4. 图算法中的最短路径和最小生成树：堆可以用于Dijkstra算法和Prim算法等图算法中，以实现最短路径和最小生成树的计算。

在堆中，常见的操作包括插入新元素、删除堆顶元素（最大值或最小值）、堆化（Heapify）等。堆的特点是在插入和删除操作时能够保持堆的性质，即父节点和子节点之间的大小关系不变。

总的来说，堆是一种非常有用的数据结构，特别适用于需要高效地找到最大值或最小值的场景，以及一些特定的算法实现中。

什么是动态规划？给出一个动态规划的前端应用示例。

动态规划是一种算法思想，通常用于解决具有重叠子问题和最优子结构性质的问题。它的基本思想是将原问题分解成若干个子问题，先求解子问题，再由子问题的解推导出原问题的解。

在前端应用中，动态规划可以用于优化一些计算密集型的算法，例如图像处理、动画渲染等。以图像处理为例，假设我们需要对一张图片进行模糊处理，可以将每个像素点的颜色值看作一个状态，然后使用动态规划算法计算出每个状态的最优值，最终得到模糊处理后的图片。

如何在JS中实现快速排序和归并排序？解释下它们的时间复杂度？

快速排序: 时间与划分是否对称有关，快速排序最坏情况下发生在两个区域分别包含n-1个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，此时时间复杂度为O(n^2)；最好情况为划分后两个子问题的大小都不大可能大于n/2，此时时间复杂度为O(nlog2(n))。

注意： 快速排序是所有内部排序算法中平均性能最优的排序算法。

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

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

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

归并排序： 归并排序和基于交换、选择的排序思想不一样，假定排序表有n个元素，则可以将它们视为n个有序的子表，每个子表长度为1，然后两两归并，得到Math.ceil(n/2)个长度为2或1的有序表；继续两两归并，如此重复，直到合成一个长度为n的有序表为止，这种方法被称为2路归并排序。由于每趟归并的时间复杂度为O(n)，共需要Math.ceil(log2(n))趟归并，因此时间复杂度为O(nlog2(n))。

function mergeSort(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);

  const merge = (left, right) => {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        result.push(left[leftIndex]);
        leftIndex++;
      } else {
        result.push(right[rightIndex]);
        rightIndex++;
      }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
  };

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

算法题：两数之和（leetCode 1）。

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

function twoSum(nums, target) {
  const map = new Map();
  
  for (let i = 0; i <= nums.length; i++) {
    const complement = target - nums[i];
    
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    
    map.set(nums[i], i);
  }
  
  return null; // 如果没有找到匹配的值
}

算法题： 有效的括号（leetCode 20）.

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

3. 每个右括号都有一个对应的相同类型的左括号。

function isValid(s){
    if (s.length % 2 !== 0) return false
    
    const stack = []

    const map = new Map()
    map.set('(',')')
    map.set('{','}')
    map.set('[',']')

    for (let i = 0; i < s.length; i++) {
        const current = s[i]
        if(map.has(current)){
            stack.push(current)
        }else {
            const top = stack.pop()
            if(current !== map.get(top)){
                return false
            }
        }
    }
    return stack.length === 0
};

算法题： 合并两个有序链表（leetCode 21）。

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
function mergeTwoLists(list1, list2) {
    const newNode = new ListNode()
    
    let current = newNode;

    while(list1 && list2){
        if(list1.val <= list2.val){
            current.next = list1;
            list1 = list1.next
        }else {
            current.next = list2
            list2 = list2.next
        }
        current = current.next
    }
    // 剩下未比较的链表直接加入到新链表后面
    current.next = list1 === null ? list2 : list1;
    return newNode.next
};

算法题： 最长不含重复字符的子序列（leetCode 3）。

给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。注意，不是子序列。

/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
    const subString = [] // 滑动窗口
    let max = 0;
    for(let char of s){
        while(subString.includes(char)){
            subString.shift()
        }
        subString.push(char);
        max = Math.max(max,subString.length)
    }
    return max;
};

算法题： 三数之和（leetCode 15）。

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {

    const res = []

    const len = nums.length;

    if(nums === null || len < 3) return res;

    nums.sort((a,b) => a-b) // 排序为递增数组

    for(let i = 0;i < len;i++){
        if(nums[i] > 0) break; //当前数字大于0，后续数字肯定比当前数字大，和不可能为0
        if(i > 0 && nums[i] === nums[i-1]) continue; // 去重

        // 思路就是双指针，两边玩中间靠

        let left = i +1 ;
        let right = len -1 ;
        while(left < right){
            const sum = nums[i] + nums[left] + nums[right]
            if(sum === 0){
                res.push([nums[i],nums[left],nums[right]])
                while(left < right && nums[left] === nums[left+1]) left++; // 去重
                while(left < right && nums[right] === nums[right-1]) right--; //去重
                left++;
                right--;
            }else if(sum < 0){
                left++;
            }else {
                right--;
            }
        } 
    }
    return res;

};

算法题： LRU缓存机制。（leetCode 146）。

请你设计并实现一个满足 LRU(最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化LRU缓存。

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。

如果插入操作导致关键字数量超过capacity ，则应该逐出最久未使用的关键字。

函数get和 put 必须以 O(1) 的平均时间复杂度运行。

思路1： 使用Map保存key-value，使用一个数组来表示key的使用情况：越靠近数组顶部表示越新使用，put时无论Map是否有key都要将对应的key放置在数组顶部，没有的话就直接push，如果Map的size超出了capacity就将数组的第一个元素删除，再将新的key放入数组。

思路2： 使用双向循环链表来保存key-value，并使用Map保存key到节点的映射；初始化一个哨兵节点作为链表初始节点，对于被访问或者新加入的节点需要将其前置，也就是放置到哨兵节点后面，保证链表最后一个节点是最久未访问的。这样get和put的时间复杂度借助Map可以做到O(1)。

以下为思路2代码：

class ListNode {
  constructor(key = 0, value = 0) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.nodeMap = new Map();
    this.dummy = new ListNode();
    this.dummy.prev = this.dummy;
    this.dummy.next = this.dummy;
    this.capacity = capacity;
  }

  getNode(key) {
    if (!this.nodeMap.has(key)) {
      return null;
    }
    const node = this.nodeMap.get(key);
    this.remove(node);
    this.pushFront(node);
    return node;
  }

  get(key) {
    const node = this.getNode(key);
    return node ? node.value : -1;
  }

  put(key, value) {
    let node = this.getNode(key);
    if (node) {
      node.value = value;
      return;
    }
    node = new ListNode(key, value);

    this.nodeMap.set(key, node);

    this.pushFront(node); // 放在链表最前面表示最近使用

    if (this.nodeMap.size > this.capacity) {
      this.nodeMap.delete(this.dummy.prev.key); // 删除最后一个节点
      this.remove(this.dummy.prev);
    }
  }

  // 从链表中移除某个节点
  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  // 将一个节点放到链表头部
  pushFront(node) {
    node.prev = this.dummy;
    node.next = this.dummy.next;
    node.prev.next = node;
    node.next.prev = node;
  }
}

算法题： 最长递增子序列（leetCode 300）。

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 子序列。要求算法的时间复杂度降低到O(nlog(n))吗?

思路： 动态规划+二分查找。

1. 首先，获取数组的长度 len。如果数组长度小于等于 1，直接返回数组长度作为 LIS 的长度。

2. 创建一个长度为 len 的数组 res，并用 0 填充。

3. 初始化最大长度maxLen 为 0。

4. 进入循环，遍历数组 nums。对于每个元素nums[i]，使用二分查找在 res 数组中找到第一个大于等于 nums[i] 的元素的位置。

5. 使用两个指针 left 和 right 分别指向 res 数组的起始和结束位置。

6. 在 left < right 的条件下进行循环：计算中间位置 mid，取左右指针的中间值。如果 res[mid] < nums[i]，说明 nums[i] 应该插入到 mid 右侧，更新 left = mid + 1。否则，说明 nums[i] 应该插入到 mid 或者 mid 左侧，更新 right = mid。

7. 循环结束后，left 的位置就是 nums[i] 应该插入的位置。将 nums[i] 插入到 res 数组的 left 位置。

8. 如果 right 等于 maxLen，说明 nums[i] 是当前最大长度的元素，更新 maxLen += 1。

9. 循环结束后，返回 maxLen 作为最长递增子序列的长度。

这段代码利用了动态规划的思想，通过维护一个递增的辅助数组 res，不断更新其中的元素，最终得到最长递增子序列的长度。时间复杂度为 O(nlog(n))，其中n是数组的长度。这是因为在每次二分查找中，需要进行O(logn) 的比较操作，而总共需要进行n次比较操作。

function lengthOfLIS(nums) {
    const len = nums.length;

    if(len <= 1) return len
    const res = Array(len).fill(0)

    let maxLen = 0;

    for(let i = 0;i < nums.length;i++){
        let left =0, right = maxLen;
        while(left < right){
            const mid = Math.floor((left + right) / 2) ;
            if(res[mid] < nums[i]){
                left = mid + 1
            }else {
                right = mid
            }
        }
        res[left] = nums[i]
        if(right === maxLen) maxLen += 1;
    }
    return maxLen;
};

算法题： 斐波那契数列（leetCode 509）。

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

// 方法一：递归

/**
 * @param {number} n
 * @return {number}
 */
function fib(n){
  if(n <= 1) return n;
  return fib(n - 1) + fib(n-2)
}

// 方法二： 循环

/**
 * @param {number} n
 * @return {number}
 */
function fib(n){
    let sum = 0, i = 0, j=1;
    while(n-- > 1){
       sum = i + j
       i = j
       j = sum
    }
    return sum
}

// 方法三： 利用数组

/**
 * @param {number} n
 * @return {number}
 */
function fib(n){
    const queue = [0,1]

    for(let i = 2; i<= n ;i++){
        queue[i] = queue[i-1] + queue[i-2]
    }

    return queue[n]
};