Question

1460. Make Two Arrays Equal by Reversing Subarrays

中文文档

Description

You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and reverse it. You are allowed to make any number of steps.

Return true _if you can make _arr_ equal to _target_ or _false_ otherwise_.

 

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse subarray [2,4,1], arr becomes [1,4,2,3]
2- Reverse subarray [4,2], arr becomes [1,2,4,3]
3- Reverse subarray [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr does not have value 9 and it can never be converted to target.

 

Constraints:

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

Solutions

Solution 1

class Solution:
  def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
    target.sort()
    arr.sort()
    return target == arr

class Solution {
  public boolean canBeEqual(int[] target, int[] arr) {
    Arrays.sort(target);
    Arrays.sort(arr);
    return Arrays.equals(target, arr);
  }
}

class Solution {
public:
  bool canBeEqual(vector<int>& target, vector<int>& arr) {
    sort(target.begin(), target.end());
    sort(arr.begin(), arr.end());
    return target == arr;
  }
};

func canBeEqual(target []int, arr []int) bool {
  sort.Ints(target)
  sort.Ints(arr)
  for i, v := range target {
    if v != arr[i] {
      return false
    }
  }
  return true
}

function canBeEqual(target: number[], arr: number[]): boolean {
  target.sort((a, b) => a - b);
  arr.sort((a, b) => a - b);
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    if (target[i] !== arr[i]) {
      return false;
    }
  }
  return true;
}

impl Solution {
  pub fn can_be_equal(mut target: Vec<i32>, mut arr: Vec<i32>) -> bool {
    target.sort();
    arr.sort();
    target == arr
  }
}

class Solution {
  /**
   * @param Integer[] $target
   * @param Integer[] $arr
   * @return Boolean
   */
  function canBeEqual($target, $arr) {
    sort($target);
    sort($arr);
    return $target === $arr;
  }
}

bool canBeEqual(int* target, int targetSize, int* arr, int arrSize) {
  int count[1001] = {0};
  for (int i = 0; i < targetSize; i++) {
    count[target[i]]++;
    count[arr[i]]--;
  }
  for (int i = 0; i < 1001; i++) {
    if (count[i] != 0) {
      return false;
    }
  }
  return true;
}

Solution 2

class Solution:
  def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
    return Counter(target) == Counter(arr)

class Solution {
  public boolean canBeEqual(int[] target, int[] arr) {
    int[] cnt1 = new int[1001];
    int[] cnt2 = new int[1001];
    for (int v : target) {
      ++cnt1[v];
    }
    for (int v : arr) {
      ++cnt2[v];
    }
    return Arrays.equals(cnt1, cnt2);
  }
}

class Solution {
public:
  bool canBeEqual(vector<int>& target, vector<int>& arr) {
    vector<int> cnt1(1001);
    vector<int> cnt2(1001);
    for (int& v : target) ++cnt1[v];
    for (int& v : arr) ++cnt2[v];
    return cnt1 == cnt2;
  }
};

func canBeEqual(target []int, arr []int) bool {
  cnt1 := make([]int, 1001)
  cnt2 := make([]int, 1001)
  for _, v := range target {
    cnt1[v]++
  }
  for _, v := range arr {
    cnt2[v]++
  }
  for i, v := range cnt1 {
    if v != cnt2[i] {
      return false
    }
  }
  return true
}

function canBeEqual(target: number[], arr: number[]): boolean {
  const n = target.length;
  const count = new Array(1001).fill(0);
  for (let i = 0; i < n; i++) {
    count[target[i]]++;
    count[arr[i]]--;
  }
  return count.every(v => v === 0);
}

impl Solution {
  pub fn can_be_equal(mut target: Vec<i32>, mut arr: Vec<i32>) -> bool {
    let n = target.len();
    let mut count = [0; 1001];
    for i in 0..n {
      count[target[i] as usize] += 1;
      count[arr[i] as usize] -= 1;
    }
    count.iter().all(|v| *v == 0)
  }
}

Solution 3

class Solution:
  def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
    cnt = [0] * 1001
    for a, b in zip(target, arr):
      cnt[a] += 1
      cnt[b] -= 1
    return all(v == 0 for v in cnt)

class Solution {
  public boolean canBeEqual(int[] target, int[] arr) {
    int[] cnt = new int[1001];
    for (int v : target) {
      ++cnt[v];
    }
    for (int v : arr) {
      if (--cnt[v] < 0) {
        return false;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool canBeEqual(vector<int>& target, vector<int>& arr) {
    vector<int> cnt(1001);
    for (int& v : target) ++cnt[v];
    for (int& v : arr)
      if (--cnt[v] < 0) return false;
    return true;
  }
};

func canBeEqual(target []int, arr []int) bool {
  cnt := make([]int, 1001)
  for _, v := range target {
    cnt[v]++
  }
  for _, v := range arr {
    cnt[v]--
    if cnt[v] < 0 {
      return false
    }
  }
  return true
}