UVa1584 Circular Sequence -- Jav

我在 github 上建立了一个 repo，专门记录自己对刘汝佳的《算法竞赛入门经典（第二版）》中每个 UVa 例题和习题的解答，目前刚刚开始，会不断更新，本人水平不高，如有错误，欢迎大家指正。当然更希望大家能提供更优的解法，共同提高进步，满意的话给个 star 啊(●ˇ∀ˇ●)

github repo 传送门

QQ: 1583801169

【原题链接】点击即达

不过UVa OJ需要科学上网才能访问，故此处贴出百度云链接，有原题的pdf文档，需要的直接下载。失效的话可以私信或者评论留下邮箱。
链接：https://pan.baidu.com/s/1C8806zQyE5-WANmgXByfPA
提取码：atqz

【题意】
  输入一个长度为 n(2 <= n <= 100) 的环状 DNA 串（只包含 A C G T），输出该 DNA 串的最小表示。例如，CTCC 的最小表示是 CCCT，CGAGTCAGCT 的最小表示为 AGCTCGAGTC。

  其中，我们能看出题意给的是一个 环状DNA串，故可以知道对于这样一个 DNA 串，有 n(DNA串的长度) 种表示，对于一个非环状的串，其表示应该有 n! 种，即全排列。故只需在 n 种表示中找出最小表示即可。

【输入】
  输入一个正整数 T，表示有 T 个 DNA 串，你需要求出这 T 个 DNA 串的最小表示。然后输入 T 个 DNA 串，每个一行。

【输出】
  每个 DNA 串的最小表示分别占一行。

【代码】

less() 函数的作用是比较以 p 开头的 DNA 串 cs 和以 q 开头的 DNA 串 cs 谁大谁小，以此来更新记录该 DNA 串 cs 最小表示的开始位置 ans。

import java.util.Scanner;

/**
 * @author Adonis
 * @Email 1583801169@qq.com
 * @Date 2019-01-18 11:11:09
 * @Version V1.0
 */

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int c = in.nextInt();
        
        for (int i=0; i<c; i++) {
            String s = in.next();
            char[] cs = s.toCharArray();
            int len = cs.length;
            int ans = 0;    // the beginning of the lexicographically smallest sequence for the test case 
            
            for (int j=1; j<len; j++) { // find the ans
                if (less(cs, j, ans)) {
                    ans = j;
                }
            }
            
            for (int j=0; j<len; j++) {
                System.out.print(cs[(ans+j)%len]);
            }
            System.out.println();
        }
        in.close();
    }
    
    /**
     * compare p and q to find
     * the lexicographically smallest sequence starting with p or q
     * @param cs 测试字符串的数组形式 
     * @param p  以p为开始的字符串cs
     * @param q  以q为开始的字符串cs
     * @return
     */
    private static boolean less(char[] cs, int p, int q) {
        int len = cs.length;
        for (int i=0; i<len; i++) { // 循环进行两个字符串同一个位置比较
            if (cs[(p+i)%len] != cs[(q+i)%len]) {   // 不相同
                return cs[(p+i)%len] < cs[(q+i)%len];
            }
        }
        return false;   // 相同无需比较，直接返回
    }

}