從LeetCode學演算法 - 109 Array (15) / Hash Table (11)

1640. Check Array Formation Through Concatenation (Easy)

寫在前面

好久不見！筆者最近剛換了工作，
所以比較忙一點XD 之後1月中會有HiSKIO 技術年貨節的活動，
歡迎大家拿著折價券來修從LeetCode學演算法的課程喲！
如果預算不夠，相信這108篇也還是很夠讀者練習的啦XDD

在更之後還有規劃0元挑戰賽的部分，
只要修課後一定時間內成功錄取新工作 ，
課程就會全額退費喲！ 這部分再請留意官方那邊的公告，
如果有開始的話，文章中也會再提醒各位。

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/leetcodeadv

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/leetcodeall

Question

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are ** distinct**. Your goal is to form arr by concatenating the arrays in pieces ** in any order**. However, you are ** not** allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1

1
2
Input: arr = [85], pieces = [[85]]
Output: true

Example 2

1
2
3
Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]

Example 3

1
2
3
Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 4

1
2
3
Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]

Example 5

1
2
Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false

Constraints

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
The integers in arr are distinct .
The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

分析/解題

給定一個陣列arr，當中有不同的整數們，
以及另一個整數陣列的陣列pieces(好饒口XD)，
當中所有的pieces中的整數也都是相異的，
我們的目標就是要將pieces拼接成arr，
但pieces中要怎麼接順序都沒關係，
但每一個pieces中的子陣列中的順序不可以被調換 。
(例如arr = [15,88], pieces = [[88],[15]]，
可以先拚[15]再拚[88]從而組出arr，可回傳true；
但arr = [49,18,16], pieces = [[16,18,49]]的話，
因為[16,18,49]內不能夠調換順序，所以只能回傳false)

如果拚得起來就回傳true，否則回傳false。

條件限制：

arr的長度和pieces的長度均為1~100之間(後者小於前者)。
pieces的所有子陣列長度總和，和arr陣列長度相等。
arr和pieces的所有子陣列中的元素值均在1~100之間。
arr中的所有整數均為相異。
pieces中的所有整數均為相異。

根據條件限制的部分，我們可以簡單得到，
反正要能對上的話，因為總個數剛好相等，
所以不存在第二種對應方式 ！
既然不存在第二種對應的方式，
那麼我們在arr中看到一個開頭時，
我們應該只要在pieces中找那個值 ，
就知道該對上pieces中的那一個子陣列囉！

那麼，我們該怎麼樣去找對應呢？
每次都掃過一輪去找，時間複雜度感覺會很糟糕，
那麼，想要迅速的找到對應的位置，
我們就會想到利用HashTable的概念。
因此，在Java使用HashMap，Python中則使用dictionary，
就可以讓我們使用O(1)的複雜度進行存取(不過前面要先花O(N)來存喲！)

這邊我們可以選擇將每個(pieces[i][0], i)的對應存入，
這樣在搜尋時，我們就知道接下來要拚入哪一組子陣列囉！

接著我們需要遍歷整個arr，
每次先拿第一個值去搜尋到對應的pieces，
接著依序一個一個去對照兩邊的值是否相等。
如果找不到對應或者是值不相等，就表示無法對應成功囉！
(可以直接回傳false)
如果全數拚完都沒問題，自然就可以回傳true。

依此，寫成程式碼如下：

Java Java的部分，我們使用HashMap來記錄，

記得使用put(key, value) 的形式！
(因為沒有重複的問題，所以也不需要檢查)

接著我們利用cnt來進行遍歷的紀錄，
這邊不要忘記先檢查 能不能找到arr[cnt]啊！
(因為有可能找不到，直接用get會有exception的！)
另外，由於get出來是Integer，
這邊我們使用(int)來將其轉型回一般的int 。
其他就依序處理即可。

Python

Python的部分，字典和list的操作方式差不多，
不過還是不要忘記先檢查喲！
另外對初學的讀者提醒一下，
Python中沒有++或–這種方便的遞增/遞減方式 ，
所以請乖乖使用cnt += 1或cnt = cnt + 1 。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(pieces的子陣列個數，最大為N))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve