目录

| | 09.栈实现队列 | 简单 |
- [x]

| | 10-I.斐波那契数列 | 简单 |
- [x] 迭代法（注意细节）
| | 10-II.跳台阶 | 简单 |
- [x] 动态规划（注意%1e7的处理）
- [x] 迭代法
| | 11.旋转数组的最小元素 | 简单 |
- [x] 排序法
- [x] 变量数组，找到第一个刚好最小的
- [ ] 二分法（特殊的二分，注意细节）
| | 12.矩阵中的路径 | 中等 |
- [x] DFS+剪枝（值得复习）
| | 13.机器人的运动范围 | 中等 |
- [ ] DFS
- [ ] BFS
| | 14-II.剪绳子 | 中等 |
- [ ] 动态规划+大数取余
- [ ] 循环取余
- [ ] 快速幂
| | 15.二进制1的个数 | 简单 |
- [x] 转成字符串
- [ ] 位运算
| | 16.数值的整数次方 | 中等 |
- [x] 快速幂
| | 17.打印从1到最大的n位数 | 简单 |
- [x]

| | 18.删除链表节点 | 简单 |
- [x]

| | 19.正则表达式的匹配 | 困难 |
- [ ]

| | 20.表示数值的字符串 | 中等 |
- [ ] 有穷自动机
| | 21.调整数组顺序 | 简单 |
- [x]

| | 22.链表倒数第k个节点 | 简单 |
- [x] 快慢指针
| | 24.链表翻转 | 简单 |
- [x] 递归法
- [x] 双指针
| | 25.合并两个排序的链表 | 简单 |
- [x]

| | 26.树的子结构 | 中等 |
- [ ] 双重递归（递归的典例）
| | 27.二叉树的镜像 | 简单 |
- [x] 递归
| | 28.对称的二叉树 | 简单 |
- [ ] 递归
| | 29.顺时针打印矩阵 | 简单 |
- [ ] DFS（层数k放置的细节）
| | 30.包含min函数的栈 | 简单 |
- [x] 模拟
| | 31.栈的压入、弹出 | 中等 |
- [x] 模拟
| | 32-I.从上到下打印二叉树 | 简单 |
- [x] 队列
| | 32-II.从上到下打印二叉树 | 简单 |
- [x] 队列
| | 32-III.从上到下打印二叉树 | 中等 |
- [ ] 队列，需要循环单调装入队列中
| | 33.二叉树的后序遍历序列 | 中等 | | | 34.二叉树中和为某一值的路径 | 中等 |
- [x] 递归
| | | | |

03

索引法

var findRepeatNumber = function(nums) {
    let m = [];
    for(let num of nums){
        if(m[num]){
            return num;
        }
        m[num]=1;
    }
    return -1;
};

第二种方法的关键点：num === nums[num]，让数字回归到它原来的下标位置处

// 原地交换
var findRepeatNumber = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];
        while(num !== i) {
            if (num === nums[num]) return num;
            [nums[i], nums[num]] = [nums[num], nums[i]];
        }
    }
    return -1;
};

集合去重

var findRepeatNumber = function(nums) {
    let set = new Set();
    for(let num of nums){
        if(set.has(num)){
            return num;
        }
        set.add(num);
    }
    return -1;
};

排序法

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums){
    nums.sort((a,b)=>(a-b));
    for(let i=0;i<nums.length;i++){
        if(nums[i]===nums[i+1]){
            return nums[i];
        }
    }
    return -1;
};

04

线性查找

注意开始if的判定条件

var findNumberIn2DArray = function(matrix, target) {
    if(matrix===null || matrix.length===0){
        return false;
    }
    let row = matrix.length;
    let col = matrix[0].length;
    let i=0,j=col-1;
    while(i<row && j>=0){
        if(matrix[i][j]<target){
            i++;
        }else if(matrix[i][j]>target){
            j--;
        }else{
            return true;
        }
    }
    return false;
};

05

调用系统函数

最推荐第二种，比较熟悉

var replaceSpace = function(s) {
    // return s.replace(/\s/g,"%20");
    return s.split(" ").join("%20");
    // return s.replaceAll(" ","%20");
};

06

递归法

var reversePrint = function(head) {
    let res = [];
    calc(head);
    return res;

    function calc(head){
        if(head===null){
            return;
        }
        calc(head.next);
        res.push(head.val);
    }
};

映射法

var reversePrint = function(head) {
    let p = head;
    let n = 0;
    while(p!==null){
        n++;
        p=p.next;
    }
    let res = [];
    p = head;
    while(p!=null){
        res[n-1]=p.val;
        n--;
        p=p.next;
    }
    return res;
};

07

09

var CQueue = function() {
    this.data = [];
    this.helper = [];
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.data.push(value);
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if (this.data.length!==0) {
        while (this.data.length > 1) {
            this.helper.push(this.data.pop());
        }
        let res = this.data.pop();
        while (this.helper.length) {
            this.data.push(this.helper.pop());
        }
        return res;
    } else {
        return -1;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

10-I

迭代法

var fib = function (n) {
    let a = 0,
        b = 1;
    for (let i = 0; i < n; ++i) {
        const c = (a + b) % (1e9 + 7);
        a = b;
        b = c;
    }
    return a;
};

10-II

动态规划

var numWays = function(n) {
    if(n==0){
        return 1;
    }
    let arr= new Array(n+1);
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    for(let i=3; i<=n; i++){
        arr[i] = arr[i-1]%1000000007 + arr[i-2]%1000000007;
    }
    return arr[n]%1000000007;
};

迭代法

var numWays = function(n) {
    let a = 1, b = 1, sum;
    for(let i = 0; i < n; i++){
        sum = (a + b) % 1000000007;
            a = b;
            b = sum;
    }
    return a;
};

11

遍历数组

class Solution {    public int minArray(int[] numbers) {        for(int i=0;i<numbers.length-1;i++){            if(numbers[i]>numbers[i+1]){                return numbers[i+1];            }        }        return numbers[0];    }}

二分

var minArray = function(numbers) {    let left=0,right=numbers.length-1;    while(left<right){        let mid = Math.floor(left + (right-left)/2);        if(numbers[mid]<numbers[right]){            right=mid;        }else if(numbers[mid]>numbers[right]){            left=mid+1;        }else{            right--;        }    }    return numbers[left];};

12

/** * @param {character[][]} board * @param {string} word * @return {boolean} */ var exist = function (board, word) {    let words = word.split('');    for (let i = 0; i < board.length; i++) {        for (let j = 0; j < board[0].length; j++) {            if (dfs(board, words, i, j, 0) === true) {                return true;            }        }    }    return false;    // 1.边界外返回false    // 2.board[i][j]!==words[k],返回false    // 3.已经访问过的坐标    function dfs(board, words, i, j, k) {        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {            return false;        }        if(board[i][j]!==words[k]){            return false;        }        if (k === words.length-1) {            return true;        }        board[i][j] = '';        let res = dfs(board, words, i - 1, j, k + 1) || dfs(board, words, i, j - 1, k + 1) || dfs(board, words, i + 1, j, k + 1) || dfs(board, words, i, j + 1, k + 1);        board[i][j] = words[k];        return res;    }}

13

数位和增量：

图例展示了 n,m = 20n,m=20 ， k \in [6, 19]k∈[6,19] 的可达解、不可达解、非解，以及连通性的变化。

根据可达解的结构和连通性，易推出机器人可 仅通过向右和向下移动，访问所有可达解 。

• 三角形内部： 全部连通，易证；
• 两三角形连通处： 若某三角形内的解为可达解，则必与其左边或上边的三角形连通（即相交），即机器人必可从左边或上边走进此三角形。

DFS：

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
    let visited = new Array(m).fill('').map((item, index) => { return new Array(n).fill(false) });
    return dfs(0, 0, 0, 0);

    function dfs(i, j, si, sj) {
        if (i >= m || j >= n || k < si + sj || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 !== 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 !== 0 ? sj + 1 : sj - 8);
    }
};

BFS：

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
    let visited = new Array(m).fill('').map((item, index) => { return new Array(n).fill(false) });
    let res = 0;
    let queue = [];
    queue.push([0, 0, 0, 0]);
    while (queue.length > 0) {
        let x = queue.shift();
        let i = x[0], j = x[1], si = x[2], sj = x[3];
        if (i >= m || j >= n || k < si + sj || visited[i][j]) {
            continue;
        }
        visited[i][j] = true;
        res++;
        queue.push([i + 1, j, (i + 1) % 10 !== 0 ? si + 1 : si - 8, sj]);
        queue.push([i, j + 1, si, (j + 1) % 10 !== 0 ? sj + 1 : sj - 8]);
    }
    return res;
};

通过leetcode题解有另外一位答主的回答，也是DSF和BFS，另一种写法可以参考

DFS：

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
    // 位数和
    function getSum(num) {
        let answer = 0;

        while (num) {
            answer += num % 10;
            num = Math.floor(num / 10);
        }

        return answer;
    }
    // 方向数组
    const directionAry = [
        [-1, 0], // 上
        [0, 1], // 右
        [1, 0], // 下
        [0, -1] // 左
    ];
    let set = new Set(['0,0']);
    dfs(0, 0, k);

    function dfs(x, y, k) {
        for (let i = 0; i < 4; i++) {
            let offsetX = x + directionAry[i][0];
            let offsetY = y + directionAry[i][1];
            if (offsetX < 0 || offsetY < 0 || offsetX > m - 1 || offsetY > n - 1 || getSum(offsetY) + getSum(offsetX) > k || set.has(`${offsetX},${offsetY}`)) {
                continue;
            }
            set.add(`${offsetX},${offsetY}`);
            dfs(offsetX, offsetY, k);
        }
    }
    return set.size;
};

BFS：

/** * @param {number} m * @param {number} n * @param {number} k * @return {number} */var movingCount = function (m, n, k) {    // 位数和    function getSum(num) {        let answer = 0;        while (num) {            answer += num % 10;            num = Math.floor(num / 10);        }        return answer;    }    // 方向数组    const directionAry = [        [-1, 0], // 上        [0, 1], // 右        [1, 0], // 下        [0, -1] // 左    ];    // 已经走过的坐标    let set = new Set(['0,0']);    // 将遍历的坐标队列，题意要求从[0,0]开始走    let queue = [[0, 0]];    // 遍历队列中的坐标    while (queue.length) {        // 移除队首坐标        let [x, y] = queue.shift();        // 遍历方向        for (let i = 0; i < 4; i++) {            let offsetX = x + directionAry[i][0];            let offsetY = y + directionAry[i][1];            // 临界值判断            if (offsetX < 0 || offsetX >= m || offsetY < 0 || offsetY >= n || getSum(offsetX) + getSum(offsetY) > k || set.has(`${offsetX},${offsetY}`)) {                continue;            }            // 走过的格子就不再纳入统计            set.add(`${offsetX},${offsetY}`);            // 将该坐标加入队列（因为这个坐标的四周没有走过，需要纳入下次的遍历）            queue.push([offsetX, offsetY]);        }    }    // 走过坐标的个数就是可以到达的格子数    return set.size;};

14-II

动态规划+大数取余

import java.math.BigInteger;
class Solution {
    public int cuttingRope(int n) {
        BigInteger[] dp = new BigInteger[n + 1];
        Arrays.fill(dp, BigInteger.valueOf(1));
        // dp[1] = BigInteger.valueOf(1);
        for(int i = 3; i < n + 1; i++){
            for(int j = 1; j < i; j++){
                dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j))).max(dp[i - j].multiply(BigInteger.valueOf(j)));
            }
        }
        return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
    }
}

这种方式效率太低，而且在JS代码中运行结果为NaN

循环取余

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
    if (n < 4) {
        return n - 1;
    } else if (n == 4) {
        return n;
    }
    let res = 1;
    while (n > 4) {
        res *= 3;
        res %= 1000000007;
        n -= 3;
    }
    // 最终剩下来的肯定是2,3,4
    return res * n % 1000000007;
};

快速幂

JS中对大数转换支持不好，在JS代码中运行失败

这个大数处理之后再弄，这里标记上

class Solution {    int mod = 1000000007;    public int cuttingRope(int n) {        if(n < 4) return n - 1;        int a = n / 3;        int b = n % 3;        if(b == 0) return (int) (myPow(3, a) % mod);        else if(b == 1) return (int) (myPow(3, a - 1) * 4 % mod);        else return (int) (myPow(3, a) * 2 % mod);    }    public long myPow(long base, int num){        long res = 1;        while(num > 0){            if((num & 1) == 1){                res *= base;                res %= mod;            }            base *= base;            base %= mod;            num >>= 1;        }        return res;    }}

15

转成字符串

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let str = n.toString(2);
    let len = str.length;
    let count = 0;
    for(let i=0;i<len;i++){
        if(str[i]==='1'){
            count++;
        }
    }
    return count;
};

位运算

var hammingWeight = function(n) {
    let cnt = 0;
    while (n) {
        cnt += n & 1;
        n >>>= 1;
    }
    return cnt;
};

16

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    let r = 1;
    let tmp = x;
    let tag = 0;
    if (n < 0) {
        tag = 1;
        n = -n;
    }
    while (n) {
        if (n & 1) {
            r *= tmp;
        }
        tmp *= tmp;
        n >>>= 1;
    }
    return tag ? 1 / r : r;
};

17

/**
 * @param {number} n
 * @return {number[]}
 */
var printNumbers = function(n) {
    let end = Math.pow(10,n)-1;
    let res = [];
    for(let i=0;i<end;i++){
        res[i]=i+1;
    }
    return res;
};

18

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
    if(head.val===val){
        head=head.next;
        return head;
    }
    let p = head;
    while(p!==null){
        if(p.next.val===val){
            p.next=p.next.next;
            break;
        }
        p=p.next;
    }
    return head;
};

20

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {

    // 状态枚举
    const   STATE_INITIAL = 1           //1. 起始的空格
    const   STATE_INT_SIGN = 2          //2. 符号位
    const   STATE_INTEGER = 3           //3. 整数部分
    const   STATE_POINT = 4             //4. 左侧有整数的小数点
    const   STATE_POINT_WITHOUT_INT = 5 //5. 左侧无整数的小数点
    const   STATE_FRACTION = 6          //6. 小数部分
    const   STATE_EXP = 7               //7. 字符 E e
    const   STATE_EXP_SIGN = 8          //8. 指数部分的符号位
    const   STATE_EXP_NUMBER = 9        //9. 指数部分的整数部分
    const   STATE_END = 10              //10. 末尾的空格

    // 字符枚举
    const   CHAR_NUMBER = 1         // 0-9
    const   CHAR_EXP = 2            // E e
    const   CHAR_POINT = 3          // .
    const   CHAR_SIGN = 4           // + -
    const   CHAR_SPACE = 5          // ' '
    const   CHAR_ILLEGAL = 6        // 除上面字符外都是非法字符


    const toCharType = char => {
        switch(char) {
            case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':  return CHAR_NUMBER
            case 'E': case 'e': return CHAR_EXP
            case '.': return CHAR_POINT
            case '+': case '-': return CHAR_SIGN
            case ' ': return CHAR_SPACE
            default: return CHAR_ILLEGAL
        }
    }    

    // 状态转移表
    const tranfer = {
        [STATE_INITIAL]: {
            [CHAR_NUMBER]: STATE_INTEGER,
            [CHAR_POINT]: STATE_POINT_WITHOUT_INT,
            [CHAR_SIGN]: STATE_INT_SIGN,
            [CHAR_SPACE]: STATE_INITIAL,
        },
        [STATE_INT_SIGN]: {
            [CHAR_NUMBER]: STATE_INTEGER,
            [CHAR_POINT]: STATE_POINT_WITHOUT_INT,
        },
        [STATE_INTEGER]: {
            [CHAR_NUMBER]: STATE_INTEGER,
            [CHAR_EXP]: STATE_EXP,
            [CHAR_POINT]: STATE_POINT,
            [CHAR_SPACE]: STATE_END,
        },
        [STATE_POINT]: {
            [CHAR_NUMBER]: STATE_FRACTION,
            [CHAR_EXP]: STATE_EXP,
            [CHAR_SPACE]: STATE_END,
        },
        [STATE_POINT_WITHOUT_INT]: {
            [CHAR_NUMBER]: STATE_FRACTION
        },
        [STATE_FRACTION]: {
            [CHAR_NUMBER]: STATE_FRACTION,
            [CHAR_EXP]: STATE_EXP,
            [CHAR_SPACE]: STATE_END,
        },
        [STATE_EXP]: {
            [CHAR_NUMBER]: STATE_EXP_NUMBER,
            [CHAR_SIGN]: STATE_EXP_SIGN,
        },
        [STATE_EXP_SIGN]: {
            [CHAR_NUMBER]: STATE_EXP_NUMBER,
        },
        [STATE_EXP_NUMBER]: {
            [CHAR_NUMBER]: STATE_EXP_NUMBER,
            [CHAR_SPACE]: STATE_END,
        },
        [STATE_END]: {
            [CHAR_SPACE]: STATE_END,
        }
    }

    const len = s.length
    let state = STATE_INITIAL // 初始状态

    for (let i = 0; i < len; i++) {
        let ch = s[i]
        let chType = toCharType(ch)
        let nextState = tranfer[state][chType]
        if (nextState) {
            state = nextState
        } else {
            return false
        }
    }  

    // 注意遍历完字符串后最后可能的状态 
    return state === STATE_INTEGER
        || state === STATE_POINT
        || state === STATE_FRACTION
        || state === STATE_EXP_NUMBER
        || state === STATE_END
};

21

/**
 * @param {number[]} nums
 * @return {number[]}
 */
 var exchange = function(nums) {
    let x = [];
    let y = [];
    for(let i=0;i<nums.length;i++){
        if(nums[i]%2){
            x.push(nums[i]);
        }else{
            y.push(nums[i])
        }
    }
    return x.concat(y);
};

22

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast=head;
        ListNode slow=head;
        while(k!=0){
            fast=fast.next;
            k--;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

24

递归法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(head==null){
        return null;
    }
    if(head.next==null){
        return head;
    }
    let last = reverseList(head.next);
    head.next.next=head;
    head.next=null;
    return last;
};

双指针

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (head == null) { return null; }
    let cur = head;
    while (head.next != null) {
        let t = head.next.next;
        head.next.next = cur;
        cur = head.next;
        head.next = t;
    }
    return cur;
};

25

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let dum = new ListNode(0), cur = dum;
    while(l1 != null && l2 != null) {
        if(l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        }
        else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 != null ? l1 : l2;
    return dum.next;
};

26

recur(A, B)函数：
1.终止条件：

• 当B为空，说明已经匹配完成了，返回true
• 当A为空，说明已经越过A的叶子节点，返回false
• 值不同：匹配失败，返回false

2.返回值：

• 判断A和B的左子节点是否相等，即recur(A.left, B.left) ；
• 判断A和B的右子节点是否相等，即recur(A.right, B.right) ；

isSubStructure(A,B)函数：
1.特例处理：当树A为空或B为空，直接返回false
2.返回值：若B是A的子结构，则：

• 以节点A为根节点的子树包含B，对应recur(A,B)
• B是A的左子树，isSubStructure(A.left,B)
• B是A的左子树，isSubStructure(A.right,B)

/**
 * 判断A的子树和B的子树是否完全相同
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function (A, B) {
    // 递归终止条件，某个树为空时必然不想等，返回false
    if (A === null || B === null) {
        return false;
    }
    // 运用 || 运算符，左边的为真就不需要往右边执行了
    return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);

    /**
     * 判断当A和B都不为空时，子树是否完全相同
     * @param {TreeNode} A 
     * @param {TreeNode} B 
     * @returns {boolean}
     */
    function recur(A, B) {
        // B为空，表示子树比较完成了
        if (B === null) {
            return true;
        }
        // A为空，表示到达了叶子节点，此时B还没到，因此比如不相等
        // A节点的值和B节点的值不相等时候返回false
        if (A === null || A.val !== B.val) {
            return false;
        }
        // 左子树和右子树同时相等时才返回true
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
};

27

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function (root) {
    if (root === null || (root.left === null && root.right === null)) {
        return root;
    }
    let temp;
    temp = mirrorTree(root.right);
    root.right = mirrorTree(root.left);
    root.left = temp;
    return root;
};

28

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    if (root === null) {
        return true;
    }
    return recur(root.left, root.right);

    function recur(L, R) {
        if (L === null && R === null) {
            return true;
        }
        if (L === null || R === null || L.val !== R.val) {
            return false;
        }
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
};

29

这里有一个细节需要注意，就是为啥是在left—->up状态下k++呢？

/**
 * 顺序打印矩阵
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
    if (!matrix || !matrix.length) {
        return [];
    }
    let row = matrix.length;
    let col = matrix[0].length;
    // res保存移动的路径
    let res = [];
    // 获取移动的方向，保存在moves对象中，相当于一个map映射
    let moves = {
        right: [0, 1],
        down: [1, 0],
        left: [0, -1],
        up: [-1, 0]
    };
    // 向内部折回的此时，就是绕了第几次圈
    let k = 0;
    // 从坐标(0,0)处开始，向右执行
    dfs(0, 0, "right");
    return res;

    function dfs(i, j, dir) {
        // 越界检查
        if (i < 0 || j < 0 || i >= row || j >= col || res.length === row * col) {
            return;
        }
        // 访问过的点加入到路径中
        res.push(matrix[i][j]);
        switch (dir) {
            case "right":
                if (j === col - 1 - k) {
                    dir = "down";
                }
                break;
            case "down":
                if (i === row - 1 - k) {
                    dir = "left";
                }
                break;
            case "left":
                if (j === k) {
                    dir = "up";
                    k++;
                }
                break;
            case "up":
                if (i === k) {
                    dir = "right";
                }
                break;
        }
        // 坐标的移动
        let x = i + moves[dir][0];
        let y = j + moves[dir][1];
        // 递归到下一步
        dfs(x, y, dir);
    }
};

30

var MinStack = function() {
    this.x_stack = [];
    this.min_stack = [Infinity];
};

MinStack.prototype.push = function(x) {
    this.x_stack.push(x);
    this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x));
};

MinStack.prototype.pop = function() {
    this.x_stack.pop();
    this.min_stack.pop();
};

MinStack.prototype.top = function() {
    return this.x_stack[this.x_stack.length - 1];
};

MinStack.prototype.min = function() {
    return this.min_stack[this.min_stack.length - 1];
};

31

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
Array.prototype.peek = function () {
    return this[this.length - 1];
}

Array.prototype.isEmpty = function () {
    return this.length === 0 ? true : false;
}
var validateStackSequences = function (pushed, popped) {
    let i = j = 0;
    let len = pushed.length;
    let stack = [];
    while (i < len && j < len) {
        if (i < len) {
            stack.push(pushed[i]);
            i++;
        }
        while (!stack.isEmpty() && stack.peek() === popped[j]) {
            stack.pop();
            j++;
        }
    }
    if (stack.isEmpty()) {
        return true;
    } else {
        return false;
    }
};

32-I

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
Array.prototype.isEmpty = function () {
    let len = this.length;
    return len === 0 ? true : false;
}
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder = function (root) {
    if (root === null) {
        return [];
    }
    let queue = [];
    let res = [];
    queue.push(root);
    while (!queue.isEmpty()) {
        let node = queue.shift();
        if (node.left !== null) {
            queue.push(node.left);
        }
        if (node.right !== null) {
            queue.push(node.right);
        }
        res.push(node.val);
    }
    return res;
};

32-II

Array.prototype.isEmpty = function () {
    let len = this.length;
    return len === 0 ? true : false;
}
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder = function (root) {
    if (root === null) {
        return [];
    }
    let queue = [];
    let res = [];
    queue.push(root);
    while (!queue.isEmpty()) {
        let tmp = [];
        for (let i = queue.length; i > 0; i--) {
            let node = queue.shift();
            if (node.left !== null) {
                queue.push(node.left);
            }
            if (node.right !== null) {
                queue.push(node.right);
            }
            tmp.push(node.val);
        }
        res.push(tmp);
    }
    return res;
};

32-III

在II中修改奇数层和偶数层的添加方向就行，这个层级是奇数还是偶数可以由结果res数组的长度来判断

Array.prototype.isEmpty = function () {
    let len = this.length;
    return len === 0 ? true : false;
}
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder = function (root) {
    if (root === null) {
        return [];
    }
    let queue = [];
    let res = [];
    queue.push(root);
    while (!queue.isEmpty()) {
        let tmp = [];
        for (let i = queue.length; i > 0; i--) {
            let node = queue.shift();
            if (node.left !== null) {
                queue.push(node.left);
            }
            if (node.right !== null) {
                queue.push(node.right);
            }
            if (res.length % 2 === 0) {
                // 偶数层
                tmp.push(node.val);
            } else {
                // 奇数层
                tmp.unshift(node.val);
            }
        }
        res.push(tmp);
    }
    return res;
};

34

/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number[][]}
 */
var pathSum = function (root, target) {
    let res = [];
    let track = [];
    recur(root, target);
    return res;

    function recur(root, target) {
        if (root === null) return;
        track.push(root.val);
        target = target - root.val;
        if (target === 0 && root.left === null && root.right === null) {
            let t = JSON.parse(JSON.stringify(track));
            res.push(t);
        }
        recur(root.left, target);
        recur(root.right, target);
        track.pop();
    }
};