通过串联Leetcode解决方案检查阵列形成  


难度级别 易得奖学金
经常问 尤伯杯
算法 排列 代码信号 编码 哈希图 访谈 面试准备 力码 力码解决方案 排序

通过级联Leetcode解决方案检查数组形成问题为我们提供了一个数组数组。 除此之外,我们还给出了一个序列。 然后,我们被告知寻找是否可以用某种方式构造给定序列 排列 数组。 我们可以按所需的任何顺序排列数组。 但是我们不能重新排列数组中的元素。 我们还被告知整数在数组数组中是唯一的。 因此,在研究解决方案之前,我们必须先看一些示例。

通过串联Leetcode解决方案检查阵列形成

arr = [15,88], pieces = [[88],[15]]
true

说明:我们可以按相反顺序排列元素。 因此,最后一个数组15将排在前面。 同样,第一个元素将返回。 这样我们就可以形成给定的数组。

arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
true

说明:如果我们首先连接最后一个元素,然后是中间数组,最后是第一个数组。 这样我们可以获得所需的序列。

通过级联Leetcode解决方案形成校验数组的方法  

通过级联Leetcode解决方案检查数组形成的问题要求我们检查是否可以从数组中获取所需的序列。 这个问题似乎是一个递归问题,我们需要检查所有可能性。 以递归的方式,我们首先尝试选择一个数组,然后检查当前数组是否合适,然后执行相同的操作,直到用尽序列为止。 但是,我们在这里拥有的优势是独特的元素。 因此,我们只需检查数组的第一个元素中的第一个元素即可。 即使检查这一点,也可以确保我们可以继续选择数组。

参见
学生出勤记录I Leetcode解决方案

选择一个数组后,我们遍历数组中的所有元素,检查数组是否具有序列中的所有元素,直到我们用完它。 用尽后,重复相同的过程。 如果数组元素和序列中的元素不匹配,则返回false。 最后,当我们找不到任何不匹配项时,我们将返回true。

通过级联Leetcode解决方案形成检查阵列的代码  

C ++代码

#include <bits/stdc++.h>
using namespace std;

bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
    unordered_map<int,int> entry;
    for(int i=0;i<pieces.size();i++)
        entry[pieces[i][0]] = i;
    int i =  0;
    while(i < arr.size()){
        if(entry.count(arr[i])){
            vector<int> &piece  = pieces[entry[arr[i]]];
            for(auto x: piece)
                if(x != arr[i++])
                    return false;
        } else {
            return false;
        }
    }
    return true;
}

int main(){
    vector<int> arr = {91, 4, 64, 78};
    vector<vector<int>> pieces = {{78},{4,64},{91}};
    cout<<(canFormArray(arr, pieces) ? "true" : "false");
}
true

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean canFormArray(int[] arr, int[][] pieces) {
        HashMap<Integer, Integer> entry = new HashMap<Integer, Integer>();
        for(int i=0;i<pieces.length;i++)
            entry.put(pieces[i][0], i);
        int i =  0;
        while(i < arr.length){
            if(entry.containsKey(arr[i])){
                int n = pieces[entry.get(arr[i])].length;
                int k = entry.get(arr[i]);
                for(int j=0;j<n;j++)
                    if(pieces[k][j] != arr[i++])
                        return false;
            } else {
                return false;
            }
        }
        return true;
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[] arr = {91, 4, 64, 78};
      int[][] pieces = {{78},{4,64},{91}};
      System.out.print(canFormArray(arr, pieces) ? "true" : "false");
  }
}
true

复杂度分析  

时间复杂度

上), 其中N是给定序列中元素的总数。 由于使用了 哈希图.

空间复杂度

O(M), 其中,M是数组数组中的数组数。