分类： leetcode

目标

给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。

示例 1：

输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2

示例 2：

输入：board = [["."]]
输出：0

说明：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 是 '.' 或 'X'

进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？

思路

这道题的描述很容易让人误解成只允许在'X'的位置上建造战舰，并且满足规则战舰不能相邻，问最多能造多少战舰。

但实际上题目的含义是，有一个棋盘，棋盘上放着战舰，每个战舰由k个'X'表示，战舰的形状是 1*k 或者 k*1，战舰的排放规则是不能相邻，让我们统计战舰数量。

刚开始想到的是使用一个二维数组保存是否访问过，从第一行开始从左到右访问，如果为'X'则向下延伸并将visited置为true。

后来看了题解，可以将原数组的'X'置为其它标记，这样就不用额外的空间了。

进阶的问题是不修改board，根据排列规则，仅统计战舰的起点，即上面与左边不能为'X'。

也有网友使用dfs来处理，子节点是下方与右侧的元素，如果是'X'则改为其它标记，否则返回。其实直接循环遍历更方便一些。

还有网友使用并查集计算连通分量，其实也没有必要。并查集主要用于快速判断元素是否属于同一个集合，统计集合中元素个数，集合元素的合并。这里仅需要连通分量个数，并且连通的关系很简单，纵向或横向，并不像图遍历那样复杂，直接计数即可。

代码

/**
 * @date 2024-06-11 8:40
 */
public class CountBattleships419 {

    /**
     * 网友题解
     * 一次扫描，不使用额外空间，不修改board
     * 统计左上顶点
     * 需满足条件：顶点左侧与上侧不能为'X'
     */
    public int countBattleships_v2(char[][] board) {
        int ans = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 'X' &&
                        (j == 0 || board[i][j - 1] != 'X') &&
                        (i == 0 || board[i - 1][j] != 'X')) {
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 看了题解，可以直接将board中的'X'置为'.'，这样就不需要额外的visited数组了
     * 一次扫描，但是修改了board
     */
    public int countBattleships_v1(char[][] board) {
        int res = 0;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            int j = 0;
            while (j < n) {
                if (board[i][j] == 'X') {
                    res++;
                    int k = i + 1;
                    while (k < m && board[k][j] == 'X') {
                        board[k][j] = '.';
                        k++;
                    }
                    while (j < n && board[i][j] == 'X') {
                        board[i][j] = '.';
                        j++;
                    }
                } else {
                    j++;
                }
            }
        }

        return res;
    }

    /**
     * 一次扫描，但是使用了额外的空间
     */
    public int countBattleships(char[][] board) {
        int res = 0;
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            int j = 0;
            while (j < n) {
                if (visited[i][j]) {
                    j++;
                    continue;
                }
                if (board[i][j] == 'X') {
                    res++;
                    int k = i;
                    while (k < m && board[k][j] == 'X') {
                        visited[k][j] = true;
                        k++;
                    }
                    while (j < n && board[i][j] == 'X') {
                        visited[i][j] = true;
                        j++;
                    }
                } else {
                    j++;
                }
            }
        }

        return res;
    }
}

性能

使用额外空间

不使用额外空间

目标

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

说明：

• 1 <= people.length <= 5 * 10^4
• 1 <= people[i] <= limit <= 3 * 10^4

思路

给定一个数组，数组元素是待救援人员的体重，每条救生艇最多载两人且体重不超过限制，问最少需要多少救生艇。

尽可能多地让两人乘一艇，将体重轻的与重的搭配，如果都是轻的则造成运力浪费。

因此先按体重从小到大排序，然后使用双指针将重的与轻的搭配即可。

代码

/**
 * @date 2024-06-10 21:18
 */
public class NumRescueBoats881 {

    public int numRescueBoats(int[] people, int limit) {
        int n = people.length;
        Arrays.sort(people);
        int end = Arrays.binarySearch(people, limit);
        if (end < 0) {
            end = -end - 1;
        }
        // [end,n) 下标小于end的元素均比limit小，end 为0则可直接返回n
        int res = n - end;
        int start = 0;
        while (start < end) {
            // 如果start == end -1 即仅剩start一个元素 不再重复累加
            // start < end 防止end - 1为负即end==0
            // 由于取开区间，不包括end，因此从end-1开始
            while (start < end - 1 && people[start] + people[end - 1] > limit) {
                end--;
                res++;
            }
            start++;
            end--;
            res++;
        }
        return res;
    }
}

性能

目标

桌子上有 n 个球，每个球的颜色不是黑色，就是白色。

给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。

在每一步中，你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。

示例 1：

输入：s = "101"
输出：1
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "011"。
最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。

示例 2：

输入：s = "100"
输出：2
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "010"。
- 交换 s[1] 和 s[2]，s = "001"。
可以证明所需的最小步数为 2 。

示例 3：

输入：s = "0111"
输出：0
解释：所有黑色球都已经在右侧。

说明：

• 1 <= n == s.length <= 10^5
• s[i] 不是 '0'，就是 '1'

思路

有一个数组，其元素值不是0就是1，现在需要将所有的1都移到右边，每一步可以选择相邻的两个元素交换其位置，问移动的最小步数。

从左向右遍历数组元素，如果值为1就累加cnt，如果值为0就将移动步数加上 cnt。简单来说就是遇到1就合并，记录其个数，遇到0就整体移动 res += cnt。每次移动都贪心地将0移至其最终位置上。

有网友提到可以使用归并排序记录逆序对。

还有网友是基于下标和计算的。因为最终0都在右边，其下标和可以通过等差数列求和得到。我们只需在遍历过程中记录0的个数，并累加0的下标，然后与最终状态的下标和相减即可。

代码

package medium;

/**
 * @date 2024-06-06 0:03
 */
public class MinimumSteps2938 {

    /**
     * 将黑球视为一个整体，遇到黑球则合并到一起增加其权重，这样就可以视为将一个带权黑球从左移到右，每一步都是必要的。
     * 这其实也算是在移动的过程中统计逆序对的个数
     */
    public long minimumSteps(String s) {
        long res = 0;
        int n = s.length();
        int i = 0;
        long cnt = 0;
        while (i < n) {
            if (s.charAt(i) == '0') {
                // 遇到0就移动  累加移动步数，可以使用双指针优化
                res += cnt;
            } else {
                // 遇到1则合并
                cnt++;
            }
            i++;
        }
        return res;
    }

    /**
     * 优化
     * 使用双指针可以减少累加次数
     */
    public long minimumSteps_v1(String s) {
        long res = 0;
        int n = s.length();
        int i = 0;
        // left指向1的位置，如果第一值是0，那么left与i一起右移
        // 如果第一个值是1，仅移动i，当遇到0时，左侧1的个数就是i-left
        // 本来从下标left到i元素个数为 i - left + 1，由于i指向的不是1，所以不用加1
        int left = 0;
        while (i < n) {
            if (s.charAt(i) == '0') {
                res += i - left;
                left++;
            }
            i++;
        }
        return res;
    }
}

性能