检查一组是否对称的有效方法

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代表路径不存在

这样就很容易知道你是否可以从一个房间到达另一个房间。你只需要实现一些简单的循环遍历矩阵。