CTF of Z2BNS
0%

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

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 672 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

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

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

示例1：

1
2
3
4
5
6
7
输入：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：

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

示例3：

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

示例4：

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

示例5：

1
2
输入：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
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

题目要求对整数数组arr进行子数组反转，如果最后可以使arr变得和target相同返回true，其实也就是数组arr中的任何两个元素都可以进行交换，所以只要target中的元素与arr中的一样（无序），就返回true，否则返回false。

c++代码：(执行用时36ms，击败49.21%，内存消耗14M，击败64.22%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        //遍历查找target中的元素是否都在arr中存在
        vector<int>::iterator it;
        for(int i=0;i<target.size();++i){
            if((it=find(arr.begin(),arr.end(),target[i]))==arr.end()){
                //target中的元素在arr中没有找到
                return false;
            }else{
                //找到了则从arr中删除掉这个元素
                arr.erase(it);
            }
        }
        return true;
    }
};
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

没有官方题解，其实思路也挺清晰的。看了一些题解后，更明白地讲就是只需判断两个数组排序后是否相等即可，使用sort函数排序，3行代码就搞定。

------------- THE END! THANKS! -------------