标签： easy

目标

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们分别含有 n 和 m 个元素。

请你计算以下两个数值：

• 统计 0 <= i < n 中的下标 i ，满足 nums1[i] 在 nums2 中 至少 出现了一次。
• 统计 0 <= i < m 中的下标 i ，满足 nums2[i] 在 nums1 中 至少 出现了一次。

请你返回一个长度为 2 的整数数组 answer ，按顺序 分别为以上两个数值。

示例 1：

输入：nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
输出：[3,4]
解释：分别计算两个数值：
- nums1 中下标为 1 ，2 和 3 的元素在 nums2 中至少出现了一次，所以第一个值为 3 。
- nums2 中下标为 0 ，1 ，3 和 4 的元素在 nums1 中至少出现了一次，所以第二个值为 4 。

示例 2：

输入：nums1 = [3,4,2,3], nums2 = [1,5]
输出：[0,0]
解释：两个数组中没有公共元素，所以两个值都为 0 。

说明：

• n == nums1.length
• m == nums2.length
• 1 <= n, m <= 100
• 1 <= nums1[i], nums2[i] <= 100

思路

有两个数组，统计在当前数组中出现，同时也在另一数组中出现的元素个数，即公共元素个数。数组 [1, 1, 1, 2] 与 [1, 2, 3] 的公共元素是 1，2，公共元素个数分别是 4、2。

常规的做法是使用HashSet分别保存数组元素，然后再次遍历数组判断是否是公共元素。由于数据范围比较小，可以直接使用数组计数。

代码

/**
 * @date 2024-07-16 0:14
 */
public class FindIntersectionValues2956 {

    /**
     * 改进
     */
    public int[] findIntersectionValues_v1(int[] nums1, int[] nums2) {
        int[] count1 = new int[101];
        for (int i : nums1) {
            count1[i]++;
        }
        int a = 0, b = 0;
        for (int i : nums2) {
            if (count1[i] != 0) {
                b++;
                a += count1[i] == -1 ? 0 : count1[i];
                count1[i] = -1;
            }
        }
        return new int[]{a, b};
    }

    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
        int[] count1 = new int[101];
        int[] count2 = new int[101];
        for (int i : nums1) {
            count1[i]++;
        }
        for (int i : nums2) {
            count2[i]++;
        }
        int a = 0;
        int b = 0;
        for (int i = 0; i < 101; i++) {
            if (count1[i] > 0) {
                b += count2[i];
            }
            if (count2[i] > 0) {
                a += count1[i];
            }
        }
        return new int[]{a, b};
    }
}

性能

目标

你有一个下标从 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);
    }

}

性能