阿里笔试——RNA嵌套 ...-白红宇

阿里笔试——RNA嵌套 ...

阅读量：4326 次

发布时间：2019-06-06

本文共 2914 字，大约阅读时间需要 9 分钟。

题目：

一条RNA是一根链状的核酸链。其上的核酸序列被称为RNA的一级结构。由于核酸互相之间的吸引力，RNA会发生折叠，其中某个片段会和另一个片段贴在一起，使得RNA出现二维的构型，这被称为RNA的二级结构。研究RNA的折叠不仅有学术上的意义，也有医疗制药方面的价值。RNA折叠总共有三种。在这里我们只关心其中一种：嵌套。在图中，上方的折叠与左、右、下三处折叠的关系即为嵌套。从二段模式图来看，嵌套是某个折叠完全处在另一折叠的内部。

下面给嵌套下一个严格的定义。（以上废话，下面重点）

抽象地讲，一个含有n个核酸的RNA可以视作一个n长的序列。我们记X=[x0,x1]是一个区间，如果1<=x0<=x1<=n，表示一个从下标x0（包含）到x1（包含）的连续范围内的所有核酸。如果X=[x0,x1]和Y=[y0,y1]是两个区间，我们记X<Y，如果x1<y0。D=(L,R)是一个二段模式，当且仅当区间L<区间R。如果有二段模式D0=(L0,R0),D1=(L1,R1)，那么我们说D0嵌套在D1中，当且仅当有L0<L1<R1<R0。一个嵌套集是一个二段模式的集合，其中任意两个二段模式D0和D1，要么D0嵌套在D1中，要么D1嵌套在D0中。

输入:

第一行，整数m，表示接下来有m行。接下来的m行，每行都有四个正整数，表示一个二段模式的四个下标。

输出:

最大的嵌套集内的二段模式的个数。

输入范例:

0 1 99 100

10 12 13 15

20 23 26 29

30 35 40 45

输出范例:

解析：

如果输入不为空则答案至少是1，这个很好理解，因为对于任意一个有效输入，它的每一个元素本身就是一个嵌套集合。

因此，假设最大的嵌套集合包含了某个元素，假设为A，则输入中被A包含或者包含A元素的必然是属于该最大嵌套集合的（否则，包含该元素，此时的结婚比最大嵌套集合大，矛盾）。于是解决方案如下：

1、假设嵌套集合包含第一个元素，并设集合的最大元素maxT和最小元素minT均等于该元素；

2、对于其他的任意元素，根据情况处理

（1）该元素包含maxT，则更新maxT为该元素，且把该元素加入嵌套集合；

（2）该元素被minT包含，则更新minT为该元素，并把该元素加入嵌套集合；

（3）该元素被maxT包含且包含minT，则把该元素加入嵌套集合；

3、计算嵌套集合的元素个数；

4、循环1-3，只是把1中的第一个元素改为下一个元素；

5、返回嵌套结合元素个数的最大值。

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            using namespace std;class Interval{public: explicit Interval(size_t left, size_t right) : mLeft(left), mRight(right) { assert(left <= right); } size_t left() const { return mLeft; } size_t right() const { return mRight; }private: size_t mLeft; size_t mRight;};inline bool operator<(const Interval& a, const Interval& b){ return a.right() < b.left();}class TwoInterval{public: explicit TwoInterval(const Interval& left, const Interval& right) : mLeft(left), mRight(right) { assert(left < right); } const Interval& left() const { return mLeft; } const Interval& right() const { return mRight; }private: Interval mLeft; Interval mRight;};inline bool within(const TwoInterval& a, const TwoInterval& b){ return b.left() < a.left() && a.right() < b.right();}void input(vector
            
             & twos){ int m = 0; { string s; getline(cin, s); istringstream is(s); is >> m; } for (int i = 0; i < m; ++i) { string s; getline(cin, s); istringstream is(s); size_t a, b, c, d; is >> a >> b >> c >> d; Interval left(a, b); Interval right(c, d); twos.emplace_back(left, right); }}// ====== 填入你自己的逻辑 ========int intussusception(vector
             
              & twos){ int ret(0), vl(twos.size()); if (vl < 1) return ret; for (int k1(0); k1 < vl; ++k1) { TwoInterval minT(twos[k1]), maxT(twos[k1]); int sum(1); for (int k2(0); k2 < vl; ++k2) { if (k2 == k1) continue; if (within(maxT, twos[k2])) ++sum, maxT = twos[k2]; else if (within(twos[k2], minT)) ++sum, minT = twos[k2]; else if (within(minT, twos[k2]) && within(twos[k2], maxT)) ++sum; } ret = ret < sum ? sum : ret; } return ret;}// ====== 结束 ========int main() { vector
              
                twos; input(twos); cout << intussusception(twos) << endl; return 0;}

转载于:https://www.cnblogs.com/lmjy/p/7183895.html

你可能感兴趣的文章