标签： easy

目标

给你两个字符串 s 和 t，每个字符串中的字符都不重复，且 t 是 s 的一个排列。

排列差 定义为 s 和 t 中每个字符在两个字符串中位置的绝对差值之和。

返回 s 和 t 之间的 排列差 。

示例 1：

输入：s = "abc", t = "bac"
输出：2
解释：
对于 s = "abc" 和 t = "bac"，排列差是：
"a" 在 s 中的位置与在 t 中的位置之差的绝对值。
"b" 在 s 中的位置与在 t 中的位置之差的绝对值。
"c" 在 s 中的位置与在 t 中的位置之差的绝对值。
即，s 和 t 的排列差等于 |0 - 1| + |2 - 2| + |1 - 0| = 2。

示例 2：

输入：s = "abcde", t = "edbac"
输出：12
解释： s 和 t 的排列差等于 |0 - 3| + |1 - 2| + |2 - 4| + |3 - 1| + |4 - 0| = 12。

说明：

• 1 <= s.length <= 26
• 每个字符在 s 中最多出现一次。
• t 是 s 的一个排列。
• s 仅由小写英文字母组成。

思路

有两个仅由小写英文字母组成的字符串，同一字符串中的字母各不相同，并且组成两个字符串所用的字母相同，只是排列可能不同。求这两个字符串中相同字母位置之差的绝对值之和。

使用长度为26的数组记录每个字母在字符串s中的位置，然后遍历字符串t，计算位置之差的绝对值并累加求和即可。

代码

/**
 * @date 2024-08-24 15:01
 */
public class FindPermutationDifference3146 {
    public int findPermutationDifference(String s, String t) {
        int res = 0;
        int[] pos = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            pos[s.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < n; i++) {
            res += Math.abs(pos[t.charAt(i) - 'a'] - i);
        }
        return res;
    }
}

性能

目标

给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

• 'A'：Absent，缺勤
• 'L'：Late，迟到
• 'P'：Present，到场

如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：

• 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
• 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。

如果学生可以获得出勤奖励，返回 true ；否则，返回 false 。

示例 1：

输入：s = "PPALLP"
输出：true
解释：学生缺勤次数少于 2 次，且不存在 3 天或以上的连续迟到记录。

示例 2：

输入：s = "PPALLL"
输出：false
解释：学生最后三天连续迟到，所以不满足出勤奖励的条件。

说明：

• 1 <= s.length <= 1000
• s[i] 为 'A'、'L' 或 'P'

思路

记录缺勤总次数，判断连续迟到天数即可。

代码

/**
 * @date 2024-08-18 19:52
 */
public class CheckRecord551 {

    public boolean checkRecord(String s) {
        int n = s.length();
        int absent = 0;
        int late = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == 'A') {
                absent++;
                if (absent == 2) {
                    return false;
                }
            } else if (c == 'L') {
                late++;
                if (late == 3) {
                    return false;
                }
                continue;
            }
            late = 0;
        }
        return true;
    }
}

性能

目标

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。

Aging 有一个整数数组 nums。如果 nums 是一个 特殊数组 ，返回 true，否则返回 false。

示例 1：

输入：nums = [1]
输出：true
解释：只有一个元素，所以答案为 true。

示例 2：

输入：nums = [2,1,4]
输出：true
解释：只有两对相邻元素： (2,1) 和 (1,4)，它们都包含了奇偶性不同的数字，因此答案为 true。

示例 3：

输入：nums = [4,3,1,6]
输出：false
解释：nums[1] 和 nums[2] 都是奇数。因此答案为 false。

说明：

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

思路

判断数组是否是特殊数组，所谓特殊数组指其每一对相邻元素的奇偶性不同。

依题意判断即可。

代码

/**
 * @date 2024-08-13 8:56
 */
public class IsArraySpecial3135 {
    public boolean isArraySpecial(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] % 2 == nums[i - 1] % 2) {
                return false;
            }
        }
        return true;
    }
}

性能

目标

给你两个长度相等的数组 nums1 和 nums2。

数组 nums1 中的每个元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。

在与 x 相加后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。

返回整数 x 。

示例 1:

输入：nums1 = [2,6,4], nums2 = [9,7,5]
输出：3
解释：与 3 相加后，nums1 和 nums2 相等。

示例 2:

输入：nums1 = [10], nums2 = [5]
输出：-5
解释：与 -5 相加后，nums1 和 nums2 相等。

示例 3:

输入：nums1 = [1,1,1,1], nums2 = [1,1,1,1]
输出：0
解释：与 0 相加后，nums1 和 nums2 相等。

说明：

• 1 <= nums1.length == nums2.length <= 100
• 0 <= nums1[i], nums2[i] <= 1000
• 测试用例以这样的方式生成：存在一个整数 x，使得 nums1 中的每个元素都与 x 相加后，nums1 与 nums2 相等。

思路

有两个整数数组 nums1 和 nums2，nums1 中的每个元素加上 x 之后可以通过调整元素位置得到 nums2，求 x。

从 nums1 到 nums2 的映射为双射，即单射和满射。为了求 x 我们只需要找到 nums1 和 nums2 的最大值或最小值即可。

还有网友对两个数组求和，相减后再除以数组长度，不过需要注意数据溢出、数据类型的问题。

代码

/**
 * @date 2024-08-08 9:11
 */
public class AddedInteger3131 {

    public int addedInteger(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int max1 = nums1[0];
        int max2 = nums2[0];
        for (int i = 1; i < n; i++) {
            if (max1 < nums1[i]) {
                max1 = nums1[i];
            }
            if (max2 < nums2[i]) {
                max2 = nums2[i];
            }
        }
        return max2 - max1;
    }
}

性能

目标

给你两个下标从 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)