难度中等442收藏分享切换为英文关注反馈
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
// 递归解法 类似于前序遍历，不同的是把每一行的值存储到二维数组中
var levelOrder = function(root, parent=[], index=0) {
if (root) {
parent[index] = parent[index] ? parent[index]: []
parent[index].push(root.val)
levelOrder(root.left, parent, index + 1)
levelOrder(root.right, parent, index + 1)
}
return parent
};
// 迭代解法
var levelOrder = function(root) {
const printArr = []
if (!root) return printArr
const list = []
list.push({ node: root, level: 0 })
while (list.length > 0) {
const { node, level } = list.shift()
if (!printArr[level]) {
printArr[level] = []
}
printArr[level].push(node.val)
node.left && list.push({ node: node.left, level: level + 1 })
node.right && list.push({ node: node.right, level: level + 1 })
}
return printArr
}难度简单504收藏分享切换为英文关注反馈
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。BFS
var maxDepth = function(root) {
if (root !== null) {
let leftDepth = maxDepth(root.left)
let rightDepth = maxDepth(root.right)
return Math.max(leftDepth, rightDepth) + 1
} else {
return 0
}
};压栈出栈
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
var tmpStack = [
{"key":root,"val":1}
];
var depth = 0;
while(tmpStack.length != 0){
var currObj = tmpStack.pop();
var currNode = currObj.key;
if(currNode != null){
var currNode_depth = currObj.val;
depth = Math.max(depth,currNode_depth);
if(currNode.left != null){
tmpStack.push({"key":currNode.left,"val":currNode_depth + 1});
}
if(currNode.right != null){
tmpStack.push({"key":currNode.right,"val":currNode_depth + 1});
}
}
}
return depth;
};难度简单724收藏分享切换为英文关注反馈
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
// 解题思路 设置check(left, right)
// 2020-5-31复习
/**
* 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) return true
function check(left, right) {
if (!left && !right) return true
if (left && right) {
return left.val === right.val && check(left.right, right.left) && check(left.left, right.right)
}
return false
}
return check(root.left, root.right)
};难度简单279收藏分享切换为英文关注反馈
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
// 找到递归中止条件
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var hasPathSum = function(root, sum) {
if (!root) {
return false
}
if (!root.left && !root.right) {
return sum - root.val === 0
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)
};难度中等486收藏分享切换为英文关注反馈
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
通过次数77,172
提交次数115,639
/**
* 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) return null
let root_val = preorder[0]
let node = new TreeNode(root_val)
let index = inorder.indexOf(root_val)
let leftArrays = inorder.slice(0, index)
let leftArrays_ = preorder.slice(1, index + 1)
let rightArrays = inorder.slice(index + 1, inorder.length)
let rightArrays_ = preorder.slice(index + 1, preorder.length)
node.left = buildTree(leftArrays_, leftArrays)
node.right = buildTree(rightArrays_, rightArrays)
return node
};难度中等187收藏分享切换为英文关注反馈
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
var buildTree = function(inorder, postorder) {
if (!inorder.length) {
return null
}
let root = new TreeNode(postorder[postorder.length - 1])
let mid = inorder.indexOf(root.val)
root.left = buildTree(inorder.slice(0, mid), postorder.slice(0, mid))
root.right = buildTree(inorder.slice(mid + 1), postorder.slice(mid, postorder.length - 1))
return root
};难度中等158收藏分享切换为英文关注反馈
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
// 判断递归条件，右孩子节点的next指向root的next的zuo'jie'dian
/**
* // Definition for a Node.
* function Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/
/**
* @param {Node} root
* @return {Node}
*/
var connect = function(root) {
if (root === null || root.left === null) {
return root
}
root.left.next = root.right
if (root.next) {
root.right.next = root.next.left
}
connect(root.left)
connect(root.right)
return root
};难度中等468收藏分享切换为英文关注反馈
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
// 如果 p 节点 q 节点分别在左右子树，则root为LCA（lower common ancestor）
// 如果 p 节点 q 节点在同一子树中
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if (root === null || root === p || root === q ) {
return root
}
let left = lowestCommonAncestor(root.left, p, q)
let right = lowestCommonAncestor(root.right, p, q)
if (left === null && right === null) {
return null
}
if (left !== null && right !== null) {
return root
}
return left === null ? right : left
};
var lowestCommonAncestor = function(root, p, q) {
let ans = null
function hasAncestor(root, p, q) {
if (!root) return false
let leftIsAns = hasAncestor(root.left, p, q)
let rightIsAns = hasAncestor(root.right, p, q)
if ((leftIsAns && rightIsAns) || ((root.val == p.val || root.val === q.val) && (leftIsAns || rightIsAns))) {
ans = root
}
return leftIsAns || rightIsAns || ((root.val === p.val || root.val === q.val))
}
hasAncestor(root, p, q)
return ans
};难度困难176收藏分享切换为英文关注反馈
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
// 非递归方法
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
if (root === null) return [];
let res = [];
let node = root,
queue = [node];
while (queue.length > 0) {
node = queue.shift();
if (node === null) {
res.push(null);
} else {
res.push(node.val);
queue.push(node.left);
queue.push(node.right);
}
}
return res;
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
if (data.length === 0) return null;
let root = new TreeNode(data.shift());
let queue = [root];
while (queue.length > 0) {
let node = queue.shift();
// 数组中的节点已经计算完毕
if (data.length <= 0) break;
let left = data.shift(); // 左子节点的值
if (left === null) {
node.left = null;
} else {
node.left = new TreeNode(left);
queue.push(node.left);
}
// 数组中的节点已经计算完毕
if (data.length <= 0) break;
let right = data.shift();
if (right === null) {
node.right = null;
} else {
node.right = new TreeNode(right);
queue.push(node.right);
}
}
return root;
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/// 递归解法
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
let res = []
function dfs(node) {
if (node) {
res.push(node.val)
dfs(node.left)
dfs(node.right)
} else {
res.push(null)
}
}
dfs(root)
return res
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
function dfs() {
if (data.length === 0 ) {
return null
}
let val = data.shift()
if (val !== null) {
let node = new TreeNode(val)
node.left = dfs()
node.right = dfs()
return node
} else {
return null
}
}
return dfs()
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/难度中等487收藏分享切换为英文关注反馈
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
// 神特么笛卡尔积 都忘记了好吗！！！
// 利用动态规划G(0) = 1, g(1) = 1
// f(i, n) = g(i-1)*g(n-i)
//
//
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
let g = new Array(n + 1).fill(0)
g[0] = 1;
g[1] = 1;
for (let i = 2; i<=n; i++) {
for (let j = 1; j<=i; j++) {
g[i] += g[j-1] * g[i-j]
}
}
return g[n]
};给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} t1
* @param {TreeNode} t2
* @return {TreeNode}
*/
// 不改变原树方法
// var mergeTrees = function(t1, t2) {
// let node = null
// if (t1 || t2) {
// node = new TreeNode((t1 ? t1.val : 0) + (t2? t2.val: 0))
// node.left = mergeTrees(t1? t1.left: null, t2? t2.left: null)
// node.right = mergeTrees(t1? t1.right: null, t2? t2.right: null)
// return node
// } else {
// return null
// }
// };
//
var mergeTrees = function(t1, t2) {
if (t1 && t2) {
t1.val += t2.val
t1.lfet = mergeTrees(t1.left, t2.left)
t1.right = mergeTrees(t1.right, t2.right)
}
return t1 || t2
};95. 不同的二叉搜索树 II hard
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
// 奇妙的判定终止方法，注意n===0和左右子树为空的情况的判定
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number} n
* @return {TreeNode[]}
*/
var generateTrees = function(n) {
function getRes(start, end) {
let res = []
if (start > end) {
res.push(null)
return res
}
for (let i = start; i <= end; i++) {
let leftTrees = getRes(start, i - 1)
let rightTrees = getRes(i + 1, end)
for (let l of leftTrees) {
for (let r of rightTrees) {
let node = new TreeNode(i)
node.left = l
node.right = r
res.push(node)
}
}
}
return res
}
if (n === 0) {
return []
}
return getRes(1, n)
};难度中等516收藏分享切换为英文关注反馈
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
// 解法 1
// 不仅要确认right > root > left ，而且要记录上一层级的最小值和最大值。
var isValidBST = function(root) {
function help(node, lower, upper) {
if (node === null) {
return true
} else {
let val = node.val
if (lower !== null && val <= lower) return false
if (upper !== null && val >= upper) return false
if (!help(node.left, lower, val)) return false
if (!help(node.right, val, upper)) return false
return true
}
}
return help(root, null, null)
}
// 根据二叉搜索树的性质，中序遍历的结果为从小到大排列的顺序
// 解法 2
var isValidBST = function(root) {
function help(node, lower, upper) {
if (node === null) {
return true
} else {
let val = node.val
if (lower !== null && val <= lower) return false
if (upper !== null && val >= upper) return false
if (!help(node.left, lower, val)) return false
if (!help(node.right, val, upper)) return false
return true
}
}
return help(root, null, null)
}
// 解法 3 利用先序遍历，迭代
function isValidBST(root) {
let stack = []
let min = Number.MIN_SAFE_INTEGER
while(stack.length || root !== null) {
while(root !== null) {
stack.push(root)
root = root.left
}
root = stack.pop()
let val = root.val
if (val <= min) return false
root = root.right
min = val
}
return true
}难度中等331收藏分享切换为英文关注反馈
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
/**
* 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 {void} Do not return anything, modify root in-place instead.
*/
// 将左子树的最后一个右节点.ritht->root.right,root.right = root.left, root.left = null,
var flatten = function(root) {
while (root !== null) {
if (root.left === null) {
root = root.right
} else {
let pre = root.left
while (pre.right !== null) {
pre = pre.right
}
pre.right = root.right
root.right = root.left
root.left = null
root = root.right
}
}
};
// 利用中序遍历stack的方法，记录上一个节点
var flatten = function(root) {
if (root === null) return
let stack = []
let pre = null
stack.push(root)
while(stack.length) {
let temp = stack.pop()
if (pre !== null) {
pre.right = temp
pre.left = null
}
if (temp.right !== null) {
stack.push(temp.right)
}
if (temp.left !== null) {
stack.push(temp.left)
}
pre = temp
}
}难度困难406收藏分享切换为英文关注反馈
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42// 创造一个函数，获取通过该节点的单路径的最大路径和
var pathSum = function(root, sum) {
// 以自己作为起始节点 有多少条路径和 = sum
function getsum(root, sum) {
let result = 0;
if (root === null) return 0
sum -= root.val;
if (sum === 0) result++
return (result + getsum(root.left, sum) + getsum(root.right, sum))
}
// 遍历每一个节点作为起始节点并作为路径和
function getTotalSum(root, sum) {
if (root) {
return getsum(root, sum) + getTotalSum(root.left, sum) + getTotalSum(root.right, sum)
}
return 0
}
return getTotalSum(root, sum)
};226. 翻转二叉树 easy
难度简单419收藏分享切换为英文关注反馈
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
备注: 这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
// 难得有一下就写出来的题目
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
if (root !== null) {
invertTree(root.left)
invertTree(root.right)
let temp = root.left
root.left = root.right
root.right = temp
}
return root
};难度中等329收藏分享切换为英文关注反馈
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
// 抢爷孙还是抢爹
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var rob = function(root) {
let map = new WeakMap()
function maxV(root) {
if (map.get(root)) return map.get(root)
if (root === null) return 0
let money = root.val
if (root.left !== null) {
money += maxV(root.left.left) + maxV(root.left.right)
}
if (root.right !== null) {
money += maxV(root.right.left) + maxV(root.right.right)
}
let result = Math.max(maxV(root.left) + maxV(root.right), money)
map.set(root, result)
return result
}
return maxV(root)
};给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
// 双递归 我太蠢了 草
// 自己作为头结点的路径和，然后遍历所有节点
/**
* 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) {
// 以自己作为头节点的个数
function getsum(root, sum) {
let result = 0;
if (root === null) return 0
sum -= root.val;
if (sum === 0) result++
return (result + getsum(root.left, sum) + getsum(root.right, sum))
}
function getTotalSum(root, sum) {
if (root) {
return getsum(root, sum) + getTotalSum(root.left, sum) + getTotalSum(root.right, sum)
}
return 0
}
return getTotalSum(root, sum)
};给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 原始二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
// 利用二叉搜索树的特性，右>中>左，将前序遍历倒一下
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var convertBST = function(root) {
let sum = 0;
function add(root) {
if (root !== null) {
add(root.right)
sum += root.val
root.val = sum
add(root.left)
return root
} else {
return null
}
}
return add(root)
};难度简单339收藏分享切换为英文关注反馈
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 : 给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
// 计算节点深度，最长路径 = 左子树深度 + 右子树深度
// 计算每个节点的max_deepth，max = left_max_deepth + right_max_deepth
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var diameterOfBinaryTree = function(root) {
// L + R + 1
let max = 0
function maxPath(root) {
if (root !== null) {
let maxL = maxPath(root.left)
let maxR = maxPath(root.right)
max = Math.max(max, maxL + maxR)
return Math.max(maxL, maxR) + 1
} else {
return 0
}
}
maxPath(root)
return max
};难度中等4293
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
// 考察进位制
var addTwoNumbers = function(l1, l2) {
// 进位
let count = 0;
let node = new ListNode('')
let p = node
while (l1 || l2 || count) {
let l1_val = l1 ? l1.val : 0;
let l2_val = l2 ? l2.val : 0;
let sum = l1_val + l2_val + count
p.next = new ListNode('')
p = p.next
if (sum >= 10) {
count = 1
p.val = sum % 10
} else {
count = 0
p.val = sum
}
if (l1) l1 = l1.next
if (l2) l2 = l2.next
}
return node.next
};难度中等3623收藏分享切换为英文关注反馈
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
/**
* @param {string} s
* @return {number}
*/
// 暴力
// var lengthOfLongestSubstring = function(s) {
// let max = 0;
// let res = []
// for (let i = 0; i < s.length; i++) {
// for (let j = i; j < s.length; j++) {
// if (res.indexOf(s[j]) === -1) {
// res.push(s[j])
// } else {
// break
// }
// }
// max = Math.max(max, res.length)
// res = []
// }
// return max
// };
// 维护下标
// var lengthOfLongestSubstring = function(str) {
// let max = 0;
// let index = -1;
// for (let i = 0, j = 0; j < str.length; j++) {
// index = str.slice(i, j).indexOf(str[j])
// if (index !== -1) {
// i = i + index + 1
// }
// max = Math.max(max, j - i + 1)
// }
// return max
// };
// 维护数组
function lengthOfLongestSubstring(str) {
let res = []
let right = 0;
let max = 0
for (; right < str.length; right++) {
let index = res.indexOf(str[right])
if (index !== -1) {
res.splice(0, index + 1)
}
res.push(str[right])
max = Math.max(max,res.length)
}
console.log(max)
return max
}难度中等374收藏分享切换为英文关注反馈
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 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
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {
function doubleP(x, n) {
if (n === 0) {
return 1
}
if (n === 1) {
return x
}
let n2 = Math.floor(n / 2)
let n2Val = doubleP(x, n2)
return n % 2 === 0 ? n2Val * n2Val : n2Val * n2Val * x
}
if (n >= 0) {
return doubleP(x, n)
} else {
return doubleP(1/x, -n)
}
};难度简单8209收藏分享切换为英文关注反馈
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
// 暴力法和一遍哈希存储法
var twoSum = function(nums, target) {
let map = new Map()
for (const key in nums) {
let res = target - nums[key]
if (map.get(res)) {
return [key, map.get(res)]
}
map.set(nums[key], key)
}
return []
};难度中等2113收藏分享切换为英文关注反馈
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
// 中心拓展法，比较奇数为中心和偶数为中心的回文结果
// 动态规划法 还没看 5.13
/**
* @param {string} s
* @return {string}
*/
// 注意边界 left >= 0 right < length slice(left + 1, right)
var longestPalindrome = function(s) {
function expandStr(s, left, right) {
while(left >= 0 && right < s.length && s[left] === s[right]) {
left--
right++
}
return s.slice(left + 1, right)
}
if (!s.length) return ""
let maxStr = ''
for (let i = 0; i < s.length; i++) {
let oddVal = expandStr(s, i, i)
let evenVal = expandStr(s, i, i + 1)
let max = oddVal.length > evenVal.length ? oddVal : evenVal
maxStr = max.length > maxStr.length ? max : maxStr
}
return maxStr
};难度中等422收藏分享切换为英文关注反馈
给定一个整数数组和一个整数 **k，**你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
- 数组的长度为 [1, 20,000]。
- 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
// 前缀和 pre[j] - pre[i - 1] = k ，利用这个规则+hashmap
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
let map = new Map()
map.set(0, 1)
let count = 0;
let preSum = 0;
for (let num of nums) {
preSum += num
if (map.has(preSum - k)) count+= map.get(preSum - k)
if (map.has(preSum)) {
map.set(preSum, map.get(preSum) + 1)
} else {
map.set(preSum, 1)
}
}
return count
};难度中等148收藏分享切换为英文关注反馈
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
- 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
提示:
- 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
- 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
- 拓扑排序也可以通过 BFS 完成。
// 把一个有向无环图变成线性排序就是拓扑排序
// 1.构建入度数组
// 2.构建出度hash表，如果[2, 0], [1, 0] => 0: [1, 2]
// 3.构建队列queue,将入度为0的都push进queue
// 4.cur = queue.pop(),检查cur在hash表中对应的出度数组，并元素对应入度数组中的item-1,如果为0，push进queue
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {number[]}
*/
var findOrder = (numCourses, prerequisites) => {
let inDegree = new Array(numCourses).fill(0) // 入度数组
let graph = {} // 哈希表
for (let i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][0]]++ // 构建入度数组
if (graph[prerequisites[i][1]]) { // 构建哈希表
graph[prerequisites[i][1]].push(prerequisites[i][0])
} else {
let list = []
list.push(prerequisites[i][0])
graph[prerequisites[i][1]] = list
}
}
let res = [] // 结果数组
let queue = [] // 存 入度为0的课
for (let i = 0; i < numCourses; i++) { // 初始时，推入所有入度为0的课
if (inDegree[i] === 0) queue.push(i)
}
while (queue.length) { // 没有了入度为0的课，没课可选，结束循环
let cur = queue.shift() // 出栈，代表选这门课
res.push(cur) // 推入结果数组
let toEnQueue = graph[cur] // 查看哈希表，获取对应的后续课程
if (toEnQueue && toEnQueue.length) { // 确保有后续课程
for (let i = 0; i < toEnQueue.length; i++) { // 遍历后续课程
inDegree[toEnQueue[i]]-- // 将后续课程的入度 -1
if (inDegree[toEnQueue[i]] == 0) { // 一旦减到0，让该课入列
queue.push(toEnQueue[i])
}
}
}
}
return res.length === numCourses ? res : [] // 选满了就返回res，否则返回[]
};难度简单959
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
通过次数236,161
提交次数342,498
// 第一个last节点是null，缓存head.next
/**
* 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) {
let p = head
let last = null
while(p) {
let cur = p.next
p.next = last
last = p
p = cur
}
return last
}
return head
};难度中等543
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
通过次数60,904
提交次数93,158
// 归并排序
var sortList = function(head) {
if (head == null || head.next === null) {
return head
}
let fastNode = head.next
let slowNode = head
while (fastNode && fastNode.next) {
slowNode = slowNode.next
fastNode = fastNode.next.next
}
let right = slowNode.next
slowNode.next = null
let l = sortList(head)
let r = sortList(right)
let p = new ListNode('')
let point = p
while (l && r) {
if (l.val <= r.val) {
point.next = new ListNode(l.val)
l = l.next
} else {
point.next = new ListNode(r.val)
r = r.next
}
point = point.next
}
point.next = l ? l : r
return p.next
};难度中等569
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
// 按照0拆分
var maxProduct = function(nums) {
let sum = 1;
let max = Number.MIN_SAFE_INTEGER;
for (let num of nums) {
sum *= num
if (max < sum) max = sum
if (sum === 0) sum = 1
}
sum = 1
for (let i = nums.length - 1; i >= 0; i--) {
sum *= nums[i]
if (max < sum) max = sum
if (sum === 0) sum = 1
}
return max
};
// 动态规划
var maxProduct = (nums) => {
let min = nums[0];
let max = nums[0];
let last = nums[0]
for (let i = 1; i < nums.length; i++) {
let temp1 = min * nums[i]
let temp2 = max * nums[i]
min = Math.min(temp1, temp2, nums[i])
max = Math.max(temp1, temp2, nums[i])
console.log(min)
console.log(max)
last = Math.max(last, max)
}
return last
}难度中等816收藏分享切换为英文关注反馈
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
// 找到倒数第n + 1个节点
var removeNthFromEnd = function(head, n) {
let fast = head
let slow = head
while(n > 0) {
fast = fast.next
n--
}
while(fast && fast.next) {
fast = fast.next
slow = slow.next
}
// 倒数第一个节点
if (fast === null) {
return head.next
}
slow.next = slow.next.next
return head
};难度简单598收藏分享切换为英文关注反馈
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
// 1. 利用hashmap
// var hasCycle = function(head) {
// if (!head || !head.next) return false
// let map =new Map()
// while(head) {
// let p = map.get(head)
// if (p) return true
// map.set(head, 1)
// head = head.next
// }
// return false
// };
// 2. 利用快慢指针
var hasCycle = function(head) {
if (!head || !head.next) return false
let slow = head
let fast = head.next
while(fast && fast.next) {
if (fast === slow) {
return true
}
fast = fast.next.next
slow = slow.next
}
return false
};难度简单664收藏分享切换为英文关注反馈
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表**：**
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
// 方法1 暴力
// 方法2 hash表方法
// 方法3 双指针
// 错的人迟早会走散，而对的人迟早会相逢！ a+c+b = b + c + a
var getIntersectionNode = function(headA, headB) {
let pointA = headA
let pointB = headB
while (pointA !== pointB) {
pointA = pointA ? pointA.next : headB
pointB = pointB ? pointB.next : headA
}
return pointA
};难度中等482
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
**说明：**不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
// 快慢指针 理解有点问题
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
if (head === null || head.next === null) return null
let slow = head
let fast = head
while(fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
fast = head
while (fast !== slow) {
fast = fast.next
slow = slow.next
}
return slow
}
}
return null
};
难度中等357收藏分享切换为英文关注反馈
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
通过次数44,717
提交次数84,929
// 用一个栈 push num、str、'['、 遇到 ']'开始出栈
/**
* @param {string} s
* @return {string}
*/
var decodeString = function(s) {
let stack = []
for (let st of s) {
if (st !== ']') {
stack.push(st)
continue
}
let str = ''
let cur = stack.pop()
while (cur !== '[') {
str = cur + str
cur = stack.pop()
}
let num = ''
cur = stack.pop()
while (!isNaN(cur)) {
num = cur + num
cur = stack.pop()
}
let result = str.repeat(num)
stack.push(cur)
stack.push(result)
}
return stack.join('')
};
// 容易写错的解法
var decodeString = (s) => {
let numStack = [] // 倍数num的等待栈
let strStack = [] // 待拼接的str的等待栈
let num = 0 // 倍数的“搬运工”
let result = '' // 字符串的“搬运工”
for (const char of s) { // 向右逐字符扫描
if (!isNaN(char)) { // 遇到数字
num = num * 10 + +char // js中+可以将数字字符转为数字
} else if (char === '[') { // 入栈的时机
strStack.push(result) // result进入strStack栈等待
result = '' // 完成进栈后 清零
numStack.push(num) // 倍数num进入栈等待
num = 0 // 完成进栈后 清零
} else if (char === ']') { // 出栈的时机，两个栈的栈顶出栈
let repeatTimes = numStack.pop() // 获取拷贝次数
result = strStack.pop() + result.repeat(repeatTimes) // 构建子串
} else { // 遇到字母，追加给result串
result += char
}
}
return result
}难度简单1590收藏分享切换为英文关注反馈
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
/**
* @param {string} s
* @return {boolean}
*/
// 中间两边法 [[{}]] 最中间总是有相邻的括号
var isValid = function(s) {
let dic = {
']': '[',
')': '(',
'}': '{'
}
let pre = ''
let stack = []
for (let st of s) {
if (!dic[st]) {
stack.push(st)
} else {
let p = stack.pop()
if (dic[st] !== p) return false
}
}
return !stack.length
};难度中等111
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
示例 2：
输入: n = 9
输出: 45
限制：
1 <= n <= 10000
// 利用 && + 递归
// 位运算
难度困难1313
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
1.暴力解法
2.动态规划 最短的板子减去自身的板子
var trap = function(height) {
let res = 0;
let n = height.length
let leftMax = []
let rightMax = []
let max = 0;
for (let i = 0; i < n; i++) {
leftMax[i] = max = Math.max(height[i], max)
}
max = 0
for (let j = n - 1 ; j >= 0; j--) {
rightMax[j] = max = Math.max(height[j], max)
}
for (let i = 0; i < n; i ++) {
res += Math.min(leftMax[i], rightMax[i]) - height[i]
}
return res
};难度中等469
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
**提示：**题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请**不要使用除法，**且在 O(n) 时间复杂度内完成此题。
进阶： 你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
var left = [1]
var right = []
right[nums.length - 1] = 1
for (let i = 1; i < nums.length; i++) {
left[i] = left[i - 1] * nums[i - 1]
}
for (let i = nums.length - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1]
}
let result = []
for (let i = 0; i < nums.length; i++) {
result.push(left[i] * right[i])
}
return result
};难度中等385收藏分享切换为英文关注反馈
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
// 螺旋矩阵 l r t b
var spiralOrder = function(matrix) {
if (!matrix.length) return []
let res = []
let l = 0, r = matrix.length - 1; t = 0, b = matrix.length - 1;
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
};难度困难409收藏分享切换为英文关注反馈
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
通过次数58,086
提交次数114,322
// 利用 currentNum - 1是否存在来减少复杂度
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
let s = new Set()
let maxLength = 0;
let currentNum = 0;
let currentLength = 0;
for (let item of nums) {
s.add(item)
}
for (const num of s) {
if (!s.has(num - 1)) {
currentLength = 1;
currentNum = num;
while(s.has(currentNum + 1)) {
currentLength ++
currentNum ++
}
maxLength = Math.max(currentLength, maxLength)
}
}
return maxLength;
};给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
通过次数93,883
提交次数121,348
/**
* @param {number[]} nums
* @return {number[][]}
*/
// 还有一个回溯法 不懂
var subsets = function(nums) {
let res = []
res.push([])
for (const item of nums) {
res.forEach(e => {
res.push(e.concat(item))
})
}
return res
};难度简单284收藏分享切换为英文关注反馈
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
// & 1 计算是否相等，移位，直到两个都为0
// 布莱恩算法，异或，数0，& n - 1,跳过非0
/**
* @param {number} x
* @param {number} y
* @return {number}
*/
var hammingDistance = function(x, y) {
let res = 0
while (x !== 0 || y!==0) {
if ((x & 1) !== (y & 1)) {
res++
}
x >>= 1
y >>= 1
}
return res
};
// 布莱恩算法
// var hammingDistance = function(x, y) {
// let v = x ^ y; // 异或：相同位为0，不同位为1
// let dis = 0;
// while (v) {
// v = v & (v - 1);
// ++dis;
// }
// return dis;
// };难度简单624
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
//投票算法 count计数器难度简单606
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
// 填充法
// 双指针
/*
* @lc app=leetcode.cn id=283 lang=javascript
*
* [283] 移动零
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
// var moveZeroes = function(nums) {
// let index = 0;
// for (let i = 0; i < nums.length; i++) {
// if (nums[i] !== 0) {
// nums[index] = nums[i]
// index++
// }
// }
// for (let i = index; i < nums.length; i++) {
// nums[i] = 0
// }
// };
var moveZeroes = function(nums) {
let i = 0, j = 0;
for (; i < nums.length; i++) {
if (nums[i] !== 0) {
let temp = nums[j]
nums[j] = nums[i]
nums[i] = temp
j++
}
}
};
// @lc code=end
难度简单364
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为*O(n)*的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
// - nums[nums[i] - 1]难度简单1011
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 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。// 一次遍历,缓存历史最小值，用当天股票减去历史最小值
var maxProfit = function(prices) {
let minValue = Number.MAX_SAFE_INTEGER
let maxValue = 0
for (let i = 0; i < prices.length; i++) {
let currentValue = prices[i] - minValue
minValue = prices[i] < minValue ? prices[i] : minValue
maxValue = currentValue > maxValue ? currentValue : maxValue
}
return maxValue
};难度简单1077
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
**注意：**给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
// 斐波那契
// dp[i] = dp[i - 1] + dp[i - 2]难度简单886
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
0 <= nums.length <= 1000 <= nums[i] <= 400
// 同 爬楼梯，从最后一个值来判断难度简单324
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :
- 输入的数组长度范围在 [1, 10,000]。
- 输入的数组可能包含重复元素 ，所以升序的意思是**<=。**
难度中等759收藏分享切换为英文关注反馈
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
let res = []
let track = []
backtrack(nums, track)
function backtrack(nums, track) {
if (nums.length === track.length) {
res.push([...track])
return
}
for (let num of nums) {
if (track.indexOf(num) !== -1) continue
track.push(num)
backtrack(nums, track)
track.pop()
}
}
return res
};难度中等1132收藏分享切换为英文关注反馈
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
// dfs
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
// dfs 判断结束条件
// left < n => + '('
// right < left => + ')'
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
let res = []
let path = ''
let left = 0, right = 0;
backtrack(res, path, left, right)
function backtrack(res, path, left, right) {
if (left === n && right === n) {
res.push(path)
return
}
if (left < n) {
backtrack(res, path + '(', left + 1, right)
}
if (right < left ) {
backtrack(res, path + ')', left, right + 1)
}
}
return res
};难度中等335收藏分享切换为英文关注反馈
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
进阶:
- 给出时间复杂度为**O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)**内用一趟扫描做到吗？
- 要求算法的空间复杂度为O(n)。
- 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
通过次数43,323
提交次数57,585
// 比特位计数 利用f(i) = f(i >> 1) + (i & 1)
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
let res = []
res [0] = 0
for (let i = 0; i <= num; i++) {
res[i] = res[i >> 1] + (i & 1)
}
return res
};难度中等745收藏分享切换为英文关注反馈
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
// 回溯法
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
const res = []
const path = []
backtracking(candidates, target)
function backtracking(arr, target) {
if (target === 0) {
res.push(path.slice())
return
}
if (target < 0) {
return
}
for (let i = 0; i < arr.length; i++) {
path.push(arr[i])
backtracking(arr.slice(i), target - arr[i])
path.pop()
}
}
return res
}难度中等501收藏分享切换为英文关注反馈
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
通过次数96,058
提交次数145,835
// 最小路径和 dp
// dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j-1])
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function(grid) {
for(var i = 0;i < grid.length;i++){
for(var j = 0;j < grid[0].length;j++){
if( i != 0 && j!= 0){
grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
}else if(i == 0 && j!=0){
grid[i][j] = grid[i][j-1]+grid[i][j];
}else if(i != 0 && j==0){
grid[i][j] = grid[i-1][j]+grid[i][j];
}else if(i == 0 && j==0){
continue;
}
}
}
return grid[grid.length-1][grid[0].length-1];
};难度中等745收藏分享切换为英文关注反馈
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
// 快慢指针，找环
/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function(nums) {
let fast = 0, slow = 0
do {
fast = nums[nums[fast]]
slow = nums[slow]
} while(fast !== slow)
let find = 0;
while (find !== slow) {
slow = nums[slow]
find = nums[find]
}
return slow
}; 难度中等589收藏分享切换为英文关注反馈
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
// 快速排序，找标记值，双指针移动
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
function quick(i, j) {
let left = i, right = j;
if (left > right) return
let temp = nums[left]
while (left !== right) {
while (nums[right] >= temp && left < right) {
right --
}
while (nums[left] <= temp && left < right) {
left ++
}
if (left < right) {
let t = nums[left]
nums[left] = nums[right]
nums[right] = t
}
}
nums[i] = nums[left]
nums[left] = temp
quick(i, left - 1)
quick(left + 1, j)
}
quick(0, nums.length - 1)
return nums[nums.length - k]
};难度中等383收藏分享切换为英文关注反馈
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意： 总人数少于1100人。
示例
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
// 按高矮排序，再进行插入
/**
* @param {number[][]} people
* @return {number[][]}
*/
var reconstructQueue = function(people) {
people.sort((a, b) => {
if (a[0] === b[0]) {
return a[1] - b[1]
} else {
return b[0] - a[0]
}
})
let ans = []
for (let i = 0; i < people.length; i++) {
ans.splice(people[i][1], 0, people[i])
}
return ans
};难度困难744收藏分享切换为英文关注反馈
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
// 1. 用栈,压入-1，(压入,)pop
// 2. 判断s[i] 和 s[i - 1]来组成动态规划
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let max = 0;
let dp = []
dp[0] = 0
// if (s[0] === '(' && s[1] === ')') {
// dp[1] = 2
// }
for (let i = 1; i < s.length; i++) {
if (s[i] === '(') {
dp[i] = 0
} else if (s[i] === ')' && s[i - 1] === '(') {
dp[i] = (dp[i - 2] || 0 ) + 2
} else if (s[i] === ')' && s[i - 1] === ')') {
if (s[i - dp[i - 1] - 1] === '(') {
dp[i] = dp[i - 1] + 2 + ((dp[i - dp[i - 1] - 2]) || 0)
} else {
dp[i] = 0
}
} else {
dp[i] = 0
}
max = Math.max(max, dp[i])
}
return max
};难度中等734收藏分享切换为英文关注反馈
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
// 双向链表+hash
class ListNode {
constructor(key, value) {
this.key = key
this.value = value
this.next = null
this.prev = null
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity
this.hashTable = {}
this.count = 0
this.dummyHead = new ListNode()
this.dummyTail = new ListNode()
this.dummyHead.next = this.dummyTail
this.dummyTail.prev = this.dummyHead
}
get(key) {
let node = this.hashTable[key]
if (node == null) return -1
this.moveToHead(node)
return node.value
}
put(key, value) {
let node = this.hashTable[key]
if (node == null) {
let newNode = new ListNode(key, value)
this.hashTable[key] = newNode
this.addToHead(newNode)
this.count++
if (this.count > this.capacity) {
this.removeLRUItem()
}
} else {
node.value = value
this.moveToHead(node)
}
}
moveToHead(node) {
this.removeFromList(node)
this.addToHead(node)
}
removeFromList(node) {
let tempForPrev = node.prev
let tempForNext = node.next
tempForPrev.next = tempForNext
tempForNext.prev = tempForPrev
}
addToHead(node) {
node.prev = this.dummyHead
node.next = this.dummyHead.next
this.dummyHead.next.prev = node
this.dummyHead.next = node
}
removeLRUItem() {
let tail = this.popTail()
delete this.hashTable[tail.key]
this.count--
}
popTail() {
let tailItem = this.dummyTail.prev
this.removeFromList(tailItem)
return tailItem
}
}难度中等282收藏分享切换为英文关注反馈
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例 1:
输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".
示例 2:
输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
// 判断回文字符串，遍历
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
let count = 0;
function countN(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
count++
left--
right++
}
}
for (let i = 0; i < s.length; i++) {
countN(i, i)
countN(i, i + 1)
}
return count
};难度中等475收藏分享切换为英文关注反馈
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
通过次数59,826
提交次数140,591
难度中等433收藏分享切换为英文关注反馈
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
通过次数86,803
提交次数135,774
// 从后往前 还有个栈的算法没看
var dailyTemperatures = function(T) {
let res = []
if (!T.length) return []
res[T.length - 1] = 0
for (let i = T.length - 2; i >= 0; i--) {
for (let j = i + 1; j < T.length; j += res[j]) {
if (T[i] < T[j]) {
res[i] = j - i
break
} else if (res[j] === 0) {
res[i] = 0
break
}
}
}
return res
};难度中等605收藏分享切换为英文关注反馈
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
let arr = new Array(m).fill([])
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0) {
arr[i][j] = 1t
} else if (j === 0) {
arr[i][j] = 1
} else {
arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
}
}
}
return arr[m - 1][n - 1]
};难度中等514收藏分享切换为英文关注反馈
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
let start = 0, end = nums.length - 1, middle
while(start <= end) {
middle = Math.floor((start + end) / 2)
if (nums[middle] === target) {
break;
} else if (nums[middle] > target) {
end = middle - 1
} else {
start = middle + 1
}
}
if (start > end) {
return [-1, -1]
}
let i = middle, j = middle;
while (nums[i - 1] === target) i--
while (nums[j + 1] === target) j++
return [i, j]
};难度中等804收藏分享切换为英文关注反馈
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
if (!digits.length) return []
const strMap = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
let result = ['']
for (let num of digits) {
let nextResult = []
let str = strMap[num]
for (let s of str) {
for (let n of result) {
nextResult.push(n + s)
}
}
result = nextResult
}
return result
};难度中等841
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
// 搜索旋转数组
var search = function(nums, target) {
if (!nums.length) return -1
let l = 0, r = nums.length - 1
while (l <= r) {
let m = Math.ceil((l + r) / 2)
if (target === nums[m]) return m
if (nums[l] <= nums[m]) {
// l ~ m
if (nums[l] <= target && target < nums[m]) {
r = m - 1
} else {
l = m + 1
}
} else {
// m ~ r
if (nums[m] < target && target <= nums[r]) {
l = m + 1
} else {
r = m - 1
}
}
}
return -1
};难度简单65
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例:
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
说明:
A.length == n + m
/**
* @param {number[]} A
* @param {number} m
* @param {number[]} B
* @param {number} n
* @return {void} Do not return anything, modify A in-place instead.
*/
// 从后往前添加
var merge = function(A, m, B, n) {
// [1,3,5,6,x,x,x,x,x]
// [2,4,7,8,10]
let p = m + n - 1, i = m - 1, j = n - 1
while (p >= 0) {
let l = i >= 0 ? A[i] : Number.MIN_SAFE_INTEGER
let r = j >= 0 ? B[j] : Number.MIN_SAFE_INTEGER
if (l > r) {
A[p] = l
i--
} else {
A[p] = r
j--
}
p--
}
return A
};难度中等513
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
通过次数99,614
提交次数180,544
// 三指针 0 ~ 1 ~ 2 往中间替换
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
if (!nums.length) return nums
let p1 = 0, p2 = nums.length - 1, p = 0;
while (p <= p2) {
if (nums[p] === 0) {
nums[p] = nums[p1]
nums[p1] = 0
p1++
p++
} else if (nums[p] === 1) {
p++
} else if (nums[p] === 2) {
nums[p] = nums[p2]
nums[p2] = 2
p2--
}
console.log(nums)
}
return nums
};难度中等404
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
if (!strs.length) return []
let dic = {}
for (let item of strs) {
const key = item.split('').sort().join()
if (!dic[key]) dic[key] = []
dic[key].push(item)
}
const result = []
for (let key in dic) {
result.push(dic[key])
}
return result
};难度中等409
给定一个非空的整数数组，返回其中出现频率前 *k* 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
通过次数68,567
提交次数113,177
// 桶排序
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
// 哈希表
// var topKFrequent = function(nums, k) {
// let dic = {}
// for (let item of nums) {
// if (dic[item]) {
// dic[item] ++
// } else {
// dic[item] = 1
// }
// }
// let keys = Object.keys(dic)
// keys.sort((pre, after) => dic[after] - dic[pre])
// return keys.slice(0, k)
// };
let topKFrequent = function(nums, k) {
let map = new Map(), arr = [...new Set(nums)]
nums.map((num) => {
if(map.has(num)) map.set(num, map.get(num)+1)
else map.set(num, 1)
})
// 如果元素数量小于等于 k
if(map.size <= k) {
return [...map.keys()]
}
return bucketSort(map, k)
};
// 桶排序
let bucketSort = (map, k) => {
let arr = [], res = []
map.forEach((value, key) => {
// 利用映射关系（出现频率作为下标）将数据分配到各个桶中
if(!arr[value]) {
arr[value] = [key]
} else {
arr[value].push(key)
}
})
// 倒序遍历获取出现频率最大的前k个数
for(let i = arr.length - 1;i >= 0 && res.length < k;i--){
if(arr[i]) {
res.push(...arr[i])
}
}
return res
}难度中等321
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 ：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
提示：
- 任务的总个数为
[1, 10000]。 n的取值范围为[0, 100]。
// 贪心算法 从小到大排序后 N + 1不断循环做减法 空白补位继续计数
/**
* @param {character[]} tasks
* @param {number} n
* @return {number}
*/
var leastInterval = function(tasks, n) {
let res = new Array(26).fill(0)
for (let item of tasks) {
res[item.charCodeAt() - 65] ++
}
res.sort((prev, next) => prev - next)
let time = 0;
while(res[25] > 0) {
let i = 0;
while (i <= n) {
if (res[25] === 0) break;
if (i < 26 && res[25 - i] > 0) {
res[25 - i] --
}
time++
i++
}
res.sort((prev, next) => prev - next)
}
return time
};难度简单514收藏分享切换为英文关注反馈
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
通过次数205,110
提交次数516,434
// KMP算法和boyer-moore
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
// var strStr = function(haystack, needle) {
// if (!needle) return 0
// return haystack.indexOf(needle)
// let p1 = 0, p2 = 0;
// while(p2 < haystack.length) {
// if ((p2 - p1 + 1 === needle.length) && haystack[p1] === needle[p1]) return p1
// }
// // for (let i = 0; i < needle.length; p++)
// };
const strStr = function(haystack, needle) {
if (needle === "") return 0;
if (haystack === "") return -1;
let inc = [];
// 计算偏移量
for (let i = 0; i < needle.length; i++) {
for (let j = 0; j <= i; j++) {
if (needle[j] !== needle[i - j]) {
inc[i] = j + 1;
break;
}
if (j === i && needle[j] === needle[i - j]) {
inc[i] = j + 1;
}
}
}
let i = 0;
let l = needle.length
while (i < haystack.length) {
for (let j = 0; j < l; j++) {
if (needle[j] !== haystack[i + j]) {
i += inc[j];
break;
}
if (j === l - 1 && needle[j] === haystack[i + j]) {
return i;
}
}
}
return -1;
};难度简单117收藏分享切换为英文关注反馈
在一个 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。
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var findNumberIn2DArray = function(matrix, target) {
if (!matrix.length) return false
let m = matrix.length
let n = matrix[0].length
let i = 0
let j = n - 1
while(i <= m - 1 && j >= 0) {
console.log('i', i, ' j', j)
let start = matrix[i][j]
if (target === start) {
return true
} else if (target > start) {
i++
} else {
j--
}
}
return false
};难度中等85
给你一根长度为 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
// 3k + b , 3最多的乘积
// 动态规划
// dp[i] = max(dp[i], max((i - j) * j, j * dp[i - j]))
class Solution {
public int cuttingRope(int n) {
if (n < 2) {
return 0;
}
int[] dp = new int[n + 1];
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = Math.max(Math.max(j * dp[i - j], j * (i - j)), dp[i]);
}
}
return dp[n];
}
}
难度简单36
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
提示：
1 <= nums.length <= 500001 <= nums[i] <= 10000
// 快速排序
/**
* @param {number[]} nums
* @return {number[]}
*/
var exchange = function(nums) {
let l = 0, r = nums.length - 1;
let t = nums[l]
while (l < r) {
while (nums[r] % 2 === 0 && l < r) {
r--
}
while (nums[l] % 2 === 1 && l < r) {
l++
}
if (l < r) {
let t = nums[r]
nums[r] = nums[l]
nums[l] = t
}
}
return nums
};难度中等90
输入两棵二叉树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
限制：
// 1.判断根节点是否包含B节点
// 2.递归，判断所有子节点是否包含B节点
var isSubStructure = function(A, B) {
if (!A || !B) {
return false
}
return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
function isSameTree(a, b) {
if (!b) {
return true
}
if (!a) {
return false
}
return a.val === b.val && isSameTree(a.left, b.left) && isSameTree(a.right, b.right)
}
};难度中等33
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
// 层序遍历 使用队列 先进先出
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var levelOrder = function(root) {
if (!root) return []
const res = []
const queue = [root]
while(queue.length) {
const node = queue.shift()
res.push(node.val)
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
return res
// if (!root) return []
// let res = []
// const print = (node, index) => {
// if (node) {
// res[index] = res[index] ? res[index] : []
// res[index].push(node.val)
// print(node.left, index + 1)
// print(node.right, index + 1)
// }
// }
// print(root, 0)
// return res.toString().split(',')
};难度中等245
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:
输入: [3,2,3]
输出: [3]
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
通过次数19,904
提交次数45,775
// 摩尔投票法
/**
* @param {number[]} nums
* @return {number[]}
*/
var majorityElement = function(nums) {
let num1, num2, count1 = 0, count2 = 0, c1 = 0, c2 = 0
for (let num of nums) {
console.log('num1', num1)
console.log('num2', num2)
if (num === num1) {
count1++
continue
}
if (num === num2) {
count2++
continue
}
if (count1 === 0) {
num1 = num
count1++
continue
}
if (count2 === 0) {
num2 = num
count2++
continue
}
count1--
count2--
}
let res = []
for (let num of nums) {
if (num1 === num) {
c1++
} else if (num2 === num) {
c2++
}
}
if (c1 > nums.length / 3) {
res.push(num1)
}
if (c2 > nums.length / 3) {
res.push(num2)
}
return res
};难度简单425
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
通过次数75,206
提交次数214,193
难度简单1034
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。X可以放在L(50) 和C(100) 的左边，来表示 40 和 90。C可以放在D(500) 和M(1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
字符串转罗马数字，从前往后加
难度中等624
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
通过次数150,049
提交次数224,930
// 递归解法
var swapPairs = function(head) {
if (!head || !head.next) return head
let firstNode = head
let secondNode = head.next
firstNode.next = swapPairs(secondNode.next)
secondNode.next = firstNode
return secondNode
};