本文共 18919 字,大约阅读时间需要 63 分钟。
题目
解题思路
代码实现
var findRepeatNumber = function(nums) { nums.sort(); for(var i = 0; i < nums.length-1; i++) { if(nums[i] == nums[i+1]) return nums[i] }};
题目
解题思路
代码实现
var findNumberIn2DArray = function(matrix, target) { return matrix.flat(Infinity).includes(target)};
题目
解题思路
代码实现
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 = bottom; 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};
题目
解题思路
代码实现
var search = function(nums, target) { if (!nums.length) return 0; let left = 0, right = nums.length - 1; while (nums[left] !== target && left < nums.length) { ++left; } while (nums[right] !== target && right >= 0) { --right; } return left <= right ? right - left + 1 : 0;};
题目
解题思路
代码实现
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;};
题目
appendTail
和 deleteHead
,分别完成在队列尾部插入整数和在队列头部删除整数的功能deleteHead
操作返回 -1
)解题思路
代码实现
var CQueue = function() { this.stack1 = []; this.stack2 = [];};CQueue.prototype.appendTail = function(value) { this.stack1.push(value)};CQueue.prototype.deleteHead = function() { if(this.stack2.length){ return this.stack2.pop() } if(!this.stack1.length) return -1 while(this.stack1.length){ this.stack2.push(this.stack1.pop()) } return this.stack2.pop()};
题目
min
函数在该栈中min
、push
及 pop
的时间复杂度都是 O(1)
解题思路
...this.items
是ES6
扩展运算符语法,主要运用于函数的调用
代码实现
var MinStack = function() { this.items = []};MinStack.prototype.push = function(x) { this.items.push(x)};MinStack.prototype.pop = function() { this.items.pop()};MinStack.prototype.top = function() { return this.items[this.items.length - 1]};MinStack.prototype.min = function() { return Math.min(...this.items)};
题目
max_value
得到队列里的最大值max_value
、push_back
和 pop_front
的均摊时间复杂度都是O(1)
pop_front
和 max_value
需要返回 -1
解题思路
代码实现
var MaxQueue = function() { this.queue = []; this.dequeue = [];};MaxQueue.prototype.max_value = function() { return this.dequeue.length ? this.dequeue[0] : -1;};MaxQueue.prototype.push_back = function(value) { this.queue.push(value); while ( this.dequeue.length && value > this.dequeue[this.dequeue.length - 1] ) { this.dequeue.pop(); } this.dequeue.push(value);};MaxQueue.prototype.pop_front = function() { if (!this.dequeue.length) { return -1; } if (this.queue[0] === this.dequeue[0]) { this.dequeue.shift(); } return this.queue.shift();};
题目
nums
和滑动窗口的大小 k
,请找出所有滑动窗口里的最大值解题思路
代码实现
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;};
题目
解题思路
代码实现
var reversePrint = function(head) { const result = [] while(head !== null) { result.unshift(head.val) head = head.next } return result};
题目
解题思路
代码实现
var deleteNode = function(head, val) { if(val == head.val){ return head.next; } else{ let pre = head; let index=0; while(pre){ pre = pre.next; index++; if(pre.val == val){ break; } }; let previous; let current = head; for(let j=0;j
题目
解题思路
代码实现
var getKthFromEnd = function(head, k) { let res = head; while (head.next) { k--; if (k <= 0) { res = res.next; } head = head.next; } return res;};
题目
解题思路
代码实现
var reverseList = function(head) { var prev = null,cur=head,temp; while(cur){ temp = cur.next;//修改前先记住下一个节点 cur.next = prev; //改别指向,第一个节点prev是null, prev = cur; //记录前一个节点,供下次循环使用 cur = temp; // cur通过temp指向下一节点 } return prev;//cur会多循环直到null};
题目
解题思路
代码实现
var copyRandomList = function(head) { const visited = new Map() function dfs(head) { if(head === null) return null if(visited.has(head)) return visited.get(head) const copy = new Node(head.val) visited.set(head, copy) copy.next = dfs(head.next) copy.random = dfs(head.random) return copy } return dfs(head)};
题目
解题思路
代码实现
var getIntersectionNode = function(headA, headB) { const map = new Map(); let node = headA; while (node) { map.set(node, true); node = node.next; } node = headB; while (node) { if (map.has(node)) return node; node = node.next; } return null;};
题目
解题思路
整体流程
代码实现
var lengthOfLongestSubstring = function(s) { const length = s.length; const map = { }; // char => boolean 代表着char是否在目前的窗口内 let i = 0, j = 0; let ans = 0; while (i < length && j < length) { if (!map[s[j]]) { ans = Math.max(j - i + 1, ans); map[s[j]] = true; ++j; } else { // 如果char重复,那么缩小滑动窗口,并更新对应的map map[s[i]] = false; ++i; } } return ans;};
题目
解题思路
代码实现
var firstUniqChar = function(s) { if (s == '') return " "; for (let i = 0 ; i < s.length; i++) { if (s.lastIndexOf(s[i]) === s.indexOf(s[i])) { return s[i] } } return " ";};
题目
解题思路
代码实现
var buildTree = function(preorder, inorder) { if (!preorder.length || !inorder.length) { return null; } const rootVal = preorder[0]; const node = new TreeNode(rootVal); let i = 0; // i有两个含义,一个是根节点在中序遍历结果中的下标,另一个是当前左子树的节点个数 for (; i < inorder.length; ++i) { if (inorder[i] === rootVal) { break; } } 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;};
题目
解题思路
isSubStructure
的职能:判断 B 是否是 A 的子结构。是,返回 true;否则,尝试 A 的左右子树isSubTree
的职能:封装“判断 B 是否是 A 的子结构”的具体逻辑。代码实现
var isSubStructure = function(A, B) { // 题目约定:约定空树不是任意一个树的子结构 if (!A || !B) { return false; } return ( isSubTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B) );};function isSubTree(pRoot1, pRoot2) { // B树遍历完了,说明B是A的子结构 if (!pRoot2) { return true; } // A遍历完了,但是B还没有遍历完,那么B肯定不是A的子结构 if (!pRoot1) { return false; } if (pRoot1.val !== pRoot2.val) { return false; } return ( isSubTree(pRoot1.left, pRoot2.left) && isSubTree(pRoot1.right, pRoot2.right) );}
题目
解题思路
代码实现
var mirrorTree = function(root) { if (!root) { return null; } // 交换当前节点的左右节点 const leftCopy = root.left; root.left = root.right; root.right = leftCopy; // 对左右子树做相同操作 mirrorTree(root.left); mirrorTree(root.right); return root;};
题目
解题思路
代码实现
var isSymmetric = function(root) { if(root==null) return true; return dfs(root.left,root.right); function dfs(p,q){ if(!p || !q) return !p&&!q; if(p.val!==q.val) return false; return dfs(p.left,q.right) && dfs(p.right,q.left); }};
题目
序列化
和反序列化
二叉树解题思路
广度优先(BFS)遍历所有节点(包括空节点)
序列化流程如下
反序列化流程如下
反序列化函数的设计关键是:数组 nodes 取出元素的顺序和原二叉树层序遍历的顺序是对应的
代码实现
// 序列化var serialize = function(root) { if (!root) { return "[]"; } let res = ""; let node = root; const queue = [node]; while (queue.length) { const front = queue.shift(); if (front) { res += `${ front.val},`; queue.push(front.left); queue.push(front.right); } else { res += "#,"; } } res = res.substring(0, res.length - 1); // 去掉最后一个逗号 return `[${ res}]`;};// 反序列化var deserialize = function(data) { if (data.length <= 2) { return null; } const nodes = data.substring(1, data.length - 1).split(","); const root = new TreeNode(parseInt(nodes[0])); nodes.shift(); const queue = [root]; while (queue.length) { const node = queue.shift(); // 第一个是左节点,节点为空,直接跳过 const leftVal = nodes.shift(); if (leftVal !== "#") { node.left = new TreeNode(leftVal); queue.push(node.left); } // 第二个是右节点,节点为空,直接跳过 const rightVal = nodes.shift(); if (rightVal !== "#") { node.right = new TreeNode(rightVal); queue.push(node.right); } } return root;};
题目
解题思路
arr.length-1-k+1
,即以arr.length-k
为下标的元素代码实现
var kthLargest = function(root, k) { //中序遍历的模板代码 let arr=[]; function dfs(node){ if(!node) return; dfs(node.left); arr.push(node.val); dfs(node.right); } dfs(root); return arr[arr.length-k];};
题目
最近公共祖先的定义
解题思路
lowestCommonAncestor(root, p, q)
的功能是找出以root为根节点的两个节点p和q的最近公共祖先。 我们考虑: (root.val - p.val) * (root.val - q.val) <= 0
来判断即可代码实现
var lowestCommonAncestor = function(root, p, q) { if ((root.val - p.val) * (root.val - q.val) <= 0) return root if (p.val < root.val) return lowestCommonAncestor(root.left, p, q) return lowestCommonAncestor(root.right, p, q)};
题目
最近公共祖先的定义
解题思路
lowestCommonAncestor(root, p, q)
的功能是找出以root为根节点的两个节点p和q的最近公共祖先。 我们考虑: lowestCommonAncestor(root.right, p , q)
lowestCommonAncestor(root.left, p , q)
代码实现
var lowestCommonAncestor = function(root, p, q) { if (!root || root === p || root === q) return root; const left = lowestCommonAncestor(root.left, p, q); const right = lowestCommonAncestor(root.right, p, q); if (!left) return right; // 左子树找不到,返回右子树 if (!right) return left; // 右子树找不到,返回左子树 return root;};
题目
解题思路
代码实现
var minNumber = function(nums) { nums.sort((a, b) => { const s1 = a + "" + b; const s2 = b + "" + a; if (s1 < s2) return -1; if (s1 > s2) return 1; return 0; }); return nums.join("");};
题目
解题思路
代码实现
var levelOrder = function(root) { if (!root) { return []; } const data = []; const queue = [root]; while (queue.length) { const first = queue.shift(); data.push(first.val); first.left && queue.push(first.left); first.right && queue.push(first.right); } return data;};
题目
解题思路
代码实现
var levelOrder = function(root) { if (!root) return []; const queue = [root]; const res = []; // 存放遍历结果 let level = 0; // 代表当前层数 while (queue.length) { res[level] = []; // 第level层的遍历结果 let levelNum = queue.length; // 第level层的节点数量 while (levelNum--) { const front = queue.shift(); res[level].push(front.val); if (front.left) queue.push(front.left); if (front.right) queue.push(front.right); } level++; } return res;};
题目
解题思路
代码实现
var levelOrder = function(root) { if (!root) return []; const queue = [root]; const res = []; let level = 0; // 代表当前层数 while (queue.length) { res[level] = []; // 第level层的遍历结果 let levelNum = queue.length; // 第level层的节点数量 while (levelNum--) { const front = queue.shift(); res[level].push(front.val); if (front.left) queue.push(front.left); if (front.right) queue.push(front.right); } // 行号是偶数时,翻转当前层的遍历结果 if (level % 2) { res[level].reverse(); } level++; } return res;};
题目
解题思路
代码实现
var maxDepth = function(root) { if(!root) return 0; return Math.max(maxDepth(root.left),maxDepth(root.right))+1;};
题目
解题思路
代码实现
var isBalanced = function(root) { //获取深度 function getHeight(root){ if(!root) return 0; return Math.max(getHeight(root.left),getHeight(root.right))+1; } if(!root) return true; //平衡二叉树的判断条件 return isBalanced(root.left) && isBalanced(root.right) && Math.abs(getHeight(root.left)-getHeight(root.right))<=1;};
题目
解题思路
代码实现
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); };
转载地址:http://qdqwi.baihongyu.com/