童欧巴

[原题链接](https://leetcode-cn.com/problems/n-queens-ii/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-85d3/) 如果你想对位运算了解更多，请[稍移玉步](https://juejin.cn/post/6904595258915422215/) 皇后可以横、直、斜走，格数不限。题目要求皇后彼此之间不能相互攻击，也就是说需要满足任意两个皇后不能在同一行、同一列以及同一条斜线上。 熟悉这道题的同学，可以看出最直观的做法是利用回溯法进行求解。 遍历枚举出所有可能的选择，依次在每一行放置一个皇后，每次新放置的皇后不能和已经放置的皇后之间存在攻击。 为了降低时间复杂度，最理想的情况是在 O(1) 的时间内判断该位置所在的几条线上是否已经有皇后，可以利用集合来进行位置判断。 为了让你更好的理解，我利用回溯法将 4 皇后可能的解法画了出来。如下图所示：  下面这张图是两条对角线方向的斜线的规律，聪明的你肯定一眼就能看出来：  ### 一句话理解四种算法思想 - 分治：分而治之，先解决子问题，再将子问题的解合并求出原问题。 - 贪心：一条路走到黑，选择当下局部最优的路线，没有后悔药。 - 回溯：一条路走到黑，手握后悔药，可以无数次重来。(英雄联盟艾克大招无冷却)。 - 动态规划：上帝视角，手握无数平行宇宙的历史存档，同时发展出无数个未来。 ## 位运算回溯 先来明确几个概念和需要用到的公式： -...

[原题链接](https://leetcode-cn.com/problems/sliding-window-maximum/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-brwq/) ## 单调队列 1.维护一个单调递减队列，从大到小，左边是出口，右边是入口 2.每次 pop 时需要判断当前队列是否为空，并且如果当前要弹出的数值等于队列出口元素时，队列移除出口元素 3.每次 push 的元素如果大于入口元素，将队列后端的数值弹出，直到 push 的元素数值小于队列入口元素，保证单调性 4.max 可以获取当前队列的最大值 ```javascript const maxSlidingWindow = function(nums, k) { const n = nums.length class slideWindow { constructor() {...

[原题链接](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-iqd5/) ## 递归 dfs ```javascript const serialize = function(root) { const res = [] function dfs(node) { if (node === null) { res.push(null) return } res.push(node.val) dfs(node.left) dfs(node.right) } dfs(root)...

[原题链接](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-eoky/) ## 递归 dfs 1.从根节点开始遍历，递归左右子树 2.递归终止条件：当前节点为空或者等于 p 或 q，返回当前节点 3.p，q 可能在相同的子树中，也可能在不同的子树中 4.如果左右子树查到节点都不为空，则表示 p 和 q 分别在左右子树中，当前节点就是最近公共祖先 5.如果左右子树中有一个不为空，则返回为空节点 ```javascript const lowestCommonAncestor = function(root, p, q) { if (root === null ||...

[原题链接](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-bwev/) ## 递归 dfs 1. root 为空时，高度为 0 2. root 的左右子树都为空时，高度为 1 3. 如果左子树或者右子树为空时，返回另一棵子树的高度 4. 否则返回两棵子树的高度最小值 ```javascript const minDepth = function(root) { if (root === null) return 0 if (root.left...

[原题链接](https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-6gok/) ## 递归 dfs ```javascript const preorder = function(root) { if (root === null) return [] const res = [] function dfs(root) { if (root === null) return res.push(root.val) for...

[原题链接](https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-dpjn/) ## 递归 dfs ```javascript const postorder = function(root) { if (root === null) return [] const res = [] function dfs(root) { if (root === null) return; for (let...

[原题链接](https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-u2td/) ## 队列 bfs 使用队列进行广度优先遍历，level 数组存放当前层级的值，处理完一层后推入结果数组 result。 ```javascript const levelOrder = function(root) { if (root == null) return [] const result = [] const queue = [root] while (queue.length >...

[原题链接](https://leetcode-cn.com/problems/contains-duplicate/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-1d58/) ## 排序 排序后看相邻两位的数字 ```js const containsDuplicate = function(nums) { nums.sort((a, b) => a - b) const n = nums.length for (let i = 0; i < n - 1;...

[原题链接](https://leetcode-cn.com/problems/merge-two-binary-trees/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-09mj/) ## dfs 递归 在 root1 上直接修改，将两个树对应的节点相加后，赋值给 root1，然后递归执行两个左右子树。 ```js const mergeTrees = function(root1, root2) { const preOrder = function(root1, root2) { if (!root1) return root2 if (!root2) return root1 root1.val...