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
1. Python
넘 간단하다.
array끼리 element만 같다면 어떻게든 스왑해서 서로 같게 할 수 있는 것
class Solution:
def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
return sorted(target) == sorted(arr)class Solution:
def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
target.sort()
arr.sort()
for i in range(len(target)):
if target[i] != arr[i]:
return False
return True
2. C
void sort(int* arr, int size){
for(int i=1; i<size; i++){
int temp = arr[i];
int j = i-1;
while(j>=0 && arr[j] > temp){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
bool canBeEqual(int* target, int targetSize, int* arr, int arrSize) {
// insertion sorting
sort(target,targetSize);
sort(arr,arrSize);
for(int j=0;j<targetSize;j++){
if(target[j]!=arr[j]) return false;
}
return true;
}C는 sort 기능이 따로 없어서 일일히 만들어줘야 한다. insertion sort를 함 만들어 봤다.
3. C++
class Solution {
public:
bool canBeEqual(vector<int>& target, vector<int>& arr) {
sort(target.begin(),target.end());
sort(arr.begin(),arr.end());
return arr==target;
}
};