标签： easy

目标

你有一个下标从 0 开始、长度为 偶数 的整数数组 nums ，同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏，游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下：

• 每一轮，Alice 先从 nums 中移除一个 最小 元素，然后 Bob 执行同样的操作。
• 接着，Bob 会将移除的元素添加到数组 arr 中，然后 Alice 也执行同样的操作。
• 游戏持续进行，直到 nums 变为空。

返回结果数组 arr 。

示例 1：

输入：nums = [5,4,2,3]
输出：[3,2,5,4]
解释：第一轮，Alice 先移除 2 ，然后 Bob 移除 3 。然后 Bob 先将 3 添加到 arr 中，接着 Alice 再将 2 添加到 arr 中。于是 arr = [3,2] 。
第二轮开始时，nums = [5,4] 。Alice 先移除 4 ，然后 Bob 移除 5 。接着他们都将元素添加到 arr 中，arr 变为 [3,2,5,4] 。

示例 2：

输入：nums = [2,5]
输出：[5,2]
解释：第一轮，Alice 先移除 2 ，然后 Bob 移除 5 。然后 Bob 先将 5 添加到 arr 中，接着 Alice 再将 2 添加到 arr 中。于是 arr = [5,2] 。

说明：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• nums.length % 2 == 0

思路

将数组从小到大排序，两个元素为一组，交换组内的元素。

代码

/**
 * @date 2024-07-12 10:16
 */
public class NumberGame2974 {
    public int[] numberGame(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i += 2) {
            int tmp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = tmp;
        }
        return nums;
    }
}

性能

目标

给你一个下标从 0 开始的 正 整数数组 nums 。

如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。

请你返回 nums 中 移除递增 子数组的总数目。

注意 ，剩余元素为空的数组也视为是递增的。

子数组 指的是一个数组中一段连续的元素序列。

示例 1：

输入：nums = [1,2,3,4]
输出：10
解释：10 个移除递增子数组分别为：[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4] 和 [1,2,3,4]。移除任意一个子数组后，剩余元素都是递增的。注意，空数组不是移除递增子数组。

示例 2：

输入：nums = [6,5,7,8]
输出：7
解释：7 个移除递增子数组分别为：[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8] 。
nums 中只有这 7 个移除递增子数组。

示例 3：

输入：nums = [8,7,6,6]
输出：3
解释：3 个移除递增子数组分别为：[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为移除 [8,7] 后 nums 变为 [6,6] ，它不是严格递增的。

说明：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

思路

有一个正整数数组，如果移除某些子数组可以使得剩余元素严格递增，则称为移除递增子数组。求移除递增子数组的个数。

显然移除递增子数组 [i, j] 后，前后的子数组严格递增，且 nums[i - 1] < nums[j + 1]。我们的目标是要找到有多少种 i, j 的组合满足条件，假设 i ≤ j。

这题的难度和我的预期不一致，作为一道简单题，编码过程也太过复杂了，边界处理以及各种特殊情况太容易出错了。

先考虑暴力求解吧，枚举i, j的组合，遍历其余元素判断是否严格递增。

看了评论，这个数据范围改一下就是一道困难题 2972.统计移除递增子数组的数目II。

代码

/**
 * @date 2024-07-10 1:27
 */
public class IncremovableSubarrayCount2970 {

    public int incremovableSubarrayCount(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            here:
            for (int j = i; j < n; j++) {
                int last = -1;
                for (int k = 0; k < n; k++) {
                    if ((k < i || k > j) && nums[k] > last) {
                        last = nums[k];
                    } else if (k < i || k > j) {
                        continue here;
                    }
                }
                res++;
            }
        }
        return res;
    }

}

性能

O(n^3)

目标

给你一个下标从 0 开始、大小为 m x n 的整数矩阵 matrix ，新建一个下标从 0 开始、名为 answer 的矩阵。使 answer 与 matrix 相等，接着将其中每个值为 -1 的元素替换为所在列的 最大 元素。

返回矩阵 answer 。

示例 1：

输入：matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
输出：[[1,2,9],[4,8,6],[7,8,9]]
解释：上图显示了发生替换的元素（蓝色区域）。
- 将单元格 [1][1] 中的值替换为列 1 中的最大值 8 。
- 将单元格 [0][2] 中的值替换为列 2 中的最大值 9 。

示例 2：

输入：matrix = [[3,-1],[5,2]]
输出：[[3,2],[5,2]]
解释：上图显示了发生替换的元素（蓝色区域）。

说明：

• m == matrix.length
• n == matrix[i].length
• 2 <= m, n <= 50
• -1 <= matrix[i][j] <= 100
• 测试用例中生成的输入满足每列至少包含一个非负整数。

思路

使用矩阵各列的最大值替换该列中值为-1的元素。

先求出各列的最大值，然后替换。

代码

/**
 * @date 2024-07-05 0:26
 */
public class ModifiedMatrix3033 {

    /**
     * 优化到一个循环中，使用局部遍历保存当前列的最大值，
     * 没必要使用数组保存所有列的最大值然后再处理
     */
    public int[][] modifiedMatrix_v1(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < n; i++) {
            int max = 0;
            for (int j = 0; j < m; j++) {
                max = Math.max(max, matrix[j][i]);
            }
            for (int j = 0; j < m; j++) {
                if (matrix[j][i] == -1) {
                    matrix[j][i] = max;
                }
            }
        }
        return matrix;
    }

    public int[][] modifiedMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] max = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                max[i] = Math.max(max[i], matrix[j][i]);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[j][i] == -1) {
                    matrix[j][i] = max[i];
                }
            }
        }
        return matrix;
    }
}

性能

目标

如果一个整数能够被其各个数位上的数字之和整除，则称之为 哈沙德数（Harshad number）。给你一个整数 x 。如果 x 是 哈沙德数 ，则返回 x 各个数位上的数字之和，否则，返回 -1 。

示例 1：

输入： x = 18
输出： 9
解释： x 各个数位上的数字之和为 9 。18 能被 9 整除。因此 18 是哈沙德数，答案是 9 。

示例 2：

输入： x = 23
输出： -1
解释： x 各个数位上的数字之和为 5 。23 不能被 5 整除。因此 23 不是哈沙德数，答案是 -1 。

说明：

• 1 <= x <= 100

思路

判断给定的整数x的各位数字之和能否整除x，如果可以返回各位数字之和，否则返回-1。

代码

/**
 * @date 2024-07-03 0:40
 */
public class SumOfTheDigitsOfHarshadNumber3099 {

    public int sumOfTheDigitsOfHarshadNumber(int x) {
        int sum = 0;
        // 容易出错的点是直接对x进行修改，后面求余的时候就错了
        int digit = x;
        while (digit > 0) {
            sum += digit % 10;
            digit /= 10;
        }
        return x % sum == 0 ? sum : -1;
    }
}

性能

目标

给你一个用字符串表示的正整数 num ，请你以字符串形式返回不含尾随零的整数 num 。

示例 1：

输入：num = "51230100"
输出："512301"
解释：整数 "51230100" 有 2 个尾随零，移除并返回整数 "512301" 。

示例 2：

输入：num = "123"
输出："123"
解释：整数 "123" 不含尾随零，返回整数 "123" 。

说明：

• 1 <= num.length <= 1000
• num 仅由数字 0 到 9 组成
• num 不含前导零

思路

去掉字符串末尾的0。

代码

/**
 * @date 2024-06-29 21:45
 */
public class RemoveTrailingZeros2710 {

    public String removeTrailingZeros(String num) {
        int n = num.length() - 1;
        while (n >= 0 && num.charAt(n) == '0') {
            n--;
        }
        return num.substring(0, n + 1);
    }
}

性能

目标

力扣城计划在两地设立「力扣嘉年华」的分会场，气象小组正在分析两地区的气温变化趋势，对于第 i ~ (i+1) 天的气温变化趋势，将根据以下规则判断：

• 若第 i+1 天的气温 高于 第 i 天，为 上升 趋势
• 若第 i+1 天的气温 等于 第 i 天，为 平稳 趋势
• 若第 i+1 天的气温 低于 第 i 天，为 下降 趋势

已知 temperatureA[i] 和 temperatureB[i] 分别表示第 i 天两地区的气温。 组委会希望找到一段天数尽可能多，且两地气温变化趋势相同的时间举办嘉年华活动。请分析并返回两地气温变化趋势相同的最大连续天数。

即最大的 n，使得第 i~i+n 天之间，两地气温变化趋势相同

示例 1：

输入： temperatureA = [21,18,18,18,31] temperatureB = [34,32,16,16,17]
输出：2
解释：如下表所示， 第 2～4 天两地气温变化趋势相同，且持续时间最长，因此返回 4 - 2 = 2

天数	0~1	1~2	2~3	3~4
变化趋势A	下降	平稳	平稳	上升
变化趋势B	下降	下降	平稳	上升

示例 2：

输入： temperatureA = [5,10,16,-6,15,11,3] temperatureB = [16,22,23,23,25,3,-16]
输出：3

说明：

• 2 <= temperatureA.length == temperatureB.length <= 1000
• -20 <= temperatureA[i], temperatureB[i] <= 40

思路

简单的计数，容易出错的点是忘记比较最后的cnt。

知识点：

• 如何比较变化是否相同，使用API Integer.compare 或者 计算 (x > y) - (x < y)， boolean 值可以隐式转换成 0 或者 1。最直接的就是判断(a>b && c>d) || (a==b && c==d) || (a<b && c<d)

代码

/**
 * @date 2024-06-21 0:35
 */
public class TemperatureTrendLCP61 {

    public int temperatureTrend_v1(int[] temperatureA, int[] temperatureB) {
        int n = temperatureA.length;
        int res = 0;
        int cnt = 0;
        for (int i = 1; i < n; i++) {
            if (Integer.compare(temperatureA[i], temperatureA[i - 1]) == Integer.compare(temperatureB[i], temperatureB[i - 1])) {
                cnt++;
            } else {
                res = Math.max(res, cnt);
                cnt = 0;
            }
        }
        return Math.max(res, cnt);
    }

}

性能

目标

给你两个字符串 a 和 b，请返回 这两个字符串中 最长的特殊序列 的长度。如果不存在，则返回 -1 。

「最长特殊序列」 定义如下：该序列为 某字符串独有的最长子序列（即不能是其他字符串的子序列） 。

字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。

• 例如，"abc" 是 "aebdc" 的子序列，因为删除 "aebdc" 中斜体加粗的字符可以得到 "abc" 。 "aebdc" 的子序列还包括 "aebdc" 、 "aeb" 和 "" (空字符串)。

示例 1：

输入: a = "aba", b = "cdc"
输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。

示例 2：

输入：a = "aaa", b = "bbb"
输出：3
解释: 最长特殊序列是 "aaa" 和 "bbb" 。

示例 3：

输入：a = "aaa", b = "aaa"
输出：-1
解释: 字符串 a 的每个子序列也是字符串 b 的每个子序列。同样，字符串 b 的每个子序列也是字符串 a 的子序列。

说明：

• 1 <= a.length, b.length <= 100
• a 和 b 由小写英文字母组成

思路

求两个字符串独有子序列的最大长度。很明显，如果二者长度不等则最大独有子序列就是最长字符串长度；如果二者长度相等，则需要看字符串是否相等，如果相等则表明没有独有子序列，返回-1，否则返回字符串长度。

代码

/**
 * @date 2024-06-16 0:07
 */
public class FindLUSlength521 {
    public int findLUSlength(String a, String b) {
        if (a.equals(b)) {
            return -1;
        } else {
            return Math.max(a.length(), b.length());
        }
    }
}

性能