Add solution 1640

halfrost · halfrost · commit bbb448d3beb3 · 2021-01-02T00:53:28.000+08:00
diff --git a/leetcode/1640.Check-Array-Formation-Through-Concatenation/1640. Check Array Formation Through Concatenation.go b/leetcode/1640.Check-Array-Formation-Through-Concatenation/1640. Check Array Formation Through Concatenation.go
@@ -0,0 +1,26 @@
+package leetcode
+
+func canFormArray(arr []int, pieces [][]int) bool {
+	arrMap := map[int]int{}
+	for i, v := range arr {
+		arrMap[v] = i
+	}
+	for i := 0; i < len(pieces); i++ {
+		order := -1
+		for j := 0; j < len(pieces[i]); j++ {
+			if _, ok := arrMap[pieces[i][j]]; !ok {
+				return false
+			}
+			if order == -1 {
+				order = arrMap[pieces[i][j]]
+			} else {
+				if arrMap[pieces[i][j]] == order+1 {
+					order = arrMap[pieces[i][j]]
+				} else {
+					return false
+				}
+			}
+		}
+	}
+	return true
+}
diff --git a/leetcode/1640.Check-Array-Formation-Through-Concatenation/1640. Check Array Formation Through Concatenation_test.go b/leetcode/1640.Check-Array-Formation-Through-Concatenation/1640. Check Array Formation Through Concatenation_test.go
@@ -0,0 +1,63 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question1640 struct {
+	para1640
+	ans1640
+}
+
+// para 是参数
+// one 代表第一个参数
+type para1640 struct {
+	arr    []int
+	pieces [][]int
+}
+
+// ans 是答案
+// one 代表第一个答案
+type ans1640 struct {
+	one bool
+}
+
+func Test_Problem1640(t *testing.T) {
+
+	qs := []question1640{
+
+		{
+			para1640{[]int{85}, [][]int{{85}}},
+			ans1640{true},
+		},
+
+		{
+			para1640{[]int{15, 88}, [][]int{{88}, {15}}},
+			ans1640{true},
+		},
+
+		{
+			para1640{[]int{49, 18, 16}, [][]int{{16, 18, 49}}},
+			ans1640{false},
+		},
+
+		{
+			para1640{[]int{91, 4, 64, 78}, [][]int{{78}, {4, 64}, {91}}},
+			ans1640{true},
+		},
+
+		{
+			para1640{[]int{1, 3, 5, 7}, [][]int{{2, 4, 6, 8}}},
+			ans1640{false},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 1640------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans1640, q.para1640
+		fmt.Printf("【input】:%v      【output】:%v      \n", p, canFormArray(p.arr, p.pieces))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/1640.Check-Array-Formation-Through-Concatenation/README.md b/leetcode/1640.Check-Array-Formation-Through-Concatenation/README.md
@@ -0,0 +1,95 @@
+# [1640. Check Array Formation Through Concatenation](https://leetcode.com/problems/check-array-formation-through-concatenation/)
+
+
+## 题目
+
+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:**
+
+```
+Input: arr = [85], pieces = [[85]]
+Output: true
+```
+
+**Example 2:**
+
+```
+Input: arr = [15,88], pieces = [[88],[15]]
+Output: true
+Explanation: Concatenate [15] then [88]
+```
+
+**Example 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:**
+
+```
+Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
+Output: true
+Explanation: Concatenate [91] then [4,64] then [78]
+```
+
+**Example 5:**
+
+```
+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，其中的整数也 互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。如果可以连接 pieces 中的数组形成 arr ，返回 true ；否则，返回 false 。
+
+## 解题思路
+
+- 简单题。题目保证了 arr 中的元素唯一，所以可以用 map 把每个元素的 index 存起来，方便查找。遍历 pieces 数组，在每个一维数组中判断元素顺序是否和原 arr 元素相对顺序一致。这个时候就用 map 查找，如果顺序是一一相连的，那么就是正确的。有一个顺序不是一一相连，或者出现了 arr 不存在的元素，都返回 false。
+
+## 代码
+
+```go
+package leetcode
+
+func canFormArray(arr []int, pieces [][]int) bool {
+	arrMap := map[int]int{}
+	for i, v := range arr {
+		arrMap[v] = i
+	}
+	for i := 0; i < len(pieces); i++ {
+		order := -1
+		for j := 0; j < len(pieces[i]); j++ {
+			if _, ok := arrMap[pieces[i][j]]; !ok {
+				return false
+			}
+			if order == -1 {
+				order = arrMap[pieces[i][j]]
+			} else {
+				if arrMap[pieces[i][j]] == order+1 {
+					order = arrMap[pieces[i][j]]
+				} else {
+					return false
+				}
+			}
+		}
+	}
+	return true
+}
+```
diff --git a/website/content/ChapterFour/1640.Check-Array-Formation-Through-Concatenation.md b/website/content/ChapterFour/1640.Check-Array-Formation-Through-Concatenation.md
@@ -0,0 +1,95 @@
+# [1640. Check Array Formation Through Concatenation](https://leetcode.com/problems/check-array-formation-through-concatenation/)
+
+
+## 题目
+
+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:**
+
+```
+Input: arr = [85], pieces = [[85]]
+Output: true
+```
+
+**Example 2:**
+
+```
+Input: arr = [15,88], pieces = [[88],[15]]
+Output: true
+Explanation: Concatenate [15] then [88]
+```
+
+**Example 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:**
+
+```
+Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
+Output: true
+Explanation: Concatenate [91] then [4,64] then [78]
+```
+
+**Example 5:**
+
+```
+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，其中的整数也 互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。如果可以连接 pieces 中的数组形成 arr ，返回 true ；否则，返回 false 。
+
+## 解题思路
+
+- 简单题。题目保证了 arr 中的元素唯一，所以可以用 map 把每个元素的 index 存起来，方便查找。遍历 pieces 数组，在每个一维数组中判断元素顺序是否和原 arr 元素相对顺序一致。这个时候就用 map 查找，如果顺序是一一相连的，那么就是正确的。有一个顺序不是一一相连，或者出现了 arr 不存在的元素，都返回 false。
+
+## 代码
+
+```go
+package leetcode
+
+func canFormArray(arr []int, pieces [][]int) bool {
+	arrMap := map[int]int{}
+	for i, v := range arr {
+		arrMap[v] = i
+	}
+	for i := 0; i < len(pieces); i++ {
+		order := -1
+		for j := 0; j < len(pieces[i]); j++ {
+			if _, ok := arrMap[pieces[i][j]]; !ok {
+				return false
+			}
+			if order == -1 {
+				order = arrMap[pieces[i][j]]
+			} else {
+				if arrMap[pieces[i][j]] == order+1 {
+					order = arrMap[pieces[i][j]]
+				} else {
+					return false
+				}
+			}
+		}
+	}
+	return true
+}
+```
diff --git a/website/content/menu/index.md b/website/content/menu/index.md
@@ -551,6 +551,7 @@ headless: true
     - [1480.Running-Sum-of-1d-Array]({{< relref "/ChapterFour/1480.Running-Sum-of-1d-Array.md" >}})
     - [1512.Number-of-Good-Pairs]({{< relref "/ChapterFour/1512.Number-of-Good-Pairs.md" >}})
     - [1573.Number-of-Ways-to-Split-a-String]({{< relref "/ChapterFour/1573.Number-of-Ways-to-Split-a-String.md" >}})
+    - [1640.Check-Array-Formation-Through-Concatenation]({{< relref "/ChapterFour/1640.Check-Array-Formation-Through-Concatenation.md" >}})
     - [1646.Get-Maximum-in-Generated-Array]({{< relref "/ChapterFour/1646.Get-Maximum-in-Generated-Array.md" >}})
     - [1647.Minimum-Deletions-to-Make-Character-Frequencies-Unique]({{< relref "/ChapterFour/1647.Minimum-Deletions-to-Make-Character-Frequencies-Unique.md" >}})
     - [1648.Sell-Diminishing-Valued-Colored-Balls]({{< relref "/ChapterFour/1648.Sell-Diminishing-Valued-Colored-Balls.md" >}})
