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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。