Javascript数据结构常见题目（一）
以下是每个问题的 JavaScript 实现：
1. 下一个更大元素 (循环数组)
function nextGreaterElements(nums) {
let n = nums.length;
let result = Array(n).fill(-1);
let stack = [];
for (let i = 0; i < 2 * n; i++) {
let num = nums[i % n];
while (stack.length && nums[stack[stack.length - 1]] < num) {
result[stack.pop()] = num;
}
if (i < n) stack.push(i);
}
return result;
}
2. 逆波兰表达式求值
function evalRPN(tokens) {
let stack = [];
for (let token of tokens) {
if (!isNaN(token)) {
stack.push(Number(token));
} else {
let b = stack.pop();
let a = stack.pop();
switch (token) {
case '+': stack.push(a + b); break;
case '-': stack.push(a - b); break;
case '*': stack.push(a * b); break;
case '/': stack.push(Math.trunc(a / b)); break;
}
}
}
return stack[0];
}
3. 二叉树的最大路径和
function maxPathSum(root) {
let maxSum = -Infinity;
function dfs(node) {
if (!node) return 0;
let left = Math.max(0, dfs(node.left));
let right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, left + right + node.val);
return Math.max(left, right) + node.val;
}
dfs(root);
return maxSum;
}
4. 从前序与中序遍历序列构造二叉树
function buildTree(preorder, inorder) {
if (!preorder.length || !inorder.length) return null;
let rootVal = preorder[0];
let root = { val: rootVal, left: null, right: null };
let mid = inorder.indexOf(rootVal);
root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
return root;
}
5. 从中序与后序遍历序列构造二叉树
function buildTreeFromInPost(inorder, postorder) {
if (!inorder.length || !postorder.length) return null;
let rootVal = postorder.pop();
let root = { val: rootVal, left: null, right: null };
let mid = inorder.indexOf(rootVal);
root.right = buildTreeFromInPost(inorder.slice(mid + 1), postorder);
root.left = buildTreeFromInPost(inorder.slice(0, mid), postorder);
return root;
}
6. 栈的链式存储
class StackNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedStack {
constructor() {
this.top = null;
}
push(value) {
let newNode = new StackNode(value);
newNode.next = this.top;
this.top = newNode;
}
pop() {
if (!this.top) return null;
let value = this.top.value;
this.top = this.top.next;
return value;
}
peek() {
return this.top ? this.top.value : null;
}
isEmpty() {
return this.top === null;
}
}
7. 下一个更大元素
function nextGreaterElement(nums1, nums2) {
let map = new Map();
let stack = [];
for (let num of nums2) {
while (stack.length && stack[stack.length - 1] < num) {
map.set(stack.pop(), num);
}
stack.push(num);
}
return nums1.map(num => map.get(num) || -1);
}
8. 括号匹配
function isValid(s) {
let stack = [];
let map = { ')': '(', '}': '{', ']': '[' };
for (let char of s) {
if (char in map) {
if (stack.pop() !== map[char]) return false;
} else {
stack.push(char);
}
}
return stack.length === 0;
}
9. 二叉树的最近公共祖先
function lowestCommonAncestor(root, p, q) {
if (!root || root === p || root === q) return root;
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root;
return left || right;
}
这些代码覆盖了您所列的所有问题，且在实践中非常实用。希望对您有所帮助！
以下是每个问题的 JavaScript 实现：
1. 最小栈
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(val) {
this.stack.push(val);
if (!this.minStack.length || val <= this.getMin()) {
this.minStack.push(val);
}
}
pop() {
if (this.stack.pop() === this.getMin()) {
this.minStack.pop();
}
}
top() {
return this.stack[this.stack.length - 1];
}
getMin() {
return this.minStack[this.minStack.length - 1];
}
}
2. 用栈实现队列
class MyQueue {
constructor() {
this.stackIn = [];
this.stackOut = [];
}
push(x) {
this.stackIn.push(x);
}
pop() {
this._move();
return this.stackOut.pop();
}
peek() {
this._move();
return this.stackOut[this.stackOut.length - 1];
}
empty() {
return !this.stackIn.length && !this.stackOut.length;
}
_move() {
if (!this.stackOut.length) {
while (this.stackIn.length) {
this.stackOut.push(this.stackIn.pop());
}
}
}
}
3. 二叉树的右视图
function rightSideView(root) {
if (!root) return [];
let result = [];
let queue = [root];
while (queue.length) {
let levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
let node = queue.shift();
if (i === levelSize - 1) result.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return result;
}
4. 表达式求值
function evaluateExpression(expression) {
let stack = [];
let num = 0;
let sign = 1;
let result = 0;
for (let char of expression) {
if (char === ' ') continue;
if (/\d/.test(char)) {
num = num * 10 + Number(char);
} else if (char === '+') {
result += sign * num;
num = 0;
sign = 1;
} else if (char === '-') {
result += sign * num;
num = 0;
sign = -1;
} else if (char === '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (char === ')') {
result += sign * num;
num = 0;
result *= stack.pop();
result += stack.pop();
}
}
return result + sign * num;
}
5. 验证二叉搜索树
function isValidBST(root, min = null, max = null) {
if (!root) return true;
if ((min !== null && root.val <= min) || (max !== null && root.val >= max)) {
return false;
}
return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}
6. 用队列实现栈
class MyStack {
constructor() {
this.queue = [];
}
push(x) {
this.queue.push(x);
let size = this.queue.length;
while (size > 1) {
this.queue.push(this.queue.shift());
size--;
}
}
pop() {
return this.queue.shift();
}
top() {
return this.queue[0];
}
empty() {
return !this.queue.length;
}
}
7. 二叉树的序列化与反序列化
class Codec {
serialize(root) {
if (!root) return 'null';
return `${root.val},${this.serialize(root.left)},${this.serialize(root.right)}`;
}
deserialize(data) {
let nodes = data.split(',');
function buildTree() {
let val = nodes.shift();
if (val === 'null') return null;
let node = { val: Number(val), left: null, right: null };
node.left = buildTree();
node.right = buildTree();
return node;
}
return buildTree();
}
}
8. 二叉树的最大深度
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
9. 二叉树的最小深度
function minDepth(root) {
if (!root) return 0;
if (!root.left) return 1 + minDepth(root.right);
if (!root.right) return 1 + minDepth(root.left);
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}
10. 路径总和
function hasPathSum(root, targetSum) {
if (!root) return false;
if (!root.left && !root.right) return root.val === targetSum;
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
这些实现涵盖了问题的核心逻辑，旨在高效地解决每个场景的问题。希望这些代码对您有帮助！
以下是每个问题的 JavaScript 解决方案：
1. 对称二叉树
function isSymmetric(root) {
function isMirror(t1, t2) {
if (!t1 && !t2) return true;
if (!t1 || !t2) return false;
return t1.val === t2.val && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}
return isMirror(root, root);
}
2. 二叉树的中序遍历
function inorderTraversal(root) {
let result = [];
function traverse(node) {
if (!node) return;
traverse(node.left);
result.push(node.val);
traverse(node.right);
}
traverse(root);
return result;
}
3. 二叉树的层序遍历
function levelOrder(root) {
if (!root) return [];
let result = [];
let queue = [root];
while (queue.length) {
let level = [];
let size = queue.length;
for (let i = 0; i < size; i++) {
let node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}
4. 二叉树的直径
function diameterOfBinaryTree(root) {
let diameter = 0;
function depth(node) {
if (!node) return 0;
let left = depth(node.left);
let right = depth(node.right);
diameter = Math.max(diameter, left + right);
return 1 + Math.max(left, right);
}
depth(root);
return diameter;
}
5. 二叉树的前序遍历
function preorderTraversal(root) {
let result = [];
function traverse(node) {
if (!node) return;
result.push(node.val);
traverse(node.left);
traverse(node.right);
}
traverse(root);
return result;
}
6. 二叉树的后序遍历
function postorderTraversal(root) {
let result = [];
function traverse(node) {
if (!node) return;
traverse(node.left);
traverse(node.right);
result.push(node.val);
}
traverse(root);
return result;
}
7. 翻转二叉树
function invertTree(root) {
if (!root) return null;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
}
8. 二叉树的所有路径
function binaryTreePaths(root) {
let paths = [];
function constructPaths(node, path) {
if (node) {
path += node.val;
if (!node.left && !node.right) {
paths.push(path);
} else {
path += '->';
constructPaths(node.left, path);
constructPaths(node.right, path);
}
}
}
constructPaths(root, '');
return paths;
}
9. 二又树的中序遍历（非递归）
function inorderTraversalIterative(root) {
let result = [];
let stack = [];
let current = root;
while (current || stack.length) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.push(current.val);
current = current.right;
}
return result;
}
10. 二分图检测
function isBipartite(graph) {
let colors = Array(graph.length).fill(0);
function dfs(node, color) {
if (colors[node] !== 0) return colors[node] === color;
colors[node] = color;
for (let neighbor of graph[node]) {
if (!dfs(neighbor, -color)) return false;
}
return true;
}
for (let i = 0; i < graph.length; i++) {
if (colors[i] === 0 && !dfs(i, 1)) return false;
}
return true;
}
11. 拓扑排序
function topologicalSort(numCourses, prerequisites) {
let graph = Array.from({ length: numCourses }, () => []);
let inDegree = Array(numCourses).fill(0);
let queue = [];
let result = [];
for (let [course, prereq] of prerequisites) {
graph[prereq].push(course);
inDegree[course]++;
}
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) queue.push(i);
}
while (queue.length) {
let course = queue.shift();
result.push(course);
for (let neighbor of graph[course]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) queue.push(neighbor);
}
}
return result.length === numCourses ? result : [];
}
这些实现涵盖了您列出的每个问题。代码力求简洁清晰，并使用了适当的数据结构和算法来提高效率。希望对您有所帮助！
以下是用 JavaScript 实现的解决方案：
1. 单源最短路径 (Dijkstra 算法)
function dijkstra(graph, start) {
let distances = Array(graph.length).fill(Infinity);
distances[start] = 0;
let visited = new Set();
while (visited.size < graph.length) {
let u = -1;
for (let i = 0; i < graph.length; i++) {
if (!visited.has(i) && (u === -1 || distances[i] < distances[u])) {
u = i;
}
}
visited.add(u);
for (let [v, weight] of graph[u]) {
distances[v] = Math.min(distances[v], distances[u] + weight);
}
}
return distances;
}
2. 关键连接 (桥检测)
function criticalConnections(n, connections) {
let graph = Array.from({ length: n }, () => []);
let discovery = Array(n).fill(-1);
let low = Array(n).fill(-1);
let bridges = [];
let time = 0;
for (let [u, v] of connections) {
graph[u].push(v);
graph[v].push(u);
}
function dfs(node, parent) {
discovery[node] = low[node] = time++;
for (let neighbor of graph[node]) {
if (neighbor === parent) continue;
if (discovery[neighbor] === -1) {
dfs(neighbor, node);
low[node] = Math.min(low[node], low[neighbor]);
if (low[neighbor] > discovery[node]) {
bridges.push([node, neighbor]);
}
} else {
low[node] = Math.min(low[node], discovery[neighbor]);
}
}
}
for (let i = 0; i < n; i++) {
if (discovery[i] === -1) dfs(i, -1);
}
return bridges;
}
3. 判断负权回路 (Bellman-Ford 算法)
function hasNegativeWeightCycle(n, edges) {
let distances = Array(n).fill(Infinity);
distances[0] = 0;
for (let i = 0; i < n - 1; i++) {
for (let [u, v, weight] of edges) {
if (distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
}
}
}
for (let [u, v, weight] of edges) {
if (distances[u] + weight < distances[v]) {
return true;
}
}
return false;
}
4. 判断图中是否存在环
function hasCycle(graph) {
let visited = new Set();
let stack = new Set();
function dfs(node) {
if (stack.has(node)) return true;
if (visited.has(node)) return false;
visited.add(node);
stack.add(node);
for (let neighbor of graph[node]) {
if (dfs(neighbor)) return true;
}
stack.delete(node);
return false;
}
for (let node = 0; node < graph.length; node++) {
if (dfs(node)) return true;
}
return false;
}
5. 图的深度优先搜索
function dfs(graph, start) {
let visited = new Set();
let result = [];
function explore(node) {
if (visited.has(node)) return;
visited.add(node);
result.push(node);
for (let neighbor of graph[node]) {
explore(neighbor);
}
}
explore(start);
return result;
}
6. 克隆图
function cloneGraph(node) {
if (!node) return null;
let map = new Map();
function clone(node) {
if (map.has(node.val)) return map.get(node.val);
let newNode = { val: node.val, neighbors: [] };
map.set(node.val, newNode);
for (let neighbor of node.neighbors) {
newNode.neighbors.push(clone(neighbor));
}
return newNode;
}
return clone(node);
}
7. 课程表 (拓扑排序)
function canFinish(numCourses, prerequisites) {
let graph = Array.from({ length: numCourses }, () => []);
let inDegree = Array(numCourses).fill(0);
for (let [course, prereq] of prerequisites) {
graph[prereq].push(course);
inDegree[course]++;
}
let queue = [];
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) queue.push(i);
}
let count = 0;
while (queue.length) {
let course = queue.shift();
count++;
for (let neighbor of graph[course]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) queue.push(neighbor);
}
}
return count === numCourses;
}
8. 最短路径 (Floyd-Warshall 算法)
function floydWarshall(graph) {
let dist = graph.map(row => [...row]);
let n = graph.length;
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
9. 图的广度优先搜索
function bfs(graph, start) {
let visited = new Set();
let queue = [start];
let result = [];
while (queue.length) {
let node = queue.shift();
if (visited.has(node)) continue;
visited.add(node);
result.push(node);
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
queue.push(neighbor);
}
}
}
return result;
}
这些实现涵盖了您所列出的所有问题。每种算法选择了高效且直观的方式，适合实际问题的解决。希望对您有所帮助！