---

我弄得東西是將全部的寶相都加進linkedlist，寶箱的實例會存放兩個矩陣:需要的鑰匙跟彈出的鑰匙，將所有擁有的鑰匙都加進HashMap裡

重複遍歷寶箱值到linkedlist沒東西:

 變歷寶箱需要的鑰匙，如果遇到沒有匹配的就continue到下個寶箱，都能匹配就將寶箱移出，把寶箱裡的鑰匙都加進HashMap中

因為k太小了，我算的時間複雜度是O(n^2)

 

---

我弄得東西是將全部的寶相都加進linkedlist，寶箱的實例會存放兩個矩陣:需要的鑰匙跟彈出的鑰匙，將所有擁有的鑰匙都加進HashMap裡

重複遍歷寶箱值到linkedlist沒東西:

 變歷寶箱需要的鑰匙，如果遇到沒有匹配的就continue到下個寶箱，都能匹配就將寶箱移出，把寶箱裡的鑰匙都加進HashMap中

因為k太小了，我算的時間複雜度是O(n^2)

package a;

import java.util.*;

import java.util.Map.Entry;

public class k734 {

public static void main(String []args) {

Scanner sc=new Scanner(System.in);

String[]s=sc.nextLine().split(" ");

Mapmykey=new LinkedHashMap<>();

int n=Integer.parseInt(s[0]);

Mapallbox=new HashMap<>();

int k=Integer.parseInt(s[2]);

int[][]nk=new int[n][k];

int[][]nk2=new int[n][k];

s=sc.nextLine().split(" ");

for(int i=1;i<s.length;i++)

mykey.put(Integer.parseInt(s[i]), true);

for(int i=0;i<n;i++) {

s=sc.nextLine().split(" ");

for(int j=0;j<k;j++)

nk[i][j]=Integer.parseInt(s[j]);

}

for(int i=0;i<n;i++) {

s=sc.nextLine().split(" ");

for(int j=0;j<k;j++)

nk2[i][j]=Integer.parseInt(s[j]);

}

for(int i=0;i<n;i++)

allbox.put(new box(nk[i],nk2[i]),0);//n<17500，O(n)

int openedbox=0;

boolean keep=true;

Queueremoveit=new LinkedList<>();

while(keep) {

keep=false;

while(!removeit.isEmpty())

allbox.remove(removeit.poll());

findingbox:for(Entry e : allbox.entrySet()) {

for(int i:e.getKey().keyin)

if(mykey.get(i)==null)

continue findingbox;

e.getKey().lock=false;

removeit.add(e.getKey());

openedbox++;

for(int i:e.getKey().keyout)

mykey.put(i, true);

keep=true;

}

}

System.out.println(openedbox);

}

}

class box {

boolean lock=true;

int[]keyin;

int[]keyout;

public box(int[]in,int[]out) {

this.keyin=in;

this.keyout=out;

}

}

請問你解決了嗎？我也卡在30%...><

 

---

我弄得東西是將全部的寶相都加進linkedlist，寶箱的實例會存放兩個矩陣:需要的鑰匙跟彈出的鑰匙，將所有擁有的鑰匙都加進HashMap裡

重複遍歷寶箱值到linkedlist沒東西:

 變歷寶箱需要的鑰匙，如果遇到沒有匹配的就continue到下個寶箱，都能匹配就將寶箱移出，把寶箱裡的鑰匙都加進HashMap中

因為k太小了，我算的時間複雜度是O(n^2)

package a;

import java.util.*;

import java.util.Map.Entry;

public class k734 {

public static void main(String []args) {

Scanner sc=new Scanner(System.in);

String[]s=sc.nextLine().split(" ");

Mapmykey=new LinkedHashMap<>();

int n=Integer.parseInt(s[0]);

Mapallbox=new HashMap<>();

int k=Integer.parseInt(s[2]);

int[][]nk=new int[n][k];

int[][]nk2=new int[n][k];

s=sc.nextLine().split(" ");

for(int i=1;i<s.length;i++)

mykey.put(Integer.parseInt(s[i]), true);

for(int i=0;i<n;i++) {

s=sc.nextLine().split(" ");

for(int j=0;j<k;j++)

nk[i][j]=Integer.parseInt(s[j]);

}

for(int i=0;i<n;i++) {

s=sc.nextLine().split(" ");

for(int j=0;j<k;j++)

nk2[i][j]=Integer.parseInt(s[j]);

}

for(int i=0;i<n;i++)

allbox.put(new box(nk[i],nk2[i]),0);//n<17500，O(n)

int openedbox=0;

boolean keep=true;

Queueremoveit=new LinkedList<>();

while(keep) {

keep=false;

while(!removeit.isEmpty())

allbox.remove(removeit.poll());

findingbox:for(Entry e : allbox.entrySet()) {

for(int i:e.getKey().keyin)

if(mykey.get(i)==null)

continue findingbox;

e.getKey().lock=false;

removeit.add(e.getKey());

openedbox++;

for(int i:e.getKey().keyout)

mykey.put(i, true);

keep=true;

}

}

System.out.println(openedbox);

}

}

class box {

boolean lock=true;

int[]keyin;

int[]keyout;

public box(int[]in,int[]out) {

this.keyin=in;

this.keyout=out;

}

}

 

Map不要亂用
mykey的部分，mykey.key是連續的[0, 100000)，請使用boolean陣列，或是BitSet會更好。

	Map	boolean[]	BitSet
查找	logN	1	1
插入	logN	1	1
記憶體	超大	M bytes	M/8 bytes
常數	超級大	幾乎為0	比boolean[]略大

還有我改到一半，才發現你的findingBox是暴搜，這題用暴搜「應該」是會爛掉的啦，這邊的做法有點類似拓撲排序，可以O(1)找到可以開的寶盒。

 

import java.util.*;

import java.util.Map.Entry;

public class Main {

 public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  BitSet mykey = new BitSet(100000);

  int n = sc.nextInt();

  sc.nextInt();

  Map<box, Integer> allbox = new HashMap<>();

  int k = sc.nextInt();

  int[][] nk = new int[n][k];

  int[][] nk2 = new int[n][k];

  int len = sc.nextInt();

  for (int i=0; i<len; i++)

   mykey.set(sc.nextInt());

  for (int i = 0; i < n; i++) {

   for (int j = 0; j < k; j++)

    nk[i][j] = sc.nextInt();

  }

  for (int i = 0; i < n; i++) {

   for (int j = 0; j < k; j++)

    nk2[i][j] = sc.nextInt();

  }

  for (int i = 0; i < n; i++)

   allbox.put(new box(nk[i], nk2[i]), 0);// n<17500，O(n)

  int openedbox = 0;

  boolean keep = true;

  Queue<box> removeit = new LinkedList<>();

  while (keep) {

   keep = false;

   while (!removeit.isEmpty())

    allbox.remove(removeit.poll());

   findingbox:for (Entry<box, Integer> e : allbox.entrySet()) {

    for (int i : e.getKey().keyin)

     if (!mykey.get(i))

      continue findingbox;

    e.getKey().lock = false;

    removeit.add(e.getKey());

    openedbox++;

    for (int i : e.getKey().keyout)

     mykey.set(i);

    keep = true;

   }

  }

  System.out.println(openedbox);

 }

}

class box {

 boolean lock = true;

 int[] keyin;

 int[] keyout;

 public box(int[] in, int[] out) {

  this.keyin = in;

  this.keyout = out;

 }

}