[面试题 02.03. 删除中间节点](#面试题 02.03. 删除中间节点)
[面试题03. 数组中重复的数字](#面试题03. 数组中重复的数字)
[剑指 Offer 04. 二维数组中的查找](#剑指 Offer 04. 二维数组中的查找)
[面试题05. 替换空格](#面试题05. 替换空格)
[面试题06. 从尾到头打印链表](#面试题06. 从尾到头打印链表)
[剑指Offer07. 重建二叉树](#剑指Offer07. 重建二叉树)
[面试题 08.03. 魔术索](#面试题 08.03. 魔术索)
[面试题 08.06. 汉诺塔问题](#面试题 08.06. 汉诺塔问题)
[面试题10- I. 斐波那契数列](#面试题10- I. 斐波那契数列)
[面试题10- II. 青蛙跳台阶问题](#面试题10- II. 青蛙跳台阶问题)
[剑指 Offer 11. 旋转数组的最小数字](#剑指 Offer 11. 旋转数组的最小数字)
[剑指 Offer 14- I. 剪绳子](#剑指 Offer 14- I. 剪绳子)
[剑指 Offer 14- II. 剪绳子 II](#剑指 Offer 14- II. 剪绳子 II)
[面试题 16.11. 跳水板](#面试题 16.11. 跳水板)
[剑指 Offer 16. 数值的整数次方](#剑指 Offer 16. 数值的整数次方)
[面试题17. 打印从1到最大的n位数](#面试题17. 打印从1到最大的n位数)
[剑指 Offer 18. 删除链表的节点](#剑指 Offer 18. 删除链表的节点)
[剑指 Offer 21. 调整数组顺序使奇数位于偶数前面](#剑指 Offer 21. 调整数组顺序使奇数位于偶数前面)
[剑指 Offer 22.链表中倒数第k个节点](#剑指Offer 22.链表中倒数第k个节点)
[剑指 Offer 24. 反转链表](#剑指 Offer 24. 反转链表)
[剑指 Offer 25. 合并两个排序的链表](#剑指 Offer 25. 合并两个排序的链表)
[剑指 Offer 27. 二叉树的镜像](#剑指 Offer 27. 二叉树的镜像)
[剑指 Offer 28. 对称的二叉树](#剑指 Offer 28. 对称的二叉树)
[面试题29. 顺时针打印矩阵](#面试题29. 顺时针打印矩阵)
[剑指Offer 30.包含min函数的栈](#剑指Offer 30.包含min函数的栈)
[剑指 Offer 32 - I. 从上到下打印二叉树](#剑指 Offer 32 - I. 从上到下打印二叉树)
[剑指 Offer 32 - III. 从上到下打印二叉树 III](#剑指 Offer 32 - III. 从上到下打印二叉树 III)
[剑指 Offer 34. 二叉树中和为某一值的路径](#剑指 Offer 34. 二叉树中和为某一值的路径)
[剑指 Offer 39. 数组中出现次数超过一半的数字](#剑指 Offer 39. 数组中出现次数超过一半的数字)
[剑指 Offer 40. 最小的k个数](#剑指 Offer 40. 最小的k个数)
[剑指 Offer 42. 连续子数组的最大和](#剑指 Offer 42. 连续子数组的最大和)
[面试题46. 把数字翻译成字符串](#面试题46. 把数字翻译成字符串)
[剑指 Offer 50. 第一个只出现一次的字符](#剑指 Offer 50. 第一个只出现一次的字符)
[剑指 Offer 51. 数组中的逆序对](#剑指 Offer 51. 数组中的逆序对)
[剑指Offer 52. 两个链表的第一个公共节点](#剑指Offer 52. 两个链表的第一个公共节点)
[剑指 Offer 53 - I. 在排序数组中查找数字 I](#剑指 Offer 53 - I. 在排序数组中查找数字 I)
[剑指 Offer 53 - II. 0～n-1中缺失的数字](#剑指 Offer 53 - II. 0～n-1中缺失的数字)
[剑指 Offer 54. 二叉搜索树的第k大节点](#剑指 Offer 54. 二叉搜索树的第k大节点)
[剑指 Offer 55 - I. 二叉树的深度](#剑指 Offer 55 - I. 二叉树的深度)
[剑指 Offer 55 - II. 平衡二叉树](#剑指 Offer 55 - II. 平衡二叉树)
[剑指 Offer 56 - I. 数组中数字出现的次数](#剑指 Offer 56 - I. 数组中数字出现的次数)
[剑指 Offer 56 - II. 数组中数字出现的次数 II](#剑指 Offer 56 - II. 数组中数字出现的次数 II)
[剑指 Offer 57. 和为s的两个数字](#剑指 Offer 57. 和为s的两个数字)
[剑指 Offer 58 - I. 翻转单词顺序](#剑指 Offer 58 - I. 翻转单词顺序)
[剑指Offer 58 - II.左旋转字符串](#剑指Offer 58 - II.左旋转字符串)
[剑指 Offer 59 - I. 滑动窗口的最大值](#剑指 Offer 59 - I. 滑动窗口的最大值)
[剑指 Offer 60. n个骰子的点数](#剑指 Offer 60. n个骰子的点数)
[剑指 Offer 61. 扑克牌中的顺子](#剑指 Offer 61. 扑克牌中的顺子)
[剑指 Offer 62. 圆圈中最后剩下的数字](#剑指 Offer 62. 圆圈中最后剩下的数字)
[剑指 Offer 63. 股票的最大利润](#剑指 Offer 63. 股票的最大利润)
[面试题64. 求1+2+…+n](#面试题64. 求1+2+…+n)
[剑指 Offer 65. 不用加减乘除做加法](#剑指 Offer 65. 不用加减乘除做加法)
[剑指 Offer 66. 构建乘积数组](#剑指 Offer 66. 构建乘积数组)
[剑指 Offer 67. 把字符串转换成整数](#剑指 Offer 67. 把字符串转换成整数)
[剑指 Offer 68 - I. 二叉搜索树的最近公共祖先](#剑指 Offer 68 - I. 二叉搜索树的最近公共祖先)
难度简单
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：
- 链表长度在[0, 20000]范围内。
- 链表元素在[0, 20000]范围内。
利用 map，边遍历边移除 如果节点值没出现过，那么正常两个指针向后走， 如果节点值出现过了，那么 curr 向后走，prev.next 指向 curr，跳过这个节点
var removeDuplicateNodes = function(head) {
let map = {},
newHead = new ListNode(null),
prev = newHead,
curr = head;
newHead.next = head;
while(curr) {
let currVal = curr.val;
if(map[currVal] === undefined) {
map[currVal] = true;
prev = curr;
curr = curr.next;
}else {
curr = curr.next;
prev.next = curr;
}
}
return newHead.next;
};固定p指针，右侧q指针扫描，然后移动p，指针q再次扫描
var removeDuplicateNodes = function(head) {
let p = head;
while (p) {
let q = p;
while (q.next) {
if (q.next.val == p.val) {
q.next = q.next.next;
} else {
q = q.next;
}
}
p = p.next;
}
return head;
};难度简单
实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。
示例：
输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f
解题思路：
1->2->3->4->5
1.当我们想要删除节点3,因为单向链表，我们只知道3，我们这时候是找不到2的。但是我们可以获得4这个节点，也可以获得指向5的指针。也就是说向后是随便找的，都能找到。
那我们现在可以做的是，直接把第4个节点的值赋给第三个，让第三个节点冒充第四个节点。
2.然后，因为我们可以获得指向5的指针，比如说指针i吧，我们把这个i赋给第三个节点的next不就完事了吗？
3.然后我们把第四个节点的next设置成null，等下次js垃圾回收，他没有被引用，则会默认被回收
但是为什么说结尾不行呢？
比如我们需要删除第五个节点的时候
我们只能获取到他的next指针指向null,我们再回看我们的代码， node.next.val，node.next.next，由于null不是object类型，不具备属性，所以会被报错。所以这个代码只能删除中间节点。
- 把当前节点的下一个节点的值拿过来覆盖掉要删除的值，然后把当前节点的
next指向下一个节点的next即可。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} node
* @return {void} Do not return anything, modify node in-place instead.
*/
var deleteNode = function (node) {
node.val = node.next.val
node.next = node.next.next
};难度简单
找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
由于只需要找出数组中任意一个重复的数字，因此遍历数组，遇到重复的数字即返回。为了判断一个数字是否重复遇到，使用集合存储已经遇到的数字，如果遇到的一个数字已经在集合中，则当前的数字是重复数字。
var findRepeatNumber = function(nums) {
const map = {};
for (const num of nums) {
if (!map[num]) {
map[num] = true;
} else {
return num;
}
}
};使用set,因为set自动忽略重复元素，遍历数组中元素，若长度未增加，则输出当前元素
var findRepeatNumber = function(nums) {
let s=new Set();
for(var i in nums){
var curLenth=s.size;
s.add(nums[i]);
if(s.size==curLenth)
return nums[i];
}
};难度中等
在一个 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。
- 从右上角 往左下找
- 横纵都是递增的, 所以从矩阵的 右上角 往 左下查找
- 当前比目标大, 如果目标存在, 只能在左下边, 此时范围缩小一列
- 当前比目标小, 目标存在的话, 只能在下边, 当前行不存在目标值, 此时范围缩小一行
var findNumberIn2DArray = function(matrix, target) {
let rows = matrix.length
if(!rows) return false
let columns = matrix[0].length
let row = 0, column = columns - 1
while (row < rows && column>= 0) { // 从右上角 往左下找
let t = matrix[row][column]
if (t === target) {
return true
} else if (t > target) { // 大于目标, 说明在左/下边
column--
} else { // 小于目标, 说明在下边
row++
}
}
return false
};时间复杂度：O(n+m)
-
flat()方法创建一个新数组，其中所有子数组元素都以递归方式连接到该数组中，直到达到指定的深度。
-
includes()方法确定数组在其条目中是否包含某个值，是返回值true还是false适当值。
var findNumberIn2DArray = function(matrix, target) {
return matrix.flat(Infinity).includes(target);
};执行用时：116 ms, 在所有 JavaScript 提交中击败了5.53%的用户
内存消耗：43.3 MB, 在所有 JavaScript 提交中击败了5.80%的用户
难度简单
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
var replaceSpace = function(s) {
return s.replace(/ /g, '%20');
};split() 方法用于把一个字符串分割成字符串数组。 join() 方法用于把数组中的所有元素放入一个字符串。
var replaceSpace = function(s) {
return s.split(" ").join("%20");
};var replaceSpace = function(s) {
let res = "";
for (const el of s) {
if (el === " ") {
res += "%20";
} else {
res += el;
}
}
return res;
};难度简单
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
var reversePrint = function (head) {
if (head === null) return []
const res = []
while (head) {
res.push(head.val)
head = head.next
}
return res.reverse()
}执行用时 :84 ms, 在所有 JavaScript 提交中击败了42.73%的用户
内存消耗 :36.6 MB, 在所有 JavaScript 提交中击败了100.00%的用户
function reverseLink(head) {
if(!head) return [];
let arr = [];
do{
arr.push(head.val);
}while(head = head.next);
arr.reverse();
return arr;
}执行用时 :68 ms, 在所有 JavaScript 提交中击败了95.75%的用户
内存消耗 :36.3 MB, 在所有 JavaScript 提交中击败了100.00%的用户
function reverseLink(head) {
if(!head) return []
let arr = reversePrint(head.next)
arr.push(head.val)
return arr
}执行用时 :80 ms, 在所有 JavaScript 提交中击败了60.56%的用户
内存消耗 :37.3 MB, 在所有 JavaScript 提交中击败了100.00%的用户
难度中等
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
注意：本题与主站 105 题重复
根据前序遍历/后序遍历+中序遍历可以重建一个二叉树，这道题考察的就是前序遍历+中序遍历重建二叉树。 对于
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]前序遍历中的3即为根节点的值，由于输入的前序遍历和后序遍历的结果中都不含重复的数字，那么在中序遍历中，3 前面的节点都是左子树上的节点，3后面的节点都是右子树上的节点，这一步可以获得根节点和左右两个子树，再递归地对左右子树进行 重建，即可构建出一个新的二叉树。
/**
* 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
let root = preorder[0]; // 前序遍历的第一个元素为根节点
let node = new TreeNode(root); // 确定根节点
let i = inorder.indexOf(root); // 获取根节点在中序遍历中的位置(用于分割左右子树)
// preorder.slice(1,index+1)是左子树的前序遍历
// inorder.slice(0,index) 是左子树的中序遍历
// 这一步递归的对左子树进行重建
node.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));
node.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));
return node
};难度简单
魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。
示例1:
输入：nums = [0, 2, 3, 4, 5]
输出：0
说明: 0下标的元素为0
示例2:
输入：nums = [1, 1, 1]
输出：1
const findMagicIndex = (nums) => {
for (let i = 0; i < nums.length; i++) {
if (nums[i] == i) return i;
}
return -1;
};难度简单
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1:
输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]
示例2:
输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]
提示:
- A中盘子的数目不大于14个。
将n个圆盘从A挪动到C步骤
-
将n-1个圆盘从A挪动到B
-
将第n个圆盘从A挪动到C
-
将n-1个圆盘从B挪动到C
将n-1个圆盘从A挪动到B 1.1. 将n-2个圆盘从A挪动到C 1.2. 将第n-1个圆盘从A挪动到B 1.3. 将n-2个圆盘从C挪动到B
将第n个圆盘从A挪动到C
将n-1个圆盘从B挪动到C 3.1. 将n-2个圆盘从B挪动到A 3.2. 将第n-1个圆盘从B挪动到C 3.3. 将n-2个圆盘从A挪动到C
var hanota = function(A, B, C) {
// n个盘子从A到C
function dfs(A, B, C, n){
if(n == 0) return;
dfs(A, C, B, n - 1) // n - 1个盘子从A到B
C.push(A.pop()); // n从A到C
dfs(B, A, C, n - 1) // n - 1个盘子从B到C
}
return dfs(A, B, C, A.length);
};难度简单
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 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
fib会重复计算之前的项，计算结果是一次性的，浪费时间和空间
超出时间限制
var fib = function(n) {
if(n<=1) return n;
return (fib(n-1) + fib(n-2)) % 1000000007;
};var fib = function(n) {
if(n === 0) return 0
if(n === 1) return 1
let a = 0
let b = 1
for(let i = 1;i < n;i++){
let t = a
a = b
b = (t + b) % 1000000007
}
return b
};执行用时 :72 ms, 在所有 JavaScript 提交中击败了31.28%的用户
内存消耗 :32.2 MB, 在所有 JavaScript 提交中击败了100.00%的用户
难度简单
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
提示：
0 <= n <= 100
注意：本题与主站 70 题相同
- 3个变量 每次递归更新前两个子问题所需步数
- 可知递推公式 f(n) = f(n-2) + f(n-1),n>=1
var numWays = function(n) {
if(n == 0){
return 1;
}
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
//f1第一阶 f2第二阶 f3下一阶
var f1 = 1,f2 = 2, f3 = 0;
while(n > 2) {
f3 = (f1 + f2) % 1000000007;
f1 = f2;
f2 = f3;
n--;
}
return f2;
};执行用时 :60 ms, 在所有 JavaScript 提交中击败了85.61%的用户
内存消耗 :32.7 MB, 在所有 JavaScript 提交中击败了100.00%的用户
var numWays = function(n) {
let arr = [1,1];
for(let i = 2; i <= n; i++) {
arr[i] = (arr[i - 1] + arr[i -2]) %1000000007;
}
return arr[n];
};执行用时 :64 ms, 在所有 JavaScript 提交中击败了70.67%的用户
内存消耗 :32.8 MB, 在所有 JavaScript 提交中击败了100.00%的用户
爬第n阶楼梯的方法数量，等于 2 部分之和
爬上 n-1阶楼梯的方法数量。因为再爬1阶就能到第n阶 爬上 n-2 阶楼梯的方法数量，因为再爬2阶就能到第n阶
var numWays = function(n) {
var dp = new Array(n+1);
dp[0]=1;
dp[1]=1;
for (var i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
dp[i] %= 1000000007;
}
return dp[n]
};执行用时 :64 ms, 在所有 JavaScript 提交中击败了70.67%的用户
内存消耗 :32.6 MB, 在所有 JavaScript 提交中击败了100.00%的用户
难度简单115
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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
var minArray = function(numbers) {
let res=numbers[0];
// 循环一半
for(let i=0; i<numbers.length/2; i++){
res=Math.min(res,numbers[i],numbers[numbers.length-1-i]) // 对比头尾取最小值
}
return res
};难度中等
给你一根长度为 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。
- dp[i] 表示正整数 i 拆分成的整数的最大乘积
- 前面的代码中的正整数 n 变成了这里的正整数 i，用指针 j 去划分 i，分成了 j 和 i - j。
- 遍历所有的 j，i−j 可以选择拆或者不拆，不拆就是 i-ji−j ，拆就是 dp[i - j]，其实就是对 i - j 调用的结果（子问题的解）。
const integerBreak = (n) => {
const dp = new Array(n + 1);
dp[1] = 1;
dp[2] = 1;
for (let i = 3; i <= n; i++) {
dp[i] = 0;
// 对于数字 i，它可以分为两份：j 和 i-j，j 的范围是 1 到 i-j
for (let j = 1; j <= i - j; j++) {
// 对于 i-j 这部分可以拆或不拆，不拆就是 i-j，拆就是 dp[i-j]
dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]);
}
}
return dp[n];
};- 空间复杂度是 O(N)
- 时间复杂度是 O(N^2)
难度中等
给你一根长度为 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。
/**
* @param {number} n
* @return {number}
*/
var cuttingRope = function(n) {
/*
尽可能大的切割，3，从4开始,4
*/
let d = [];
d[1] = 0;
d[2] = 1;
d[3] = 2;
d[4] = 4;
if(n<=4){
return d[n];
}
let MAX_VALUE = 1e9+7;
res = 1
while(n>4){
res = (res % MAX_VALUE) * 3;
n-=3;
}
//还要乘下小于或等于4
res *= n
return res % MAX_VALUE;
};难度简单
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
- 遍历数字的 32 位。如果某一位是 11 ，将计数器加一
var hammingWeight = function(n) {
var bits = 0
var mask = 1
for(var i = 0; i < 32; i++){
if((n & mask) != 0){
bits++
}
mask <<= 1
}
return bits
};时间复杂度：O(1)
空间复杂度：O(1)
- 不断把数字最后一个 11 反转，并把答案加一。当数字变成 00 的时候偶，我们就知道它没有 11 的位了，此时返回答案。
var hammingWeight = function(n) {
var sum = 0
while(n != 0){
sum++
n &= (n - 1)
}
return sum
};时间复杂度：O(1)
空间复杂度：O(1)
难度简单
你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。
示例：
输入：
shorter = 1
longer = 2
k = 3
输出： {3,4,5,6}
提示：
- 0 < shorter <= longer
- 0 <= k <= 100000
k 等于0 时返回 空数组 shorter == longer 相等时 返回一个 值 [shorter*k]
当两类板长度不同时，短板数越多则总长就最短，依次排列即可。
根据数学归纳法，2种长度板子，必须用k块，不同的情况共k+1中，公式为(k - i) * shorter + i * longer
var divingBoard = function(shorter, longer, k) {
if(k == 0) return []
if(shorter == longer) return [shorter*k]
var arr = []
for(let i = 0;i <= k;i++){
arr.push(i * longer + shorter * (k-i))
}
//for(let i = 0,j = k; i < k+1, j > -1;j--, i++){
// arr.push(j * shorter + longer * i)
//}
return arr
};执行用时 :152 ms, 在所有 JavaScript 提交中击败了99.00%的用户
内存消耗 :47.7 MB, 在所有 JavaScript 提交中击败了100.00%的用户
难度中等
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
- x是1或者n是0的时候，直接返回1即可
- n大于0的时候要分为两种情况，一种是偶数，一种是奇数。
- 偶数次幂可以直接二分
- 奇数次幂(n - 1) / 2) * x
- n小于0的时候，需要把它转化为正数方便计算，同时1/myPow(x, -n)。
function myPow(x, n) {
// 几种特殊情况，直接返回结果
if (x === 1 || n === 0) {
return 1;
}
if (x === -1) {
return n % 2 === 0 ? 1 : -1;
}
// n === 1 作为递归的出口，也可以用 n === 0
if (n === 1) {
return x;
}
// 负数指数
if (n < 0) {
return 1 / myPow(x, -n);
}
// 偶数次幂可以直接二分
if (n % 2 === 0) {
return myPow(x * x, n / 2);
} else {
// 奇数次幂
return myPow(x * x, (n - 1) / 2) * x;
}
}难度简单
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
说明：
- 用返回一个整数列表来代替打印
- n 为正整数
先获取最大值，再建立一个循环，将1 - max的每一个值push到res数组中，最后返回
var printNumbers = function(n) {
//const max = 10 ** n - 1;
const max = Math.pow(10, n) - 1;
const res = [];
for (let i = 1; i <= max; ++i) {
res.push(i);
}
return res;
};执行用时 :108 ms, 在所有 JavaScript 提交中击败了98.54%的用户
内存消耗 :45.4 MB, 在所有 JavaScript 提交中击败了100.00%的用户
难度简单
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
**注意：**此题对比原题有改动
示例 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.
- 改变val值的head.next指向
- 不相等则递归子链表对比
- 终止条件：值相等
var deleteNode = function(head, val) {
if(head.val == val){
return head.next
}
head.next = deleteNode(head.next,val);
return head
};难度中等
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。
解题思路用一个光标去扫描字符串，遇到空格，跳过，遇到整数部分，一套处理逻辑，遇到小数点，遇到e/E，遇到小数部分，又一套处理逻辑，遇到末尾的空格，跳过。
const isNumber = (s) => {
let cursor = 0; // 扫描字符的光标
let isValid; // 标识变量，当前扫描时是否有效
const scanSignedInteger = (s) => { // 扫描有符号整数的字符
if (s[cursor] === '+' || s[cursor] === '-') { // 遇到+-，指针后移
cursor++;
}
return scanUnsignedInteger(s); // 考察无符号数字部分
};
const scanUnsignedInteger = (s) => { // 扫描无符号整数部分的字符
const temp = cursor; // 临时保存当前指针位置
while (s[cursor] >= '0' && s[cursor] <= '9') { // 遇到0-9数字就指针后移
cursor++; // 函数结束时，指针已扫完连续数字部分
}
return s[temp] >= '0' && s[temp] <= '9'; // 判断当前指针是否指向数字0-9
};
while (s[cursor] === ' ') { // 跳过开头的空格字符
cursor++;
}
isValid = scanSignedInteger(s); // 先扫描整数部分
if (s[cursor] === '.') { // 此时扫完整数部分，看看有没有遇到小数点
cursor++; // 指针跳过小数点
if (scanUnsignedInteger(s)) { // 扫描小数部分的整数
isValid = true; // 如果返回true，说明暂时是有效的数字
}
// 如果返回false，还不能说明是错的，因为有 '3.' 这种case
}
if (s[cursor] === 'e' || s[cursor] === 'E') { // 看看有没有遇到e/E
cursor++; // 指针跳过E/e
if (isValid) { // E/e前面一定要是有效整数
isValid = scanSignedInteger(s); // E/e后面可以是有符号整数 比如 1e-9
}
}
while (s[cursor] === ' ') { // 跳过结尾的空格字符
cursor++;
}
if (s[cursor] !== undefined) { // 此时指针该越界了，我们希望它是undefined
return false; // 如果不是，那就false 比如 '3..' '3 8'，一个是.一个是8
}
return isValid;
};难度简单
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
- 指针p表示已经遇到的奇数元素的个数，初始值为0；
- 只有遍历到的nums[i]全为奇数时，p和i保持相同大小，如果遇到偶数元素，那么i直接跳过继续i++,而p则会停留在为偶数元素的位置上，nums[i]和nums[p]互换，这样才能在一次遍历中把奇数元素位置的元素变为偶数。
var exchange = function(nums) {
let p = 0, len = nums.length;
for(let i = 0; i < len; i++){
if(nums[i] % 2 != 0){
let temp = nums[i];
nums[i] = nums[p];
nums[p++] = temp;
}
}
return nums;
};难度简单56
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
- p,q两个指针，让p先走k步，然后p,q一起走，直到p为null
var getKthFromEnd = function(head, k) {
let p = head, q = head;
let i = 0;
while (p) {
if (i >= k) {
q = q.next;
}
p = p.next;
i++;
}
return i < k ? null : q;
};难度简单50
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
- 将单链表中的每个节点的后继指针指向它的前驱节点
var reverseList = function(head) {
if (!head || !head.next) return head;
var prev = null,cur = head, temp;
while(cur){
temp = cur.next;//修改前先存储 cur 后继节点
cur.next = prev; // // 反转 cur 的后继指针
prev = cur; //变更prev、cur
cur = temp; // cur通过temp指向下一节点
}
return prev;//cur会循环直到null
};-
时间复杂度：O(n)
-
空间复杂度：O(1)
-
不断递归反转当前节点
head的后继节点next -
最先调用的函数会在递归过程中最后被执行，而最后调用的会最先执行
-
最先返回最后两个节点 然后开始反转操作，依次从后面两两节点开始反转
var reverseList = function(head) {
// 如果只有一个节点 或者 递归到了尾节点，返回当前节点
if(!head || !head.next) return head;
// 存储当前节点的下一个节点
let next = head.next;
let reverseHead = reverseList(next);
// 断开 head
head.next = null;
// 反转，后一个节点连接当前节点 2.next = 1 1.next = null
next.next = head;
return reverseHead;
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
难度简单
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
- 如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。
var mergeTwoLists = function(l1, l2) {
if (l1 === null) {
return l2;
} else if (l2 === null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};- 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。
- 空间复杂度：O(n + m)，其中 n 和 m分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。
思想
- 当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。
算法
- 首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。
在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。
var mergeTwoLists = function(l1, l2) {
const prehead = new ListNode(-1);
let prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 === null ? l2 : l1;
return prehead.next;
};- 时间复杂度：O(n + m) ，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。
- 空间复杂度：O(1) 。我们只需要常数的空间存放若干变量。
作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/ 来源：力扣（LeetCode）
难度简单
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
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
注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/
- 时间复杂度：O(n)
- 空间复杂度：O(n)
- 递归交换当前节点的左右节点，当节点为null时返回
/**
* 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) return null
const left = mirrorTree(root.left)
const right = mirrorTree(root.right)
root.left = right
root.right = left
return root
};难度简单
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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
- 类似于一张白纸对折的原理
var isSymmetric = function(root) {
function isMirror(r1,r2){
//如果都为null 对称
if(!r1 && !r2){
return true
}
//只要其中一个为空，另一个不为，则不对称
if(!r1 || !r2){
return false
}
//判断根节点
//判断r1的左树和r2的右
//判断r2的左树和r1的右
return r1.val == r2.val && isMirror(r1.left,r2.right) && isMirror(r1.right,r2.left)
}
return isMirror(root,root)
};难度简单
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 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
可以模拟打印矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，则顺时针旋转，进入下一个方向。
-
一层层向里处理，按顺时针依次遍历：上层、右层、下层、左层
-
- 不再形成“环”了，剩下一行或一列，循环结束后单独判断
top < bottom && left < right 是 while 循环的条件 无法构成“环”了，就退出循环，分 3 种情况： top === bottom && left < right —— 剩一行 top < bottom && left === right —— 剩一列 top === bottom && left === right —— 剩一项（也是一行/列）
处理剩下的单行或单列
因为是按顺时针推入结果数组的，所以 剩下的一行，从左至右 依次推入结果数组 剩下的一列，从上至下 依次推入结果数组
var spiralOrder = function (matrix) {
if (matrix.length === 0) return []
const res = []
let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1
while (top < bottom && left < right) {
for (let i = left; i < right; i++) res.push(matrix[top][i]) // 上层
for (let i = top; i < bottom; i++) res.push(matrix[i][right]) // 右层
for (let i = right; i > left; i--) res.push(matrix[bottom][i])// 下层
for (let i = bo5；ttom; i > top; i--) res.push(matrix[i][left]) // 左层
right--
top++
bottom--
left++ // 四个边界同时收缩，进入内层
}
if (top === bottom) // 剩下一行，从左到右依次添加
for (let i = left; i <= right; i++) res.push(matrix[top][i])
else if (left === right) // 剩下一列，从上到下依次添加
for (let i = top; i <= bottom; i++) res.push(matrix[i][left])
return res
};难度简单
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
- 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
- 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
- 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
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.getMin = function() {
return this.min_stack[this.min_stack.length - 1];
};-
时间复杂度：O(1）
-
空间复杂度：O(n)
var arr = [], sortArr = [];
var MinStack = function() {
arr = [];
sortArr = [];
};
//将元素 x 推入栈中
MinStack.prototype.push = function(x) {
arr.push(x);
if(!sortArr.length){
sortArr.push(x);
}else{
sortArr.push(x < sortArr[sortArr.length - 1] ? x : sortArr[sortArr.length - 1]);
}
};
//删除栈顶的元素
MinStack.prototype.pop = function() {
arr.pop();
sortArr.pop();
};
//获取栈顶元素
MinStack.prototype.top = function() {
return arr[arr.length - 1];
};
//检索栈中的最小元素
MinStack.prototype.getMin = function() {
return sortArr[sortArr.length - 1];
};var arr = [], sortArr = [];
var MinStack = function() {
arr = [];
sortArr = [];
};
//将元素 x 推入栈中
MinStack.prototype.push = function(x) {
arr.push(x);
if(!sortArr.length || x <= sortArr[sortArr.length - 1]){
sortArr.push(x);
}
};
//删除栈顶的元素
MinStack.prototype.pop = function() {
if(arr.pop() == sortArr[sortArr.length - 1]){
sortArr.pop();
}
};
//获取栈顶元素
MinStack.prototype.top = function() {
return arr[arr.length - 1];
};
//检索栈中的最小元素
MinStack.prototype.getMin = function() {
return sortArr[sortArr.length - 1];
};难度中等
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
- 利用队列的数据结构，将根节点先保存在队列中，左子树或右子树不为空时，队列中加入该节点
- 另外使用一个数组res，保存队列先进先出的值
- 时间复杂度为O(N),空间复杂度为O(N)
var levelOrder = function(root) {
if(!root) return [];
const queue=[root];
let res=[];
while(queue.length){
let t=queue.shift();
res.push(t.val);
if(t.left) queue.push(t.left);
if(t.right) queue.push(t.right);
}
return res;
};难度简单
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
var levelOrder = function(root) {
let res = []
dfs(root, res, 0)
return res
};
function dfs(root, arr, i) {
if(!root) return
if(!arr[i]) arr[i] = []
arr[i].push(root.val)
dfs(root.left, arr, i + 1)
dfs(root.right, arr, i + 1)
}难度中等
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
- level: 当前层级;
- ltor: 当前是否from left to right
var levelOrder = function(root) {
const res = [];
function dfs(root, level, ltor) {
if (!root) return;
res[level] = res[level] || [];
if (ltor) {
res[level].push(root.val);
} else {
res[level].unshift(root.val);
}
dfs(root.left, level + 1, !ltor);
dfs(root.right, level + 1, !ltor);
}
dfs(root, 0, true);
return res;
};难度中等
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
提示：
节点总数 <= 10000
注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number[][]}
*/
var pathSum = function(root, sum) {
var path=[], //保存路径
res=[]; //保存路经的数组
/*辅助函数---增加参数列表，用来实现对res,path的引用值的传递，因为res，path为数组，是对象范畴
本题目中需要根据条件，回溯更新路径path直到符合条件.
*/
var resuc = function (root, sum, res, path) {
if (root) {
//单个节点要做的事
path.push(root.val);
if (!root.left && !root.right && sum-root.val == 0) {
res.push([...path]);
}
//左右子节点递归调用
resuc(root.left, sum - root.val,res, path);
resuc(root.right, sum - root.val, res, path);
path.pop(); //回溯先序遍历一条路径结束，不符合条件时，将最后一个数弹出如5,4,4,7-->5,4,4,-2。
}
return res;
}
return resuc(root, sum, res, path);
};难度中等
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
/**
* @param {string} s
* @return {string[]}
*/
var permutation = function (s) {
var res = new Set();
var path = [];
var visited = [];
dfsHelper([...s], path, res,visited);
return Array.from(res);
};
function dfsHelper(arr, path, res,visited) {
if (arr.length === path.length) { //说明走到底(叶子节点)
res.add(path.join(''))
return;
}
for (let i = 0; i < arr.length; i++) {
if(visited[i]){
continue;
}
visited[i] = true;
//进入下一层
path.push(arr[i]);
dfsHelper(arr, path, res,visited);
path.pop();
visited[i] = false;
}
}难度简单
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/
如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n/2的元素（下标从 0 开始）一定是众数
var majorityElement = function(nums) {
nums.sort((a, b) => a - b);
return nums[Math.floor(nums.length / 2)];
};- 时间复杂度：O(nlogn)。将数组排序的时间复杂度为O(nlogn)。
- 空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。如果自己编写堆排序，则只需要使用 O(1)的额外空间。
投票算法的原理是通过不断消除不同元素直到没有不同元素，剩下的元素就是我们要找的元素。
-
我们维护一个候选众数 majority和它出现的次数 count。初始时 majority可以为nums[0]，count 为 1；
-
我们遍历数组 nums 中的所有元素，对于每个元素 i，在判断 i之前，如果 count 的值为 0，我们先将 i的值赋予 majority，随后我们判断 i：
- 如果 i与 majority相等，那么计数器 count 的值增加 1；
- 如果 i与 majority不等，那么计数器 count 的值减少 1。
在遍历完成后，majority即为整个数组的众数。
var majorityElement = function(nums) {
let count = 1;
let majority = nums[0];
for(let i = 1; i < nums.length; i++) {
if (count === 0) {
majority = nums[i];
}
if (nums[i] === majority) {
count ++;
} else {
count --;
}
}
return majority;
};- 时间复杂度：O(N)，其中N为数组长度
- 空间复杂度：O(1)
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
输入: [1,2,3,2,4,2,5,2,3]
输出: 0根据题目意思，显然可以先遍历一遍数组，在hash中存每个元素出现的次数，然后再遍历一次数组，找出众数。
function MoreThanHalfNum_Solution(numbers)
{
let hash = {};
numbers.forEach(item => {
if(hash[item]){
hash[item]++;
}else{
hash[item] = 1;
}
})
for(const key in hash){
if(hash[key] > numbers.length / 2){
return key;
}
}
return 0;
}时间复杂度：O(n) 空间复杂度：O(n)
假如数组中存在众数，那么众数一定大于数组的长度的一半。 思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。
具体做法：
-
初始化：候选人majority= numbers[0]， 候选人的投票次数count= 0
-
遍历数组，如果count=0， 表示没有候选人，则选取当前数为候选人，随后我们判断 i：
- 如果 i与 majority相等，那么计数器 count 的值增加 1；
- 如果 i与 majority不等，那么计数器 count 的值减少 1。
-
直到数组遍历完毕，最后检查majority是否为众数
function MoreThanHalfNum_Solution(numbers)
{
let count = 1;
let majority = numbers[0];
for(let i = 1; i < numbers.length; i++){
if(count === 0){
majority = numbers[i];
}
if(numbers[i] === majority){
count ++;
}else{
count --;
}
}
count = 0;
for(let i = 0; i < numbers.length; i++){
if(numbers[i] === majority){
count++;
}
}
return count > numbers.length / 2 ? majority : 0;
};时间复杂度：O(n) 空间复杂度：O(1)
难度简单
输入整数数组 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]
- 对原数组从小到大排序后取出前 k个数即可。
var getLeastNumbers = function(arr, k) {
let vec = Array(k);
arr.sort((a, b) => a - b);
for(let i = 0; i < k; ++i){
vec[i] = arr[i];
}
return vec;
};- 时间复杂度：O(nlogn)，其中 n 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。
- 空间复杂度：O(logn)，排序所需额外的空间复杂度为 (logn)
从数组中取出 k 个元素构造一个大顶堆，然后将其余元素与大顶堆对比，如果小于堆顶则替换堆顶，然后堆化，所有元素遍历完成后，堆中的元素即为前 k 个最小值
具体步骤如下：
- 从数组中取前 k 个数（ 0 到 k-1 位），构造一个大顶堆
- 从 k 位开始遍历数组，每一个数据都和大顶堆的堆顶元素进行比较，如果大于堆顶元素，则不做任何处理，继续遍历下一元素；如果小于堆顶元素，则将这个元素替换掉堆顶元素，然后再堆化成一个大顶堆。
- 遍历完成后，堆中的数据就是前 K 小的数据
let getLeastNumbers = function(arr, k) {
// 从 arr 中取出前 k 个数，构建一个大顶堆
let heap = [,], i = 0
while(i < k) {
heap.push(arr[i++])
}
buildHeap(heap, k)
// 从 k 位开始遍历数组
for(let i = k; i < arr.length; i++) {
if(heap[1] > arr[i]) {
// 替换并堆化
heap[1] = arr[i]
heapify(heap, k, 1)
}
}
// 删除heap中第一个元素
heap.shift()
return heap
};
// 原地建堆，从后往前，自上而下式建大顶堆
let buildHeap = (arr, k) => {
if(k === 1) return
// 从最后一个非叶子节点开始，自上而下式堆化
for(let i = Math.floor(k/2); i>=1 ; i--) {
heapify(arr, k, i)
}
}
// 堆化
let heapify = (arr, k, i) => {
// 自上而下式堆化
while(true) {
let maxIndex = i
if(2*i <= k && arr[2*i] > arr[i]) {
maxIndex = 2*i
}
if(2*i+1 <= k && arr[2*i+1] > arr[maxIndex]) {
maxIndex = 2*i+1
}
if(maxIndex !== i) {
swap(arr, i, maxIndex)
i = maxIndex
} else {
break
}
}
}
// 交换
let swap = (arr, i , j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}- 时间复杂度：遍历数组需要 O(n) 的时间复杂度，一次堆化需要 O(logk) 时间复杂度，所以利用堆求 Top k 问题的时间复杂度为 O(nlogk)
- 空间复杂度：O(k)
难度简单
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5-100 <= arr[i] <= 100
注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/
- 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
- 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
- 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
- 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
var maxSubArray = function(nums) {
let ans = nums[0];
let sum = 0;
for(const num of nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
};- 时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
- 空间复杂度：O(1)。我们只需要常数空间存放若干变量。
这个分治方法类似于「线段树求解 LCIS 问题」的 pushUp 操作。 也许读者还没有接触过线段树，没有关系，方法二的内容假设你没有任何线段树的基础。当然，如果读者有兴趣的话，推荐看一看线段树区间合并法解决 多次询问 的「区间最长连续上升序列问题」和「区间最大子段和问题」，还是非常有趣的。
我们定义一个操作 get(a, l, r) 表示查询 a 序列 [l, r][l,r] 区间内的最大子段和，那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？对于一个区间 [l, r]，我们取 m = {l + r}/{2}，对区间 [l, m]和 [m + 1, r]分治求解。当递归逐层深入直到区间长度缩小为 11 的时候，递归「开始回升」。这个时候我们考虑如何通过 [l, m]区间的信息和 [m + 1, r]区间的信息合并成区间 [l, r]的信息。最关键的两个问题是：
- 我们要维护区间的哪些信息呢？
- 我们如何合并这些信息呢？
对于一个区间 [l, r]，我们可以维护四个量：
- lSum 表示 [l, r][l,r] 内以 ll 为左端点的最大子段和
- rSum 表示 [l, r][l,r] 内以 rr 为右端点的最大子段和
- mSum 表示 [l, r][l,r] 内的最大子段和
- iSum 表示 [l, r][l,r] 的区间和
以下简称 [l, m][l,m] 为 [l, r][l,r] 的「左子区间」，[m+1,r] 为 [l, r][l,r] 的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到[l,r] 的信息）？对于长度为 11 的区间 [i, i][i,i]，四个量的值都和a i相等。对于长度大于 1的区间：
- 首先最好维护的是 iSum，区间[l,r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
- 对于 [l, r]的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。
- 对于 [l, r]的 rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。
- 当计算好上面的三个量之后，就很好计算 [l, r] 的 mSum 了。我们可以考虑 [l, r]的 mSum 对应的区间是否跨越 mm——它可能不跨越 mm，也就是说 [l, r]的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个；它也可能跨越 mm，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。
这样问题就得到了解决。
力扣（LeetCode）
function Status(l, r, m, i) {
this.lSum = l;
this.rSum = r;
this.mSum = m;
this.iSum = i;
}
const pushUp = (l, r) => {
const iSum = l.iSum + r.iSum;
const lSum = Math.max(l.lSum, l.iSum + r.lSum);
const rSum = Math.max(r.rSum, r.iSum + l.rSum);
const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
return new Status(lSum, rSum, mSum, iSum);
}
const getInfo = (a, l, r) => {
if (l === r) {
return new Status(a[l], a[l], a[l], a[l]);
}
const m = (l + r) >> 1;
const lSub = getInfo(a, l, m);
const rSub = getInfo(a, m + 1, r);
return pushUp(lSub, rSub);
}
var maxSubArray = function(nums) {
return getInfo(nums, 0, nums.length - 1).mSum;
};假设序列 a 的长度为 n。
- 时间复杂度：假设我们把递归的过程看作是一颗二叉树的先序遍历，那么这颗二叉树的深度的渐进上界为O(logn)，这里的总时间相当于遍历这颗二叉树的所有节点，故总时间的渐进上界是O(∑i=1logn2i−1)=O(n)，故渐进时间复杂度为 O(n)。
- 空间复杂度：递归会使用 O(logn) 的栈空间，故渐进空间复杂度为 O(logn)。
难度中等
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
在跳台阶基础上增加跳两级的条件。
当 num 对 100 取余的余数在 [0,26) 中，就可以跳两级，否则只能跳一级
跳台阶，f(n) = f(n-1) + f(n-2)
翻译，若 n % 100 ∈ [0,26)，则 f(n) = f(n // 10) + f(n // 100)；
否则 f(n) = f(n // 10) 。// 表示向下取整。
var translateNum = function(num) {
if(num == 0){
return 1;
}
if(num >= 10 && num < 26){
return 2;
}
let b1 = Math.floor(num / 10), r1 = num % 10,
b2 = Math.floor(num / 100), r2 = num % 100;
if(r2 >= 10 && r2 < 26){
return translateNum(b2) + translateNum(b1);
}
return translateNum(b1);
};执行用时 :72 ms, 在所有 JavaScript 提交中击败了32.11%的用户
内存消耗 :32.3 MB, 在所有 JavaScript 提交中击败了100.00%的用户
var translateNum = function(num) {
if(num <10){
return 1;
}
let dual = num % 100;
let nextOne = Math.floor(num / 10);
let nextTwo = Math.floor(num / 100);
//10-25之间才有 可能双位数
if(dual >= 10 && dual <= 25){
return translateNum(nextOne) + translateNum(nextTwo);
} else {
return translateNum(nextOne)
}
};执行用时 :64 ms, 在所有 JavaScript 提交中击败了74.65%的用户
内存消耗 :32.1 MB, 在所有 JavaScript 提交中击败了100.00%的用户
dp[0]=1，dp[1]=1 ，dp[2]=2
dp[2]=dp[0]+dp[1]
递推公式：dp[i]=dp[i−2]+dp[i−1]
const translateNum = (num) => {
const str = num.toString()
const n = str.length
const dp = new Array(n + 1)
dp[0] = 1
dp[1] = 1
for (let i = 2; i < n + 1; i++) {
const temp = Number(str[i - 2] + str[i - 1])
if (temp >= 10 && temp <= 25) {
dp[i] = dp[i - 1] + dp[i - 2]
} else {
dp[i] = dp[i - 1]
}
}
return dp[n] // 翻译前n个数的方法数，翻译整个数字
}执行用时 :72 ms, 在所有 JavaScript 提交中击败了32.11%的用户
内存消耗 :32.4 MB, 在所有 JavaScript 提交中击败了100.00%的用户
当前 dp 项只和它前面的两项有关，我们无需用数组存储所有的 dp 项
用两个变量去存dp 项前面的两项，在遍历中不断更新这两个变量，可将空间复杂度优化到 O(1)
const translateNum = (num) => {
const str = num.toString()
const n = str.length
let prev = 1
let cur = 1
for (let i = 2; i < n + 1; i++) {
const temp = Number(str[i - 2] + str[i - 1])
if (temp >= 10 && temp <= 25) {
const t = cur // 缓存上个状态
cur = prev + cur // 当前状态=上上个状态+上个状态
prev = t // 更新上上个状态
} else {
// cur = cur
prev = cur // 这里容易忘了
}
}
return cur
}执行用时 :68 ms, 在所有 JavaScript 提交中击败了50.99%的用户
内存消耗 :32.3 MB, 在所有 JavaScript 提交中击败了100.00%的用户
难度中等
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解题思路： 使用一个数组来维护滑动窗口
遍历字符串，判断字符是否在滑动窗口数组里
- 不在则 push 进数组
- 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
- 然后将 max 更新为当前最长子串的长度
遍历完，返回 max 即可
var lengthOfLongestSubstring = function(s) {
let arr = [], max = 0
for(let i = 0; i < s.length; i++) {
let index = arr.indexOf(s[i])
if(index !== -1) {
arr.splice(0, index+1);
}
arr.push(s.charAt(i))
max = Math.max(arr.length, max)
}
return max
};- 时间复杂度：O(n2)， 其中 arr.indexOf() 时间复杂度为 O(n) ，arr.splice(0, index+1) 的时间复杂度也为 O(n)
- 空间复杂度：O(n)
var lengthOfLongestSubstring = function(s) {
let index = 0, max = 0
for(let i = 0, j = 0; j < s.length; j++) {
index = s.substring(i, j).indexOf(s[j])
if(index !== -1) {
i = i + index + 1
}
max = Math.max(max, j - i + 1)
}
return max
};- 时间复杂度：O(n2)
- 空间复杂度：O(n)
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
// 哈希集合，记录每个字符是否出现过
const occ = new Set();
const n = s.length;
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
let rk = -1, ans = 0;
for (let i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.delete(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
};难度简单
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
遍历字符串，将每个字符的值与出现次数记录到 map 中 再次遍历 map.keys() ，获取 map 中每个字符出现的次数，判断是否仅仅只有 1 次，返回第一个仅出现一次的字符
var firstUniqChar = function(s) {
if(!s) return " "
let map = new Map()
for(let c of s) {
if(map.has(c)) {
map.set(c, map.get(c) + 1)
} else {
map.set(c, 1)
}
}
for(let c of map.keys()) {
if(map.get(c) === 1) {
return c
}
}
return " "
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
难度困难
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
双重循环，挨个检查是否为逆序对。
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
let res = 0;
const length = nums.length;
for (let i = 0; i < length; ++i) {
for (let j = i + 1; j < length; ++j) {
if(nums[i] > nums[j]){
res++;
}
}
}
return res;
};- 时间复杂度是O(N^2)，无法通过
- 空间复杂度：O(1)
归并排序的核心思想：
- 如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
以下引自xin-tan
借助归并排序的思路，在归并的过程中，快速统计逆序对。应用归并排序的题目真的不多，这题很有研究和收藏意义。
核心的解决逻辑都封装在 findInversePairNum 函数中。它的职能就是统计数组arr[start, end]范围中的逆序对，并且统计完后，arr[start, end]范围中的元素会被排序（这点和归并排序的过程一样）。
那么函数又是如何快速统计逆序对的呢？大体过程如下：
- 递归调用，拿到左子数组和右子数组的逆序对（此时，左子数组和右子数组也都排序完成了）
- 指针 i 和 j 分别指向左子数组和右子数组的最右侧，此时会有 2 种情况：
- arr[i] > arr[j]：那么说明arr[i]大于右子数组中所有元素，逆序对增加j - start - length，向左边移动指针 i
- arr[i] <= arr[j]: 对arr[i]来说，不存在逆序对，向左边移动指针 j
- i 和 j 遍历完各自数组后，最后返回逆序对之和
var reversePairs = function(nums) {
return findInversePairNum(nums, 0, nums.length - 1);
};
function findInversePairNum(arr, start, end) {
if (start >= end) return 0;
const copy = new Array(end - start + 1);
const length = Math.floor((end - start) / 2); // 左数组长度
const leftNum = findInversePairNum(arr, start, start + length);
const rightNum = findInversePairNum(arr, start + length + 1, end);
let i = start + length;
let j = end;
let copyIndex = end - start;
let num = 0;
while (i >= start && j >= start + length + 1) {//对左子数组和右子数组排序
if (arr[i] > arr[j]) {
//arr[i]大于右子数组中所有元素，逆序对增加j - start - length，向左边移动指针 i
num += j - start - length;
copy[copyIndex--] = arr[i--];
} else {//不存在逆序对，向左边移动指针 j
copy[copyIndex--] = arr[j--];
}
}
//i 和 j 遍历各自数组
while (i >= start) {
copy[copyIndex--] = arr[i--];
}
while (j >= start + length + 1) {
copy[copyIndex--] = arr[j--];
}
for (let k = start; k <= end; ++k) {
arr[k] = copy[k - start];
}
return num + leftNum + rightNum;
}- 时间复杂度是O(NlogN)
- 空间复杂度是O(N)
难度简单
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表**：**
在节点 c1 开始相交。
解题思路：
尝试消除 A、B 链表的长度差，同步遍历链表节点，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。
var getIntersectionNode = function(headA, headB) {
let headNodeA = headA,headNodeB = headB;
while(headNodeA || headNodeB) {
if(headNodeA === headNodeB) return headNodeA
headNodeA = headNodeA === null ? headB : headNodeA.next
headNodeB = headNodeB === null ? headA : headNodeB.next
}
return null
};- 时间复杂度：O(N)。
- 空间复杂度：O(1)。
难度简单
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
- 二分查找到等于当前值的索引，把索引赋值给 left，或者直到左指针大于等于右指针停下
- 判断 nums[left] 是否等于 target，不等，返回 0
- 从 left 指针的位置往两边找，看看这个数重复几次，返回
var search = function(nums, target) {
let count = 0,
n = nums.length,
left = 0,
right = n - 1;
while (left < right) {
let mid = (left + right) >> 1;
if (nums[mid] === target) {
left = mid;
break;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (nums[left] !== target) return 0;
// 找到起始位置, 从当前位置往两边找，看看重复几次
let copy = left - 1;
while (copy >= 0 && nums[copy] === target) {
copy--;
count++;
}
while (nums[left] === target && left < n) {
left++;
count++;
}
return count;
};难度简单
一个长度为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
-
left 指向 0，right 指向最后一个元素
-
计算中间坐标 mid：
- 如果mid = nums[mid]，说明[0, mid]范围内不缺失数字，left 更新为 mid + 1
- 如果mid < nums[mid]，说明[mid, right]范围内不缺失数字，right 更新为 mid - 1
-
检查 left 是否小于等于 mid，若成立，返回第 2 步；否则，向下执行
-
返回 left 即可
根据题意，可以知道mid > nums[mid]这种情况不存在。
var missingNumber = function(nums) {
let left = 0,
right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (mid === nums[mid]) {
left = mid + 1;
} else if (mid < nums[mid]) {
right = mid - 1;
}
}
return left;
};难度简单
给定一棵二叉搜索树，请找出其中第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
- 最终返回的倒数第k个元素就是arr.length-1-k+1 ，即以arr.length-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) {
let arr = []
function traversal(node) {
if(!node) return
traversal(node.left)
arr.push(node.val)
traversal(node.right)
}
traversal(root)
return arr[arr.length - k]
};难度简单
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
提示：
节点总数 <= 10000
注意：本题与主站 104 题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
var maxDepth = function(root) {
if(!root){
return 0
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};难度简单
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 。
类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。
var isBalanced = function(root) {
// 遍历到底还没有发现高度差超过 1 的左右子树，那么这个子树肯定符合平衡二叉树的规范
if (!root) {
return true
}
// 判断左右子树的高度差，如果超过 1 那么立即返回 false
if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
return false
}
// 分别递归左右子树
return isBalanced(root.left) && isBalanced(root.right)
// 获取某个子树的高度
function getHeight (root) {
if (!root) {
return 0
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1
}
};时间复杂度：O(n ^ 2)
空间复杂度：O(n)
自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
return height(root) >= 0
function height(root){
if(root == null){
return 0
}
let leftHeight = height(root.left)
let rightHeight = height(root.right)
if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1){
return -1
}else{
return Math.max(leftHeight,rightHeight) + 1
}
}
};难度中等
一个整型数组 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]
/**
* @param {number[]} nums
* @return {number[]}
*/
var singleNumbers = function(nums) {
// 定义一个 mask，表示要找的两个数字的异或
// 因为出现了两次的数字的异或为 0，也就不会被记录在 mask 中
let mask = 0
for (let num of nums) {
mask ^= num
}
// 获取到 mask 后，此时的任务就是找到其中一个只出现过一次的数字，记为 num1
// 将 mask 与 num1 进行异或计算，就能获得第二个数字，记为 num2
// 异或结果的某一位是 1，表示当前位的运算数字一个是 1 ，一个是 0
// 即找到了不同的一位，以下取最低位的 1
// 获取最低位的 1，记为 diff
const diff = mask & -mask
let num1 = 0
for (let num of nums) {
// 若 num 与 diff 的与运算结果为 1，则说明这些 num 是一组的
// 与此同时，结果为 0 的表示另外一组
// 原因是：异或为 1，表示运算数分别是 0 / 1
if (num & diff) {
// 此时的过程就相当于 在一堆数字(除了一个数字外其它成对)中找个唯一的一个
num1 ^= num
}
}
// 此时 num1 就是其中一个只出现一次的数字
// 将 num1 与 mask 异或，得到另外一个
const num2 = mask ^ num1
return [num1, num2]
};难度中等
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
异或的性质
- 两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算，得出的数字。 运算的逻辑是 如果同一位的数字相同则为 0，不同则为 1
异或的规律
- 任何数和本身异或则为0
- 任何数和 0 异或是本身
不开辟额外空间
var singleNumber = function(nums) {
let res = 0;
for (let i = 0; i < 32; i++) {
let cnt = 0;
let bit = 1 << i;
for (let j = 0; j < nums.length; j++) {
if (nums[j] & bit) cnt++;
}
if (cnt % 3 != 0) res = res | bit;
}
return res;
};-
时间复杂度是O(N)
-
空间复杂度是O(1)
难度简单
输入一个递增排序的数组和一个数字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]
设置左右两个指针，左指针指向数组首元素，右指针指向数组尾元素 当左右指针指向的两个元素的和大于target时，右指针减一 当左右指针指向的两个元素的和小于target时，左指针加一 当左右指针指向的两个元素的和等于target时，将两元素保存到结果数组中，退出循环即可。
var twoSum = function(nums, target) {
let left = 0;
let right = nums.length-1;
while(left < right) {
let sum = nums[left] + nums[right];
if(sum === target) {
return [nums[left], nums[right]];
}else if(sum > target) {
-- right;
}else if(sum < target) {
++ left;
}
}
return -1;
};难度简单
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
if (!root) {
return true
}
// 判断左右子树的高度差，如果超过 1 那么立即返回 false
if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
return false
}
// 分别递归左右子树
return isBalanced(root.left) && isBalanced(root.right)
// 获取某个子树的高度
function getHeight (root) {
if (!root) {
return 0
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1
}
};难度简单
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
-
窗口的左边界和右边界永远只能向右移动
-
当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
-
当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
-
当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)，那么我们已经找到了一个 i开头的序列，也是唯一一个 i 开头的序列，接下来需要找 i+1 开头的序列，所以窗口的左边界要向右移动
var findContinuousSequence = function(target) { var i = 1;//滑动窗口的左边界 var j = 1;//滑动窗口的有边界 var sum = 0;//滑动窗口中数字的和 var res = []; while(i <= target / 2){ if(sum < target){ // 右边界向右移动 sum += j; j++; }else if(sum > target){ // 左边界向右移动 sum -= i; i ++; }else{ // 记录结果 var arr = []; for(var k = i; k < j; k++){ arr.push(k); } res.push(arr); // 左边界向右移动 sum -= i; i++; } } return res; };
- 时间复杂度是 O(n)
- 空间复杂度是 O(n)
#### 剑指 Offer 58 - I. 翻转单词顺序
难度简单
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
###### 双指针
- 倒序遍历字符串 s，去掉头尾空格，记录单词左右索引边界 i , j ；
- 每确定一个单词的边界，则将其添加至单词列表 res；
- 最后，将单词列表拼接为字符串，并返回即可。
```js
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function(s) {
s = s.trim()
var j = s.length - 1, i = j
var res = []
while(i >= 0){
while(i >= 0 & s[i] != ' '){i -= 1} //搜索首个空格
res.push(s.slice(i + 1, j + 1)) //添加单词
while(s[i] == ' '){i -= 1} //跳过单词间空格
j = i //j 指向下个单词的尾字符
}
return res.join(' ')
};
- 时间复杂度 O(N)
- 空间复杂度 O(N)
- trim()把字符串两端空格去掉
- split(' ')把字符串切割成以空格为界限的单词块
- filter()过滤掉数组中的纯空格
- reverse()进行数组反转
- join(' ')把数组变成中间只带一个空格的字符串
var reverseWords = function(s) {
let t = s.trim().split(' ').filter(el => el);
return t.reverse().join(' ');
};- 时间复杂度 O(N)
- 空间复杂度 O(N)
难度简单
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
- 切片，使用 "++" 运算符拼接
- slice(start, end) end省略时代表到尾部 substring(start, end)提取一个字符串,end不支持负数 substr(start, len)提取一个长度为len的字符串
var reverseLeftWords = function(s, n) {
return s.slice(n) + s.slice(0, n)
//return s.substring(n) + s.substring(n, 0);
//return s.substr(n,s.length-n+1) + s.substr(0, n);
};- 新建一个[]，记为 res ；
- 先向 res添加 “第 n + 1位至末位的字符” ；
- 再向 res 添加 “首位至第 n位的字符” ；
- 将 res转化为字符串并返回。
var reverseLeftWords = function(s, n) {
var res = []
for(var i = n; i < s.length; i++){
res.push(s[i])
}
for(var i = 0; i < n; i++){
res.push(s[i])
}
return res.join('')
}利用求余运算，简化代码
var reverseLeftWords = function(s, n) {
var res = []
for(var i = n; i < n + s.length; i++){
res.push(s[i % s.length])
}
return res.join('')
}var reverseLeftWords = function(s, n) {
var res = ""
for(var i = n; i < s.length; i++){
res += s[i]
}
for(var i = 0; i < n; i++){
res += s[i]
}
return res
};同理，利用求余运算，简化代码
var reverseLeftWords = function(s, n) {
var res = ""
for(var i = n; i < n + s.length; i++){
res += s[i % s.length]
}
return res
};难度简单
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
直接移动这个滑动窗口，每次统计窗口中的最大值即可。
var maxSlidingWindow = function(nums, k) {
if (k <= 1) return nums;
const res = [];
for (let i = 0; i < nums.length - k + 1; ++i) {
res.push(Math.max(...nums.slice(i, i + k)));
}
return res;
};- 时间复杂度是O(kN)，其中 k 是滑动窗口的长度。
- 空间复杂度是O(N)。
基于单调队列,js数组模拟队列操作
var maxSlidingWindow = function(nums, k) {
if (!nums || !nums.length || k <= 0) return []
if (k === 1) return nums
let res = [], queue = []
for (let i = 0; i < nums.length; i++) {
if(i >= k) {
// 尾部元素出滑动窗口
let outElem = nums[i - k]
if (outElem === queue[0]) queue.shift()
}
// 当前元素进入滑动窗口
let inElem = nums[i]
while (queue.length && queue[queue.length - 1] < inElem) queue.pop()
queue.push(inElem)
if (i >= k - 1) res.push(queue[0])
}
return res
};难度中等
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
限制：
1 <= n <= 11
解题思路：
- 用一个数组cnts，cnts[i] 表示点数之和，那么cnts[i] 就等于前面六个相加，或者前面五个相加
- 从后往前遍历，逻辑可以统一为 cnts[i] 等于前面六个cnts[j]相加，其中j等于i - 1, i - 2, i - 3, i - 4, i - 5, i - 6。
- 如果使用迭代，只需要迭代n - 1次，每次迭代相当于一次投掷，而内层循环的逻辑就是上面提到的，我们每次投掷都去更新cnts[i]
var twoSum = function(n) {
if (n < 1) {
return [];
}
const res = [0, 1, 1, 1, 1, 1, 1];
for (let i = 1; i < n; i++) {
for (let j = 6 * n; j > 0; j--) {
res[j] = res
.slice(Math.max(0, j - 6), j)
.reduce((acc, cur) => acc + cur, 0);
}
}
return res.slice(1).map(num => num / Math.pow(6, n)).filter(Boolean);
};/**
* @param {number} n
* @return {number[]}
*/
var twoSum = function(n) {
function diceCnt(n) {
if (n === 1) {
return [0, 1, 1, 1, 1, 1, 1];
}
cnts = diceCnt(n - 1);
for (let i = 6 * n; i > 0; i--) {
cnts[i] = cnts
.slice(Math.max(i - 6, 0), i)
.reduce((acc, cur) => acc + cur, 0);
}
return cnts;
}
return diceCnt(n)
.map(num => num / Math.pow(6, n))
.filter(Boolean)
};难度简单
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
限制：
数组长度为 5
数组的数取值为 [0, 13] .
依据题意数组需要满足：
- 除 0 以外，数组最大数与最小数之差不能超过 4 ；因为长度为 5 的数组里数字若是连续的必定满足这一条件
- 除 0 以外，数组中不能有相同的数字
故解题思路为：
- 获取数组 最大数 与 最小数 ，对数组进行排序
- 以上条件都需要除去 0 ，故使用了数组的 filter方法 将数组中的 0 过滤掉
- 获取到 最大数 与 最小数 之后，判断它们的差是否大于 4 ，大于 4 则不符题意，返回 false
- 遍历一次新数组判断是否有重复的数字，有重复则不符题意，返回 false
- 以上都判断都通过，说明符合题意，返回 true
var isStraight = function (nums) {
// 先将 nums 从小到大进行排序，再把数组中的 0 去掉
nums = nums.sort((a, b) => a - b).filter(item => item !== 0)
// 找出数组中的最大数与最小数，分别在数组的头和尾，判断它们的差是否超过 4，超过则说明不是连续的
if (nums[nums.length - 1] - nums[0] > 4) return false
// 遍历数组找出是否有重复的数字，因为涉及到 i + 1，所以遍历长度是 数组长度-1
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] === nums[i + 1]) return false // 若有重复，提前返回 false
}
return true
};- 时间复杂度 O(NlogN)=O(5log5)=O(1) ： 其中 N 为 nums长度，本题中N=5 ；数组排序使用 O(NlogN) 时间。
- 空间复杂度 O(1)。
- 遍历五张牌，遇到大小王（即 0 ）直接跳过。
- 判别重复： 利用 Set 实现遍历判重， Set 的查找方法的时间复杂度为 O(1) ；
- 获取最大 / 最小的牌： 借助辅助变量 ma 和 mi ，遍历统计即可。
var isStraight = function(nums) {
if (!nums || nums.length === 0) { return false; }
let set = new Set();
let max = 0;
let min = 14;
for (let i = 0; i < nums.length; i++) {
let num = nums[i];
if (num === 0) { continue; } // 跳过大小王
if (set.has(num)) {
return false;// 若有重复，提前返回 false
}
set.add(num);// 添加此牌至 Set
max = Math.max(max, num);// 最大牌
min = Math.min(min, num);// 最小牌
}
return max - min < 5;// 最大牌 - 最小牌 < 5 则可构成顺子
};- 时间复杂度O(N)=O(5)=O(1) ： 其中 N为 nums长度，本题中 N≡5 ；遍历数组使用 O(N)时间。
- 空间复杂度O(N)=O(5)=O(1) ： 用于判重的辅助 Set 使用 O(N)额外空间。
难度简单
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
限制：
1 <= n <= 10^51 <= m <= 10^6
- 长度为 n 的序列会先删除第 m % n 个元素，然后剩下一个长度为 n - 1 的序列。那么，我们可以递归地求解 f(n - 1, m)，就可以知道对于剩下的 n - 1 个元素，最终会留下第几个元素，我们设答案为 x = f(n - 1, m)。
- 由于我们删除了第 m % n 个元素，将序列的长度变为 n - 1。当我们知道了 f(n - 1, m) 对应的答案 x 之后，我们也就可以知道，长度为 n 的序列最后一个删除的元素，应当是从 m % n 开始数的第 x 个元素。因此有 f(n, m) = (m % n + x) % n = (m + x) % n。
var lastRemaining = function(n, m) {
return f(n, m);
};
function f(n, m){
if(n == 1){
return 0;
}
let x = f(n - 1, m);
return (m + x) % n;
}- 时间复杂度：O(n)，需要求解的函数值有 n 个。
- 空间复杂度：O(n)，函数的递归深度为 n，需要使用 O*(*n) 的栈空间。
var lastRemaining = function(n, m) {
let f = 0;
for(let i = 2; i != n + 1; ++i){
f = (m + f) % i;
}
return f;
};- 时间复杂度：O(n)，需要求解的函数值有 n 个。
- 空间复杂度：O(1)，只使用常数个变量。
难度中等
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
限制：
0 <= 数组长度 <= 10^5
我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。形式上，对于每组 i 和 j（其中 j>i）我们需要找出 max(prices[j]−prices[i])。
var maxProfit = function(prices) {
let maxprofit = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
const profit = prices[j] - prices[i];
if (profit > maxprofit) {
maxprofit = profit;
}
}
}
return maxprofit;
};- 时间复杂度：O(n^2)。循环运行 n (n-1)/2次。
- 空间复杂度：O(1)。只使用了常数个变量。
用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。
var maxProfit = function(prices) {
let minprice = Number.MAX_VALUE;
let maxprofit = 0;
for (const price of prices) {
maxprofit = Math.max(price - minprice, maxprofit);
minprice = Math.min(price, minprice);
}
return maxprofit;
};- 时间复杂度：O(n)，只需要遍历一次。
- 空间复杂度：O(1)，只使用了常数个变量。
难度中等
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
示例 2：
输入: n = 9
输出: 45
限制：
1 <= n <= 10000
&& 特性：
对于 A && B 这个表达式，如果 A 表达式返回 False ，那么 A && B 已经确定为 False ，此时不会去执行表达式 B。同理，对于逻辑运算符 ||， 对于 A || B 这个表达式，如果 A 表达式返回 True ，那么 A || B 已经确定为 True ，此时不会去执行表达式 B
如果左边表达式为 false，不执行右边； 左边为true继续执行右边。
传入 n return n && n + (n-1) => n + (n-1) return 1 && n + (n-1) + ... + 1 => n + (n-1) + ... + 1 return 0 && 不执行 最后得到的结果： n + (n-1) + ... + 1
var sumNums = function(n) {
return n && (n + sumNums(n - 1));
};难度简单
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
提示：
a,b均可能是负数或 0- 结果不会溢出 32 位整数
var add = function(a, b) {
while(b != 0){// 当进位为 0 时跳出
let c = (a & b) << 1; // c = 进位
a ^= b;// a = 非进位和
b = c;// b = 进位
}
return a;
};- 时间复杂度 O(1)： 最差情况下（例如 a= 0x7fffffff , b = 1b=1 时），需循环 32 次，使用 O(1)时间；每轮中的常数次位操作使用 O(1)时间。
- 空间复杂度 O(1) ： 使用常数大小的额外空间。
难度中等
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
注意：本题与主站 8 题相同：https://leetcode-cn.com/problems/string-to-integer-atoi/
/**
* @param {string} str
* @return {number}
*/
var strToInt = function(str) {
if(!str || str === ' ') return 0;
let len = str.length;
//最大值和最小值
const Max = Math.pow(2, 31) - 1;
const Min = Math.pow(2, 31);
//存储数字的队列
const numsQueue = [];
let pointer = 0;
//记录是否负数的变量
let isNegative = false;
//跳过开头的指针
while(str[pointer] === ' ') {
pointer++;
}
//开头正负号的判断
if(str[pointer] === '+' || str[pointer] === '-') {
//如果是负数，改变标识变量的值，正数不用变
if(str[pointer] === '-') {
isNegative = true;
}
//指针后移
pointer++;
}
//处理后面的字符
for(let i = pointer; i < len; i++) {
let char = str[pointer]
//如果是数字
if(char >= '0' && char <= '9') {
numsQueue.push(char);
}else {
//其他字符直接退出循环
break;
}
pointer++;
}
//如果数字队列中没有数字则为无效串，直接返回0
if(numsQueue.length < 1) {
return 0;
}
//队列转换为数字
let res = 0;
while(numsQueue.length) {
res *= 10;
//乘一是将字符转为数值型
res += numsQueue.shift() * 1;
//如果溢出则退出循环
if(res >= Max + 1) {
break;
}
}
//判断正负，还需处理溢出的情况
if(isNegative) {
return res >= Max + 1 ? -Min : -res;
}else {
return res >= Max ? Max : res;
}
};难度中等
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
解题思路
b[当前] = 左积 * 右积
先循环两次 分别获取 当前位置 左边 和 右边的积, 最后再循环一次得到b的每一项, b[当前] = 左积 * 右积
/**
* @param {number[]} a
* @return {number[]}
*/
var constructArr = function(a) {
let n = a.length
// 一. 获取 当前 之前的累积
let left = Array(n)
left[0] = 1
for(let i = 1; i < n; i++){
left[i] = left[i - 1] * a[i - 1]
}
// 二. 获取 当前 之后的累积
let right = Array(n)
right[n - 1] = 1
for(let i = n - 2; i >= 0; i--){
right[i] = right[i + 1] * a[i + 1]
}
// 三. b[i] = 左积 * 右积
let b = []
for(let i = 0; i < n; i++){
b[i] = left[i] * right[i]
}
return b
};合起来就是
var constructArr = function(a) {
let n = a.length
// 一. 获取 i 的左积
let left = Array(n)
left[0] = 1
for(let i = 1; i < n; i++){
left[i] = left[i - 1] * a[i - 1]
}
// 二. 获取 i 的右积 同时 得出 b
let b = []
let right = 1
b[n - 1] = left[n - 1] * right
for(let i = n - 2; i >= 0; i--){
right *= a[i + 1]
b[i] = left[i] * right
}
return b
};难度简单
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
注意：本题与主站 235 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
- 既然是BST，如果p和q都比root.val小，则递归左子树，如果都比root.val大，则递归右子树，否则，root 即为所求
- 因为 root 为 p,q 的最近公共祖先，只可能是下面的情况
- p,q 分居root的两个子树
- p 为 root ，q 在root的左或右子树中
- q 为 root ， p 在root 的左或右子树中
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
const lowestCommonAncestor = (root, p, q) => {
if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
}
if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
};