05 August 2008
给定两个长度相等的整数数组 target 和 arr。在一个步骤中，可以选择 arr 的任何非空子数组并将其反转。您以进行任意数量的步骤。
如果可以使 arr 等于 target，则返回 true，否则返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 sub-array [2,4,1], arr becomes [1,4,2,3]
2- Reverse sub-array [4,2], arr becomes [1,2,4,3]
3- Reverse sub-array [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.
找重复
1
2
3
4
5
6
7
8
class Solution {
public boolean canBeEqual(int[] target, int[] arr) {
int[] dp = new int[1000];
for(int i : arr) dp[i - 1]++;
for(int i : target) dp[i - 1]--;
return Arrays.equals(dp, new int[1000]);
}
}
排序
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public boolean canBeEqual(int[] target, int[] arr) {
Arrays.sort(target);
Arrays.sort(arr);
for(int i=0; i<arr.length; i++){
if(target[i] != arr[i]){
return false;
}
}
return true;
}
}