POJ 1007 DNA Sorting O(N) 复杂度的解题思路
source link: https://blog.sbw.so/u/poj-1007-dna-sorting-accept-solution.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
POJ 1007 DNA Sorting O(N) 复杂度的解题思路
POJ 1007 这个题是一个难度一般的算法题，核心是要计算每一个字符串的权值然后累加并排序。在本题中，这个权值是指为字符串中的每一个字母计算它后面有多个个字母比它小，即发生了多个次“反转”。从这个描述的一般认识来看，这是个 N^2 复杂度的模拟问题，核心在于算法优化及找模型。但由于题目的测试数据比较简单，使用 N^2 复杂度的简单方法也可以很容易通过。这就导致了这个题目的实际比赛难度其实很低。这里从解题思路及推导过程给大家做一个线性复杂度，O(N) 解题方法的分享。
首先我们来分析一下这个题目的特点，它说计算一个DNA串的反转值，那么我们以下面这个串为例，做一次计算。为了方便统计，我们把每个字母位上的反转值都标注出来：
// A(0) - C(1) - G(2) - T(3) - G(2) - C(1) - A(0)通过简单的观察，我们首先能发现几个简单的特点：
1. 字母 'A' 是不会产生权重的，因为在它的右边不可能出现更小的字母。
2. 最右边的字母是不会产生权重的，因为它在右边没有其它字母。
3. 对于字母 'T' 来说，它产生的权重就是它右边所有非 'T' 的字母的个数，因为其它所有字母都比它小。
找递推关系
通过上面手动计算的过程可以发现，我们的关注点往往是一个字母及它右边的部分，即一个字母左边的其它字母是不影响的。所以第二步，我们尝试在上一个字母序列的左边增加一个项，看看字符串变长的过程中会发生什么：
// A(0) - C(1) - G(2) - T(3) - G(2) - C(1) - A(0)// A(0) - A(0) - C(1) - G(2) - T(3) - G(2) - C(1) - A(0)// G(4) - A(0) - C(1) - G(2) - T(3) - G(2) - C(1) - A(0)// C(2) - A(0) - C(1) - G(2) - T(3) - G(2) - C(1) - A(0)// T(6) - A(0) - C(1) - G(2) - T(3) - G(2) - C(1) - A(0)通过增加的四种字符串可以发现，在左边增加的字符串是可以由右边计算出来的，并且对右边已经计算好的字符串的权值没有影响。这个推论可以告诉们，如果从右往左进行扫描，并且找到最左侧一个字符权值与已扫描字符串的关系的话，这个题就可以有线性的解决方法了。
然后经过简单分析，结合上一步发现的3个特点并找规律可以得出：最左边一个字符的权值就是右边已经发现的字符中小于它的字符的个数，而这个个数在从右往左的扫描中是可以很方便记录下来的，于是就可以写出解题代码：
0MS O(N) AC 代码
#include <cstdio>#include <algorithm>struct S {char s[51];int value;};S data[100];int len, count;int calc(char *s){int a(0), g(0), c(0), t(0);int r(0);for (int i(len - 1); i != -1; --i){switch (s[i]){case 'A':++a;break;case 'C':++c;r += a;break;case 'G':++g;r += a + c;break;case 'T':++t;r += a + c + g;break;default:;}}return r;}bool f(const S a, const S b) {return a.value < b.value;}int main(){scanf("%d %d", &len, &count);for (int i(0); i != count; ++i){scanf("%s", data[i].s);data[i].value = calc(data[i].s);}std::sort(data, data + count, f);for (int i(0); i != count; ++i){//printf("%s %d\n", data[i].s, data[i].value);printf("%s\n", data[i].s);}return 0;}这里的 calc 函数就是计算一个字符串权值的核心代码，从右往左扫描，记录已经发现的各个字母的数量，当前扫描的字母的权值可以直接由这个数据算出，经过一次扫描后，整个字符串的权值之和就累加要变量 r 中了。
同时这里有两个小优化，一个是由于题目给出的数据范围很小，不妨直接定义最大范围的数据结构来减少运行时内存申请，第二个是直接使用 STL 的 std::sort 进行排序，但由于 POJ 的系统编译器版本比较低，不支持 Lambda 表达式，所以使用 f 这个函数作为 Compare Function 进行处理。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK