Make Two Arrays Equal by Reversing Subarrays
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
思路一： 用 map 存储数组，并记录数组值的个数，最后比对两个数组是否一致。优化，由于数字出现的范围是[1, 1000], 可以用数组来代替 map
public boolean canBeEqual(int[] target, int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : target) {
map.compute(num, (k, v) -> v == null ? 1 : v + 1);
}
for (int i : arr) {
if (map.containsKey(i)) {
Integer v = map.get(i);
if (v == 1) map.remove(i);
else map.put(i, v - 1);
} else {
return false;
}
}
return map.isEmpty();
}