目录

1. 题目描述

2. 解题分析

3. 代码实现

给你一个整数数组 arr &＃xff0c;数组中的每个整数 互不相同 。另有一个由整数数组构成的数组 pieces&＃xff0c;其中的整数也 互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是&＃xff0c;不允许 对每个数组 pieces[i] 中的整数重新排序。

如果可以连接 pieces 中的数组形成 arr &＃xff0c;返回 true &＃xff1b;否则&＃xff0c;返回 false 。

示例 1&＃xff1a;

输入&＃xff1a;arr &＃61; [15,88], pieces &＃61; [[88],[15]]
输出&＃xff1a;true
解释&＃xff1a;依次连接 [15] 和 [88]
示例 2&＃xff1a;

输入&＃xff1a;arr &＃61; [49,18,16], pieces &＃61; [[16,18,49]]
输出&＃xff1a;false
解释&＃xff1a;即便数字相符&＃xff0c;也不能重新排列 pieces[0]

示例 3&＃xff1a;

输入&＃xff1a;arr &＃61; [91,4,64,78], pieces &＃61; [[78],[4,64],[91]]
输出&＃xff1a;true
解释&＃xff1a;依次连接 [91]、[4,64] 和 [78]

提示&＃xff1a;

• 1 <&＃61; pieces.length <&＃61; arr.length <&＃61; 100
• sum(pieces[i].length) &＃61;&＃61; arr.length
• 1 <&＃61; pieces[i].length <&＃61; arr.length
• 1 <&＃61; arr[i], pieces[i][j] <&＃61; 100
• arr 中的整数 互不相同
• pieces 中的整数 互不相同&＃xff08;也就是说&＃xff0c;如果将 pieces 扁平化成一维数组&＃xff0c;数组中的所有整数互不相同&＃xff09;

来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
链接&＃xff1a;https://leetcode-cn.com/problems/check-array-formation-through-concatenation
著作权归领扣网络所有。商业转载请联系官方授权&＃xff0c;非商业转载请注明出处。

2. 解题分析

        pieces的每个元素都是数组&＃xff0c;允许对pieces中的各元素进行重排&＃xff0c;但是不能对各元素&＃xff08;数组&＃xff09;内部的元素进行次序重排。

        重排能够成立的前提条件是&＃xff0c;将pieces完全展平后后所包含的元素集合与arr中的元素集合完全相同。

        所以&＃xff0c;判断是否能够重排pieces能够形成arr只需要判断pieces中每个其中数组元素是否恰好包含arr中某一个slice&＃xff08;即按照相同顺序连续排在一起&＃xff09;。

        

3. 代码实现

from typing import Listclass Solution:def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:for p in pieces:# print(p)k &＃61; 0while k&＃61;len(arr) or arr[k&＃43;j] !&＃61; p[j]:return False# The same segment is found for p.breakelse:k &＃43;&＃61; 1# Didn&＃39;t found p[0] in arr.if k &＃61;&＃61; len(arr):return Falsereturn Trueif __name__ &＃61;&＃61; &＃39;__main__&＃39;:sln &＃61; Solution()arr &＃61; [15]pieces &＃61; [[15]]print(sln.canFormArray(arr,pieces))arr &＃61; [15]pieces &＃61; [[25]]print(sln.canFormArray(arr,pieces)) arr &＃61; [15,88]pieces &＃61; [[88],[15]]print(sln.canFormArray(arr,pieces))arr &＃61; [49,18,16]pieces &＃61; [[16,18,49]]print(sln.canFormArray(arr,pieces))arr &＃61; [91,4,64,78]pieces &＃61; [[78],[4,64],[91]] print(sln.canFormArray(arr,pieces))

        注意&＃xff0c;因为题设条件已经限定了pieces的各数组元素总长等于arr的长度&＃xff0c;因此不需要考虑pieces所包含的所有数的集合构成了arr中元素集合的真子集的情况&＃xff0c;也就免掉了额外的validity检查。

回到主目录&＃xff1a;笨牛慢耕的Leetcode解题笔记(动态更新。。。)