檢查一組是否對稱的有效方法

Question

我需要編寫一個驗證器來檢查使用Gson從JSON解析的房間，即對於每對房間A和B，如果您可以從A到B，然後你可以從B到A

下面是該JSON格式： https://jsfiddle.net/tgtbqzky/

{ 
    "initialRoom": "MatthewsStreet", 
    "rooms": [ 
    { 
     "name": "MatthewsStreet", 
     "description": "You are on Matthews, outside the Siebel Center", 
     "directions": [ 
     { 
      "direction": "East", 
      "room": "SiebelEntry" 
     } 
     ] 
    }, 
    { 
     "name": "SiebelEntry", 
     "description": "You are in the west entry of Siebel Center. You can see the elevator, the ACM office, and hallways to the north and east.", 
     "directions": [ 
     { 
      "direction": "West", 
      "room": "MatthewsStreet" 
     }, 
     { 
      "direction": "Northeast", 
      "room": "AcmOffice" 
     }, 
     { 
      "direction": "North", 
      "room": "SiebelNorthHallway" 
     }, 
     { 
      "direction": "East", 
      "room": "SiebelEastHallway" 
     } 
     ] 
    }, 
    { 
     "name": "AcmOffice", 
     "description": "You are in the ACM office. There are lots of friendly ACM people.", 
     "directions": [ 
     { 
      "direction": "South", 
      "room": "SiebelEntry" 
     } 
     ] 
    }, 
    { 
     "name": "SiebelNorthHallway", 
     "description": "You are in the north hallway. You can see Siebel 1112 and the door toward NCSA.", 
     "directions": [ 
     { 
      "direction": "South", 
      "room": "SiebelEntry" 
     }, 
     { 
      "direction": "NorthEast", 
      "room": "Siebel1112" 
     } 
     ] 
    }, 
    { 
     "name": "Siebel1112", 
     "description": "You are in Siebel 1112. There is space for two code reviews in this room.", 
     "directions": [ 
     { 
      "direction": "West", 
      "room": "SiebelNorthHallway" 
     } 
     ] 
    }, 
    { 
     "name": "SiebelEastHallway", 
     "description": "You are in the east hallway. You can see Einstein Bros' Bagels and a stairway.", 
     "directions": [ 
     { 
      "direction": "West", 
      "room": "SiebelEntry" 
     }, 
     { 
      "direction": "South", 
      "room": "Siebel1314" 
     }, 
     { 
      "direction": "Down", 
      "room": "SiebelBasement" 
     } 
     ] 
    }, 
    { 
     "name": "Siebel1314", 
     "description": "You are in Siebel 1314. There are happy CS 126 students doing a code review.", 
     "directions": [ 
     { 
      "direction": "North", 
      "room": "SiebelEastHallway" 
     } 
     ] 
    }, 
    { 
     "name": "SiebelBasement", 
     "description": "You are in the basement of Siebel. You see tables with students working and door to computer labs.", 
     "directions": [ 
     { 
      "direction": "Up", 
      "room": "SiebelEastHallway" 
     } 
     ] 
    } 
    ] 
} 

我在想，如果要走的路將是兩個嵌套的循環，其中，環外將循環通過所有的房間，內部會循環通過每個循環內可能的每個方向，然後我將每一對我加入到一個Arr ayList。

如果我遇到了一些已經存在的東西，我會從ArrayList中移除它，並且如果在我的for循環結尾，ArrayList仍然包含一個元素，這意味着它的對應對不存在，並且因此JSON無效。如果ArrayList的大小爲零，那麼數據是有效的。

有沒有人有更有效的方法來解決這個問題？我覺得自從它本質上證明給定集合是否是對稱的，必須有一個更優化的方法。

Answer 1

您應該能夠通過定義一對房間的「規範名稱」，比如按字母順序排列房間中的房間名稱，並將所有房間對映射到他們的規範名稱，來驗證您的套房的對稱性：

static String canonicalName(String roomA, String roomB) { 
    if (roomA.compareTo(roomB) < 0) { 
     return roomA + "|" + roomB; 
    } else { 
     return roomB + "|" + roomA; 
    } 
} 

這將產生一對房間，其中它們中的一個是"AcmOffice"相同的密鑰"AcmOffice|MatthewsStreet"，另一種是"MatthewsStreet"，無論的量級。

現在你可以把它們映射到列表中，這樣的：

Map<String,List<String>> mp = new HashMap<>(); 
for (PairOfRooms pair : allRoomPairs) { 
    String key = canonicalName(pair.roomA, pair.roomB); 
    List<String> list = mp.get(key); 
    if (list == null) { 
     list = new ArrayList<>(); 
     mp.put(key, list); 
    } 
    list.add(pair.roomA + "|" + pair.roomB); 
} 

通過所有對去後，檢查裏面的地圖列表：

• 如果列表中有兩個不同的項目，一切很好
• 如果列表中有一個項目，其對稱項目丟失
• 如果列表中有兩個以上的項目，則有重複項目

Answer 2

1. 生成代理對象用於對室A，B，方向
2. 實現一個equals和的compareTo
3. 實現一個方法來獲得相對房間
4. 把你的反序列化元素陣列。
5. 使用地圖來檢查是否找到相反的方法。

它運行在O（n）的

其中給出

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

class RoomPath implements Comparable<RoomPath> 
{ 
    String from; 
    String to; 
    String direction; 

    public RoomPath(String A, String B, String dir) 
    { 
     from = A; 
     to = B; 
     direction = dir; 
    } 

    public RoomPath opposite() 
    { 
     String oppDirection =""; 
     switch(direction) 
     { 
      case "North" : oppDirection = "South"; break; 
      case "South" : oppDirection = "North"; break; 
      case "West" : oppDirection = "East"; break; 
      case "East" : oppDirection = "West"; break; 
     } 
     return new RoomPath(to, from, oppDirection); 
    } 

    public int compareTo(RoomPath other) 
    { 
     int v1 = from.compareTo(other.from); 
     if(v1 == 0) 
     { 
      v1 = to.compareTo(other.to); 
      if(v1 == 0) 
      { 
       return direction.compareTo(other.direction); 
      } 
      return v1; 
     } 
     return v1; 
    } 

    public bool equals(Object e) 
    { 
     if (!(e instanceof RoomPath)) return false; 
     RoomPath path = (RoomPath)e; 
     return compareTo(e) == 0; 
    } 

    public int hashCode() { 
     int dirnumber = 0; 
     switch(dirnumber) 
     { 
      case "North" : dirnumber = 0; break; 
      case "South" : dirnumber = 1; break; 
      case "West" : dirnumber = 2; break; 
      case "East" : dirnumber = 3; break; 
     } 

     return (from.hashCode() + 31 * b.hashCode()) << 2 | dirnumber; 
     //left as exercise 
     return 0; 
    } 


} 


/* Name of the class has to be "Main" only if the class is public. */ 
class Ideone 
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
     List<RoomPath > roompaths = ... ; //the parsing function 
     List<RoomPath > symetrics = new ArrayList<RoomPath>(); 
     Map<RoomPath, bool> syms = new HashMap<>(); 
     for (RoomPath path : roompaths) 
     { 
      if(!syms.containsKey(path)) 
      { 
       syms.put(path, false); 
      } 

      if(syms.containsKey(path.opposite())) 
      { 
       symetrics.insert(path); 
      } 
     } 
     bool allok = symetrics.size()*2 = roompaths.size(); 
    } 
} 

Answer 3

我寧願到JSON transfrom到一些二維矩陣是這樣的：

哪：W代表West，E代表Est，N代表Nord，S代表Sud，X代表路徑不存在

這樣就很容易知道你是否可以從一個房間到達另一個房間。你只需要實現一些簡單的循環遍歷矩陣。