LEETCODE 1460. Make Two Arrays Equal by Reversing Sub-arrays 解题思路分析

题目大意：

通过翻转子数组使两个数组相等

给你两个长度相同的整数数组 target 和 arr 。

每一步中，你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。

如果你能让 arr 变得与 target 相同，返回 True；否则，返回 False 。

示例 1：

输入：target = [1,2,3,4], arr = [2,4,1,3]
输出：true
解释：你可以按照如下步骤使 arr 变成 target：
1- 翻转子数组 [2,4,1] ，arr 变成 [1,4,2,3]
2- 翻转子数组 [4,2] ，arr 变成 [1,2,4,3]
3- 翻转子数组 [4,3] ，arr 变成 [1,2,3,4]
上述方法并不是唯一的，还存在多种将 arr 变成 target 的方法。

示例 2：

输入：target = [7], arr = [7]
输出：true
解释：arr 不需要做任何翻转已经与 target 相等。

示例 3：

输入：target = [1,12], arr = [12,1]
输出：true

示例 4：

输入：target = [3,7,9], arr = [3,7,11]
输出：false
解释：arr 没有数字 9 ，所以无论如何也无法变成 target 。

示例 5：

输入：target = [1,1,1,1,1], arr = [1,1,1,1,1]
输出：true

提示：

• target.length == arr.length
• 1 <= target.length <= 1000
• 1 <= target[i] <= 1000
• 1 <= arr[i] <= 1000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1460

解题思路分析：

两个数组只要满足他们所包含的数字种类以及相应的个数相同，那么就一定可以翻转成功。因此本题就转化为判断两个数组中每种元素的个数是否相同。解题步骤：

1. 定义两个长度为1001的数组（题目规定数组内元素的取值范围是1-1000），用来分别记录两个数组中每种数字元素的个数。
2. 循环两个数组，统计两个数组中每种元素个数
3. 查看两个数组中每种元素个数是否相同

实现代码：

public boolean canBeEqual(int[] target, int[] arr) {
    int[] count1=new int[1001]; // 统计target中每种元素个数
    int[] count2=new int[1001]; // 统计arr中每种元素个数
    for(int i=0;i<target.length;i++){
        count1[target[i]]++; // target数组的当前元素个数加一
        count2[arr[i]]++; // arr数组的当前元素个数加一
    }
    for(int i=0;i<1001;i++){ // 循环每种字符
        if(count1[i]!=count2[i]) return false; // 如果个数不同返回false
    }
    return true;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 98.78% of Java online submissions for Make Two Arrays Equal by Reversing Sub-arrays.

Memory Usage: 39.7 MB, less than 100.00% of Java online submissions for Make Two Arrays Equal by Reversing Sub-arrays.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1460-make-two-arrays-equal-by-reversing-sub-arrays-解题思路分析/