首页 » C++ » 阿里笔试——RNA嵌套

阿里笔试——RNA嵌套

原文 http://blog.csdn.net/u013949069/article/details/74885829

2017-07-09 18:20:05阅读(773)

题目:

一条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行,每行都有四个正整数,表示一个二段模式的四个下标。

输出:

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

输入范例:

4

0 1 99 100

10 12 13 15

20 23 26 29

30 35 40 45

输出范例:

2

解析:

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

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

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

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

(1)该元素包含maxT, 则更新maxT为该元素,且把该元素加入嵌套集合;

(2)该元素被minT包含,则更新minT为该元素,并把该元素加入嵌套集合;

(3)该元素被maxT包含且包含minT,则把该元素加入嵌套集合;

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

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

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

代码:

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <cassert>
#include <map>
#include <algorithm>
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<TwoInterval>& 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<TwoInterval>& 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<TwoInterval> twos;
	input(twos);
	cout << intussusception(twos) << endl;
	return 0;
}



最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹