首页 > 笔试面试题, 算法 数据结构 > Twitter online 两题

Twitter online 两题

2013年6月15日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

今天有个群里发了两道twitter online的题目,看了下,练手写一下。

题一:

A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0..N−1]. Sets S[K] for 0 ≤ K < N are defined as follows: S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }. Sets S[K] are finite for each K.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns the size of the largest set S[K] for this array. The function should return 0 if the array is empty.

原题不存在数组元素不小于len的情况,后面的两种解法都是考虑元素有大于len的情况,开始没看清,做了个稍微复杂的情况;区别在于,如果元素不越界,S集合就是一个个的环,当元素值等于下标值,环大小为1;如果元素有越界情况,则S集合就不一定是环,就需要记录之前遍历的集合大小了,先给出本题的解法,后面讨论元素越界的情况。

class Solution
{
public:
	int solution(int * A, int len)
	{
		if(NULL == A || len <= 0)
		{
			return 0;
		}

		int maxSet = 1, count = 0;
		for(int i = 0, j, index; i < len; ++i)
		{
			index = i;
			while(A[index] >= 0)
			{
				++count;
				j = index;
				index = A[index];
				A[j] = -1;
			}
			maxSet = count > maxSet ? count : maxSet;
			count = 0;
		}
		return maxSet;
	}
};

如下,考虑数组元素值有越界的情况
解法一:备忘搜索

这道题目最简单就是暴搜,但是搜索过程中会有已经搜过点,故做一个备忘录,这样算法时间复杂度可以达到O(n),空间O(n);

代码如下:

其中,M数组作为备忘录,记录已经搜过的点作为S集合起始点的集合大小;关键是递归函数sizeCount,递归回溯时可以将本次遍历过程中每个点作为集合起始点时的集合size存入M数组,在该函数中,如果计算过则直接+1,无需再遍历;

在solution函数中,遍历的过程中如果M计算过则可以直接跳过了,都无需与maxSet进行判断,原因就不赘述了。

class Solution
{
private:
	int sizeCount(int * A, int * M, int i, int len)
	{
		int count = 1;
		if(A[i] < len)
		{
			if(M[A[i]] == 0)
			{
				count = 1 + sizeCount(A,M,A[i],len);
			}else  // pruning
			{
				count = 1 + M[A[i]];
			}
		}
		M[i] = count;
		return M[i];
	}
public:
	int solution(int * A, int len)
	{
		if(NULL == A || len <= 0)
		{
			return 0;
		}

		int maxSet = 0;
		int * M = new int [len]; // memorandum
		memset(M,0,sizeof(int)*len);

		for(int i = 0; i < len; ++i)
		{
			if(M[i] == 0)
			{
				M[i] = sizeCount(A,M,i,len);
				if(M[i] > maxSet)
				{
					maxSet = M[i];
				}
			}// pruning-if M[i]!=0 then M[i] <= maxSet
		}
		delete [] M;
		return maxSet;
	}
};

测试如下:

// Simple Test
void main()
{
	Solution testCase;

	int A[] = {1,2,3,4,5,6};
	printf("%d\n", testCase.solution(A,6));

	int B[] = {1,4,5,0,2,6};
	printf("%d\n", testCase.solution(B,6));
}

解法二:并查集
题目也是典型的合并集合,找最大集合size,并查集的应用,使用并查集,注意的是这个题目集合合并的是A数组的“下标”,代码如下:

class Solution
{
private:
	class UnionSet
	{
	public:
		int * father, * num, maxSize;
		// make set
		UnionSet(int len):maxSize(1)
		{
			father = new int [len];
			num = new int [len];
			for(int i = 0; i < len; ++i)
			{
				num[i] = 1;
			}
			for(int i = 0; i < len; ++i)
			{
				father[i] = i;
			}
		}
		~UnionSet()
		{
			delete [] father;
			delete [] num;
		}
		// find set
		int findSet(int x)
		{
			if(x != father[x])
			{
				father[x] = findSet(father[x]);
			}
			return father[x];
		}
		// union
		void unionSet(int a, int b)
		{
			int x = findSet(a);
			int y = findSet(b);
			if(x == y)
			{
				return;
			}
			if(num[x] >= num[y])
			{
				father[y] = x;
				num[x] += num[y];
				maxSize = num[x] > maxSize ? num[x]: maxSize;
			}else
			{
				father[x] = y;
				num[y] += num[x];
				maxSize = num[y] > maxSize ? num[y]: maxSize;
			}
		}
	};

public:
	int solution(int * A, int len)
	{
		if(NULL == A || len <= 0)
		{
			return 0;
		}
		UnionSet unionSet(len);
		for(int i = 0; i < len; ++i)
		{
			if(A[i] < len)
			{
				unionSet.unionSet(i,A[i]);
			}
		}
		return unionSet.maxSize;
	}
};

测试示例可参考解法一后面的test case。

题二:

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001) and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps.

Write a function:

class Solution { public int solution(int N); }

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5.

Assume that:

N is an integer within the range [1..2,147,483,647].

Complexity:

expected worst-case time complexity is O(log(N));

expected worst-case space complexity is O(1).

Copyright 2009–2013 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

这个题目的解决方案就不分析了,较简单,只是在写的时候,尽可能让代码简洁些吧,如下:

class Solution
{
public:
	int solution(int N)
	{
		// count = 0 indicates getting in Gap; -1 not.
		int maxGap = 0, count = -1, x = 0;
		while(N)
		{
			x = N & 1;
			N = N >> 1;
			if(0 == x && count >= 0)
			{
				++count;
			}
			if(1 == x)
			{
				maxGap = count > maxGap ? count : maxGap;
				count = 0;
			}
		}
		return maxGap;
	}
};

测试如下:

// Simple Test
void main()
{
	Solution testCase;

	printf("%d\n",testCase.solution(529)); // 4
	printf("%d\n",testCase.solution(9));   // 2
	printf("%d\n",testCase.solution(20));  // 1
	printf("%d\n",testCase.solution(15));  // 0
	printf("%d\n",testCase.solution(1041));  // 5
}

(全文完)

  • Tutu

    膜拜大神!

  • Rick

    备忘搜索 has some problem, try {2, 3, 4, 5, 6, 7, 0, 1}, which would be dead lock

  • flying

    对不起,是我想错了。你是对的。

    • Yx.Ac

      :-)

  • flying

    第一段程序好像有bug吧?访问标记直接在原数组上修改了,导致每轮大循环计算count时取数组元素时数据已经被篡改了。感觉应该有更快的算法。但还没想清楚。

  • Haiming Wang

    无越界情况下的解法是不是有点问题?考虑两个环share一些元素的情况。

    • Yx.Ac

      @Haiming Wang 这种情况不存在吧?如果是两个环share则就存在重复元素了,题目中说了都是不同的数字。