首页 > 专题系列 > Java解POJ > POJ 3080 Blue Jeans [解题报告] Java
2013
11-12

POJ 3080 Blue Jeans [解题报告] Java

Blue Jeans

问题描述 :

The Genographic Project is a research partnership between IBM and The National Geographic Society that is analyzing DNA from hundreds of thousands of contributors to map how the Earth was populated.

As an IBM researcher, you have been tasked with writing a program that will find commonalities amongst given snippets of DNA that can be correlated with individual survey information to identify new genetic markers.

A DNA base sequence is noted by listing the nitrogen bases in the order in which they are found in the molecule. There are four bases: adenine (A), thymine (T), guanine (G), and cytosine (C). A 6-base DNA sequence could be represented as TAGACC.

Given a set of DNA base sequences, determine the longest series of bases that occurs in all of the sequences.

输入:

Input to this problem will begin with a line containing a single integer n indicating the number of datasets. Each dataset consists of the following components:
  • A single positive integer m (2 <= m <= 10) indicating the number of base sequences in this dataset.
  • m lines each containing a single base sequence consisting of 60 bases.

输出:

For each dataset in the input, output the longest base subsequence common to all of the given base sequences. If the longest common subsequence is less than three bases in length, display the string “no significant commonalities” instead. If multiple subsequences of the same longest length exist, output only the subsequence that comes first in alphabetical order.

样例输入:

3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

样例输出:

no significant commonalities
AGATAC
CATCATCAT

解题代码:

方法一:
import java.util.*;

public class Main
{
 static String w[] = new String[10];
 public static void main(String args[])
{
   int t, n, i, j = 0, k;
   Scanner cin = new Scanner( System.in );
       
   t = cin.nextInt();
   String p = new String();
   String best;// = new String("");
       
   while( t-- != 0 ) {
     n = cin.nextInt();
     best = "";
     for( i=0; i< n; i++ )
  	   w[i] = cin.next();

     for( i=w[0].length(); i>=3; i-- ) {
        for( j=0; j<=w[0].length()-i; j++ ) {
    	    p = w[0].substring( j, i+j );
    	    for( k=1; k< n; k++ ) {
    		if( w[k].indexOf( p ) == -1 )
    		   break;
    	    }
    			   
    	   if( k == n && ( best == "" || p.compareTo( best ) < 0 ) )
    		   best = p;
    	}
   	if( best != "" )
   	   break;
    }
    if( i >= 3 )
	System.out.println( best );
   else
	System.out.println( "no significant commonalities" );
  }
  return;
 }
}


方法二:
import java.io.IOException;   
import java.util.ArrayList;   
import java.util.List;   
import java.util.Scanner;   
  
public class Main {   
       
    public static void main(String[] args) throws IOException {   
        //Scanner scn = new Scanner(Main.class.getResourceAsStream("in.dat"));   
        Scanner scn = new Scanner(System.in);   
        int n,m = 0;   
        List data = null;;   
        while(true){   
            n = scn.nextInt();   
            for(int i = 0; i < n; i++){   
                data = new ArrayList();   
                m = scn.nextInt();   
                for(int j = 0; j < m; j++){   
                    data.add(scn.next());   
                }   
                System.out.println(work(data,data.size()));   
            }   
            return;   
               
        }   
           
    }   
  
    private static String work(List data, int m) {   
        String str = data.get(0);   
        int len = str.length();   
        String sub = "";   
        String common = "";   
        int size = 0;   
        boolean find = false;   
        for(int i = 0; i < len - 1; i++){   
            for(int j = i; j < len; j++){   
                sub = str.substring(i,j + 1);   
                int k = 0;   
                for(k = 1; k < m; k++){   
                    if(data.get(k).indexOf(sub) == -1){   
                        find = false;   
                        break;   
                    }   
                }   
                if(k == m){   
                    find = true;   
                }   
                if(find){//如果找到   
                    if(sub.length() < 3){   
                        continue;   
                    }   
                    if(sub.length() == size && common.compareTo(sub) > 0){   
                        common = sub;   
                    }else if(sub.length() > size){   
                        size = sub.length();   
                        common = sub;   
                    }   
                       
                }   
            }   
        }   
           
        return size == 0?"no significant commonalities":common;   
    }   
  
}

  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!