分为数据结构和算法两个板块, 作为一级标题
- 每个类型作为二级标题
  - 每个题目作为三级标题
    - 思路里面的每个 > 作为一种思路的表示
- 前提数据结构
数据结构
- 链表
  - 链接">JZ6 从尾到头打印链表 - 链接
  - JZ23 链表中环的入口结点
  - JZ22 链表中倒数最后k个结点
  - JZ76 删除链表中重复的结点
- 树
  - JZ55 二叉树的深度
  - JZ77 按之字形顺序打印二叉树
- 进阶
  - ????? JZ34 二叉树中和为某一值的路径(二)
  - 链接">??? JZ36 二叉搜索树与双向链表 - 链接
  - ??? JZ86 在二叉树中找到两个节点的最近公共祖先
  - JZ68 二叉搜索树的最近公共祖先
  - JZ30 包含min函数的栈
算法
- 搜索算法
  - JZ53 数字在升序数组中出现的次数
  - 链接">??? JZ44 数字序列中某一位的数字 - 链接
  - JZ71 跳台阶扩展问题
- 回溯
- 排序
- 位运算
- 模拟
- 其他算法

引言: 题型来自于牛客

分为数据结构和算法两个板块, 作为一级标题

每个类型作为二级标题

每个题目作为三级标题

思路里面的每个 > 作为一种思路的表示

前提数据结构

## 链表节点
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
## 树节点
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

数据结构

链表

JZ6 从尾到头打印链表 - 链接

# 描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
# 思路
> 使用[栈]实现, 从头结点遍历链表节点, 将节点加到栈中, 遍历完成后, 将栈中元素弹出
> 使用js数组[unshift]反向队列, 头部插入元素, 这样子不用弹栈
# 实现
```js
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head)
{
    // write code here
    if(!head) return [] 
    let res = []
       let pNext = head
    while(pNext){
        res.unshift(pNext.val)
        pNext = pNext.next;
    } 
    return res
}


<a name="wgfHq"></a>
### JZ24 反转链表 - [链接](https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=23286&ru=/practice/d0267f7f55b3412ba93bd35cfa8e8035&qru=/ta/coding-interviews/question-ranking)
```markdown
## 描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。


## 思路
> 通过设置三个变量 pre、current 和 next，分别用来保存前继节点、当前节点和后继结点。
从第一个节点开始向后遍历，
首先将当前节点的后继节点保存到 next 中，
然后将当前节点的后继节点设置为 pre，然后再将 pre 设置为当前节点，
current 设置为 next 节点，开始下一次循环。


## 实现
```js
function ReverseList(pHead) {
  // write code here
  if (!pHead || !pHead.next) return pHead;
  let pre = null;
  let cur = pHead;
  let next = null;
  while(cur){  
      next = cur.next;
      cur.next = pre;
      pre=cur
      cur=next
  }
  return pre;
}


<a name="ptTkM"></a>
### JZ25 合并两个排序的链表
```markdown
## 描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。


## 思路
> 比较两个链表的值, 返回最小值, 通过递归的方式，依次将两个链表的元素递归进行对比。


## 实现
```js
function Merge(pHead1, pHead2)
{
    // write code here
  if (!pHead1) return pHead2;
  if (!pHead2) return pHead1;

  let head = null;
  if (pHead1.val < pHead2.val) {
    head = pHead1;
    head.next = arguments.callee(pHead1.next, pHead2);
  } else {
    head = pHead2;
    head.next = arguments.callee(pHead1, pHead2.next);
  }
  return head;
}


<a name="pu9MH"></a>
### JZ52 两个链表的第一个公共结点
```markdown
## 描述
输入两个链表，找出它们的第一个公共结点, 并返回。



## 思路
> 第一个链表上顺序遍历每个结点，每遍历到一个结点的时候，在第二个链表上顺序遍历每个结点。
如果在第二个链表上有一个结点和第一个链表上的结点一样，说明两个链表在这个结点上重合，于是就找到了它们的公共结点。
如果第一个链表的长度为 m，第二个链表的长度为 n。这一种方法的时间复杂度是 O(mn）。

> 第二种方式是利用栈的方式，通过观察我们可以发现两个链表的公共节点，都位于链表的尾部，以此我们可以分别使用两个栈，依次将链表元素入栈。
然后在两个栈同时将元素出栈，比较出栈的节点，最后一个相同的节点就是我们要找的公共节点。
这一种方法的时间复杂度为 O(m+n)，空间复杂度为 O(m+n)

> 第三种方式是，首先分别遍历两个链表，得到两个链表的长度。然后得到较长的链表与较短的链表长度的差值。
我们使用两个指针来分别对两个链表进行遍历，首先将较长链表的指针移动 n 步，n 为两个链表长度的差值，然后两个指针再同时移动，判断所指向节点是否为同一节点。
这一种方法的时间复杂度为 O(m+n)，相同对于上一种方法不需要额外的空间。

> 循环对比, 一个链表到尾部后继续从头开始, 类似于辗转相比



## 实现
- 暴力循环法
```js
function hasNode(head, node) {
    while (head) {
        if (head.val === node.val) {
            // 再二次匹配确认一下, 防止单匹配出错
            let p1 = head, p2 = node;
            while (p1 && p2) {
                p1 = p1.next
                p2 = p2.next
                // 说明是最后一个了
                if (!p1 && !p2) return true
                // 说明后面有不匹配的
                if (p1.val !== p2.val) return false
            }
            return false
        }
        else head = head.next;
    }
    return false
}
function FindFirstCommonNode(pHead1, pHead2) {
    if (!pHead1 || !pHead2) return null;

    let p = pHead2
    while (p) {
        if (hasNode(pHead1, p)) return p
        else p = p.next
    }
    return null
}

栈弹出法 ```js


- 循环获得长度 + 指针
```js

辗转循环对比法

function FindFirstCommonNode(pHead1, pHead2)
{
  // write code here
  if (pHead1 == null || pHead2 == null) return null;
  let p1 = pHead1;
  let p2 = pHead2;
  while (p1 !== p2){
      p1 = p1.next;
      p2 = p2.next;
      if (p1 === p2) break;
      if (p1 === null) p1 = pHead2;
      if (p2 === null) p2 = pHead1;
  }
  return p1;
}

```

JZ23 链表中环的入口结点

## 描述
一个链表中包含环，如何找出环的入口结点？


## 思路
> 首先使用快慢指针的方式我们可以判断链表中是否存在环，当快慢指针相遇时，说明链表中存在环。相遇点一定存在于环中，
因此我们可以从使用一个指针从这个点开始向前移动，每移动一个点，环的长度加一，当指针再次回到这个点的时候，指针走了一圈，因此通过这个方法我们可以得到链表中的环的长度，我们将它记为 n 。
然后我们设置两个指针，首先分别指向头结点，然后将一个指针先移动 n 步，然后两个指针再同时移动，当两个指针相遇时，相遇点就是环的入口节点。

> 标记记录法: 
对链表进行遍历, 并对节点进行Map压入, 节点继续next, 如果map匹配到了说明是有环的, 如果到null都没匹配到说明没有环

## 实现
- 快慢指针法
```js
function EntryNodeOfLoop(pHead)
{
        // 设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步
        // 假如有环，一定相遇于环中某点(结论1)
        // 接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。
    if(pHead === null || pHead.next === null) return null;
    let p1 = pHead,p2 = pHead;
    while(p2 && p2.next){
        p1 = p1.next;
        p2 = p2.next.next;
                // 第一次两者在某点相遇
        if(p1 === p2){
                        // p2从头部出发，p1从相遇点出发
            p2 = pHead;
            while(p1 !== p2){
                p1 = p1.next;
                p2 = p2.next;
            }
            if(p1 === p2)  return p1;
        }
    }
    return null
}

map标记匹配

function EntryNodeOfLoop(pHead) {
// write code here
let map = new Map();
let node = pHead;
while (!map.has(node)) {
  if(!node) return null
  map.set(node, node);
  node = node.next;
}
return node;
}

```

JZ22 链表中倒数最后k个结点

## 描述
输入一个链表，输出该链表中倒数第 k 个结点


## 思路
> 使用两个指针，先让第一个和第二个指针都指向头结点，然后再让第二个指针走 k-1 步，到达第 k 个节点。然后两个指针同时向后移动，当第二个指针到达末尾时，第一个指针指向的就是倒数第 k 个节点了。


## 实现
- 双指针法
```js
function FindKthToTail( pHead ,  k ) {
    // write code here
    if(!pHead||!k) return null
    let p1 = pHead, p2 = pHead, count = 1;
    while(count < k){
        // 证明 k 范围过大
        if(!p2.next) return null
        p2=p2.next;
        count++;
    }
    while(p2.next){
        p2 = p2.next
        p1 = p1.next
    }
    return p1
}


<a name="p6zdn"></a>
### ??? JZ35 复杂链表的复制
```markdown
## 描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）


## 思路
> 第一种方式，首先对原有链表每个节点进行复制，通过 next 连接起来。然后当链表复制完成之后，再来设置每个节点的 random 指针，这个时候每个节点的 random 的设置都需要从头结点开始遍历，因此时间的复杂度为 O(n^2)。

> 第二种方式，首先对原有链表每个节点进行复制，并且使用 Map 以键值对的方式将原有节点和复制节点保存下来。当链表复制完成之后，再来设置每个节点的 random 指针，这个时候我们通过 Map 中的键值关系就可以获取到对应的复制节点，因此不必再从头结点遍历，将时间的复杂度降低为了 O(n)，但是空间复杂度变为了 O(n)。这是一种以空间换时间的做法。

> 第三种方式，首先对原有链表的每个节点进行复制，并将复制后的节点加入到原有节点的后面。当链表复制完成之后，再进行random 指针的设置，由于每个节点后面都跟着自己的复制节点，因此我们可以很容易的获取到 random 指向对应的复制节点。最后再将链表分离，通过这种方法我们也能够将时间复杂度降低为 O(n)。


## 实现

JZ76 删除链表中重复的结点

## 描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5


## 思路
> 解决这个问题的第一步是确定删除的参数。当然这个函数需要输入待删除链表的头结点。头结点可能与后面的结点重复，也就是说头结点也可能被删除，
所以在链表头额外添加一个结点。
接下来从头遍历整个链表。如果当前结点的值与下一个结点的值相同，那么它们就是重复的结点，都可以被删除。
循环last指针知道last.next与last不同, 这时候到了最后一个重复节点, 就把pre.next指向last.next
我们要确保 pre要始终与下一个没有重复的结点连接在一起。


## 实现
- 双指针循环法
```js
function deleteDuplication(pHead)
{
    // write code here
     if(!pHead|| !pHead.next) return pHead;
    // 新增一个头结点， 避免第一个节点和第二个节点相同
    let head = {
        val : 0,
        next : pHead
    }
    // 设置pre指针指向当前确定的不重复的节点
    let pre = head
    // 设置last指针一直向后搜索
    let last = head.next
    while(last){
        // 当有重复值
        if(last.next && last.val===last.next.val){
            // 找到最后一个相同节点
            while(last.next&&last.val===last.next.val){
                last = last.next
            }
            pre.next = last.next
            // last = last.next 提出去了
        }else{
            pre = pre.next
            // last = last.next 提出去了
        }
        last = last.next

    }
    return head.next
}



<a name="au5yQ"></a>
### JZ18 删除链表的节点
```markdown
## 描述
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。


## 思路
> 循环查找是否相等，当满足删除条件（链表当前节点=val）时，执行链表删除操作，注意边界条件和特殊情况的处理。


## 实现
- 循环
```js
function deleteNode(head, val) {
    // write code here
    // 处理特殊情况
    if (!head) return head;
    // 头部是要删除的
    if (head.val === val) return head.next;
    //设置一个pre前节点，以便删除操作
    let pre = null
    let cur = head
    // 链表当前值 与val值不相等时，一直向下找
    while (cur.val != val) {
        pre = cur;
        cur = cur.next;
    }
    // 跳出循环向下执行，说明，链表当前值与val相等，执行链表删除操作
    pre.next = cur.next;
    return head
}

修正版本方式没有删除项的死循环

function deleteNode(head, val) {
  // write code here
  if (!head) return head;
  if (head.val === val) return head.next;
  let pre = null
  let cur = head
  while (cur) {
      if(cur.val === val){
         pre.next = cur.next;
         break;
      }
      pre = cur;
      cur = cur.next;
  }
  return head
}

```

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

树

JZ55 二叉树的深度

## 描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。


## 思路
> 递归实现
对节点左右节点比较, 并返回最大值, 迭代累加即可

> 遍历到叶子节点累加值实现
对数进行遍历并传递值, 子节点继承并累加, 如果节点是叶子节点就把数值记录并最后比较

## 实现
- 递归实现
```js
function TreeDepth(pRoot)
{
    // write code here
    if(!pRoot) return 0
    return Math.max(TreeDepth(pRoot.left),TreeDepth(pRoot.right)) + 1
}

遍历实现

function TreeDepth(pRoot) {
  // write code here
  if (!pRoot) return 0
  // 遍历到子节点实现, 问题是会有额外空间使用
  let node = pRoot
  let stack = [node]
  let count = [0]
  while (stack.length) {
      node = stack.pop()
      // 没有深度证明是根节点, 设置为1
      if (node && !node.deep) node.deep = 1
      // 有深度就直接+1
      else node.deep++

      // 如果左右节点都没有就记录进去
      if (!node.left && !node.right) count.push(node.deep)

      // 有节点的话就对节点进行操作
      if (node.left) {
          node.left.deep = node.deep
          stack.push(node.left)
      }

      if (node.right) {
          node.right.deep = node.deep
          stack.push(node.right)
      }
  }
  return Math.max(...count)
}

```

JZ77 按之字形顺序打印二叉树

## 描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）


## 思路
> 两个栈
正常的广度遍历的话，都是同样的顺序，从左到右, 而我们要在广度遍历的基础上改造为之字形遍历。
需要在奇数行从左至右，在偶数行从右至左，因为是先进后出，分析可得我们需要的数据结构是栈
我们需要的不只是一个栈，而是两个栈，这个大家画图研究下就能想到
两个栈是这么用的，这个栈保存这一行的数据，另一个栈保存下一行的数据，然后一行打印完后交替



## 实现
- 两个栈轮流压栈弹栈: 
简单记忆为: 左->右就先压左, 后压右, 右->左就先压右, 后压左
```js
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Print(pRoot) {
    // write code here
    if (!pRoot) return []
    // 左右栈
    let LRstack = [pRoot]
    let RLstack = []
    // 临时节点, 临时结果数组
    let node = null, data = []
    // 最终结果数组
    let res = []
    // 记录长度数组
    let LRlen = LRstack.length
    let RLlen = RLstack.length

    while (LRstack.length || RLstack.length) {
        // 执行过程中会修改数组, 因此需要提前记录
        LRlen = LRstack.length
        RLlen = RLstack.length
        data = []

        if (!RLlen) {
            // 这一轮是 左-> 右
            while (LRstack.length) {
                node = LRstack.pop()
                data.push(node.val)
                // 先压入左节点, 再压入右节点 这样子 从左->右遍历后 , 数组 pop 就是逆序(偶数反向打印)的
                node.left && RLstack.push(node.left)
                node.right && RLstack.push(node.right)
            }
        }
        if (!LRlen) {
            // 这一轮是 右-> 左
            while (RLstack.length) {
                node = RLstack.pop()
                data.push(node.val)
                // 先压入右节点, 再压入左节点 这样子 从右->左遍历后 , 数组 pop 就是正序(奇数正向打印)的
                node.right && LRstack.push(node.right)
                node.left && LRstack.push(node.left)
            }
        }
        res.push(data)
    }
    return res
}
module.exports = {
    Print: Print
};



<a name="RmMzd"></a>
### JZ54 二叉搜索树的第k个节点
```markdown
## 描述
给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值


## 思路
> 首先，我们可以先画图。画完图后我们要想办法从中找出第K小的节点。
因为这是二叉搜索树，我们可以轻易发现它的中序遍历序列就是从小到大排列，也就是我们可以直接中序遍历，同时计数，就可以得到我们想要的节点了。
不过需要注意的是我们的计数变量k应该在函数外面，不然递归进去后回来时是无法获得已经改变了的k值的。


## 实现
- 递归实现中序遍历, 然后直接取值即可
```js
function KthNode( proot ,  k ) {
    // write code here
if(!proot||!k) return -1
    let arr = []
    function midOrder(root){
        if(!root) return 
        midOrder(root.left)
        arr.push(root.val)
        midOrder(root.right)
    }
    midOrder(proot)
    if(k > arr.length) return -1
    else return arr[k-1]
}

进阶

能不能使用树遍历的非递归形式





<a name="WAu7o"></a>
### JZ7 重建二叉树
```markdown
## 描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。


## 思路
> 通过递归创建根节点并返回,返回前对左右子树进行调用
 *  1. 判断先序后序是否有效,无效返回 null
 *  2. 确定根节点
 *  3. 在中序数组中确定根节点位置,其左边都是左子树,右边是右子树

## 实现
- 递归
```js
function reConstructBinaryTree(pre, vin) {
    if (!pre.length || !vin.length) return null; //其实判断一个就可以了
    let root = new TreeNode(pre[0]); // 先序数组的第一个就是根节点
    let index = vin.indexOf(pre[0]); //确定中序位置,中序左边是左子树,右边是右子树
    let leftPre = pre.slice(1, index + 1); //左子树先序
    let rightPre = pre.slice(index + 1); // 右子树先序
    let leftVin = vin.slice(0, index); // 左子树中序
    let rightVin = vin.slice(index + 1); // 右子树中序

    // 继续递归调用创建左右树
    root.left = reConstructBinaryTree(leftPre, leftVin);
    root.right = reConstructBinaryTree(rightPre, rightVin);
    // 返回根节点
    return root;
}





<a name="MC9ad"></a>
### JZ26 树的子结构
```markdown
## 描述
输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）


## 思路
> 分析如何判断树B是不是树A的子结构，只需要两步。很容易看出来这是一个递归的过程。一般在树的求解方面都和递归有关。
Step1.对树A节点进行递归并判断
Step2.判断树A中以R为根结点的子树是不是包含和树B一样的结点。


## 实现
- 递归
```js
function isSubTree(tree1, tree2) {
    //     此处tree2需要在tree1之前判断, 判断是否为子结构
    if (!tree2) return true;
    if (!tree1) return false;
    if (tree1.val !== tree2.val) return false;
    return isSubTree(tree1.left, tree2.left) && isSubTree(tree1.right, tree2.right)
}

function HasSubtree(pRoot1, pRoot2) {
    // write code here
    if (!pRoot1 || !pRoot2) return false;

    return isSubTree(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
}






<a name="NZkNB"></a>
### JZ27 二叉树的镜像
```markdown
## 描述
操作给定的二叉树，将其变换为源二叉树的镜像。


## 思路
> 如果是空的, 就要返回空
将右子树旋转后结果给左子树
将左子树旋转后结果给右子树
但是要注意提前报错左子树变量, 不然再次赋值时候左子树已经是反转过的右子树了


## 实现
```js
function Mirror( pRoot ) {
    // write code here
    if(!pRoot) return null

    let temp = pRoot.left;
    pRoot.left = Mirror(pRoot.right)
    pRoot.right = Mirror(temp)

    return pRoot
}




<a name="wcjY6"></a>
### JZ32 从上往下打印二叉树
```markdown
## 描述
不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回


## 思路
> 层序打印树, 可以看出可以使用队列然后循环出队入队即可


## 实现
- 使用队列实现
```js
function PrintFromTopToBottom(root)
{
    // write code here
    if(!root) return []

    let res = [] , node = null
    const queue = [root]

    while(queue.length){
        let node = queue.shift()
        res.push(node.val)
        node.left && queue.push(node.left)
        node.right && queue.push(node.right)
    }

    return res
}




<a name="cprv0"></a>
### JZ33 二叉搜索树的后序遍历序列
```markdown
## 描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
2.该题我们约定空树不是二叉搜索树
3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历



## 思路
> 后序遍历
对于目标数组, 使用pop得到根节点后, 剩下的就是左右子树
对剩余数组进行遍历, 前面一部分应该是左子树, 如果向左子树push时候, 右子树长度不为0, 说明不是升序, 直接 return false, 否则正常压入
对右节点正常压入即可
之后对左子树和右子树进行是否后后序遍历的迭代判断, 注意是左右子树有长度情况下才迭代, 没有长度就是true的


## 实现
```js
function VerifySquenceOfBST(sequence) {
    // write code here
    if (!sequence.length) return false;
    if (sequence.length === 1) return true;

    let root = sequence.pop(), item
    const left = [], right = []

    while (sequence.length) {
        item = sequence.shift()
        // 向左子树push时候
        if (item < root) {
            // 右子树应该是空的, 如果不是这样子就是 false
            if (right.length) return false
            else left.push(item)
        } else {
            // 向右子树push时候, 左子树可以是空的
            right.push(item)
        }
    }

    // 需要在有长度的基础上递归, 不然只有第一次是正确的
    let leftVal = left.length ? VerifySquenceOfBST(left) : true
    let rightVal = right.length ? VerifySquenceOfBST(right) : true

    return leftVal && rightVal
}






<a name="UirQx"></a>
### JZ82 二叉树中和为某一值的路径(一)
```markdown
## 描述
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n


## 思路
> 递归实现
递归, 并传入节点和比较值, 如果到叶子节点还没有匹配就false, 左右节点取或

> 遍历传递
从根节点开始向下遍历, 并传递剩余匹配值, 一直循环直到遍历所有叶子节点



## 实现
- 递归实现
```js
function hasPathSum(root, sum) {
    // write code here
    if (!root) return false

    if (!root.left && !root.right && root.val === sum) return true

    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)
}

遍历实现 (深度, 也可以采用广度的方式, 但是核心思想是目标匹配值继承)

function hasPathSum(root, sum) {
  // write code here
  if (!root) return false

  root.target = sum
  let que = [root]
  while (que.length) {
      // 此处你可以深度或者广度, 此次采用深度
      let node = que.pop()
      if (!node.left && !node.right && node.val === node.target) return true

      // 
      if (node.left) {
          node.left.target = node.target - node.val
          que.push(node.left)
      }

      //
      if (node.right) {
          node.right.target = node.target - node.val
          que.push(node.right)
      }

  }
  return false
}

```

????? JZ34 二叉树中和为某一值的路径(二)

## 描述
输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n


## 思路



## 实现

??? JZ36 二叉搜索树与双向链表 - 链接

## 描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示



## 思路
> 容易发现是中序遍历的左右连接
但是获取中序遍历后, 4的左右均为null, 这时候需要重新指向

> 参考题解, 更简洁的实现和更好的思路

## 实现
- 中序遍历 + 遍历修改指向
```js
function Convert(pRootOfTree) {
    // write code here
    if (!pRootOfTree) return null

    const res = LNR(pRootOfTree)
    // 遍历后再进行左右指针挂载
    res.forEach((item, index, arr) => {
        if (!index) item.left = null
        else item.left = arr[index - 1]

        if (index === arr.length - 1) item.right = null
        else item.right = arr[index + 1]
    })

    return res[0]
}

// 中序遍历函数
function LNR(pRootOfTree) {
    // write code here
    if (!pRootOfTree) return []

    const res = []

    if (pRootOfTree.left) res.push(...LNR(pRootOfTree.left))
    res.push(pRootOfTree)
    if (pRootOfTree.right) res.push(...LNR(pRootOfTree.right))

    return res
}

![](https://cdn.nlark.com/yuque/0/2022/png/26183548/1646822177508-7aa8a748-d38f-4fed-91ad-9f1de751bd3e.png#clientId=udb9b6f47-7ec9-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=u42808747&margin=%5Bobject%20Object%5D&originHeight=572&originWidth=2016&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=u9c21992c-566b-44f7-b55b-671675c99bd&title=)




<a name="zAJQv"></a>
### JZ79 判断是不是平衡二叉树
```markdown
## 描述
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
样例解释：
注：我们约定空树是平衡二叉树。


## 思路
> 递归实现
　　正常思路，应该会获得节点的左子树和右子树的高度，然后比较高度差是否小于1。
　　可是这样有一个问题，就是节点重复遍历了，影响效率了。

> 第二种方法：
　　改进办法就是在求高度的同时判断是否平衡，如果不平衡就返回-1，否则返回树的高度。
　　并且当左子树高度为-1时，就没必要去求右子树的高度了，可以直接一路返回到最上层了


## 实现
- 递归实现 - 求子树高度同时判断是否平衡
```js
function IsBalanced_Solution(pRoot) {
  // write code here
    // 空树是平衡二叉树
  if (!pRoot) return 1;

  // 求左子树是否平衡
  let left = IsBalanced_Solution(pRoot.left);
  if (!left) return 0; // 0 表示不平衡

  let right = IsBalanced_Solution(pRoot.right);
  if (!right) return 0;
//     console.log(Math.abs(right - left) <= 1 && Math.max(left, right) + 1)
  // 左右均有值, 那就取最大值+1返回
  return Math.abs(right - left) <= 1 && Math.max(left, right) + 1;
}

![image.png](https://cdn.nlark.com/yuque/0/2022/png/26183548/1646825371348-099fb4cd-87e7-4e5e-9e90-efeea44035b6.png#clientId=udb9b6f47-7ec9-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=160&id=ud28da167&margin=%5Bobject%20Object%5D&name=image.png&originHeight=319&originWidth=739&originalType=binary&ratio=1&rotation=0&showTitle=false&size=12897&status=done&style=none&taskId=u57e0b2b2-a83c-422b-8945-d2f32d1ad3c&title=&width=369.5)




<a name="A12P5"></a>
### JZ8 二叉树的下一个结点 - [链接](https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=23451&ru=%2Fpractice%2F9023a0c988684a53960365b889ceaf5e&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=)
> 分类

```markdown
## 描述
给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示


## 思路
> 重点是分类实现!
- 为空返回null
- 如果有右节点, 那就是右节点的最最左节点, 循环实现
- 如果没有右节点, 那就往上找, 判断节点是不是父节点的左节点, 不是就继续找
- 最后如果都没有匹配就是null

## 实现
- 条件分析+实现
```js
function GetNext(pNode)
{
//    1.二叉树为空，则返回空
    if(!pNode) return null;

//    2.存在右孩子，返回右孩子的最左节点
    if(pNode.right){
        pNode = pNode.right;
        while(pNode.left){
            pNode = pNode.left;
        }
        return pNode;
    }

//     3.不存在右孩子则一直找到该节点是父节点的左孩子为止，返回父节点
    while(pNode.next){
        let pRoot = pNode.next;

        if(pRoot.left === pNode) return pRoot;

        pNode = pNode.next;
    }

    // 最后的节点
    return null
}

![image.png](https://cdn.nlark.com/yuque/0/2022/png/26183548/1646904242873-2868978c-3f78-496f-b60f-4c04ede57653.png#clientId=uf6e6d812-f6c0-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=352&id=u431e698b&margin=%5Bobject%20Object%5D&name=image.png&originHeight=704&originWidth=734&originalType=binary&ratio=1&rotation=0&showTitle=false&size=218374&status=done&style=none&taskId=ue81a1103-8a9a-426e-9223-1711651e266&title=&width=367)




<a name="FoqFH"></a>
### JZ28 对称的二叉树
> 额外递归函数

```markdown
## 描述
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）


## 思路
> 递归
根据图片的树, 不难发现, 平衡的关键是, 对比根节点下, 左右节点的值
如果值存在且相同时候, 要交错比较(左节点左子树比较右节点右子树, 左节点右子树比较右节点左子树)
其他情况判断返回即可


## 实现
- 递归
```js
function isBalance(node1, node2) {
    // 两个都是空的, 平衡
    if (!node1 && !node2) return true

    // 一真一空, 或者值不匹配(能走到值说明两棵树都是有的), 不平衡
    if (!node1 || !node2 || node1.val !== node2.val) return false

    // 递归对比是否是平衡树
    return isBalance(node1.left, node2.right) && isBalance(node1.right, node2.left)
}

function isSymmetrical(pRoot) {
    // write code here
    if (!pRoot) return true
    // 递归实现思路, 判断左右子树是否是对称树, 所以需要一个辅助函数
    return isBalance(pRoot.left, pRoot.right)
}
module.exports = {
    isSymmetrical: isSymmetrical
};

![image.png](https://cdn.nlark.com/yuque/0/2022/png/26183548/1646906971715-24fa3af3-645a-4965-9be6-0eae99ccbd0e.png#clientId=uf6e6d812-f6c0-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=134&id=u3967170f&margin=%5Bobject%20Object%5D&name=image.png&originHeight=268&originWidth=577&originalType=binary&ratio=1&rotation=0&showTitle=false&size=10106&status=done&style=none&taskId=udbfeb555-54ce-44ec-a0ea-fd117faf344&title=&width=289)![image.png](https://cdn.nlark.com/yuque/0/2022/png/26183548/1646906975748-f2d90a10-d6f2-408b-a558-7cb78f116662.png#clientId=uf6e6d812-f6c0-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=120&id=u0d7b30b7&margin=%5Bobject%20Object%5D&name=image.png&originHeight=240&originWidth=527&originalType=binary&ratio=1&rotation=0&showTitle=false&size=8438&status=done&style=none&taskId=u810affd8-2096-4c0e-9e06-e10adcf755a&title=&width=264)




<a name="o4SAe"></a>
### ??? JZ78 把二叉树打印成多行
```markdown
## 描述
给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
该二叉树多行打印层序遍历的结果是
[
[1],
[2,3],
[4,5]
]


## 思路
- 使用两个队列轮轮流入队出队实现即可

- 优化, 使用一个队列实现(记录长度的方式)


## 实现
```js
function Print(pRoot) {
    // write code here
    if (!pRoot) return []
    let que1 = [pRoot], que2 = [], res = [], tempAr = []
    while (que1.length || que2.length) {
        if (que1.length) {
            // 此时que2.length为0, 执行的是奇数行操作
            tempAr = []
            que1.forEach(item => {
                tempAr.push(item.val)
                item.left && que2.push(item.left)
                item.right && que2.push(item.right)
            })
            que1 = []
            res.push(tempAr)
        }
        if (que2.length) {
            // 此时que1.length为0, 执行的是偶数行操作
            tempAr = []
            que2.forEach(item => {
                tempAr.push(item.val)
                item.left && que1.push(item.left)
                item.right && que1.push(item.right)
            })
            que2 = []
            res.push(tempAr)
        }
    }
    return res
}
module.exports = {
    Print: Print
};

![image.png](https://cdn.nlark.com/yuque/0/2022/png/26183548/1646907182683-66522e7a-0d16-49a1-b4b7-ea173881e1d4.png#clientId=uf6e6d812-f6c0-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=176&id=u13a923c2&margin=%5Bobject%20Object%5D&name=image.png&originHeight=352&originWidth=358&originalType=binary&ratio=1&rotation=0&showTitle=false&size=14764&status=done&style=none&taskId=ue3526d8a-2b31-47c9-83e6-007d3df0017&title=&width=179)




<a name="aKtZs"></a>
### JZ37 序列化二叉树
> 先序遍历先序遍历构建树

```markdown
## 描述
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，可以根据层序遍历的方案序列化，如下图:

层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。



## 思路
> 先序遍历序列化, 先序遍历构建树
注意对空节点的 '#' 存储和 对 '#' 节点的null构建


## 实现
```js
function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function Serialize(pRoot) {
    // write code here
    let arr = [];

    //先序遍历，将结点放在数组中(先序遍历: node节点先)
    function NLR(pRoot) {
        if (!pRoot) {
            arr.push('#');//以 # 号结尾
        } else {
            arr.push(pRoot.val);
            NLR(pRoot.left);
            NLR(pRoot.right);
        }
    }

    NLR(pRoot);
    return arr;
}
function Deserialize(s) {
    // write code here
    if (!s.length) return null;

    //数组从前往后出，构建二叉树
    let root = null, number = s.shift();

    if (number !== '#') {
        root = new TreeNode(number);
        root.left = Deserialize(s);
        root.right = Deserialize(s);
    }
    return root;
}
module.exports = {
    Serialize: Serialize,
    Deserialize: Deserialize
};

![image.png](https://cdn.nlark.com/yuque/0/2022/png/26183548/1646914830972-514112a6-27a6-40dc-98bd-dd39de326874.png#clientId=uf6e6d812-f6c0-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=146&id=u8c899fd5&margin=%5Bobject%20Object%5D&name=image.png&originHeight=292&originWidth=614&originalType=binary&ratio=1&rotation=0&showTitle=false&size=12428&status=done&style=none&taskId=ucb6717f5-ac55-4dd3-bc79-f0806e5868b&title=&width=307)



<a name="Af91L"></a>
### ??? JZ84 二叉树中和为某一值的路径(三)
```markdown
## 描述



## 思路



## 实现

??? JZ86 在二叉树中找到两个节点的最近公共祖先

## 描述



## 思路



## 实现

JZ68 二叉搜索树的最近公共祖先

## 描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2.二叉搜索树是
若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值

3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。


## 思路
> 
如果两个值都小于根节点，说明祖先在左子树一侧
如果两个值都大于根节点，说明祖先在右子树一侧
如果根节点的值恰好在两个给定值之间，这个根节点就是最近的公共祖先

## 实现
```js
function lowestCommonAncestor( root ,  p ,  q ) {
    // write code here
        // 如果两个值都小于根节点，说明祖先在左子树一侧
        if(p<root.val && q<root.val)
            return lowestCommonAncestor(root.left,p,q);

        // 如果两个值都大于根节点，说明祖先在右子树一侧
        if(p>root.val && q>root.val)
            return lowestCommonAncestor(root.right,p,q);

        // 剩最后一种情况：如果根节点的值恰好在两个给定值之间，这个根节点就是最近的公共祖先
        return root.val;

}




<a name="uCB65"></a>
### JZ86 在二叉树中找到两个节点的最近公共祖先
```markdown
## 描述
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。



## 思路
> 递归实现
如果树为空，直接返回null
如果 p和q中有等于 root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）
递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
否则，如果 left不为空，在左子树中有找到节点（p或q）
这时候要再判断一下右子树中的情况，
如果在右子树中，p和q都找不到，则 p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
否则，当 left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root

> 中序遍历+标记
先来一遍中序遍历，我们知道，中序遍历会以根节点为中心，将左右子树分成两半，
然后利用给定的两个值o1,o2，然后找出他们俩的下标，如果两个下标一个在左，一个在右，
则此根节点就是最近公共祖先，如果这两下标均在根节点的一侧，则更新根节点，继续上述步骤

## 实现
- 递归实现
```js
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
 * 
 * @param root TreeNode类 
 * @param o1 int整型 
 * @param o2 int整型 
 * @return int整型
 */
function lowestCommonAncestor(root, o1, o2) {
    // write code here
    // 如果树为空，直接返回null
    if (!root) return -1;

    // 如果 p和q中有等于 root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）
    if (root.val === o1 || root.val === o2) return root.val;

    // 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
    let left = lowestCommonAncestor(root.left, o1, o2);

    // 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
    let right = lowestCommonAncestor(root.right, o1, o2);

    // 如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
    if (left < 0) return right;
    // 否则，如果 left不为空，在左子树中有找到节点（p或q），
    // 这时候要再判断一下右子树中的情况，
    // 如果在右子树中，p和q都找不到，则 p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
    if (right < 0) return left;

    //否则，当 left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
    return root.val;
}
module.exports = {
    lowestCommonAncestor: lowestCommonAncestor
};

![image.png](https://cdn.nlark.com/yuque/0/2022/png/26183548/1646965052387-1eb908dc-7133-4954-aa9c-7a97c0abc91e.png#clientId=uf6e6d812-f6c0-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=289&id=u7c66eacb&margin=%5Bobject%20Object%5D&name=image.png&originHeight=578&originWidth=744&originalType=binary&ratio=1&rotation=0&showTitle=false&size=40272&status=done&style=none&taskId=ue1cc44a1-e750-459b-9208-448fa44c46d&title=&width=372)



<a name="FIKur"></a>
## 队列 && 栈

<a name="jssBX"></a>
### JZ9 用两个栈实现队列
```markdown
## 描述
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素


## 思路
> 
栈(先进后出): 压栈push, 弹栈pop, 栈容量length, 清空=[]
队列(先进先出): 进队push, 出队shift, 队长length, 清空=[]
使用两个栈, 一个栈作为进栈, 另一个为空, 在需要出队时候全部顺序弹出到另一个栈中, 然后另一个栈pop即可, 后续需要再次弹回原来的栈, 保持队列的可用性


## 实现
- 需要回倒一下
```js
const stackIn = []
const stackOut = []
function push(node) {
    // write code here
    stackIn.push(node)
}
function pop() {
    // write code here
    while (stackIn.length) {
        stackOut.push(stackIn.pop())
    }
    let res = stackOut.pop()
    // 再倒回原来的栈中
    while (stackOut.length) {
        stackIn.push(stackOut.pop())
    }
    return stackOut.pop()
}

理解栈中的顺序

const stackIn = []
const stackOut = []
function push(node) {
  // write code here
  stackIn.push(node)
}
function pop() {
  // write code here
  // 有的话证明上次队列没有完全出队
  if(stackOut.length) return stackOut.pop()

  // 到这里说明已经完全出队了, 需要进入下批次的队伍
  while (stackIn.length) {
      stackOut.push(stackIn.pop())
  }
  return stackOut.pop()
}

```

JZ30 包含min函数的栈

## 描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素


## 思路
> 什么叫最小的元素?
有两个栈, 正常栈和最小栈
在压入时候, 如果最小栈为空, 就直接压入; 如果值比最小值小, 就压入; 如果值大于最小值, 那就压入最小值
为什么压入最小值? 保证当前的值和最小值一一对应, 这样子pop时候对最小栈pop即可
最后获取min时候直接去最后一个


## 实现
```js
let Stack = [];
let minStack = [];
function push(node) {
  // write code here
    Stack.push(node)
    if (!minStack.length ) minStack.push(node);
    else if (node <= min()) minStack.push(node);
    else minStack.push(min());
}
function pop() {
  // write code here
        minStack.pop()
  return Stack.pop();

}
function top() {
  // write code here
  return Stack.length && Stack[Stack.length - 1];
}
function min() {
  // write code here
 return minStack[minStack.length - 1]
}




<a name="Xy7O9"></a>
### JZ31 栈的压入、弹出序列
```markdown
## 描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。


## 思路
> 需要个辅助栈帮我们临时储存已经压入栈中的值


## 实现
- 每操作一步就进行比较
```js
function IsPopOrder(pushV, popV) {
  // write code here
    // 还有双指针法可以使用
  let steps = pushV.length + popV.length;
  let stack = [];
  let i = 0;
  while (i < steps) {
    // 执行步骤,先入栈
    if (i < pushV.length) stack.push(pushV[i]);

    // 进行是否出栈判断
    while (stack.length && stack[stack.length - 1] === popV[0]) {
      stack.pop();
      popV.shift();
    }
    i++;
  }
  return !popV.length;
}






<a name="AQfKW"></a>
### JZ73 翻转单词序列
```markdown
## 描述
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？



## 思路
> 根据空格划分, 反转后, 空格拼接


## 实现
```js
function ReverseSentence(str)
{
    // write code here
    return str.split(' ').reverse().join(' ')
}






<a name="apN9s"></a>
### JZ59 滑动窗口的最大值
```markdown
## 描述
给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。



## 思路
> 是滑动窗口范围内的最大值, 使用数组的 slice 可以不影响原数组, 且返回指定范围
不过要注意 slice(start, end), 从start开始, 不包含end


## 实现
```js
function maxInWindows(num, size) {
    // write code here
    if (!size || !num.length) return []

    let start = 0
    const res = [], maxVal = 0

    while (start + size <= num.length) {
        maxVal = Math.max(...num.slice(start, start + size))
        res.push(maxVal)
        start++
    }
    return res
}

简化的代码

function maxInWindows(num, size) {
  // write code here
  if (!size || !num.length) return []

  let start = 0, res = []

  while (start + size <= num.length) {
      res.push(Math.max(...num.slice(start, start + size)))
      start++
  }

  return res
}

```

算法

搜索算法

JZ53 数字在升序数组中出现的次数

## 描述
给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数



## 思路
> 一次遍历法


## 实现
- 一次遍历法
```js
function GetNumberOfK(data, k)
{
    // write code here
    return data.filter(item=>item===k).length
}





<a name="YXggO"></a>
### JZ4 二维数组中的查找
```markdown
## 描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。

给定 target = 3，返回 false。


## 思路
> 双重循环

> 条件匹配循环
可以看到: 数组 上=>下: 递增  左=>右: 递增
所以可以直接对比目标值的大小来快速缩小范围, 减少循环次数
从右上角找到左下角

## 实现
- 条件匹配循环(从右上角找到左下角)
```js
function Find(target, array) {
    // write code here
    let maxRow = array.length, maxCol = array[0].length
    let row = 0, col = maxCol - 1;

    while (col >= 0 && row < maxRow) {
        //         let curRow = array[row]
        const curNum = array[row][col];

        if (curNum === target) return true

        if (target > curNum) row++

        else if (target < curNum) col--

    }
    return false
}






<a name="xbIEI"></a>
### JZ11 旋转数组的最小数字
```markdown
## 描述
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。


## 思路
- 双指针逼近
旋转后是这样子的 - _ - 两边大, 中间小, 一直逼近最中间
直到两个标记位遇见即可


## 实现
- 双指针逼近
```js
function minNumberInRotateArray(rotateArray) {
    // write code here

    //  旋转后是这样子的 - _ - 两边大, 中间小, 一直逼近最中间
    //  直到两个标记位遇见即可
    if (!rotateArray.length) return -1

    let pre = 0, last = rotateArray.length - 1

    while (pre < last) {
        rotateArray[pre] >= rotateArray[last] && pre++ //前面大, 前面后移
        rotateArray[pre] <= rotateArray[last] && last-- //后面大, 后面迁移
    }
    return rotateArray[pre]
}






<a name="eSOIu"></a>
### ??? JZ38 字符串的排列 - [链接](https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=23291&ru=%2Fpractice%2F9f3231a991af4f55b95579b44b7a01ba&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13)
```markdown
## 描述
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。


## 思路



## 实现

??? JZ44 数字序列中某一位的数字 - 链接

## 描述



## 思路



## 实现
```js
function findNthDigit( n ) {
    // write code here
        // 0
        // 1 ~ 9      | digit = 1 start = 1 * 1       count = 1 * 9 * 1
        // 10 ~ 99    | digit = 2 start = 1 * 10      count = 10 * 9 * 2
        // 100 ~ 999  | digit = 3 start = 1 * 10 * 10 count = 100 * 9 * 3
        if (n <= 0) return 0;
        let start = 1, digit = 1, count = 9;
        while (n > count) {
            n -= count; // 减去当前位数的总长度
            start *= 10; //起始位数
            digit ++; // 层级位数 个位(0~9), 十位(10~99),...
            count = start * 9 * digit; 
        }
        // 找到当前位数的区间了
        let num = (start + (n - 1) / digit) + ""; // 减去第0号元素0
        let idx =  parseInt((n - 1) % digit) * 1;
        return num.charAt(idx) + ""
}



<a name="HR8j2"></a>
## 动态规划

<a name="mOMTF"></a>
### JZ42 连续子数组的最大和
```markdown
## 描述
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值


## 思路
    * 动态规划解题三步走
    *
    * 1. 定义数组元素的意义
    *     此处定义 dp[i] 为到第 i 个元素时候, 其所含有的连续子数组的最大和
    *
    * 2. 找出数组元素的关系
    *     到 dp[i] 时候, dp[i]取值显然为 dp[i-1]+arr[i] 和 arr[i] 的最大值
    *
    * 3. 初始条件
    *     不难发现, 只有dp[0]需要初始化为 arr[0]
    *


## 实现
- 动态规划 dp
```js
function FindGreatestSumOfSubArray(array)
{
    // write code here
    // 使用动态规划解题
    /**
    * 动态规划解题三步走
    *
    * 1. 定义数组元素的意义
    *     此处定义 dp[i] 为到第 i 个元素时候, 其所含有的连续子数组的最大和
    *
    * 2. 找出数组元素的关系
    *     到 dp[i] 时候, dp[i]取值显然为 dp[i-1]+arr[i] 和 arr[i] 的最大值
    *
    * 3. 初始条件
    *     不难发现, 只有dp[0]需要初始化为 arr[0]
    *
    */
    let dp = [array[0]]
    let cur = 1
    while(cur<array.length){
        dp[cur] = Math.max( dp[cur-1]+array[cur], array[cur])
        cur++
    }
    // dp[i] 是每一步最大的, 只需要找到最大连续子数组的一步即可
    return Math.max(...dp)
}





<a name="Dm9Q4"></a>
### JZ85 连续子数组的最大和(二)
```markdown
## 描述
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。
1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个
3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组
4.返回的数组不计入空间复杂度计算


## 思路
- 动态规划三步走
1. 定以数组意义
2. 确定数组元素对应关系
3. 初始条件

4. 遍历分解小问题最后求值


## 实现
```js
function FindGreatestSumOfSubArray(array) {
    // write code here
    // 在最大连续子数组的基础上我们发现这道题是需要返回数组的, 而不是上次的值, 但是返回数组时候, 还需要进行最大小值比较, 所以每次累加的话就很难受, 于是设计 dp 数组结构为
    /**
    *    dp = [node]
    *    node = {
    *    val: 0, 记录当前节点最大连续数组
    *    start: 0 , 记录当前节点对应的数组开始索引
    *    end: 1 , 记录当前节点对应的数组结束索引 (slice取不到最后一项)
    *    }
    }
    */
    function maxNode(dpArr, arr, i) {
        // 进行条件判断
        let dpVal = dp[i - 1].val + arr[i]
        let val, start, end = i + 1
        if (dpVal >= arr[i]) {
            // 说明可以推入当前节点
            val = dpVal
            start = dp[i - 1].start
        } else if (dpVal < arr[i]) {
            // 从这个节点重新断点开始
            val = arr[i]
            start = i
        }

        return { val, start, end, }
    }

    // 1. 设置 dp 数组意义: dp[i] 表示 到第i节点时候的最大连续子数组节点
    // 3. 初始条件 dp[0]
    const dp = [{
        val: array[0],
        start: 0,
        end: 1
    }]
    let resVal = array[0]
    let resTag = dp[0]
    // 2. 数组元素之间的联系: dp[i] = Math.max(dp[i-1].val+arr[i], arr[i]) 的最大值节点
    let cur = 1;
    while (cur < array.length) {
        dp[cur] = maxNode(dp, array, cur)
        if (resVal <= dp[cur].val) {
            // 更新最大值
            resVal = dp[cur].val
            resTag = dp[cur]
        } else if (resVal === dp[cur].val) {
            // 加不加都一样就添加, 因为这样子数组长度会+1
            resVal = dp[cur].val
            resTag.end++
        }
        cur++
    }
    return array.slice(resTag.start, resTag.end)
}






<a name="nqlLM"></a>
### JZ69 跳台阶
```markdown
## 描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。


## 思路
- 动态规划三步走
1. 定以数组意义
2. 确定数组元素对应关系
3. 初始条件

4. 遍历分解小问题最后求值


## 实现
```js
function jumpFloor(number)
{
    // write code here
    const dp = [1, 2]
    if(number<3) return dp[number-1]
    // dp[i] = dp[i-1] + dp[i-2]
    let cur = 2
    while(cur<number){
        dp[cur] = dp[cur-1] + dp[cur-2]
        cur++
    }
    return dp[number-1]
}




<a name="rGURO"></a>
### JZ10 斐波那契数列
```markdown
## 描述
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
和青蛙跳台阶一样, 就是初始条件不一样

## 思路
- 动态规划三步走
1. 定以数组意义
2. 确定数组元素对应关系
3. 初始条件

4. 遍历分解小问题最后求值


## 实现
```js
function Fibonacci(number)
{
    // write code here
    const dp = [1, 1]
    if(number<3) return dp[number-1]
    // dp[i] = dp[i-1] + dp[i-2]
    let cur = 2
    while(cur<number){
        dp[cur] = dp[cur-1] + dp[cur-2]
        cur++
    }
    return dp[number-1]
}
module.exports = {
    Fibonacci : Fibonacci
};




<a name="SDhGw"></a>
### ??? JZ19 正则表达式匹配 - [链接](https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4?tpId=13&tqId=1375406&ru=%2Fpractice%2F28970c15befb4ff3a264189087b99ad4&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13)
```markdown
## 描述



## 思路



## 实现

JZ71 跳台阶扩展问题

## 描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。


## 思路
- 动态规划

1. 确定dp数组意义, 即dp[i]的意义
2. 确定元素之间的关系, 由题不难发现为 dp[i]为0~i-1的累加
3. 初始条件, dp[0] = 1 , 第一步只有一种跳跃方式



## 实现
- 动态规划
```js
function jumpFloorII(number)
{
 // write code here
 const dp = [1]
 let cur = 1
 while(cur<=number){
     dp[cur] = dp.reduce((sum,num)=>sum+num)
     cur++
 }
 return dp[number]
}




<a name="pPEDH"></a>
### JZ70 矩形覆盖
```markdown
## 描述
我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？


## 思路
- 动态规划三步走
1. 确定dp[i] 意义:
    此处取dp[i]为第2*i的覆盖方法

2. 确定dp元素关系:
    dp[i-1], 距离dp[i] 只有一个 | 也就只有一种方法 
    dp[i-2], 距离dp[i] 有 || 或者 = 但是上一个和 dp[i-1]一样, 所以也就只有一种方法 
    不难发现 dp[i] = dp[i-1] + dp[i-2]

3. 初始条件
    因为i的含义, 而且联系是 i-1, i-2, 所以初始条件取到 [0, 1, 2]

4. 遍历求值即可


## 实现
- 动态规划
```js
function rectCover(number)
{
    // write code here
    // 
    const dp = [0,1,2] // dp[i] 为要覆盖2*i范围的操作方法
    // 注意初始化从 0, 1, ...n

    // dp[i-1], 距离dp[i] 只有一个 | 也就只有一种方法 
    // dp[i-2], 距离dp[i] 有 || 或者 = 但是上一个和 dp[i-1]一样, 所以也就只有一种方法 
    // dp[i] = dp[i-1] + dp[i-2]
    let cur = 3
    while(cur<=number){ // 因为要最后取到 dp[i] 所以要相等
        dp[cur] = dp[cur-1] + dp[cur-2]
        cur++
    }
    return dp[number]
}





<a name="Fnob5"></a>
### JZ63 买卖股票的最好时机(一)
```markdown
## 描述
假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费


## 思路
    // 动态规划三步走
    // 1. 确定dp[i]意义: dp[i]取第i天卖出时候的最大收益, 但是计算收益需要有买入和卖出, 卖出很好理解, 也就是当前的prices[i], 买入应该是需要继承之前的dp[i-1]的买入大小
    // 2. 确定dp元素关系: dp[i].buy = dp[i-1].buy<prices[i]?dp[i-1].buy:prices[i]   dp[i].val = prices[i] - dp[i].buy
    // 3. 初始化条件: dp[0] = {val:0, buy:prices[0]}
    // 4. 操作


## 实现
- 动态规划
```js
function maxProfit(prices) {
    // write code here
    // 动态规划三步走
    // 1. 确定dp[i]意义: dp[i]取第i天卖出时候的最大收益, 但是计算收益需要有买入和卖出, 卖出很好理解, 也就是当前的prices[i], 买入应该是需要继承之前的dp[i-1]的买入大小
    // 2. 确定dp元素关系: dp[i].buy = dp[i-1].buy<prices[i]?dp[i-1].buy:prices[i]   dp[i].val = prices[i] - dp[i].buy
    // 3. 初始化条件: dp[0] = {val:0, buy:prices[0]}
    // 4. 操作
    const dp = [{ val: 0, buy: prices[0] }]
    let i = 1, money = 0

    while (i < prices.length) {
        const buy = dp[i - 1].buy < prices[i] ? dp[i - 1].buy : prices[i]
        const val = prices[i] - buy
        val > money && (money = val)
        dp[i++] = { val, buy }
    }

    return money
}




<a name="zr26d"></a>
### JZ47 礼物的最大价值
```markdown
## 描述
在一个m\times nm×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
如输入这样的一个二维数组，
[
[1,3,1],
[1,5,1],
[4,2,1]
]
那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12



## 思路
动态规划三步走
1. 确定dp意义: 因为是二维的, 所以需要二维 dp[i][j], 定义为到达第i行第j列时候的礼物的最大价值
2. 确定dp元素间关系: 由题知道只能向下或者向右移动, 还要有礼物的最大价值, 显然: dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3. 初始化条件: 由1,2知, 最终取dp[i-1][j-1] 所以需要初始化 第0行 和 第0列 - for循环
4. 操作


## 实现
- 动态规划
```js
function maxValue(grid) {
    // write code here
    // 动态规划三步走
    // 1. 确定dp意义: 因为是二维的, 所以需要二维 dp[i][j], 定义为到达第i行第j列时候的礼物的最大价值
    // 2. 确定dp元素间关系: 由题知道只能向下或者向右移动, 还要有礼物的最大价值, 显然: dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    // 3. 初始化条件: 由1,2知, 最终取dp[i-1][j-1] 所以需要初始化 第0行 和 第0列 - for循环
    // 4. 操作

    // 初始化索引
    let rowMax = grid.length, colMax = grid[0].length
    let row = 1, col = 1;

    // 定义二维数组
    const dp = new Array(rowMax)
    dp[0] = [grid[0][0]]
    for (let i = 1; i < rowMax; i++) {
        dp[i] = [grid[i][0] + dp[i - 1][0]]
    }
    for (let i = 1; i < colMax; i++) {
        dp[0][i] = dp[0][i - 1] + grid[0][i]
    }

    while (row < rowMax) {
        while (col < colMax) {
            dp[row][col] = Math.max(dp[row - 1][col], dp[row][col - 1]) + grid[row][col]
            col++
        }
        col = 1
        row++
    }

    return dp[rowMax - 1][colMax - 1]

}




<a name="nqUKV"></a>
### JZ48 最长不含重复字符的子字符串 - [链接](https://www.nowcoder.com/practice/48d2ff79b8564c40a50fa79f9d5fa9c7?tpId=13&tqId=2276769&ru=%2Fpractice%2F2237b401eb9347d282310fc1c3adb134&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13)
```markdown
## 描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。


## 思路
1. 确定dp意义: 因为是数组, 取dp[i]为i节点字符串时候的最长子字符串, 但是不够存储, 而js二维数组不好定义, 
    所以采取对象形式存储, 类似 dp[i] = {len:1, str:'a'}
2. 确定dp元素关系: 当到达dp[i]时, 如果dp[i-1]中含有s[i], 那么就重复了, 这时候节点就应该取之前节点s[i]相同元素后面的, 否则拼入即可, 
    显然: dp[i].str = dp[i-1].includs(s[i])? 截取拼入 : 直接拼入; dp[i].len = dp[i].str.length
3. 初始条件, 因为是 i-1, 所以开始初始 0


## 实现
- 动态规划
```js
function lengthOfLongestSubstring(s) {
    // write code here
    // 动态规划三步走
    // 1. 确定dp意义: 因为是数组, 取dp[i]为i节点字符串时候的最长子字符串, 但是不够存储, 而js二维数组不好定义, 
    //    所以采取对象形式存储, 类似 dp[i] = {len:1, str:'a'}
    // 2. 确定dp元素关系: 当到达dp[i]时, 如果dp[i-1]中含有s[i], 那么就重复了, 这时候节点就应该取之前节点s[i]相同元素后面的, 否则拼入即可, 
    //    显然: dp[i].str = dp[i-1].includs(s[i])? 截取拼入 : 直接拼入; dp[i].len = dp[i].str.length
    // 3. 初始条件, 因为是 i-1, 所以开始初始 0
    // 4. 操作

    const dp = [{ str: s[0], len: 1 }]
    let i = 1, maxLen = 1

    while (i < s.length) {

        // 如果之前含有当前字符的话, 是需要从不含该字符截取一下 譬如前一个是 bac, 当前是 a, 那么现在结果应该是 ca, 而不是 a
        let hasChar = dp[i - 1].str.indexOf(s[i])
        let preStr = hasChar === -1 ? dp[i - 1].str : dp[i - 1].str.slice(hasChar + 1)

        let str = preStr + s[i]
        let len = str.length

        len > maxLen && (maxLen = len)
        dp[i] = { str, len }
        i++
    }

    return maxLen
}




<a name="vNdtc"></a>
### ??? JZ46 把数字翻译成字符串 - [链接](https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668?tpId=13&tqId=1024831&ru=%2Fpractice%2F48d2ff79b8564c40a50fa79f9d5fa9c7&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13)
```markdown
## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

回溯

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

排序

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

位运算

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

模拟

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

其他算法

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

## 描述



## 思路



## 实现

数据结构与算法

🤺 剑指Offer

分为`数据结构`和`算法`两个板块, 作为一级标题

每个`类型`作为二级标题

每个`题目`作为三级标题

思路里面的每个 `>` 作为一种思路的表示

前提数据结构

数据结构

链表

JZ6 从尾到头打印链表 - 链接

JZ23 链表中环的入口结点

JZ22 链表中倒数最后k个结点

JZ76 删除链表中重复的结点

树

JZ55 二叉树的深度

JZ77 按之字形顺序打印二叉树

进阶

????? JZ34 二叉树中和为某一值的路径(二)

??? JZ36 二叉搜索树与双向链表 - 链接

??? JZ86 在二叉树中找到两个节点的最近公共祖先

JZ68 二叉搜索树的最近公共祖先

JZ30 包含min函数的栈

算法

搜索算法

JZ53 数字在升序数组中出现的次数

??? JZ44 数字序列中某一位的数字 - 链接

JZ71 跳台阶扩展问题

回溯

排序

位运算

模拟

其他算法

🤺 剑指Offer

分为数据结构和算法两个板块, 作为一级标题

每个类型作为二级标题

每个题目作为三级标题

思路里面的每个 > 作为一种思路的表示

前提数据结构

数据结构

链表

JZ6 从尾到头打印链表 - 链接

JZ23 链表中环的入口结点

JZ22 链表中倒数最后k个结点

JZ76 删除链表中重复的结点

树

JZ55 二叉树的深度

JZ77 按之字形顺序打印二叉树

进阶

????? JZ34 二叉树中和为某一值的路径(二)

??? JZ36 二叉搜索树与双向链表 - 链接

??? JZ86 在二叉树中找到两个节点的最近公共祖先

JZ68 二叉搜索树的最近公共祖先

JZ30 包含min函数的栈

算法

搜索算法

JZ53 数字在升序数组中出现的次数

??? JZ44 数字序列中某一位的数字 - 链接

JZ71 跳台阶扩展问题

回溯

排序

位运算

模拟

其他算法

分为`数据结构`和`算法`两个板块, 作为一级标题

每个`类型`作为二级标题

每个`题目`作为三级标题

思路里面的每个 `>` 作为一种思路的表示