C++刷题：环状DNA序列整理

大家好，欢迎来到IT知识分享网。

问题描述：

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

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

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

例如：

`ATCA` 的最小表示是 `AATC`

`CGAGTC` 的最小表示是 `AGTCCG`

其中：

`n <= 100`

DNA 由大写英文字母 `A`、`G`、`C`、`T` 组成

示例 1

输入：`ATCA`

输出：`AATC`

示例 2

输入：`CGAGTC`

输出：`AGTCCG`

问题分析：

        最直观的想法，便是将环状DNA所有可能的表示全部存储起来，然后进行字典序比较。输出字典序最小的表示。从头开始遍历DNA序列，分别以当前碱基作为起始形成一段序列，需要两重循环，时间复杂度为O()。而比较字典序最小，则可以直接使用每条序列第一个字符的ASCII码值对比即可。

        当两条序列的第一个字典序相同时，继续往后比较下一个碱基的字典序，直到比较出最小字典序的序列。完整代码如下：

#include <iostream> #include <string> #include <vector> using namespace std; std::string solution(std::string dna_sequence) { // Please write your code here int n = dna_sequence.size(); vector<std::string> st; for (int i = 0; i < n; ++i) { string curSt; //从 i 开始生成一种表示法，并添加到 st 向量中 for (int j = 0; j < n; ++j) { curSt += dna_sequence[(i + j) % n]; } st.push_back(curSt); } //此时st中存储了环状DNA全部的可能表示 //找字典序最小 string minSt = st[0]; for (const auto &s : st) { if (s < minSt) { minSt = s; } } return minSt; } int main() { // You can add more test cases here std::cout << solution("ATCA") << std::endl; std::cout << solution("CGAGTC") << std::endl; std::cout << solution("TCATGGAGTGCTCCTGGAGGCTGAGTCCATCTCCAGTAG") << std::endl; return 0; }