1640. Check Array Formation Through Concatenation #
题目 #
- 给你一个整数数组
arr，数组中的每个整数 互不相同 。另有一个由整数数组构成的数组pieces，其中的整数也 互不相同 。请你以 任意顺序 连接pieces中的数组以形成arr。但是，不允许 对每个数组pieces[i]中的整数重新排序。 - 如果可以连接
pieces中的数组形成arr，返回true；否则，返回false。 1 <= pieces.length <= arr.length <= 100sum(pieces[i].length) == arr.length1 <= pieces[i].length <= arr.length1 <= arr[i], pieces[i][j] <= 100arr中的整数 互不相同pieces中的整数 互不相同（也就是说，如果将pieces扁平化成一维数组，数组中的所有整数互不相同）
思路 #
哈希 #
排序+二分 #
代码 #
哈希 #
class Solution {
public boolean canFormArray(int[] arr, int[][] pieces) {
boolean[] visited = new boolean[arr.length];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
for (int[] piece: pieces) {
if (map.containsKey(piece[0]) == false) return false;
for (int i = map.get(piece[0]); i < map.get(piece[0]) + piece.length; i++) {
if (i == arr.length) return false;
if(arr[i] != piece[i-map.get(piece[0])]) return false;
visited[i] = true;
}
}
for (boolean flag:visited) {
if (flag == false) return false;
}
return true;
}
}