第一道程序设计题

2.1 一个环，N个点，任意相邻两点有一个距离。要求写一个算法，输入为点i和点j，输出是他们之间的最短路径。
某环形公路上有N个站点，分别记为A1,...,An,从Ai到A(i+1)的距离为Di，An到A1的距离为D0。假设D0~D(n-1)保存在数组D[N]中。现在要求你写一个函数，能够高效的计算出公路上任意两点的最近距离，要求空间复杂度不能超过O(N)。

【思考】
1、问题抽象
1）环形公路可以表示为一个环，站点即为环上的点，环可以用哪种数据结构表示呢？当然是双端链表了。
2）站点如何表示呢？站点可以视为一个点对象，画出双端链表上的点，我们发现该点对象应该有3个属性：第一属性是站点名Ai，第二个属性时其到前一个站点A(i-1)的距离D(i-1)，第三个属性时其到下一个站点A(i+1)的距离D(i+1)。

3）现在我们有了对题目中研究对象的抽象（环形公路抽象为双端链表，站点抽象为点对象），现在可以把原问题转变为我们程序员熟悉的问题了：
给定双端链表中的2个点对象，求该2点间的最大距离为多少？

2、解决问题
问题抽象后，解决该问题变的简单了很多，点Ai到点Aj无非就有2条路径，一条路径是按图中顺时针方向（经由下一个站点）到达点Aj，另一条路径是按图中逆时针方向（经由前一个站点）到达点Aj。我们只要比较这俩条路径得到较小的那个值即可。
3、时间复杂度分析
顺时针方向和逆时针方向遍历链表的和正好是链表的长度n，故该算法时间复杂度为O(n)。
4、JAVA语言实现

在JAVA中双端链表可以用LinkedList表示。具体代码如下

//站点对象类

public class Point{
   private String name; //站点名称，如Ai
   private double nextPointDistance; //到下一个站点的距离，D(i+1)
   private double previousPointDistance; //到前一个站点的距离，D(i-1)
   
   //constructor
   public Point(){}
   
   //get and set method
   public String getName(){
    return name;
   }//end getName()
   
   public void setName(String name){
    this.name=name;
   }//end setName()
   
   public double getnextPointDistance(){
    return nextPointDistance;
   }//end getnextPointDistance()
   
   public void setnextPointDistance(double nextPointDistance){
    this.nextPointDistance=nextPointDistance;
   }//end setnextPointDistance()
   
   public double getpreviousPointDistance(){
    return previousPointDistance;
   }//end getpreviousPointDistance()
   
   public void setpreviousPointDistance(double previousPointDistance){
    this.previousPointDistance=previousPointDistance;
   }//end setpreviousPointDistance()
   }//end setName()   
}//end class Point

主函数shortestPath

public class HighRoad{
  private LinkedList ll; //双端链表
  
  //------------------------------------------------------
  //constructor
  //------------------------------------------------------
  public HighRoad(String[] pointName,double[] distance){
      initial(pointName,distance)
  }
  
  //------------------------------------------------------
  // API
  //------------------------------------------------------
  /**
  * 求2站点间最大距离
  * @parm name1 站点i
  * @parm name2 站点j
  * @return 返回最大路径,-1代表错误
  */
  public double shortestPath(String name1,String name2){
    //输入控制
	if(ll==null)
	  return -1;
	
	int llSize=ll.size();
	if(llSize<1)  //站点数小于2
      return -1;
	  
	if(name1==null || name1=="" || name2==null || name2=""){
	    System.out.println("请输入站点名称");
	}//end if
	
	//在双端链表中获取这2个站点的位置
	Point point1=findPoint(name1,ll);
	Point point2=findPoint(name2,ll);	
	
	//顺时针方向路径
	double rightPath=rightPath(point1,point2);
    //逆时针方向路径
	double leftPath=leftPath(point1,point2);
	
	return min(rightPath,leftPath);
  }//end shortestPath()

主函数中调用的函数

  //------------------------------------------------------
  // private method
  //------------------------------------------------------
  
  //初始化双端链表，将距离和站点名称列入双端链表
  private void initial(String[] pointName,double[] distance) throws Exception{
    if(pointName==null || distance==null){
		 throw new Exception("请输入站点名称 或 站点距离");
	
	int pointNumber=pointName.length();
	if(pointNumber!=distance.length())
	    throw new Exception("站点数目要和距离数目一致");
		
    //至少要有2个站点
	if(pointNumber< 2)
	    throw new Exception("至少要有2个站点");
	
	//第一个站点和最后一个站点要特殊处理下（数组下标对应关系可以从图中看出来）
	Point firstPoint=new Point(pointName[0],distance[0+1],distance[0]);
		ll.addLast(firstPoint);
	
	if(pointNumber>=2){ //如果多于2个剩余元素（除了第一个站点和最后一个站点）按以下规则添加
	    for(int i=1;i<pointNumber-1;i++){
	        Point point=new Point(pointName[i],distance[i+1],distance[i]);
			ll.addLast(point);
	    }//end for
	}//end if

	 //最后一个元素添加
	Point lastPoint=new Point(pointName[pointNumber-1],distance[0],distance[pointNumber-1-1]);
	ll.addLast(lastPoint);
  }//end initial()

  //------------------------------------------------------
  private Point findPoint(String name,LinkedList ll){
     Point point=null;
	 
     Iterator it=ll.iterator();
	 while(it.hasNext()){
	    point=(Point)it.next();
		if(point.getName.equels(name))
		  return point;
	 }//end while
  }//end findPoint()
  
  //------------------------------------------------------  
  //顺时针方向路径
  private double rightPath(Point point1,Point point2){
    double result=0; //存储路径值
	Point current=point1;
	
	while(current!=point2){
	  result+=current.getnextPointDistance();
	  current=current.next(); //指向下一个站点
	}//end while
	
	return result;
  }//end rightPath()

  //------------------------------------------------------   
   //逆时针方向路径
  private double leftPath(Point point1,Point point2){
    double result=0; //存储路径值
	Point current=point1;
	
	while(current!=point2){
	  result+=current.getpreviousPointDistance();
	  current=current.previous(); //指向前一个站点
	}//end while
	
	return result;
  }//end leftPath()  
  
  //获取较小值
  private double min(double a,double b){
    if(a<b)
	  return a;
	else
	  return b;
  }//end min()
      
}//end class HighRoad

测试用例设计：

1、只有一个站点
2、只有2个站点
3、多于2个站点

第二道程序设计题

//---------------------------------------------------
public class AlgorithmReverse{
Stack stack; //栈
StringBuffer sb; //保存翻转结果

public AlgorithmReverse(){
   stack=new Stack();
   sb=new StringBuffer();
}

public String reverse(String src){
   //输入控制
    if(src==null || src=="")
      return src;  
    
	else{
        for(int i=0;i<src.length(); ){
		   //入栈
		   char temp=src.getChar(i);
		   if( temp !=' ')
		      stack.push(temp);
		   //出栈
		   else{
		      if(!stack.empty()){
			     for(int j=0;j<stack.size();j++){
				    sb.append(stack.pop());
				 }//end for
			  }//end if
		   }//end else
		   //只加入一个空格
		   sb.append(' ');
		   //删除重复空格，返回下一个i的值
		   i=deleteSpace(src,i+1);
		}//end for
		
		return sb.toString();
	}//end else	
}//end reverse()
//---------------------------------------------------
		//删除重复空格，返回下一个i的值
		private int deleteSpace(src,int i){
		 while(src.getChar(i) !=' '){
		    i++;
		 }//end while
		 
		 return i;
		}//end delteSpace()

} //end class AlgorithmReverse
//------------------------------------

第三道程序设计题