被围绕的区域(深度优先搜索、广度优先搜索)、_x 的平方根(数学、二分查找)、按要求补齐数组(贪心、数组)

被围绕的区域(深度优先搜索、广度优先搜索)

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
输入：board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]] 输出：[[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 1：

示例 2：
输入：board = [[“X”]]
输出：[[“X”]]
提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 为 ‘X’ 或 ‘O’

解答：

class Solution {
    int[] dx = { 1, -1, 0, 0 };
    int[] dy = { 0, 0, 1, -1 };
    public void solve(char[][] board) {
        int n = board.length;
        if (n == 0) {
            return;
        }
        int m = board[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O') {
                queue.offer(new int[] { i, 0 });
            }
            if (board[i][m - 1] == 'O') {
                queue.offer(new int[] { i, m - 1 });
            }
        }
        for (int i = 1; i < m - 1; i++) {
            if (board[0][i] == 'O') {
                queue.offer(new int[] { 0, i });
            }
            if (board[n - 1][i] == 'O') {
                queue.offer(new int[] { n - 1, i });
            }
        }
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            board[x][y] = 'A';
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O') {
                    continue;
                }
                queue.offer(new int[] { mx, my });
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
}

x 的平方根(数学、二分查找)

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 _x _是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

解答：

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = 46340;
        while (left < right) {
            int mid = (left + right) / 2;
            if (mid * mid < x)
                left = mid + 1;
            else if (mid * mid > x)
                if ((mid - 1) * (mid - 1) <= x)
                    return mid - 1;
                else
                    right = mid - 1;
            else
                return mid;
        }
        if (left * left > x)
            return left - 1;
        return left;
    }
}

按要求补齐数组(贪心、数组)

给定一个已排序的正整数数组 _nums，_和一个正整数 _n 。_从 [1, n] 区间内选取任意个数字补充到 _nums _中，使得 [1, n] 区间内的任何数字都可以用 _nums _中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。
示例 1:
输入: nums = [1,3], n = 6
输出: 1
解释: 根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。 现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。 其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。 所以我们最少需要添加一个数字。
示例 2:
输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2, 4]。
示例 3:
输入: nums = [1,2,2], n = 5
输出: 0

解答：

class Solution {
    public int minPatches(int[] nums, int n) {
        int patches = 0, i = 0;
        long miss = 1;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss)
                miss += nums[i++];
            else {
                miss += miss;
                patches++;
            }
        }
        return patches;
    }
}

本文内容到此结束了，
如有收获欢迎点赞👍收藏💖关注✔️，您的鼓励是我最大的动力。
如有错误❌疑问💬欢迎各位大佬指出。
保持热爱，奔赴下一场山海。🏃🏃🏃