环状DNA序列的最小表示法

问题描述

环状 DNA 又称超螺旋，即一段碱基序列呈现环状，在分析时，需要将相同序列的环状 DNA 分到相同组内，现需将环状碱基序列按照最小表示法进行排序。

一段长度为 n 的碱基序列，按照顺时针方向，碱基序列可以从任意位置起开始该序列顺序，因此长度为 n 的碱基序列有 n 种表示法。例如：长度为 6 的碱基序列 CGAGTC，有 CGAGTC、GAGTCC、AGTCCG 等表示法。在这些表示法中，字典序最小的称为“最小表示”。

输入一个长度为 n（n <= 100）的环状碱基序列（只包含 A、C、G、T 这 4 种碱基）的一种表示法，输出该环状碱基序列的最小表示。

例如：
ATCA 的最小表示是 AATC
CGAGTC 的最小表示是 AGTCCG

输入描述

一段 DNA 碱基序列

输出描述

DNA 碱基序列的最小表示

备注：
n <= 100
DNA 由大写英文字母 A、G、C、T 组成

示例 1
输入：ATCA
输出：AATC

示例 2
输入：CGAGTC
输出：AGTCCG

解题思路

理解环状序列：
- 环状序列可以看作是一个长度为 n 的字符串，可以从任意位置开始。
- 例如，序列 ATCA 可以有以下表示：ATCA, TCAA, CAAT, AATC。
生成所有可能的表示：
- 对于一个长度为 n 的序列，可以生成 n 种不同的表示。
- 具体来说，对于序列 s，我们可以通过将 s 循环移位来生成所有可能的表示。
比较字典序：
- 生成所有可能的表示后，我们需要比较这些表示的字典序，找到最小的那个。
优化比较：
- 直接生成所有表示并比较可能会导致不必要的计算。我们可以通过一些技巧来优化这个过程，例如使用双指针或滑动窗口来比较字符串。

算法步骤

初始化最小表示：
- 将输入序列的第一个表示作为初始的最小表示。
循环比较：
- 从第二个位置开始，生成新的表示，并与当前最小表示进行比较。
- 如果新的表示比当前最小表示小，则更新最小表示。
返回结果：
- 最终得到的最小表示即为所求。

数据结构选择

使用字符串来存储和比较序列。
使用循环移位来生成所有可能的表示。

代码实现

#include <iostream>
#include <string>
#include <algorithm>std::string solution(std::string dna_sequence) {int n = dna_sequence.length();std::string min_representation = dna_sequence;// 生成所有可能的表示并比较for (int i = 1; i < n; ++i) {// 生成新的表示std::string new_representation = dna_sequence.substr(i) + dna_sequence.substr(0, i);// 比较新的表示与当前最小表示if (new_representation < min_representation) {min_representation = new_representation;}}return min_representation;
}int main() {// 你可以添加更多测试用例std::cout << (solution("ATCA") == "AATC") << std::endl;std::cout << (solution("CGAGTC") == "AGTCCG") << std::endl;std::cout << (solution("TCATGGAGTGCTCCTGGAGGCTGAGTCCATCTCCAGTAG") == "AGGCTGAGTCCATCTCCAGTAGTCATGGAGTGCTCCTGG") << std::endl;return 0;
}

关键步骤解释

初始化最小表示：
- std::string min_representation = dna_sequence;
- 将输入序列的第一个表示作为初始的最小表示。
生成所有可能的表示并比较：
- for (int i = 1; i < n; ++i)：从第二个位置开始循环。
- std::string new_representation = dna_sequence.substr(i) + dna_sequence.substr(0, i);：生成新的表示。
- if (new_representation < min_representation)：比较新的表示与当前最小表示。
- min_representation = new_representation;：如果新的表示更小，则更新最小表示。
返回结果：
- return min_representation;：返回最终的最小表示。