当前位置：首页 > article >正文

40环状DNA序列的最小表示法Java版-青训营刷题

article 2025/2/12 7:52:11

问题描述

小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) {
        // 将 DNA 序列加倍
        String doubledDna = dna_sequence + dna_sequence;
        // 初始化最小顺序为原始 DNA 序列
        String minOrder = dna_sequence;

        // 遍历加倍后的字符串，寻找最小的子串
        for (int i = 1; i < dna_sequence.length(); i++) {
            // 提取从当前索引开始的子串，长度与原始 DNA 序列相同
            String substring = doubledDna.substring(i, i + dna_sequence.length());
            // 如果当前子串比当前最小顺序更小，则更新最小顺序
            if (minOrder.compareTo(substring) >= 0) {
                minOrder = substring;
            }
        }

        return minOrder;
    }

    public static void main(String[] args) {
        // 测试用例
        System.out.println(solution("ATCA").equals("AATC")); // 输出 true
        System.out.println(solution("CGAGTC").equals("AGTCCG")); // 输出 true
        System.out.println(solution("TCATGGAGTGCTCCTGGAGGCTGAGTCCATCTCCAGTAG").equals("AGGCTGAGTCCATCTCCAGTAGTCATGGAGTGCTCCTGG")); // 输出 true
    }
}

代码解释

代码功能概述

这段代码的目的是找到一个 DNA 序列的最小循环子串。具体来说，对于一个给定的 DNA 序列，我们希望找到一个最小的子串，使得这个子串可以通过循环移位得到原始序列。例如，对于 DNA 序列 "ATCA"，其最小循环子串是 "AATC"，因为 "AATC" 是通过将 "ATCA" 循环左移一位得到的。

代码结构

代码包含一个 Main 类，其中定义了两个方法：

solution 方法：实现核心逻辑，用于找到最小循环子串。
main 方法：测试 solution 方法的正确性。

代码详细解释

1. `solution` 方法

java复制

public static String solution(String dna_sequence) {
    // 将 DNA 序列加倍
    String doubledDna = dna_sequence + dna_sequence;
    // 初始化最小顺序为原始 DNA 序列
    String minOrder = dna_sequence;

    // 遍历加倍后的字符串，寻找最小的子串
    for (int i = 1; i < dna_sequence.length(); i++) {
        // 提取从当前索引开始的子串，长度与原始 DNA 序列相同
        String substring = doubledDna.substring(i, i + dna_sequence.length());
        // 如果当前子串比当前最小顺序更小，则更新最小顺序
        if (minOrder.compareTo(substring) >= 0) {
            minOrder = substring;
        }
    }

    return minOrder;
}

关键逻辑解释

加倍 DNA 序列：

java复制
```
String doubledDna = dna_sequence + dna_sequence;
```
- 为了能够比较所有可能的循环子串，我们将原始 DNA 序列加倍。例如，对于 "ATCA"，加倍后的结果是 "ATCAATCA"。这样可以方便地通过索引截取所有可能的循环子串。
初始化最小顺序：

java复制
```
String minOrder = dna_sequence;
```
- 将 minOrder 初始化为原始 DNA 序列。这是为了在循环中有一个初始的比较基准。
循环遍历加倍后的字符串：

java复制
```
for (int i = 1; i < dna_sequence.length(); i++) {
    String substring = doubledDna.substring(i, i + dna_sequence.length());
    if (minOrder.compareTo(substring) >= 0) {
        minOrder = substring;
    }
}
```
- 循环范围：从索引 1 开始，一直到 dna_sequence.length() - 1。这是因为索引 0 对应的子串就是原始 DNA 序列本身。
- 提取子串：通过 doubledDna.substring(i, i + dna_sequence.length()) 提取从索引 i 开始的子串，长度与原始 DNA 序列相同。例如，对于 "ATCAATCA"，当 i = 1 时，提取的子串是 "TCAATC"。
- 比较子串：使用 compareTo 方法比较当前子串和 minOrder。如果当前子串更小（或相等），则更新 minOrder。
返回结果：

java复制
```
return minOrder;
```
- 最终返回找到的最小循环子串。

2. `main` 方法

java复制

public static void main(String[] args) {
    // 测试用例
    System.out.println(solution("ATCA").equals("AATC")); // 输出 true
    System.out.println(solution("CGAGTC").equals("AGTCCG")); // 输出 true
    System.out.println(solution("TCATGGAGTGCTCCTGGAGGCTGAGTCCATCTCCAGTAG").equals("AGGCTGAGTCCATCTCCAGTAGTCATGGAGTGCTCCTGG")); // 输出 true
}