问题描述
小C正在研究一种环状的 DNA 结构，它由四种碱基A、C、G、T构成。这种环状结构的特点是可以从任何位置开始读取序列，因此一个长度为 n 的碱基序列可以有 n 种不同的表示方式。小C的任务是从这些表示中找到字典序最小的序列，即该序列的“最小表示”。
例如：碱基序列 ATCA 从不同位置读取可能的表示有 ATCA, TCAA, CAAT, AATC，其中 AATC 是字典序最小的表示。
测试样例
样例1：
输入：
dna_sequence = "ATCA"
输出：'AATC'
样例2：
输入：
dna_sequence = "CGAGTC"
输出：'AGTCCG'
样例3：
输入：
dna_sequence = "TTGAC"
输出：'ACTTG'
方法一：枚举法
public class Main {public static String solution(String dna_sequence) {// Please write your code hereint A_num = 0;for(char ch : dna_sequence.toCharArray()){if(ch == 'A') A_num++;}if(A_num != 0){String res = dna_sequence;for(int i = 0;i < A_num;i++){int index = dna_sequence.indexOf('A');dna_sequence = dna_sequence.substring(index)+dna_sequence.substring(0,index);res = MinString(res,dna_sequence);if(dna_sequence.charAt(0) == 'A'){dna_sequence = dna_sequence.substring(1) + 'A';}}return res;}int C_num = 0;for(char ch : dna_sequence.toCharArray()){if(ch == 'C') C_num++;}if(C_num != 0){String res = dna_sequence;for(int i = 0;i < C_num;i++){int index = dna_sequence.indexOf('C');dna_sequence = dna_sequence.substring(index)+dna_sequence.substring(0,index);res = MinString(res,dna_sequence);if(dna_sequence.charAt(0) == 'C'){dna_sequence = dna_sequence.substring(1) + 'C';}}return res;}int G_num = 0;for(char ch : dna_sequence.toCharArray()){if(ch == 'G') G_num++;}if(G_num != 0){String res = dna_sequence;for(int i = 0;i < G_num;i++){int index = dna_sequence.indexOf('G');dna_sequence = dna_sequence.substring(index)+dna_sequence.substring(0,index);res = MinString(res,dna_sequence);if(dna_sequence.charAt(0) == 'G'){dna_sequence = dna_sequence.substring(1) + 'G';}}return res;}return dna_sequence;}private static String MinString(String res, String dna_sequence) {if(res.equals(dna_sequence)) return res;for(int i = 0;i < res.length();i++){if(res.charAt(i) < dna_sequence.charAt(i)){return res;}if(res.charAt(i) > dna_sequence.charAt(i)){return dna_sequence;}}return res;}public static void main(String[] args) {// You can add more test cases hereSystem.out.println(solution("ATCA").equals("AATC"));System.out.println(solution("CGAGTC").equals("AGTCCG"));System.out.println(solution("TCATGGAGTGCTCCTGGAGGCTGAGTCCATCTCCAGTAG").equals("AGGCTGAGTCCATCTCCAGTAGTCATGGAGTGCTCCTGG"));}
}
