LeetCode-1640. 能否连接形成数组【数组,哈希表】
2023-09-14 09:01:27 时间
题目描述:LeetCode-1640. 能否连接形成数组
给你一个整数数组 arr ,数组中的每个整数 互不相同 。另有一个由整数数组构成的数组 pieces,其中的整数也 互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是,不允许 对每个数组 pieces[i] 中的整数重新排序。
如果可以连接 pieces 中的数组形成 arr ,返回 true ;否则,返回 false 。
示例 1:
输入:arr = [15,88], pieces = [[88],[15]]
输出:true
解释:依次连接 [15] 和 [88]
示例 2:
输入:arr = [49,18,16], pieces = [[16,18,49]]
输出:false
解释:即便数字相符,也不能重新排列 pieces[0]
示例 3:
输入:arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
输出:true
解释:依次连接 [91]、[4,64] 和 [78]
提示:
1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
1 <= pieces[i].length <= arr.length
1 <= arr[i], pieces[i][j] <= 100
arr 中的整数 互不相同
pieces 中的整数 互不相同(也就是说,如果将 pieces 扁平化成一维数组,数组中的所有整数互不相同)
解题思路一:需要注意的点是:1.arr中数字互不相同。2.pieces是arr的分片。然后我们只需要对piece分片进行逐一匹配即可。这里用到unordered_map<int,int>在arr中进行检索,匹配不到可以直接返回。可以看注释。
class Solution {
public:
bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
unordered_map<int,int> index;
for(int i=0;i<pieces.size();++i){//这里的i是pieces的坐标,即第几个piece
index[pieces[i][0]]=i;
}
for(int i=0;i<arr.size();){//在匹配每一个piece时会进行++i
auto it = index.find(arr[i]);//it指向对应arr[i]的piece地址
if(it == index.end()) return false;//arr还没有遍历完就已经找不到与之对应的piece了,可以直接返回
for(int x:pieces[it->second]){//it->first是对应的arr[i],it->second是对应的arr[i]的piece地址。
if(arr[i++]!=x) return false;//只要一个不相等就可以直接返回了,因为匹配不了
}
}
return true;//匹配成功
}
};
复杂度分析
时间复杂度:O(n),其中 n 是数组 arr 的长度。
空间复杂度:O(n)。保存哈希表需要 O(n) 的空间。
解题思路二:暂无
解题思路三:暂无
相关文章
- LeetCode笔记:Biweekly Contest 83
- leetcode刷题(132)——完全背包问题思路理解
- LeetCode 141. 环形链表
- 【day09】LeetCode(力扣)每日一刷[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]
- leetcode最长无重复字符串_直线是一维还是二维
- JavaScript刷LeetCode拿offer-分治_2023-03-01
- LeetCode周赛331,思维题训练场
- 前端工程师leetcode算法面试之二叉树深度广度遍历
- 用javascript分类刷leetcode--双指针(图文视频讲解)
- Leetcode LRU 缓存机制