标签： easy

目标

有 n 座山排成一列，每座山都有一个高度。给你一个整数数组 height ，其中 height[i] 表示第 i 座山的高度，再给你一个整数 threshold 。

对于下标不为 0 的一座山，如果它左侧相邻的山的高度 严格大于 threshold ，那么我们称它是 稳定 的。我们定义下标为 0 的山 不是 稳定的。

请你返回一个数组，包含所有 稳定 山的下标，你可以以 任意 顺序返回下标数组。

示例 1：

输入：height = [1,2,3,4,5], threshold = 2
输出：[3,4]
解释：
下标为 3 的山是稳定的，因为 height[2] == 3 大于 threshold == 2 。
下标为 4 的山是稳定的，因为 height[3] == 4 大于 threshold == 2.

示例 2：

输入：height = [10,1,10,1,10], threshold = 3
输出：[1,3]

示例 3：

输入：height = [10,1,10,1,10], threshold = 10
输出：[]

说明：

• 2 <= n == height.length <= 100
• 1 <= height[i] <= 100
• 1 <= threshold <= 100

思路

返回数组的稳定下标，如果一个元素的左侧相邻元素严格大于 threshold 称当前元素是稳定的。

代码

/**
 * @date 2024-12-19 21:50
 */
public class StableMountains3285 {

    public List<Integer> stableMountains(int[] height, int threshold) {
        List<Integer> res = new ArrayList<>();
        int prev = height[0];
        int n = height.length;
        for (int i = 1; i < n; i++) {
            if (prev > threshold) {
                res.add(i);
            }
            prev = height[i];
        }
        return res;
    }
}

性能

目标

给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。

你需要对 nums 执行 k 次操作，每次操作中：

• 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
• 将 x 替换为 x * multiplier 。

请你返回执行完 k 次乘运算之后，最终的 nums 数组。

示例 1：

输入：nums = [2,1,3,5,6], k = 5, multiplier = 2
输出：[8,4,6,5,6]
解释：
操作 结果
1 次操作后 [2, 2, 3, 5, 6]
2 次操作后 [4, 2, 3, 5, 6]
3 次操作后 [4, 4, 3, 5, 6]
4 次操作后 [4, 4, 6, 5, 6]
5 次操作后 [8, 4, 6, 5, 6]

示例 2：

输入：nums = [1,2], k = 3, multiplier = 4
输出：[16,8]
解释：
操作 结果
1 次操作后 [4, 2]
2 次操作后 [4, 8]
3 次操作后 [16, 8]

说明：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 10
• 1 <= multiplier <= 5

思路

有一个数组 nums，我们需要执行 k 次操作，每次操作选择数组中最小元素 min，并将它的值替换为 min * multiplier，返回最终的数组。

使用最小堆，堆中元素为 [value, index]，获取堆顶元素，将其值乘以 multiplier 再放回堆中，操作完 k 次之后，遍历堆中元素，根据 index 重写 nums 即可。需要注意处理值相等的情况，堆排序不稳定。

代码

/**
 * @date 2024-12-13 2:13
 */
public class GetFinalState3264 {

    public int[] getFinalState(int[] nums, int k, int multiplier) {
        int n = nums.length;
        // 注意这里需要处理相等的情况，堆排序是不稳定的
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> {
            int compare = nums[a] - nums[b];
            if (compare != 0){
                return compare;
            }
            return a - b;
        });
        for (int i = 0; i < n; i++) {
            q.offer(i);
        }
        for (int i = 0; i < k; i++) {
            int index = q.poll();
            nums[index] *= multiplier;
            q.offer(index);
        }
        return nums;
    }
}

性能

目标

给你一个下标从 0 开始、长度为 n 的整数排列 nums 。

如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为 半有序排列 。你可以执行多次下述操作，直到将 nums 变成一个 半有序排列 ：

• 选择 nums 中相邻的两个元素，然后交换它们。

返回使 nums 变成 半有序排列 所需的最小操作次数。

排列 是一个长度为 n 的整数序列，其中包含从 1 到 n 的每个数字恰好一次。

示例 1：

输入：nums = [2,1,4,3]
输出：2
解释：可以依次执行下述操作得到半有序排列：
1 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
2 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明，要让 nums 成为半有序排列，不存在执行操作少于 2 次的方案。

示例 2：

输入：nums = [2,4,1,3]
输出：3
解释：
可以依次执行下述操作得到半有序排列：
1 - 交换下标 1 和下标 2 对应元素。排列变为 [2,1,4,3] 。
2 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
3 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明，要让 nums 成为半有序排列，不存在执行操作少于 3 次的方案。

示例 3：

输入：nums = [1,3,4,2,5]
输出：0
解释：这个排列已经是一个半有序排列，无需执行任何操作。

说明：

• 2 <= nums.length == n <= 50
• 1 <= nums[i] <= 50
• nums 是一个 排列

思路

有一个数组 nums，求将最小值移动到第一个位置，最大值移动到最后一个位置需要的最小操作次数。

我们可以记录数组中第一个出现的最小值以及最后一个出现的最大值的下标，记为 minIndex 与 maxIndex，如果 minIndex > maxIndex，最少交换次数为 minIndex + n - maxIndex - 2，否则为 minIndex + n - maxIndex - 1。

注意：交换次数等于 minIndex 前面的元素个数 加上 maxIndex 后面的元素个数，如果 minIndex > maxIndex，当我们将最小值放到第一个位置时，maxIndex 已经向后移了一位。

代码

/**
 * @date 2024-12-11 8:47
 */
public class SemiOrderedPermutation2717 {

    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length;
        int minIndex = 0;
        int maxIndex = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            } else if (nums[i] >= nums[maxIndex]) {
                maxIndex = i;
            }
        }
        int res = minIndex + n - maxIndex - 1;
        return minIndex > maxIndex ? res - 1 : res;
    }
}

性能

目标

给定一个 8 x 8 的棋盘，只有一个 白色的车，用字符 'R' 表示。棋盘上还可能存在白色的象 'B' 以及黑色的卒 'p'。空方块用字符 '.' 表示。

车可以按水平或竖直方向（上，下，左，右）移动任意个方格直到它遇到另一个棋子或棋盘的边界。如果它能够在一次移动中移动到棋子的方格，则能够 吃掉 棋子。

注意：车不能穿过其它棋子，比如象和卒。这意味着如果有其它棋子挡住了路径，车就不能够吃掉棋子。

返回白车将能 吃掉 的 卒的数量。

示例 1：

输入：
[
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".","R",".",".",".","p"],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]
输出：3
解释：
在本例中，车能够吃掉所有的卒。

示例 2：

输入：
[
    [".",".",".",".",".",".",".","."],
    [".","p","p","p","p","p",".","."],
    [".","p","p","B","p","p",".","."],
    [".","p","B","R","B","p",".","."],
    [".","p","p","B","p","p",".","."],
    [".","p","p","p","p","p",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]
输出：0
解释：
象阻止了车吃掉任何卒。

示例 3：

输入：
[
    [".",".",".",".",".",".",".","."]
    [".",".",".","p",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    ["p","p",".","R",".","p","B","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".","B",".",".",".","."],
    [".",".",".","p",".",".",".","."],
    [".",".",".",".",".",".",".","."]
]
输出：3
解释： 
车可以吃掉位置 b5，d6 和 f5 的卒。

说明：

• board.length == 8
• board[i].length == 8
• board[i][j] 可以是 'R'，'.'，'B' 或 'p'
• 只有一个格子上存在 board[i][j] == 'R'

思路

8 x 8 的棋盘上有一个白车 R，若干个白象 B 和黑卒 'p'，空格由 '.' 表示。问白车能够吃掉黑卒的数量，注意车只能吃掉同行同列四个方向上第一个遇到的黑卒。

首先需要找到白车的位置，按行遍历棋盘，记录当前行上一个棋子，遇到白车时判断上一个棋子是否是黑卒，如果是计入结果，然后判断后面遇到的第一个棋子，如果是黑卒计入结果。当前行遍历完成后结束循环，按照同样方法遍历白车所在列即可。

代码

/**
 * @date 2024-12-06 9:05
 */
public class NumRookCaptures999 {

    public int numRookCaptures(char[][] board) {
        int res = 0;
        int rookRow = -1;
        int rookCol = -1;
        here:
        for (int i = 0; i < 8; i++) {
            // 首先按行遍历，找到白色车的位置(rookRow, rookCol)，同时判断它前后的棋子是否是黑卒
            char[] row = board[i];
            char last = '.';
            for (int j = 0; j < 8; j++) {
                if (row[j] == 'R') {
                    // 如果找到白车，判断当前行前面的棋子是否是黑卒
                    if (last == 'p') {
                        res++;
                    }
                    // 记录坐标
                    rookCol = j;
                    rookRow = i;
                } else if (rookCol != -1 && row[j] != '.') {
                    // 判断后面第一个棋子是否是黑卒
                    if (row[j] == 'p') {
                        res++;
                    }
                    break here;
                }
                if (row[j] != '.') {
                    last = row[j];
                }
            }
            if (rookCol != -1) {
                break;
            }
        }

        for (int i = rookRow - 1; i >= 0; i--) {
            if (board[i][rookCol] != '.') {
                // 找到上面第一个棋子
                if (board[i][rookCol] == 'p') {
                    res++;
                }
                break;
            }
        }
        for (int i = rookRow + 1; i < 8; i++) {
            if (board[i][rookCol] != '.') {
                // 找到下面第一个棋子
                if (board[i][rookCol] == 'p') {
                    res++;
                }
                break;
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 colors ，它表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

• colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
• colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。

环中连续 3 块瓷砖的颜色如果是 交替 颜色（也就是说中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。

请你返回 交替 组的数目。

注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。

示例 1：

输入：colors = [1,1,1]
输出：0

解释：

示例 2：

输入：colors = [0,1,0,0,1]
输出：3

解释：

交替组包括：

说明：

• 3 <= colors.length <= 100
• 0 <= colors[i] <= 1

思路

有一个环形二进制数组（认为首尾相邻），判断存在多少个交替组，如果元素与它左右相邻的两个元素值不相等，称这三个元素为一个交替组。

直接模拟判断即可，第一个元素的左邻居以及最后一个元素的右邻居需要特殊处理。也可以通过取模统一处理，定义 i 的初值为 n，i < 2n，循环内下标使用 (i - 1) % n，i % n，(i + 1) % n，不过没有必要对循环内的所有下标进行模运算，特殊处理效率更高。

官网题解循环使用的初值是 0，i < n，不过循环内部计算的是 (i - 1 + n) % n，i，(i + 1) % n，节省了两次 i % n 取余运算。

代码

/**
 * @date 2024-11-26 8:56
 */
public class NumberOfAlternatingGroups3206 {

    public int numberOfAlternatingGroups_v1(int[] colors) {
        int n = colors.length;
        int res = 0;
        boolean b = colors[n - 1] != colors[0];
        if (colors[0] != colors[1] && b) {
            res++;
        }
        if (colors[n - 1] != colors[n - 2] && b) {
            res++;
        }
        for (int i = 1; i < n - 1; i++) {
            if (colors[i - 1] != colors[i] && colors[i + 1] != colors[i]) {
                res++;
            }
        }
        return res;
    }

    public int numberOfAlternatingGroups(int[] colors) {
        int n = colors.length;
        int res = 0;
        for (int i = n; i < 2 * n; i++) {
            if (colors[(i - 1) % n] != colors[i % n] && colors[(i + 1) % n] != colors[i % n]) {
                res++;
            }
        }
        return res;
    }
}

性能

目标

给你一个整数 n ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 pick ，其中 pick[i] = [xi, yi] 表示玩家 xi 获得了一个颜色为 yi 的球。

如果玩家 i 获得的球中任何一种颜色球的数目 严格大于 i 个，那么我们说玩家 i 是胜利玩家。换句话说：

• 如果玩家 0 获得了任何的球，那么玩家 0 是胜利玩家。
• 如果玩家 1 获得了至少 2 个相同颜色的球，那么玩家 1 是胜利玩家。
• ...
• 如果玩家 i 获得了至少 i + 1 个相同颜色的球，那么玩家 i 是胜利玩家。

请你返回游戏中 胜利玩家 的数目。

注意，可能有多个玩家是胜利玩家。

示例 1：

输入：n = 4, pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]
输出：2
解释：
玩家 0 和玩家 1 是胜利玩家，玩家 2 和玩家 3 不是胜利玩家。

示例 2：

输入：n = 5, pick = [[1,1],[1,2],[1,3],[1,4]]
输出：0
解释：
没有胜利玩家。

示例 3：

输入：n = 5, pick = [[1,1],[2,4],[2,4],[2,4]]
输出：1
解释：
玩家 2 是胜利玩家，因为玩家 2 获得了 3 个颜色为 4 的球。

说明：

• 2 <= n <= 10
• 1 <= pick.length <= 100
• pick[i].length == 2
• 0 <= xi <= n - 1
• 0 <= yi <= 10

思路

有 n 个玩家，pick[i][j] 表示第 i 次操作，玩家 pick[i][0] 捡起了颜色为 pick[i][1] 的球，如果玩家 pick[i][0] 捡起同一颜色球的数量大于 pick[i][0] 则胜出，求胜出玩家的总数。

只要达到条件就胜出，并不是零和游戏。玩家与球的颜色是一对多的关系，并且需要针对每种颜色计数，判断是否存在某些颜色球的个数 大于 玩家编号。

使用二维数组 playerBall[i][c] 表示玩家 i 捡起颜色为 c 的球的数目，遍历 pick 数组计算 playerBall[i][c]，然后遍历 playerBall 统计胜出玩家的数目。

代码

/**
 * @date 2024-11-23 14:17
 */
public class WinningPlayerCount3238 {

    public int winningPlayerCount(int n, int[][] pick) {
        int[][] playerBall = new int[n][11];
        for (int i = 0; i < pick.length; i++) {
            // pick的i表示的是操作次数，j为0表示用户，j为1表示球的颜色
            playerBall[pick[i][0]][pick[i][1]]++;
        }
        int res = 0;
        for (int i = 0; i < playerBall.length; i++) {
            for (int j = 0; j < playerBall[i].length; j++) {
                if (playerBall[i][j] > i){
                    res++;
                    break;
                }
            }
        }
        return res;
    }
}

性能

目标

大小为 n x n 的矩阵 grid 中有一条蛇。蛇可以朝 四个可能的方向 移动。矩阵中的每个单元格都使用位置进行标识： grid[i][j] = (i * n) + j。

蛇从单元格 0 开始，并遵循一系列命令移动。

给你一个整数 n 表示 grid 的大小，另给你一个字符串数组 commands，其中包括 "UP"、"RIGHT"、"DOWN" 和 "LEFT"。题目测评数据保证蛇在整个移动过程中将始终位于 grid 边界内。

返回执行 commands 后蛇所停留的最终单元格的位置。

示例 1：

输入：n = 2, commands = ["RIGHT","DOWN"]
输出：3

示例 2：

输入：n = 3, commands = ["DOWN","RIGHT","UP"]
输出：1

说明：

• 2 <= n <= 10
• 1 <= commands.length <= 100
• commands 仅由 "UP"、"RIGHT"、"DOWN" 和 "LEFT" 组成。
• 生成的测评数据确保蛇不会移动到矩阵的边界外。

思路

有一个 n x n 矩阵 grid，初始时位置 (0, 0) 有条蛇，有一系列命令可以操作蛇移到，操作保证在矩阵内移动，问蛇最后停留的位置，格子的标识为 grid[i][j] = (i * n) + j。

直接模拟操作就可以了，将操作映射为行列的增减，直接计算位置即可。

最快的解法仅比较操作的第一个字符，并且上下移动直接减加 n，最后不用乘法计算。

代码

/**
 * @date 2024-11-21 0:39
 */
public class FinalPositionOfSnake3248 {

    /**
     * 最快题解
     */
    class Solution {
        public int finalPositionOfSnake(int n, List<String> commands) {
            int ans = 0;
            for (String c : commands) {
                if (c.charAt(0) == 'U') {
                    ans -= n;
                } else if (c.charAt(0) == 'D') {
                    ans += n;
                } else if (c.charAt(0) == 'L') {
                    --ans;
                } else {
                    ++ans;
                }
            }
            return ans;
        }
    }

    public static Map<String, int[]> map = new HashMap<>(4);

    static {
        map.put("UP", new int[]{-1, 0});
        map.put("RIGHT", new int[]{0, 1});
        map.put("DOWN", new int[]{1, 0});
        map.put("LEFT", new int[]{0, -1});
    }

    public int finalPositionOfSnake(int n, List<String> commands) {
        int[] move = new int[2];
        for (String command : commands) {
            move[0] += map.get(command)[0];
            move[1] += map.get(command)[1];
        }
        return move[0] * n + move[1];
    }

}

性能