算法题

发表于 2021-05-07 更新于 2022-06-22 分类于前端面试阅读次数：

本文字数： 31k 阅读时长 ≈ 28 分钟

持续更新中······

算法题

1. 两数之和⭐️

题目描述

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

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

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

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

解法1：暴力

// brute force way
var twoSum = function(nums, target) {
    for(let i = 0; i<nums.length; i++){
        for(let j = i+1; j<nums.length; j++){
            if(nums[i]+nums[j]==target){
                return[i, j];
            }
        }
    }
};

复杂度分析

时间复杂度：O(N²)，其中N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
空间复杂度：O(1)。

解法2：哈希表

// hash table
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

复杂度分析

时间复杂度：O(N)，其中N是数组中的元素数量。对于每一个元x，我们可以O(1)地寻找target - x。
空间复杂度：O(N)，其中N是数组中的元素数量。主要为哈希表的开销。

2. 两数相加⭐️⭐️

题目描述

2. 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

解法：链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let carry = 0;
    let dummy = new ListNode();
    let curr = dummy;
    while(l1 || l2){
        let x = l1 ? l1.val : 0;
        let y = l2 ? l2.val : 0;
        
        let sum = x + y + carry;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        
        carry = Math.floor(sum/10);
        if(l1) l1 = l1.next;
        if(l2) l2 = l2.next;
    }
    if(carry != 0) curr.next = new ListNode(carry);
    return dummy.next;
};

思路

【简单易懂Java/C++/Python/JS】【培养算法思维】- 两数相加

7. 整数反转⭐️

题目描述

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321
示例 3：

输入：x = 120
输出：21
示例 4：

输入：x = 0
输出：0

解法：数组

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let isNeg = false;
    if(x<0){
        x *= -1;
        isNeg = true;
    }
    let arr = x.toString().split('');
    let res = [];
    for(let i=arr.length-1; i>=0; i--){
        res.push(arr[i]);
    }
    res = Number(res.join(''));
    if(isNeg) res *= -1;
    if(res < (-1)*Math.pow(2, 31) || res > Math.pow(2, 31)-1) return 0;
    return res;
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	128 ms	39.5 MB	JavaScript	2021/06/27 23:24	数组

9. 回文数⭐️

题目描述

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

示例 4：

输入：x = -101
输出：false

解法：双指针

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    let arr = x.toString().split('');
    let i = 0;
    let j = arr.length - 1;
    while(i<j) {
        if(arr[i] !== arr[j]) return false;
        i++;
        j--;
    }
    return true;
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	152 ms	47.2 MB	JavaScript	2021/07/14 00:08	双指针

11. 盛最多水的容器⭐️⭐️

题目描述

11. 盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

输入：height = [1,2,1]
输出：2

解法：双指针

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let i = 0;
    let j = height.length-1;
    let res = 0;
    while(i<j){
        res = Math.max(res, (j - i) * Math.min(height[i], height[j]));
        if(height[i] < height[j]) i++;
        else j--;
    }
    return res;
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	84 ms	46.9 MB	JavaScript	2021/07/13 23:51	双指针🚩

42. 接雨水⭐️⭐️⭐️

题目描述

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

解法1：双指针

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let res = 0;
    let i = 0;
    let j = height.length-1;
    let leftMax = 0;
    let rightMax = 0;
    while(i<j){
        if(height[i]<height[j]) {
            if(height[i]<leftMax) res += leftMax - height[i];
            else leftMax = height[i];
            i++;
        }
        else {
            if(height[j]<rightMax) res += rightMax - height[j];
            else rightMax = height[j]; 
            j--;
        }
    }
    return res;
};

解法2：动态编程

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let res = 0;
    let leftArr = [];
    let rightArr = [];
    let leftMax = 0;
    let rightMax = 0;
    for(let n of height) {
        leftMax = Math.max(n, leftMax);
        leftArr.push(leftMax - n);
    }
    height = height.reverse();
    for(let n of height) {
        rightMax = Math.max(n, rightMax);
        rightArr.push(rightMax - n);
    }
    rightArr = rightArr.reverse();
    for(let i=0; i<height.length; i++) {
        res += Math.min(leftArr[i], rightArr[i]);
    }
    return res;
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	84 ms	39.7 MB	JavaScript	2021/07/15 10:01	动态编程🚩
通过	76 ms	39.6 MB	JavaScript	2021/07/15 09:38	双指针🚩
超出时间限制	N/A	N/A	JavaScript	2021/07/15 01:01

226. 翻转二叉树⭐️

题目描述

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

4
/
2 7
/ \ /
1 3 6 9

输出：

4
/
7 2
/ \ /
9 6 3 1

解法：递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(root == null){
        return null;
    }
    let tempNode = root.left;
    root.left = root.right;
    root.right = tempNode;

    invertTree(root.left);
    invertTree(root.right);
    return root;
};

144. 二叉树的前序遍历⭐️

题目描述

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

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

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

解法：递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    if(!root) return [];
    let res = [];
    res.push(root.val);
    res = res.concat(preorderTraversal(root.left));
    res = res.concat(preorderTraversal(root.right));
    return res;
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	120 ms	38.8 MB	JavaScript	2021/06/27 23:03	递归📝

剑指OFFER

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

题目描述

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

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

解法1：暴力

//暴力
/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    for(let i = 0; i<nums.length; i++){
        for(let j = i+1; j<nums.length; j++){
            if(nums[i] == nums[j]){
                return nums[i];
            }
        }
    }
};

时间复杂度：O(N²)

解法2：数组占位

//数组占位
/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    let temp = [];
    for(let i=0; i<nums.length; i++){
        if(temp[nums[i]] == 1){
            return nums[i];
        }
        temp[nums[i]] = 1;
    }
};

时间复杂度：O(N)

解法3：哈希表

//哈希表
/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    let map = new Map();
    for(let i=0; i<nums.length; i++){
        if(map.has(nums[i])){
            return nums[i];
        }
        map.set(nums[i], i);
    }
};

时间复杂度：O(N)

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	120 ms	45.6 MB	JavaScript	2021/05/08 19:12	哈希表🚩
通过	100 ms	44.4 MB	JavaScript	2021/05/08 19:07	数组占位🚩
通过	1392 ms	42.9 MB	JavaScript	2021/05/08 19:00	暴力解法

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

题目描述

剑指 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

解法：坐标法

//坐标法/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */var findNumberIn2DArray = function(matrix, target) {    if(!matrix[0]) return false;    let y = 0;    let x = matrix[0].length - 1;    while(y<matrix.length && x>=0){        if(target == matrix[y][x]) return true;        else if(target > matrix[y][x]) {            y++; //下移        }        else {            x--; //上移        }    }    return false;};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	88 ms	41 MB	JavaScript	2021/05/08 22:40

剑指 Offer 05. 替换空格⭐️

题目描述

剑指 Offer 05. 替换空格

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

解法1：调用函数

repleace/replaceAll
encodeURIComponent
split/join

解法2：原地修改

//原地修改/** * @param {string} s * @return {string} */var replaceSpace = function(s) {    s = s.split(''); //将字符串变为数组    let oldLength = s.length;    let countSpace = 0;    for(let i=0; i<s.length; i++){        if(s[i] == ' '){            countSpace++;        }    }    s.length += countSpace * 2; //注意是2，不是3    let i = s.length-1; //指向s末尾    let j = oldLength-1; //指向有效字符串    for(; j>=0; i--, j--){        if(s[j] == ' '){            s[i] = '0';            s[--i] = '2';            s[--i] = '%';        }        else{            s[i] = s[j];        }    }    return s.join('');};

思路：【原地修改】替换空格

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	84 ms	37.7 MB	JavaScript	2021/05/09 00:21	原地修改🚩
通过	84 ms	37.7 MB	JavaScript	2021/05/08 22:51	replaceAll()

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

题目描述

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

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

解法1：反转数组

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
    if(!head) return [];
    let arr = [];
    while(head){
        arr.push(head.val);
        head = head.next;
    }
    let length = arr.length;
    if(length%2 == 0){
        for(let i=0; i<length/2; i++){
            let temp = arr[i];
            arr[i] = arr[length-i-1];
            arr[length-i-1] = temp;
        }
    }
    else{
        for(let i=0; i<(length-1)/2; i++){
            let temp = arr[i];
            arr[i] = arr[length-i-1];
            arr[length-i-1] = temp;
        }
    }
    return arr;
};

解法2：模拟栈

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {number[]} */var reversePrint = function(head) {    if(!head) return [];    let heap = [];    let length = 0;    while(head){        heap.push(head.val);        head = head.next;        length++;    }    let arr = [];    // while(heap){    //     arr.push(heap.pop);    // }    for(let i=0; i<length; i++){        arr[i] = heap.pop();    }    return arr;};

解法3：unshift()

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

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	88 ms	40 MB	JavaScript	2021/05/09 01:18	unshift()🚩
通过	100 ms	40.3 MB	JavaScript	2021/05/09 01:18	栈🚩
通过	116 ms	39.9 MB	JavaScript	2021/05/09 01:05	反转数组

剑指 Offer 07. 重建二叉树⭐️⭐️

题目描述

剑指 Offer 07. 重建二叉树

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3/ \9  20/  \15   7
限制：

0 <= 节点个数 <= 5000

解法：分治思想（递归）

/** * Definition for a binary tree node. * function TreeNode(val) { *     this.val = val; *     this.left = this.right = null; * } *//** * @param {number[]} preorder * @param {number[]} inorder * @return {TreeNode} */var buildTree = function(preorder, inorder) {    if(!preorder.length || !inorder.length) return null;    const rootVal = preorder[0];    const rootNode = new TreeNode(rootVal);    let i = inorder.indexOf(rootVal); //前序数组中根结点的下标，也是左子树的结点数    rootNode.left = buildTree(preorder.slice(1, i+1), inorder.slice(0, i));    rootNode.right = buildTree(preorder.slice(i+1), inorder.slice(i+1));    return rootNode;};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	168 ms	110.6 MB	JavaScript	2021/05/09 01:59	分治思想🚩

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

题目描述

剑指 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.stackA = [];    this.stackB = [];};/**  * @param {number} value * @return {void} */CQueue.prototype.appendTail = function(value) {    this.stackA.push(value);};/** * @return {number} */CQueue.prototype.deleteHead = function() {    if(this.stackB.length){        return this.stackB.pop();    }    else{        while(this.stackA.length){            this.stackB.push(this.stackA.pop());        }        if(!this.stackB.length){            return -1;        }        else{            return this.stackB.pop();        }    }};/** * Your CQueue object will be instantiated and called as such: * var obj = new CQueue() * obj.appendTail(value) * var param_2 = obj.deleteHead() */

思路

【栈】用两个栈实现队列

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	424 ms	49.4 MB	JavaScript	2021/05/12 10:58	两个栈实现队列🚩

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

题目描述

剑指 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

解法1：递归

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

超出时间限制

解法2：动态规划-数组

/** * @param {number} n * @return {number} */var fib = function(n) {    let arr = [];    arr[0] = 0;    arr[1] = 1;    if(n>=2){        for(let i=2; i<=n; i++){            arr[i] = (arr[i-1] + arr[i-2]) % 1000000007;        }    }    return arr[n];};

解法3：动态规划

/** * @param {number} n * @return {number} */var fib = function(n) {    let a = 0;    let b = 1;    let sum = 0;    for(let i=0; i<n; i++){        sum = (a + b) % 1000000007;        a = b;        b = sum;    }    return a;};

思路

面试题10- I. 斐波那契数列（动态规划，清晰图解）

何为动态规划？

已知问题规模为n的前提A，求解一个未知解B。（我们用An表示“问题规模为n的已知条件”）

此时，如果把问题规模降到0，即已知A0，可以得到A0->B.

如果从A0添加一个元素，得到A1的变化过程。即A0->A1; 进而有A1->A2; A2->A3; …… ; Ai->Ai+1. 这就是严格的归纳推理，也就是我们经常使用的数学归纳法；
对于Ai+1，只需要它的上一个状态Ai即可完成整个推理过程（而不需要更前序的状态）。我们将这一模型称为马尔科夫模型。对应的推理过程叫做“贪心法”。

然而，Ai与Ai+1往往不是互为充要条件，随着i的增加，有价值的前提信息越来越少，我们无法仅仅通过上一个状态得到下一个状态，因此可以采用如下方案：

{A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,…,Ai}->Ai+1. 这种方式就是第二数学归纳法。
对于Ai+1需要前面的所有前序状态才能完成推理过程。我们将这一模型称为高阶马尔科夫模型。对应的推理过程叫做“动态规划法”。

参考资料：六大算法之三：动态规划

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	92 ms	37.6 MB	JavaScript	2021/05/12 14:44	动态规划🚩
通过	100 ms	37.8 MB	JavaScript	2021/05/12 13:51	动态规划：数组🚩
超出时间限制	N/A	N/A	JavaScript	2021/05/12 11:04	递归

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

题目描述

剑指 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

解法：动态规划

思路

面试题10- II. 青蛙跳台阶问题（动态规划，清晰图解）

此类求多少种可能性的题目一般都有递推性质，即 f(n)和f(n−1)…f(1)之间是有联系的。

设跳上n级台阶有f(n)种跳法。在所有跳法中，青蛙的最后一步只有两种情况：跳上1级或2级台阶。

当为1级台阶：剩n-1个台阶，此情况共有f(n-1)种跳法；
当为2级台阶：剩n-2个台阶，此情况共有f(n-2)种跳法。

f(n)为以上两种情况之和，即f(n) = f(n-1) + f(n-2)，以上递推性质为斐波那契数列。

本题可转化为求斐波那契数列第n项的值，与面试题10- I. 斐波那契数列等价，唯一的不同在于起始数字不同。
青蛙跳台阶问题：f(0)=1, f(1)=1, f(2)=2；
斐波那契数列问题：f(0)=0, f(1)=1, f(2)=1。

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    let a = 1;
    let b = 1;
    let sum;
    for(let i=0; i<n; i++){
        sum = (a + b) % 1000000007;
        a = b;
        b = sum;
    }
    return a;
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	76 ms	37.6 MB	JavaScript	2021/05/12 14:59	动态规划🚩

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

题目描述

剑指 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

解法1：从后往前找最小值

//从后往前找最小值/** * @param {number[]} numbers * @return {number} */var minArray = function(numbers) {    let min = numbers.pop();    while(numbers.length){        let temp = numbers.pop();        if(temp <= min){            min = temp;        }        else break;    }    return min;};

解法2：二分法

//二分法/** * @param {number[]} numbers * @return {number} */var minArray = function(numbers) {    let left = 0;     let right = numbers.length - 1;        while(left<right){        let middle = Math.floor((left+right)/2);        if(numbers[middle]>numbers[right]) left = middle + 1;        else if(numbers[middle]<numbers[right]) right = middle;        else right--; //题解中有解释：                      //right--只需证明每次执行此操作后，                      //旋转点x仍在[left, right]区间内即可    }    return numbers[left];};

思路

面试题11. 旋转数组的最小数字（二分法，清晰图解）

补充思考：为什么本题二分法不用numbers[middle]和numbers[left]作比较？

二分目的是判断middle在哪个排序数组中，从而缩小区间。

而在numbers[middle] > numbers[left]情况下，无法判断middle在哪个排序数组中。本质上是由于right初始值肯定在右排序数组中； left初始值无法确定在哪个排序数组中。

举例如下：

对于以下两示例，当left = 0, right = 4, middle = 2时，有numbers[middle] > numbers[left]，而结果不同。
[1, 2, 3, 4 ,5] 旋转点 x = 0：middle在右排序数组（此示例只有右排序数组）；
[3, 4, 5, 1 ,2] 旋转点 x = 3：middle在左排序数组。

剑指 Offer 12. 矩阵中的路径⭐️⭐️

题目描述

剑指 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 仅由大小写英文字母组成

解法：DFS+剪枝

//DFS+剪枝/** * @param {character[][]} board * @param {string} word * @return {boolean} */var exist = function(board, word) {    for(let i=0; i<board[0].length; i++){        for(let j=0; j<board.length; j++){            //遍历board找到word的第一个字符            if(dfs(board, word, i, j, 0)) return true;        }    }    return false;};//深度优先搜索（DFS)var dfs = function(board, word, x, y, index){    if(x<0 || x>board[0].length || y<0 || y>=board.length || board[y][x]!==word[index]) return false;    else if(index === word.length-1) return true; //说明遍历结束    else{        let letter = board[y][x];        board[y][x] = '-'; //上锁        let res = dfs(board, word, x-1, y, index+1)||dfs(board, word, x+1, y, index+1)||dfs(board, word, x, y-1, index+1)||dfs(board, word, x, y+1, index+1);        board[y][x] = letter; //恢复现场        return res;    }}

思路

面试题12. 矩阵中的路径（ DFS + 剪枝，清晰图解）

本问题是典型的矩阵搜索问题，可使用深度优先搜索（DFS）+ 剪枝解决。

深度优先搜索：可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝：在搜索中，遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为可行性剪枝。

剪枝示例图

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	116 ms	42.1 MB	JavaScript	2021/05/13 13:38	dfs递归+剪枝🚩

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

题目描述

剑指 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

解法：DFS+剪枝

/** * @param {number} m * @param {number} n * @param {number} k * @return {number} */var movingCount = function(m, n, k) {    let memory = [];    for(let i=0; i<m; i++){        memory[i] = [];        for(let j=0; j<n; j++){            memory[i][j] = false;        }    }    let res = 0;    var dfs = function(row, col, m, n, k, memory){        if(row===m || col===n || memory[row][col] || digitsSum(row)+digitsSum(col)>k) return;        else{            memory[row][col] = true;            res++;            dfs(row+1, col, m, n, k, memory);            dfs(row, col+1, m, n, k, memory);        }}    dfs(0, 0, m, n, k, memory);    return res;};var digitsSum = function(n){    return Math.floor(n/10) + n%10;}

思路

Java超100% DFS+剪枝简单代码

剑指 Offer 14- I. 剪绳子

题目描述

剑指 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

解法1：动态规划

//动态规划
/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
    const dp = new Array(n + 1).fill(1); //dp[len]表示绳长为len时的最大乘积
    dp[2] = 1;
    for(let len=3; len<=n; len++){
        for(let cutLen=2; cutLen<len; cutLen++){
            dp[len] = Math.max(dp[len], 
                               Math.max(cutLen*(len-cutLen), cutLen*dp[len-cutLen]));
        }
    }
    return dp[n];
};

思路

剑指 Offer 14- I. 剪绳子，还是动态规划好理解，但是贪心真的快

我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来

用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[len]表示长度为len的绳子剪成m段后的最大乘积，初始化dp[2] = 1
我们先把绳子剪掉第一段（长度为cutLen），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
剪了第一段后，剩下(len - cutLen)长度可以剪也可以不剪。
- 如果不剪的话长度乘积即为cutLen * (len - cutLen)；
- 如果剪的话长度乘积即为cutLen * dp[len - cutLen]。
- 取两者最大值max(cutLen * (len - cutLen), cutLen * dp[len - cutLen])
判断第一段长度cutLen的取值范围为[2, len)
通过不同的cutLen，求出了很多的dp[len]，取其中的最大值，因此最终dp[len]的转移方程为dp[len] = max(dp[len], max(cutLen * (len - cutLen), cutLen * dp[len - cutLen]))
最后返回dp[n]即可

解法2：贪心算法

//贪心算法
/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
    let res = 1;
    //当n≤3时，按照规则应不切分，但由于题目要求必须剪成m>1段，因此必须剪出一段长度为1的绳子，即返回n-1。
    if(n<=3) res *= n-1;
    else{
        res = Math.pow(3, Math.floor(n/3));
        n %= 3;
        
        // 余数=0时，直接返回res
        // 余数=1时，要将一个1+3转换为2+2，因此返回 3^{a-1} * 4
        // 余数=2时，返回 3^a * 2
        if(n==2) res *= n;
        else if(n==1) res = res / 3 * 4;
    }
    return res;
};

思路

面试题14- I. 剪绳子（数学推导 / 贪心思想，清晰图解）

上文证明了两个重要结论：① 当所有绳段长度相等时，乘积最大。 ② 最优的绳段长度为3。

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	92 ms	37.8 MB	JavaScript	2021/05/13 18:25	贪心算法🚩
通过	88 ms	37.7 MB	JavaScript	2021/05/13 16:13	动态规划🚩

剑指 Offer 14- II. 剪绳子 II⭐️⭐️

题目描述

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 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。

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

示例 1：

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

示例 2:

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

提示：

2 <= n <= 1000

解法：BigInt + 动态规划

//BigInt + 动态规划/** * @param {number} n * @return {number} */var cuttingRope = function(n) {    let dp = new Array(n).fill(BigInt(1));    for (let i = 0; i < n; i++) {        for (let j = i - 1; j >= 0; j--) {            dp[i] = max(dp[i], dp[j] * BigInt((i - j)), BigInt((j + 1) * (i - j)));        }    }    return dp[n - 1] % (1000000007n);};//因为Math.max不能求BigInt类型的最值，所以我们自己写一个max函数判断最值const max = (...args) => args.reduce((prev, curr) => prev > curr ? prev : curr)

补充资料：BigInt - JavaScript | MDN

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	824 ms	43.9 MB	JavaScript	2021/05/15 10:29	BigInt+动态规划🚩

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

题目描述

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

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

提示：

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

解法1：位运算-逐位判断

//位运算-逐位判断/** * @param {number} n - a positive integer * @return {number} */var hammingWeight = function(n) {    let res = 0;    while(n != 0){        if(n & 1 == 1) res++;        n >>>= 1;    }    return res;};

补充材料：JS移位运算符(<<、>>和>>>)

解法2：位运算-巧用n&(n-1)

//位运算-巧用n&(n-1)/** * @param {number} n - a positive integer * @return {number} */var hammingWeight = function(n) {    let res = 0;    while(n != 0){        n &= (n-1);        res++;    }    return res;};

思路

n&(n-1)

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	120 ms	39.1 MB	JavaScript	2021/05/15 11:24	位运算-巧用n&(n-1)🚩
通过	120 ms	39.3 MB	JavaScript	2021/05/15 11:12	位运算-逐位判断🚩

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

题目描述

剑指 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) {    let res = 1.0;    if(n<0){        n = -n;        x = 1/x;    }    while(n!=0){        if(n & 1 == 1) res *= x;        x *= x;        n >>>= 1;    }    return res;};

思路

简单理解快速幂

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	104 ms	38.1 MB	JavaScript	2021/05/15 11:57	快速幂-迭代🚩

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

题目描述

剑指 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.

解法：单指针

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

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	100 ms	39.3 MB	JavaScript	2021/06/03 17:02	单指针

剑指 Offer 24. 反转链表⭐️

题目描述

剑指 Offer 24. 反转链表

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

示例：

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

限制：

0 <= 节点个数 <= 5000

解法1：三指针迭代

/** * 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 pre = null;    let cur = head;    let next;    while(cur){        next = cur.next;        cur.next = pre; //反转Node        pre = cur;        cur = next;    }    return pre;};

解法2：递归

/**
 * 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 || head.next == null) return head;
    let res = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return res;
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	96 ms	39.8 MB	JavaScript	2021/06/27 00:44	三指针迭代🚩
通过	92 ms	40 MB	JavaScript	2021/06/09 18:43	递归🚩

剑指 Offer 26. 树的子结构⭐️⭐️

题目描述

剑指 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 recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);};let recur = function(M, N){    if(N == null) return true;    else if(M == null || M.val != N.val) return false;    return recur(M.left, N.left) && recur(M.right, N.right);}

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	164 ms	57.7 MB	JavaScript	2021/06/23 23:14	前序遍历+递归🚩

剑指 Offer 27. 二叉树的镜像⭐️

题目描述

剑指 Offer 27. 二叉树的镜像

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

例如

输入：

4
/
2 7
/ \ /
1 3 6 9

镜像输出：

4
/
7 2
/ \ /
9 6 3 1

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

限制：

0 <= 节点个数 <= 1000

解法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 null;    let temp = mirrorTree(root.left);    root.left = mirrorTree(root.right);    root.right = temp;    return root;};

解法2：辅助栈（队列）

/** * 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 null;    let stack = [root];    while(stack.length != 0){        let node = stack.pop();        if(node.left) stack.push(node.left);        if(node.right) stack.push(node.right);        let temp = node.left;        node.left = node.right;        node.right = temp;    }    return root;};

**注意：**while的循环条件，因为

if([]) console.log("It's true"); //It's true
if([] != null) console.log("It's true"); //It's true
if([] != []) console.log("It's true"); //It's true  奇奇怪怪！

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	88 ms	39 MB	JavaScript	2021/06/24 00:24	辅助栈（队列）🚩
通过	76 ms	38.9 MB	JavaScript	2021/06/23 23:22	递归🚩

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

题目描述

剑指 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) return [];    let res = [];    let l = 0; //left    let r = matrix[0].length - 1; //right    let t = 0; //top    let b = matrix.length - 1; //bottom    while(true){        for(let i=l; i<=r; i++) res.push(matrix[t][i]);        if(++t > b) break;        for(let i=t; i<=b; i++) res.push(matrix[i][r]);        if(--r < l) break;        for(let i=r; i>=l; i--) res.push(matrix[b][i]);        if(--b < t) break;        for(let i=b; i>=t; i--) res.push(matrix[i][l]);        if(++l > r) break;    }    return res;};

提交记录

交结果	执行用时	内存消耗	语言	提交时间	备注
通过	108 ms	41.4 MB	JavaScript	2021/06/25 00:27	设定边界🚩

剑指 Offer 28. 对称的二叉树⭐️

题目描述

剑指 Offer 28. 对称的二叉树

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

例如，二叉树 [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 recur(root.left, root.right);};let recur = function(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);}

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	100 ms	39.9 MB	JavaScript	2021/06/25 00:59	递归🚩

剑指 Offer 30. 包含min函数的栈⭐️

题目描述

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.

解法：辅助栈

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.x_stack = [];
    this.min_stack = [Infinity];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.x_stack.push(x);
    this.min_stack.push(Math.min(x, this.min_stack[this.min_stack.length-1]));
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.x_stack.pop();
    this.min_stack.pop();
};

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

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

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

拓展知识：

new操作符会改变函数this的指向，如：

function Fn(){
    this.num = 1; //在经过 a = new Fn()后，这里会变为 a.num = 1
}
var a = new Fn();
console.log(a.num); //1

为什么this会指向a？首先new关键字会创建一个空的对象，然后会自动调用一个apply函数，将this指向这个空对象，这样的话函数内部的this就会被这个空的对象替代。

更多请看这里：彻底理解js中this的指向,不必硬背。 - 追梦子 - 博客园

剑指 Offer 39. 数组中出现次数超过一半的数字⭐️

题目描述

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

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

解法：哈希表

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let map = new Map();
    for(let n of nums){
        if(!map.has(n)) map.set(n, 1);
        else {
            map.set(n, map.get(n)+1);
        }
        if(map.get(n) == Math.ceil(nums.length/2)) return n;
    }
    return 0;
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	76 ms	41.1 MB	JavaScript	2021/07/14 23:59	哈希表

剑指 Offer 40. 最小的k个数⭐️

题目描述

剑指 Offer 40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

解法：排序

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var getLeastNumbers = function(arr, k) {
    return arr.sort((a, b) => a-b).splice(0, k);
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	132 ms	42.3 MB	JavaScript	2021/07/06 00:06	排序

剑指 Offer 50. 第一个只出现一次的字符⭐️

题目描述

剑指 Offer 50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例：

s = “abaccdeff”
返回 “b”

s = “”
返回 " "

限制：

0 <= s 的长度 <= 50000

解法：哈希表

/**
 * @param {string} s
 * @return {character}
 */
var firstUniqChar = function(s) {
    let map = new Map();
    for(let char of s){
        if(map.has(char)) map.set(char, true);
        else map.set(char, false);
    }
    for(let item of map){
        if(item[1] === false) return item[0];
    }
    return " ";
};

提交记录

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	124 ms	41.3 MB	JavaScript	2021/07/06 00:38	哈希表

算法题

1. 两数之和⭐️

题目描述

解法1：暴力

解法2：哈希表

2. 两数相加⭐️⭐️

题目描述

解法：链表

7. 整数反转⭐️

题目描述

解法：数组

提交记录

9. 回文数⭐️

题目描述

解法：双指针

提交记录

11. 盛最多水的容器⭐️⭐️

题目描述

解法：双指针

提交记录

42. 接雨水⭐️⭐️⭐️

题目描述

相关问题

解法1： 双指针

解法2：动态编程

提交记录

226. 翻转二叉树⭐️

题目描述

解法：递归

144. 二叉树的前序遍历⭐️

题目描述

解法：递归

提交记录

剑指OFFER

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

题目描述

解法1：暴力

解法2：数组占位

解法3：哈希表

提交记录

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

题目描述

解法：坐标法

提交记录

剑指 Offer 05. 替换空格⭐️

题目描述

解法1：调用函数

解法2：原地修改

提交记录

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

题目描述

解法1：反转数组

解法2：模拟栈

解法3：unshift()

提交记录

剑指 Offer 07. 重建二叉树⭐️⭐️

题目描述

解法：分治思想（递归）

提交记录

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

题目描述

解法：两个栈实现队列

提交记录

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

题目描述

解法1：递归

解法2：动态规划-数组

解法3：动态规划

何为动态规划？

提交记录

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

题目描述

解法：动态规划

提交记录

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

题目描述

解法1：从后往前找最小值

解法2：二分法

剑指 Offer 12. 矩阵中的路径⭐️⭐️

题目描述

解法1：双指针