https://www.hblyan.com/tag/Leecode/ https://www.hblyan.com/archives/131.html 2023-02-27T22:06:00+08:00 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。示例 1：输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。示例 2:输入：root = [] 输出：[]思路首先看到这道题，我是没有什么思路的（因为没怎么见过二叉树，完美二叉树...以至于他们有啥区别我还不知道）所以看了半小时没有任何思路~还是得多刷题多理解概念性的东西~主要思路是遍历每一层的节点，假设每层有N的节点，那么N-1就是最后一个节点。我们可以在遍历每一层的结点的同时将下一层推入当前栈，那么当到达第N层的N-1个节点就结束，到达下一层。/** * // 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) { return root } let que = [root] //首先加入我们的根节点 while (que.length > 0) { //当栈中存在元素就代表没有遍历完 let size = que.length; //记录当前层的节点数 for (let i = 0; i < size; i++) { //遍历当前层的节点数 const node = que.shift()//每次遍历，操作的节点 if (i < size - 1) { //如果不是N-1的节点，那么就指向右侧节点 node.next = que[0] } if (node.left != null) {//如果该节点存在下一层，那么就将他塞进栈中 que.push(node.left) } if (node.right != null) { que.push(node.right) } } } return root };温故而知新[link][item desc='完美二叉树, 完全二叉树和完满二叉树' name="完美二叉树, 完全二叉树和完满二叉树" link="https://blog.csdn.net/weixin_43955170/article/details/122887498" pic="https://img-blog.csdnimg.cn/f70e60d6f0474b99943f12e1c87e6c49.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWWFrZTE5NjU=,size_20,color_FFFFFF,t_70,g_se,x_16"][/link] https://www.hblyan.com/archives/129.html 2023-02-24T23:27:00+08:00 给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/max-area-of-island著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。[tag type="primary"]深度优先搜索[/tag] 示例 1：输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 输出：6 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。示例 2：输入：grid = [[0,0,0,0,0,0,0,0]] 输出：0思路首先考虑深度搜索优先算法，在遍历的到每个1的时候，将该1的上下左右延申去寻找对接数为1 则该岛屿面积+1优化性能，可以将每次参与面积计算的1置为0，则不会重复计算/** * @param {number[][]} grid * @return {number} */ var maxAreaOfIsland = function (grid) { let count = 0; let result = 0; let sr = 0; let sc = 0; function fill(sr, sc) { if (sr < 0 || sr >= grid.length || sc < 0 || sc >= grid[0].length) { return; } if (!grid[sr][sc]) { return } count++ grid[sr][sc] = 0 fill(sr + 1, sc) fill(sr - 1, sc) fill(sr, sc + 1) fill(sr, sc - 1) } //遍历每个数 for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[i].length; j++) { count = 0 fill(i, j) //计算岛屿面积 result = Math.max(result, count) //每次遇到岛屿 保留最大面积 } } return result };温故而知新计算数组的边界，一定要考虑 length是否相等。 https://www.hblyan.com/archives/128.html 2023-02-23T19:28:00+08:00 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的 子串 。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/permutation-in-string著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。[tag type="primary"]双指针[/tag] 示例 1：输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba").示例 2：输入：s1= "ab" s2 = "eidboaoo" 输出：false提示：1 <= s1.length, s2.length <= 104s1 和 s2 仅包含小写字母思路因为全是小写字母的字符串，可以根据对应的ASCLL码去比较是否相等或者计数用数组去记录字母的数量，下标表示对应的字母 比如 a => 97 那么 【a-z】 - a呢 就是【97-123】- 97 就是 0-26那可以用长度为26的数组去记录 s1 和 s2 中的目标字符串s2 的目标字符串我们可以用双指针去记录/** * @param {string} s1 * @param {string} s2 * @return {boolean} */ var checkInclusion = function (s1, s2) { let arr1 = new Array(26).fill(0) let arr2 = new Array(26).fill(0) for (let i = 0; i < s1.length; i++) { if (!s2[i]) return false ++arr1[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)] // 对应的元素就是 对应的数量值 ++arr2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)] } if (arr1.toString() === arr2.toString()) { return true } let star = 0; let end = star + s1.length - 1; while (end < s2.length - 1) { end++ if (s2[star] === s2[end]) { //优化(虽然没有看到实际的效率 占用内存还是和原来差不多)，如果窗口移动 减去的左边值和右边增加的值一样那么跳过本次比较操作 star++ continue; } --arr2[s2[star].charCodeAt(0) - 'a'.charCodeAt(0)] ++arr2[s2[end].charCodeAt(0) - 'a'.charCodeAt(0)] if (arr1.toString() === arr2.toString()) { return true } star++ } return false };温故而知新字符串获取ascll码 string.charCodeAt(index) [a-z] => [97-123] https://www.hblyan.com/archives/124.html 2023-02-22T08:48:00+08:00 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。示例 1：输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]示例 2：输入：head = [1], n = 1 输出：[]示例 3：输入：head = [1,2], n = 1 输出：[1]思路常规的链表寻找特殊节点，两次遍历利用手动记录的index取操作链表利用快慢指针寻找规律，当next为null时就可以找到该节点/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd1 = function (head, n) { let count = 1, next = head.next; while (next) { count++ next = next.next } let index = count - n + 1 let result = new ListNode(0, head); count = 1 let tmp = result; while (tmp) { if (count++ == index) { tmp.next = tmp.next.next; } else { tmp = tmp.next; } } return result.next; }; var removeNthFromEnd2 = function (head, n) { let star = new ListNode(0, head), end = new ListNode(0, head); let result1 = star, result2 = end; let count = 1; while (result2.next) { if (count > n) { result1 = result1.next } result2 = result2.next count++ } result1.next = result1.next.next return star.next; }; https://www.hblyan.com/archives/121.html 2023-02-21T16:06:00+08:00 给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/middle-of-the-linked-list著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。示例 1：输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.示例 2：输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。提示：给定链表的结点数介于 1 和 100 之间。思路第一种方法： 因为链表没有方法直接获取长度，所以先遍历了一遍，获取总长度然后取中间数。二次遍历截取到中间数直接返回。第二种方法：利用step步数。意思就是两个指针同时从起点开始运动，一个每次行走1，一个每次行走2，当第二个指针没有下一步操作的时候，则下一次的首指针为中间数。/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var middleNode1 = function (head) { let count = 1; let tmp = head.next; while (tmp != null) { tmp = tmp.next count++ } let index = count % 2 === 0 ? (count / 2 + 1) : Math.ceil(count / 2) tmp = head.next; let c = 1; while (tmp != null) { if (c++ === index - 1) return tmp tmp = tmp.next } return head; }; var middleNode2 = function (head) { let left = head, right = head; if (!left.next) return left //考虑特殊情况 while ((right.next.next != null && right.next.next.next != null)) { left = left.next; right = right.next.next; } return left.next; }; https://www.hblyan.com/archives/120.html 2023-02-20T21:29:00+08:00 猜数字游戏的规则如下：每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：-1：我选出的数字比你猜的数字小 pick < num1：我选出的数字比你猜的数字大 pick > num0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num返回我选出的数字。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/guess-number-higher-or-lower著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。示例 1： 输入：n = 10, pick = 6 输出：6 示例 2： 输入：n = 1, pick = 1 输出：1 示例 3： 输入：n = 2, pick = 1 输出：1 示例 4： 输入：n = 2, pick = 2 输出：2吐槽首先吐槽这个题目，很简单的题目，我看了十分钟没看懂题目什么意思？？？ 竟然就是你输入范围 N，然后系统已经生成了一个数字，guessNumber 去返回这个系统数字！！所以 需要我 猜什么？ 哈哈思路二分法比较每次中间数 guess返回的结果判断 大小，直到返回正确的数/** * Forward declaration of guess API. * @param {number} num your guess * @return -1 if num is higher than the picked number * 1 if num is lower than the picked number * otherwise return 0 * var guess = function(num) {} */ /** * @param {number} n * @return {number} */ var guessNumber = function (n) { let left = 0, mid = 0, right = n; while (left <= right) { mid = left + Math.floor((right - left) / 2) if (guess(mid) === 0) return mid; if (guess(mid) === -1) { right = mid - 1 } else { left = mid + 1 } } }; https://www.hblyan.com/archives/119.html 2023-02-19T14:49:00+08:00 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。示例 1：输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2：输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。示例 3：输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。提示：2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers 按 非递减顺序 排列-1000 <= target <= 1000仅存在一个有效答案思路1利用双指针确定当前数和差值（也就是要寻找的数），要寻找的数字就可以在剩余的数中利用二分法/** * @param {number[]} numbers * @param {number} target * @return {number[]} */ var twoSum = function (numbers, target) { let left = 0, length = numbers.length; function FindMid(arr, star, target) { let left1 = star + 1 let right1 = arr.length - 1 let mid = 0; while (left1 <= right1) { mid = left1 + Math.floor((right1 - left1) / 2) if (arr[mid] === target) return mid; if (arr[mid] < target) { left1 = mid + 1 } else { right1 = mid - 1 } } return -1; } while (left < length) { let value = target - numbers[left] let tmp = FindMid(numbers, left, value) if (tmp != -1) { return [left + 1, tmp + 1] } left++ } return };思路2纯双指针的用法，不过右指针需要每次遍历一遍，比较耗时，建议采用上述的 二分法 减少遍历次数/** * @param {number[]} numbers * @param {number} target * @return {number[]} */ var twoSum = function (numbers, target) { let left = 0, length = numbers.length, right = 1; while (left < length) { let value = target - numbers[left] right = left + 1 while (right < length) { if (numbers[right] === value) return [left + 1, right + 1] right++ } left++ } return }; https://www.hblyan.com/archives/117.html 2023-02-19T13:19:00+08:00 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/move-zeroes著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。示例 1:输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]示例 2:输入: nums = [0] 输出: [0]提示:1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1进阶：你能尽量减少完成的操作次数吗？思路双指针，左指针指向当前位，如果当前不为0则+1，右指针每次向右+1循寻找不为0的数替换/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ var moveZeroes = function (nums) { let left = 0, length = nums.length, right = 1; while (right < length && left < length) { let tmp = null if (nums[left]) { left++ right++ continue; } if (nums[right]) { tmp = nums[left] nums[left] = nums[right] nums[right] = tmp left++ } right++ } };总结TM的 这个题目 看着 挺简单的，刚开始做的复杂了，想的是两个指针一起运动 = = ！后来想到 以左指针为主就可以了 = = ！/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ var moveZeroes = function (nums) { let left = 0, length = nums.length, right = 1; while (left < length) { let tmp = null if (nums[left] === 0) { if (nums[right] != 0) { if (nums[right]) { tmp = nums[left] nums[left] = nums[right] nums[right] = tmp } left++ right++ } else { //这里会出现很多问题 比如 [0010] [0000] [0001]等，后来直接重写了 tmp = nums[left + 2] if (tmp ) { nums[left + 2] = nums[left] nums[left] = tmp left = left + 2 tmp = nums[right + 2] nums[right + 2] = nums[right] nums[right] = tmp } left = left + 2 right = right + 2 } } else if (nums[right] === 0) { left++ right++ } else { left = right + 1 right += 2 } } }; https://www.hblyan.com/archives/116.html 2023-02-18T14:40:00+08:00 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/squares-of-a-sorted-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。示例 1：输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]示例 2：输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]提示：1 <= nums.length <= 104-104 <= nums[i] <= 104nums 已按 非递减顺序 排序进阶：请你设计时间复杂度为 O(n) 的算法解决本问题思路根据题目可以总结出，数组是递增的顺序，因为说 是 非递减并且是排序的数组那么平方后，最大的数肯定是两头的数字，这里想到用双指针进行对比两头数字每次比较，大的值则插入返回数组中的头部/** * @param {number[]} nums * @return {number[]} */ var sortedSquares = function (nums) { let left = 0, right = nums.length - 1, result = [] while (left <= right) { if (left == right) { result.unshift(Math.pow(nums[right], 2)); left++ } //边界处理 else { if (Math.abs(nums[left]) < Math.abs(nums[right])) { //右侧大，则加入数组 右指针减1 result.unshift(Math.pow(nums[right], 2)) right-- } else { result.unshift(Math.pow(nums[left], 2)) //反之 left++ } } } return result; }; https://www.hblyan.com/archives/98.html 2023-02-11T23:06:00+08:00 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/two-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。示例 1：输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 3：输入：nums = [3,3], target = 6 输出：[0,1]思路利用Map key 唯一的特点，记录每次target与item的补数，单次循环即可满足查询条件/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { let result = [] let map = new Map() for(let i=0;i<nums.length;i++){ if(map.has(nums[i])){ result[0] = map.get(nums[i]) result[1] = i return result } map.set(target - nums[i],i) } return Array.from(reuslt); };