剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

限制：

2 <= n <= 100000

解答：

/**
 * 集合解法
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    const set = new Set()
    for (let i = nums.length - 1; i >= 0; i--) {
        if (set.has(nums[i])) {
            return nums[i]
        } else {
            set.add(nums[i])
        }
    }
};

var swap = (nums, index1, index2) => {
    let temp = nums[index1]
    nums[index1] = nums[index2]
    nums[index2] = temp
}

/**
 * 置换解法
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    for (let i = 0;i < nums.length;) {
        const curNum = nums[i]
        if (curNum !== i && nums[curNum] === curNum) {
            return curNum
        }
        if (curNum !== i && nums[curNum] !== curNum) {
            swap(nums, curNum, i)
        }
        if (nums[i] === i) {
            i++
        }
    }
};

思路:
要确认面试官要求：空间复杂度优先？时间复杂度优先？

1. 时间复杂度优先
   用集合或者哈希记录是否重复，遍历一次即可。空间复杂度O(N)，时间复杂度O(N)
2. 空间复杂度有限
   置换解法，将数字放到数组中数字对应的下标里（数字0放到数组的第0个位置）；交换过程中如果发现要换的数字和目标位置的数字相同即为重复。空间复杂度O(1)，时间复杂度O(N)

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000
0 <= m <= 1000

解答：
从右上角开始查找，当前项比target大则向左走，比target小则向下走，越界说明不存在。
最坏情况是走到对角线，时间复杂度O(n+m)，空间复杂度O(1)。

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var findNumberIn2DArray = function(matrix, target) {
    if (matrix.length === 0 || matrix[0].length === 0) {
        return false
    }
    const n = matrix.length // 行数
    const m = matrix[0].length // 列数
    let x = 0, y = m - 1, cur = matrix[x][y]
    while (1) {
        if (cur === target) return true
        if (cur > target) y = y - 1
        if (cur < target) x = x + 1
        if (x > n - 1 || y < 0) return false
        cur = matrix[x][y]
    }
};

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."

限制：

0 <= s 的长度 <= 10000

解答：

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    return s.replaceAll(' ', '%20')
};

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function(s) {
    let target = ' '
    let obj = '%20'
    let result = ''
    for (let i = 0; i < s.length; i++) {
        if (s[i] === target) {
            result += obj
        } else {
            result += s[i]
        }
    }
    return result
};

思路：

JS可以用string.prototype.replace来实现。自己实现就是遍历字符，推入新的字符串，遇到空格的时候将要替换的字符推入新字符串。

这种做法好处就是可以忽略替换字符串导致的字符串长度变化；缺点是多用了一个字符串的空间。

时间复杂度O(n)，空间复杂度O(n)

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

解答：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
    const stack = []
    let cur = head
    while (cur !== null) {
        stack.push(cur.val)
        cur = cur.next
    }
    return stack.reverse()
};

思路：

先入后出，很自然想到栈。

时间复杂度O(n)，空间复杂度O(n)

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

限制：

0 <= 节点个数 <= 5000

解答：

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (preorder.length === 0) return null
    const rootNode = preorder[0]
    const rootNodeInorderIndex = inorder.findIndex(i => i === rootNode) // 1
    const leftSubtreeInorder = inorder.slice(0, rootNodeInorderIndex) // [9] (0, 1)
    const rightSubtreeInorder = inorder.slice(rootNodeInorderIndex + 1, inorder.length) // [15, 20, 7] (2-4)
    const leftSubtreePreorder = preorder.slice(1, 1 + leftSubtreeInorder.length) // (1, 2)
    const rightSubtreePreorder = preorder.slice(1 + leftSubtreeInorder.length, preorder.length) // (2, 5)
    const leftSubtree = buildTree(leftSubtreePreorder, leftSubtreeInorder)
    const rightSubtree = buildTree(rightSubtreePreorder, rightSubtreeInorder)
    return new TreeNode(rootNode, leftSubtree, rightSubtree)
};

思路：

考虑前序遍历和中序遍历的定义：

前序遍历：[根节点，…左子树，…右子树]

中序遍历：[…左子树，根节点，…右子树]

步骤：

• 从前序遍历结果可以找到根节点。
• 根据根节点，从中序遍历结果找到左子树的中序遍历结果和右子树的中序遍历结果。
• 根据中序遍历结果，可以在前序遍历结果中找到左子树和右子树的前序遍历结果。
• 根据左右子树的前、中序遍历结果，递归地构建左右子树。
• 组装根节点、左右子树。

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

• 1 <= values <= 10000
• 最多会对 appendTail、deleteHead 进行 10000 次调用

解答：

var CQueue = function() {
    this.inStack = []
    this.outStack = []
};

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

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    // 都为空
    if (this.outStack.length === 0 && this.inStack.length === 0) return -1
    // outStack不为空
    if (this.outStack.length > 0) {
        return this.outStack.pop()
    }
    if (this.outStack.length === 0 && this.inStack.length > 0) {
        while (this.inStack.length) {
            this.outStack.push(this.inStack.pop())
        }
        return this.outStack.pop()
    }
};

思路：

两个栈，一个为输入栈，一个为输出栈。

入队列时，直接压入输入栈。

出队列时：

1. 检查输出栈是否为空，不为空则直接输出；
2. 若输出栈为空，检查输入栈是否为空，为空则返回-1；
3. 若输入栈不为空，将输入栈中的元素依次压入输出栈。再弹出栈顶元素。

剑指 Offer 10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

提示：

• 0 <= n <= 100

解答：

/**
  * 缓存递归
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    const memory = {}
    function fibWithMemory (n, memory) {
        if (n === 0) return 0
        if (n === 1) return 1
        if (memory[n] !== undefined) return memory[n]
        const fibPrev2 = fibWithMemory(n - 2, memory)
        if (memory[n - 2] === undefined) memory[n - 2] = fibPrev2
        const fibPrev1 = fibWithMemory(n - 1, memory)
        if (memory[n - 1] === undefined) memory[n - 1] = fibPrev1
        return (fibPrev2 + fibPrev1) % (1000000007)
    }
    return fibWithMemory(n, memory)
};

/**
 * 动态规划
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if (n === 0) return 0
    if (n === 1) return 1
    let p0 = 0, p1 = 1, res
    for (let i = 2; i <= n; i++) {
        res = (p0 + p1) % 1000000007
        p0 = p1
        p1 = res
    }
    return res
};

思路：

带缓存的递归；判断有缓存就直接返回缓存结果。

空间复杂度O(n)，时间复杂度O(n)

剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

提示：

• 0 <= n <= 100

解答：

/**
 * @param {number} n
 * @return {number}
 * 记忆化递归
 */
var numWays = function(n) {
    const memory = {
        2: 2,
        1: 1,
        0: 1
    }
    function numWaysWithMemory(n, memory) {
        if (memory[n] !== undefined) return memory[n]
        let wayPrev1, wayPrev2
        // 1
        if (memory[n - 1] !== undefined) {
            wayPrev1 = memory[n - 1]
        } else {
            wayPrev1 = numWaysWithMemory(n - 1, memory)
            memory[n - 1] = wayPrev1
        }
        // 2
        if (memory[n - 2] !== undefined) {
            wayPrev2 = memory[n - 2]
        } else {
            wayPrev2 = numWaysWithMemory(n - 2, memory)
            memory[n - 2] = wayPrev2
        }
        return (wayPrev1 + wayPrev2) % 1000000007
    }
    return  numWaysWithMemory(n, memory)
};

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    if (n === 0) return 1
    if (n === 1) return 1
    let p0 = 1, p1 = 1, res
    for (let i = 2; i <= n; i++) {
        res = (p0 + p1) % 1000000007
        p0 = p1
        p1 = res
    }
    return res
};

思路： TODO

同斐波那契数列

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1

示例 2：

输入：[2,2,2,0,1]
输出：0

解答：

/**
 * @param {number[]} numbers
 * @return {number}
*  直接的想法，遍历。
 */
var minArray = function(numbers) {
    for (let i = numbers.length - 1; i > 0; i--) {
        if (numbers[i] < numbers[i - 1]) {
            return numbers[i]
        }
    }
    return numbers[0]
};


/**
 * @param {number[]} numbers
 * @return {number}
 * 二分法加速
 */
var minArray = function(numbers) {
    let left = 0, right = numbers.length - 1
    while (numbers[left] >= numbers[right] && right - left > 0) {
        let pivot = Math.floor((left + right) / 2)
        if (numbers[pivot] < numbers[pivot - 1]) return numbers[pivot]
        if (numbers[pivot] > numbers[left]) {
            left = pivot
        } else if (numbers[pivot] < numbers[left]) {
            right = pivot - 1
        } else {
            left = left + 1
        }
    }
    return numbers[left]
};

思路：

直接的想法，倒序遍历一次，时间复杂度O(n)，空间复杂度O(1)

二分查找，时间复杂度O(logn)，空间复杂度O(1)；难点是中间条件的写法细节。

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• board 和 word 仅由大小写英文字母组成

解答：

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    const boardHeight = board.length
    const boardWidth = board[0].length
    function dfs (board, word, x, y) {
        if (word.length <= 1 && board[x][y] === word[0]) return true
        if (board[x][y] !== word[0]) return false
        const temp = board[x][y]
        board[x][y] = '\0'
        let res = false
        // left
        if (y >= 1) {
            res = dfs(board, word.slice(1), x, y - 1)
        }
        // right
        if (y + 1 < boardWidth && !res) {
            res = dfs(board, word.slice(1), x, y + 1)
        }
        // up
        if (x >= 1 && !res) {
            res = dfs(board, word.slice(1), x - 1, y)
        }
        // down
        if (x + 1 < boardHeight && !res) {
            res = dfs(board, word.slice(1), x + 1, y)
        }
        board[x][y] = temp
        return res
    }
    return !board.every((row, rowIndex) => {
        const res = row.every((item, columnIndex) => {
            const res = !dfs(board, word, rowIndex, columnIndex)
            return res
        })
        return res
    })
};

思路：

1. dfs函数，从当前格子开始做dfs寻找单词。
2. 遍历，对每个格子都做dfs。

细节注意：

这里dfs进入一个新节点时如果不是直接返回true或false，而是需要继续遍历，则将当前格子中的字符替换为\0，这样的好处是无需额外的空间来标记是否已经访问过该格子。同时dfs返回时要将该替换行为复原。

剑指 Offer 13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

提示：

• 1 <= n,m <= 100
• 0 <= k <= 20

解答：

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function(m, n, k) {
    let count = 0
    const row = new Array(n).fill(0)
    let visited = []
    for (let i = 0; i < m; i++) {
        visited.push(row.slice())
    }
    function dfs (curM, curN) {
        if (getDigitSum(curM) + getDigitSum(curN) > k) return
        count++
        visited[curM][curN] = 1
        if (curM - 1 > 0 && visited[curM - 1][curN] !== 1 ) {
            dfs(curM - 1, curN)
        }
        if (curN - 1 > 0 && visited[curM][curN - 1] !== 1) {
            dfs(curM, curN - 1)
        }
        if (curM + 1 < m && visited[curM + 1][curN] !== 1) {
            dfs(curM + 1, curN)
        }
        if (curN + 1 < n && visited[curM][curN + 1] !== 1) {
            dfs(curM, curN + 1)
        }
    }
    function getDigitSum (number) {
        let num = number, sum = 0
        while (Math.floor(num / 10) > 0) {
            sum += num % 10
            num = Math.floor(num / 10)
        }
        return sum + num
    }
    dfs(0, 0)
    return count
};

思路：

1. 写一个计算数字位数和的util function
2. 从0,0开始做dfs，用一个数组记住访问过的元素。生成visited数组的方法可以记一下：new Array(length).fill(0)

剑指 Offer 14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

• 2 <= n <= 58

解答：

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
    const mem = {
        2: 1,
        3: 2,
        4: 4,
        5: 6,
        6: 9 
    }
    if (mem[n] !== undefined) return mem[n]
    let count3 = Math.floor(n / 3)
    let left3 = n % 3
    let count2 = Math.floor(left3 / 2)
    let left2 = left3 % 2
    // 余1的情况要考虑是否可以凑成4，4 > 1 * 3
    if (left2 === 1 && count2 === 0 && count3 > 1) {
        count3 -= 1
        count2 = 2
    }
    let result = 1
    while(count3 > 0) {
        result = (result * 3) % 1000000007
        count3 -= 1
    }
    return result * Math.pow(2, count2) % 1000000007
};

思路：

贪心算法，通过局部最优来达到全局最优。

考虑绳子长度为1-8的情况：

绳子长度	最优分段
1	1
2	2
3	3
4	[2，2]
5	[2，3]
6	[3，3]
7	3，[2，2]
8	3，[2，3]
9	3，[3，3]

可以看到，绳子长度为7-9可以分解为一段长度为3的绳子，再加上绳子长度为4-6时的分段情况。

由此推出，将长度为3作为一个局部，可以凑成3时就凑成3。但最后要考虑余数为1的情况，要转成2*2，因为1*3 < 2*2。

这题的难点，主要是考虑大数的情况

剑指 Offer 15. 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

• 输入必须是长度为 32 的 二进制串 。

解答：

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let count = 0
    while (n !== 0) {
        n = n & (n - 1)
        count++
    }
    return count
};

思路：

利用n & (n - 1)可以抹去最低位的1的特点做循环，直至将所有1抹去，统计次数即可。

剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

解答：

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if (n === 0) return 1
    if (n === 1) return x
    const isNegative = n < 0
    const positivePow = isNegative ? -n : n
    let next = Math.floor(positivePow / 2)
    let isOdd = positivePow % 2 === 1
    const divideResult = myPow(x, next)
    const powResult = isOdd ? divideResult * divideResult * x : divideResult * divideResult
    return isNegative ? 1 / powResult : powResult
};

思路：

a^2n = (a^n)^2，根据此公式进行分治。

时间复杂度O(logn)，空间复杂度O(1)

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

• 用返回一个整数列表来代替打印
• n 为正整数

解答：

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

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

• 题目保证链表中节点的值互不相同
• 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

解答：

/**
 * 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) {
    let cur = head
    let prev = null
    while (cur.val !== null) {
        if (cur.val === val) {
            if (prev === null) {
                return cur.next
            } else {
                prev.next = cur.next
                return head
            }
        } else {
            prev = cur
            cur = cur.next
        }
    }
};

思路：

记录前一个节点，找到节点后将prev.next指向cur.next即可。

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

提示：

1. 0 <= nums.length <= 50000
2. 1 <= nums[i] <= 10000

解答：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var exchange = function(nums) {
    let left = 0, right = nums.length - 1
    while (left < right) {
        while (left < right && nums[left] % 2 === 1) {
            left++
        }
        while (left < right && nums[right] % 2 === 0) {
            right--
        }
        const temp = nums[left]
        nums[left] = nums[right]
        nums[right] = temp
    }
    return nums
};

思路：

设置一个左指针和一个右指针，左指针找到奇数，右指针找到偶数后进行交换。

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解答：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let p1 = head, p2 = head
    for (let i = 0; i < k; i++) {
        p2 = p2.next
    }
    if (p2 === null) return p1
    while (p2.next !== null) {
        p1 = p1.next
        p2 = p2.next 
    }
    p2.next = null
    return p1.next
};

思路：

设置两个指针p1和p2，p2先走k步；然后同时循环向前移动这两个指针，当p2指向最后一个节点时，p1会停在倒数第k个节点上。

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

解答：

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

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

解答：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if (l1 === null) return l2
    if (l2 === null) return l1
    let dumHead = new ListNode()
    let p1 = l1, p2 = l2, p3 = dumHead
    while (p1 !== null && p2 !== null) {
        if (p1.val <= p2.val) {
            p3.next = p1
            p1 = p1.next
            p3 = p3.next
        } else {
            p3.next = p2
            p2 = p2.next
            p3 = p3.next
        }
    }
    p3.next = p2 === null ? p1 : p2
    return dumHead.next
};

思路：

1. 建一个dumHead指针，然后比较两个链表上的元素
2. 将较小的元素连接到dumHead指针这个链表上
3. 循环直至到达其中一个链表的尽头，这时将另一个链表剩余部分接入。
4. 返回dumHead.next

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

    3
   / \
  4  5
 / \
1  2

给定的树 B：

   4
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

0 <= 节点个数 <= 10000

解答:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function(A, B) {
    if (A === null || B === null) return false
    return  compare(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
};

function compare(A, B) {
    if (B === null) return true
    if (A === null || A.val !== B.val) return false
    return compare(A.left, B.left) && compare(A.right, B.right)
}

思路：

1. 实现一个方法，输入两个根节点，判断这两个树是否完全相同
2. 对A树进行dfs，递归应用上面的方法

难点主要在于如何把compare方法的条件写对。

剑指 Offer 29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：

• 0 <= matrix.length <= 100
• 0 <= matrix[i].length <= 100

解答：

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if (matrix.length === 0 || matrix[0].length === 0) return []
    const width = matrix[0].length
    const height = matrix.length
    const size = width * height
    let L = 0, R = width - 1, U = 0, D = height - 1
    let result = []
    while (L <= R && U <= D) {
        // 上
        for (let i = L; i <= R; i++) {
            result.push(matrix[U][i])
        }
        // 右
        for (let i = U + 1; i <= D; i++) {
            result.push(matrix[i][R])
        }
          // 注意这个退出条件，避免[[3], [2]]或[[3, 2]]这种情况重复访问。
        if (L === R || U === D) return result
          // 下
        for (let i = R - 1; i > L; i--) {
            result.push(matrix[D][i])
        }
          // 左
        for (let i = D; i > U; i--) {
            result.push(matrix[i][L])
        }
        L++
        U++
        D--
        R--
    }
    return result
};

思路：
思路1：模拟顺时针打印的路径，逐个访问。用一个数组记录访问。空间复杂度O(mn)，时间复杂度O(n)

思路2：按层访问，如上面题解。用LRUD四个指针来逐层访问。注意中间的退出条件。

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

        4
       /  \
      2   7
    / \  / \
    1  3 6  9

镜像输出：

   4
 /  \
 7   2
/ \  / \
9  6 3  1

解答：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function(root) {
    if (root === null) return root
    const temp = root.left
    root.left = root.right
    root.right = temp
    mirrorTree(root.right)
    mirrorTree(root.left)
    return root
};

剑指 Offer 28. 对称的二叉树

难度简单211

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2  2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1
 / \
2   2
 \   \
  3   3

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

限制：

0 <= 节点个数 <= 1000

解答：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) return true
    return compareSymmetric(root.left, root.right)
};

function compareSymmetric (node1, node2) {
    if (node1 === null && node2 === null) return true
    if (node1 !== null && node2 !== null) {
        if (node1.val === node2.val) {
            return compareSymmetric(node1.left, node2.right) && compareSymmetric(node1.right, node2.left)
        }
        return false
    }
    return false
}

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed 是 popped 的排列。

解答：

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function(pushed, popped) {
    const auxStack = []
    let j = 0
    for (let i = 0; i < pushed.length; i++) {
        auxStack.push(pushed[i])
        if (auxStack[auxStack.length - 1] === popped[j]) {
            while (auxStack.length > 0 && auxStack[auxStack.length - 1] === popped[j]) {
                auxStack.pop()
                j++
            }
        }
    }
    return !Boolean(auxStack.length)
};

思路：

1. 题目提示，每个压入栈的数字都不相等，因此无需考虑有相同元素的情况。
2. 入栈队列跟出栈队列时一对多的关系。这个算法的核心就是对元素出入栈的情况进行模拟。
3. 维护一个出栈队列的下标j，从0开始；
4. 对pushed进行遍历：
   1. 将每个项压入栈内；
   2. 如果当前遍历项和popped[j]相等，那么说明要进行弹出操作了，这里要把能需要弹出的项都弹出，因此循环执行：
      1. 判断栈不为空且栈顶元素和popped[j]相等，则弹出栈顶元素
      2. j++
5. 结束后判断栈是否为空，如果为空即说明合法。

剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回：

[3,9,20,15,7]

提示：

1. 节点总数 <= 1000

解答：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder = function(root) {
    if (root === null) {
        return []
    }
    const nodequeue = [root]
        const result = []
        while (nodequeue.length > 0) {
            const cur = nodequeue.shift()
            result.push(cur.val)
            cur.left && nodequeue.push(cur.left)
            cur.right && nodequeue.push(cur.right)
        }
        return result
};

思路：

利用队列先进先出的特点进行bfs。

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

思路：

虽然难度是简单，但是写好这一题并不容易；

因为是在排序数组中查找，所以很自然地要使用二分法来加速查找；

用二分法查找两次：

1. 查找第一个等于target的值的下标
2. 查找最后一个等于target的值的下标
3. 根据下标算出数字个数

解答：

/**

 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

var search = function(nums, target) {
    function leftBound (nums, target, lower) {
        let left = 0, right = nums.length - 1
        while (left <= right) {
            let pivot = Math.floor((left + right) / 2)
            const isEdge = lower ? (pivot === 0 || nums[pivot - 1] < target) : (pivot === nums.length - 1 || nums[pivot + 1] > target)
            if ((nums[pivot] === target && isEdge)) { 
                return pivot
            } else if (nums[pivot] > target) {
                right = pivot - 1
            } else if (nums[pivot] < target) {
                left = pivot + 1
            } else {
                lower ? left-- : right++
            }
        }
        return -1
    }
    const l = leftBound(nums, target, true)
    const r = leftBound(nums, target, false)
    if (l > -1 && r > -1) return r - l + 1
    return 0
};

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：

1 <= 数组长度 <= 10000

思路：

排序数组中查找，同样地，二分。

解答：

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let left = 0, right = nums.length - 1
    while (left <= right) {
        const mid = Math.floor((left + right) / 2)
        if (nums[mid] === mid) {
            left = mid + 1
        } else if (nums[mid] > mid) {
            right = mid - 1
        }
    }
    return left
};

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

限制：

1 ≤ k ≤ 二叉搜索树元素个数

思路：

因为是二叉搜索树；二叉搜索树的中序遍历结果即为所有节点的递增序列。

因此可以通过中序遍历结果来得到答案。

而因为题目为找出第k大的节点，因此应该考虑中序遍历的相反顺序的遍历结果，这样可以做一些剪枝，得到结果后马上返回。

解答：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function(root, k) {
    const midOrderTraverse = (root, arr) => {
        if (root === null) return
        const res1 = midOrderTraverse(root.right, arr)
        if (res1) return res1
        arr.push(root.val)
        if (arr.length === k) return arr[k - 1]
        const res2 = midOrderTraverse(root.left, arr)
        if (res2) return res2
    }
    return midOrderTraverse(root, [])
};

剑指 Offer 55 - I. 二叉树的深度

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

例如：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

提示：

1. 节点总数 <= 10000

思路：

没什么好说的，dfs统计最大深度。

解答：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */

var maxDepth = function(root) {
    let maxDepth = 0
    const dfs = (root, depth) => {
        if (root === null) return
        const curDepth = depth + 1
        maxDepth = (maxDepth > curDepth) ? maxDepth : curDepth
        dfs(root.left, curDepth)
        dfs(root.right, curDepth)
    }
    dfs(root, 0)
    return maxDepth
};

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回 false 。

限制：

• 0 <= 树的结点个数 <= 10000

注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/

思路：

自底向上的递归判断是否平衡：

考虑一个树，只要它的左子树或右子树不平衡，那么它也不是平衡的；

如果它的左子树和右子树都是平衡的，那么只要比较二者的深度相差是否大于1。

时间复杂度为O(n)，空间复杂度O(n)

解答：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */

var isBalanced = function(root) {
    const dfs = (root) => {
        if (root === null) return [0, true]
        const [leftDepth, isLeftSubTreeBalance] = dfs(root.left)
        const [rightDepth, isRightSubTreeBalance] = dfs(root.right)
        const diff = leftDepth - rightDepth
        if (!(isLeftSubTreeBalance && isRightSubTreeBalance) || (diff > 1 || diff < -1)) return [0, false]
        return [Math.max(leftDepth, rightDepth) + 1, true]
    }
    const res = dfs(root)
    return res[1]
};

剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

• 2 <= nums.length <= 10000

思路：

b ^ b = 0
a ^ b ^ b = a
b ^ b ^ a = a

由上，所有数字异或一遍，即可得到只出现一次的数字。

但是这道题有两个只出现了一次的数字；

这里需要做分组异或。

所有数字做异或之后，得到了两个不同数字的异或。

可以根据这个结果中为1的位置，来对数组中的所有数字进行分类。

这两个只出现了一次的数字，各自必然会被分入不同的组中。

这时候再对这两个组进行异或操作即可得到答案。

解答：

/**
 * @param {number[]} nums
 * @return {number[]}
 */

var singleNumbers = function(nums) {
    let res = nums[0]
    for (let i = 1; i < nums.length; i++) {
        res = res ^ nums[i]
    }
    let rightshift = 0
    let cp = res
    while (cp % 2 === 0) {
        cp = cp >> 1
        rightshift++
    }

    let xor1
    let xor2
    for (let i = 0; i < nums.length; i++) {
        if ((nums[i] >> rightshift) % 2 === 0) {
            if (xor1 === undefined) {
                xor1 = nums[i]
            } else {
                xor1 = xor1 ^ nums[i]
            }
        } else {
            if (xor2 === undefined) {
                xor2 = nums[i]
            } else {
                xor2 = xor2 ^ nums[i]
            }
        }
    }
    return [xor1, xor2]
};

剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

通过次数125,019

提交次数188,475

思路：

如果考虑空间复杂度为O(n)的解法，用哈希表记录的方法即可。

如果需要空间复杂度为O(1)，则需要使用双指针法。（因为这里是递增排序的数组）

使用左右指针指向数组开头和结尾。将这两个指针的和与target做比较，大于target则左移右指针，小于target则右移左指针。

解答：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

var twoSum = function(nums, target) {
    let left = 0, right = nums.length - 1
    while (left < right) {
        const sum = nums[left] + nums[right]
        if (sum === target){
            return [nums[left], nums[right]]
        }
        if (sum > target) {
            right--
        }
        if (sum < target) {
            left++
        }
    }
};