现在你的任务是完成getValidOrder函数，如果有合法

腾讯的笔试题为什么会出现小米？

import java.util.ArrayList;
import java.util.List;

/**
 */
public class Px {
    private List<String> orders=new ArrayList<String>();
    public static void main(String[] args)
    {
        Px p=new Px();
        List<String>allMembers=new ArrayList<String>();
        allMembers.add("a");
        allMembers.add("b");
        allMembers.add("c");
        allMembers.add("d");
        List<Request> ls=new ArrayList<Request>();
        ls.add(getNewRequest("a"));
        ls.get(0).requestItems.add(getNewRequestItem("b",true));
        ls.get(0).requestItems.add(getNewRequestItem("c",false));
        ls.add(getNewRequest("b"));
        ls.get(1).requestItems.add(getNewRequestItem("a",true));
        ls.get(1).requestItems.add(getNewRequestItem("c",false));
        List<String> orders= p.getValidOrder(allMembers,ls);
        System.out.println(orders);
    }
    private static Request getNewRequest(String owner)
    {
        Request obj=new Request();
        obj.owner=owner;
        obj.requestItems=new ArrayList<RequestItem>();
        return obj;
    }
    private static RequestItem getNewRequestItem(String member,boolean frant)
    {
        RequestItem obj=new RequestItem();
        obj.member=member;
        obj.standFront=frant;
        return obj;
    }
    /**
     * @param allMembers  参与排序的所有的成员
     * @param requests       请求排序的条件，每个request不能为空
     * @return
     */
    public List<String> getValidOrder(List<String>allMembers, List<Request> requests)
    {
        if(requests==null||requests.size()==0) return allMembers; 
        if(isOk(allMembers,requests))  
        {
            return orders;
        }
        return null;
    }
    private boolean isOk(List<String>allMembers,List<Request> requests)
    {
         if(allMembers.size()==1)
         {
             orders.add(allMembers.get(0));
             return true;
         }
         List<String> delete=new ArrayList<String>();
         for(int i=0;i<requests.size();i++)
         {
              for(int j=0;j<requests.get(i).requestItems.size();j++)
              {
                    //owner要求排在这个人的后面，证明owner是没有资格在本局进行排序
                    if(!requests.get(i).requestItems.get(j).standFront)   
                    {
                         if(!delete.contains(requests.get(i).owner))
                         {
                              delete.add(requests.get(i).owner); 
                         }
                    }
                    else
                    {
                         //owner要求排在这个人的前面，说明至少这个人在本局是没有资格进行排序
                         if(!delete.contains(requests.get(i).requestItems.get(j).member))
                         {
                             delete.add(requests.get(i).requestItems.get(j).member);
                         }
                    }
              }
         }
         if(delete.size()==allMembers.size())
         {
             //出现了环形的闭合回路
             return false;
         }
         allMembers.removeAll(delete);  //排除不能在本局排序的，其余的都可以在本局任意位置出现
         orders.addAll(allMembers);
         List<Request> reqnew=new ArrayList<Request>();
         for(int j=0;j<requests.size();j++)
          {
                if(!allMembers.contains(requests.get(j).owner)) 
                {
                     reqnew.add(requests.get(j));
                     for(int i=0;i<requests.get(j).requestItems.size();i++)
                     {
                         if(allMembers.contains(requests.get(j).requestItems.get(i).member))
                         {
                              reqnew.get(reqnew.size()-1).requestItems.remove(requests.get(j).requestItems.get(i));
                         }
                     }
                }
          }
         return isOk(delete,reqnew);  //递归调用
    }
}
class RequestItem
{
    public String member;
    public boolean standFront; //true表示要排在这个人的前面，false表示要排在这个人的后面
}
class Request
{
    public String owner;    //那个人提出的要求
    List<RequestItem> requestItems;    //他要排在哪些人的前面，哪些人的后面
}

我很想知道 如果A要求排在B前面 ，B要求排在A前面 这题怎么做？ 还是我理解错题意了？

#include<iostream>
#include<string>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;

class RequestItem
{
public:
	string member;
    bool standFront; //true表示要排在这个人的前面，false表示要排在这个人的后面
};
class Request
{
public:
	string owner;    //那个人提出的要求
    vector<RequestItem> requestItems;    //他要排在哪些人的前面，哪些人的后面
};

typedef struct node
{
  int adjent;
  struct node* next;
}*graphnode;

typedef struct elem
{
  int in;
  graphnode first;  
}graphelem;

vector<string> getValidOrder(vector<string>& m, vector<Request>& r)
{
  int len=m.size();
  graphelem* gra=new graphelem[len];
  size_t i,j;
  vector<string>::iterator ite1=m.begin(),ite2,ite3;
  int index1,index2;
  for(i=0;i<len;++i)
    gra[i].in=0;
  for(i=0;i<r.size();++i)
   {
           ite2=find(m.begin(),m.end(),r[i].owner);   
	    index1=ite2-ite1;                          //要求者 A
        for(j=0;j<r[i].requestItems.size();++j)
         {	
	         ite3=find(m.begin(),m.end(),r[i].requestItems[j].member); 	 
	         index2=ite3-ite1;                           //被要求者 B	   
             if(r[i].requestItems[j].standFront)  //A->B    
              {		
			       gra[index2].in++;
			       graphnode tmp= new struct node;
			       tmp->next=gra[index1].first;
			       tmp->adjent=index2;
			       gra[index1].first=tmp;
	       }
	     else                              //B->A
	          {	        
			       gra[index1].in++;
		           graphnode tmp= new struct node;
			       tmp->next=gra[index2].first;
			       tmp->adjent=index1;
			       gra[index2].first=tmp;
	          }
	  }
     }
   int* s=new int[len];    //拓扑排序
   int top=-1,count=0,tmp;
   vector<string> res;
   for(i=0;i<len;++i)
    if(gra[i].in==0)
      s[++top]=i;
   while(top!=-1)
   {
     tmp=s[top--];
     res.push_back(m[tmp]);
	 ++count;
	 for(graphnode p=gra[tmp].first;p;p=p->next)
	 {
	   if(--gra[p->adjent].in==0)
	     s[++top]=p->adjent;
	 }
   }  
   if(count<len)	 
	 res.clear();
	return res;	       
}

拓排+1

拓扑排序。

如果甲要求排在乙的前面，而已也要求排在甲的前面怎么解决呢？这个怎么满足要求？新人不懂，求轻喷