当前位置:首页 » 编程语言

腾讯2015实习生招聘模拟考--其中一题

2015-03-22 21:36 本站整理 浏览(213)

描述:

DNA中有A、C、G、T等基因单元吧,ACGT算是在单词表中的正常顺序,而CA,GA,GC,TA,TC,TG算是逆序对,给你一个基因序列,即包含A、C、G、T的字符串数组,请在线性时间复杂度内求出逆序对的个数。

思路:

先用四个变量第i个字符前的A、C、G、T字符数存储起来,当道第i个字符时,假设第i个字符为C,则对于C前面出现的字符G,T所出现的次数即为构成的逆序对GC和TC逆序对的个数,题目得解。

代码:

public static int inversionPairsCount(String str)
	{
		int countFinal=0;
		int arr[]=new int[4];
		Arrays.fill(arr, 0);
		int len=str.length();
		int i=0;
		char ch;
		while(i<len)
		{
			ch=str.charAt(i);
			i++;
			switch (ch) {
			case 'A':
				{
					arr[0]++;
					countFinal=countFinal+arr[1]+arr[2]+arr[3];
				}
				break;
			case 'C':
				{
				    arr[1]++;
				    countFinal=countFinal+arr[2]+arr[3];
				}
				break;
			case 'G':
				{
					countFinal=countFinal+arr[3];
					arr[2]++;
				}
				break;
			default:
					arr[3]++;
				break;
			}
		}
		return countFinal;
	}