leetcode刷题记录--数据结构；深度优先搜索算法；二叉树；平衡树；1020. 飞地的数量；1669. 合并两个链表；108. 将有序数组转换为二叉搜索树

1020. 飞地的数量

难度中等131

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1：

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

示例 2：

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。

class Solution {
    public int numEnclaves(int[][] grid) {
        int res = 0;
        for(int i = 1;i < grid.length-1;i++){
            for(int j = 1;j < grid[0].length-1;j++){
                int numberZ = 0;
                int numberF = 0;
                if(dfsZ(grid,i,j,numberZ) != 0 && dfsF(grid,i,j,numberF) != 0){
                    res += numberZ + numberF;
                }
            }
        }
        return res;
    }
    public int dfsZ(int [][]grid,int x,int y,int number){
        if(flag(x,y,grid)){
            if(grid[y][x+1] == 1){
                dfsZ(grid,x+1,y,number++);
            }
            if(grid[y+1][x] == 1){
                dfsZ(grid,x,y+1,number++);
            }
        }else {
            return 0;
        }
        return number;
    }

    public int dfsF(int [][]grid,int x,int y,int number){
        if(flag(x,y,grid)){
            if(grid[y][x-1] == 1){
                dfsF(grid,x-1,y,number++);
            }
            if(grid[y-1][x] == 1){
                dfsF(grid,x,y-1,number++);
            }
        }else {
            return 0;
        }
        return number;
    }
    public boolean flag(int x,int y,int [][]grid){
        if(x == grid[0].length || y == grid.length || x == 0 || y == 0){
            return false;
        }else{
            return true;
        }
    }
}

1669. 合并两个链表

难度中等40

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果：

请你返回结果链表的头指针。

示例 1：

输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

示例 2：

输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode res = list1;
        int i = 0;
        ListNode temp = res;
        ListNode temp1 = res;
        while(i < a-1){
            temp = temp.next;
            i++;
        }
        int j = 0;
        while(j <= b){
            temp1 = temp1.next;
            j++;
        }
        temp.next = list2;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = temp1;
        return res;
    }
}

108. 将有序数组转换为二叉搜索树

难度简单933

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 左右等分建立左右子树，中间节点作为子树根节点，递归该过程
        return nums == null ? null : buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }
        int m = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = buildTree(nums, l, m - 1);
        root.right = buildTree(nums, m + 1, r);
        return root;
    }
}