POJ1007 DNA Sorting

这个主要是计算字符串的逆序数并且排序。

 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int strLen = cin.nextInt();
        int strCount = cin.nextInt();
        cin.nextLine();
        List<DNA> dnaList = new ArrayList<DNA>();

        for(int idx = 0;idx<strCount;idx++){
            String dnaStr = cin.nextLine();
            dnaList.add(new DNA(dnaStr,calcInversionNum(dnaStr)));
        }

        Collections.sort(dnaList,new Comparator<DNA>() {
            public int compare(DNA o1, DNA o2) {
                return o1.getInversionNum()-o2.getInversionNum();
            }
        });


        for (DNA dna : dnaList) {
            System.out.println(dna.getDnaStr());
        }
    }
    
    private static int calcInversionNum(String dnaStr){
        char[] charArray = dnaStr.toCharArray();
        int inversionNum = 0;
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            for (int j = i+1;j < charArray.length;j++){
                if(c>charArray[j]){
                    inversionNum++;
                }
            }
        }
        return inversionNum;
    }
    
    
    static class  DNA {
        private String dnaStr;
        private int inversionNum;

        DNA(String dnaStr, int inversionNum) {
            this.dnaStr = dnaStr;
            this.inversionNum = inversionNum;
        }

        public String getDnaStr() {
            return dnaStr;
        }

        public void setDnaStr(String dnaStr) {
            this.dnaStr = dnaStr;
        }

        public int getInversionNum() {
            return inversionNum;
        }

        public void setInversionNum(int inversionNum) {
            this.inversionNum = inversionNum;
        }
    }
}