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]

给你一个大小为 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是否相等。

给你两个字符串 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 <= 104
s1 和 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]

给你一个链表，删除链表的倒数第 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;
};

给定一个头结点为 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;
};

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！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
        }
    }
};

给你一个下标从 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] <= 1000
numbers 按 非递减顺序 排列
-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


};

给定一个数组 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
        }
    }

};

给你一个按 非递减顺序 排序的整数数组 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] <= 104
nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 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;
};

给定一个整数数组 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);
   
};