博客

笔试代码题–搜狗–汪仔做对的题数范围

注意：朋友对了k道题，不一定是str1中的所有对。


* 题目：总共n道题，汪仔知道朋友做的k道题是对的，他知道自己做的题目是str1，问最少对几道，最多对几道

求start:不一样的题目数d： d = n – count，如果d>k,比如n=5,k=3,c=1,d=4,也就是有可能不确定的4道都错，而且一样的也错，对的最少是0道。

但是如果d<k,比如：n=5,k=4,c=2,d=3，因为朋友对了4道，其中两道一样，就算不确定的3道都是错的，剩下的1道也是对的。

最差举例：原题正确答案：AAAAA,朋友：AAABA,汪仔：BBABD，朋友对了4道，1，2，3，5，汪仔对了1道：3，朋友和汪仔相同的2道：3,4。

求end:一样的count大于朋友做对的题数k，那么最大值就是不一样的全对，加上k道也全对，

否则就是，一样的count小于朋友做对的题数k，那么最大值就是一样的都对加上除了对的k剩下的也都对。

count<k,举例：原题正确答案：AAABD,朋友：AAABB,汪仔：AAAAD，朋友对了4道，1，2，3，4，汪仔对了4道：1，2，3，5，朋友和汪仔相同的3道：1，2，3。算法就是，一样的全对， 不确定的也对。

struct Interval
{
	int start;
	int end;
};
class Solution
{
public:
	/*
	* 注意：朋友对了k道题，不一定是str1中的所有对，
	* 题目：总共n道题，汪仔知道朋友做的k道题都是对的，他知道自己做的题目是str1，问最少对几道，最多对几道
	* n :int 整型 总题数
	* k :int整型 朋友作对的题数，
	* str1 :string字符串 长度为n只包含ABCD的字符串，其中第i个代表汪仔的题目
	* str2 :string字符串 长度为n只包含ABCD的字符串，其中第i个代表朋友的题目
	*/
	Interval solve(int n, int k, string str1, string str2)
	{
		int start = 0;
		int end = 0;
		int count = 0;
		for (int i = 0; i < n; i++)
		{
			if (str1[i] == str1[i])
				count++;
		}//相同的题数是count
		int d = n - count;//不一样的题目数d
		start = (d < k) ? (k - d) : 0;
		end = (count > k) ? (d + k) : (count + n - k);
		
		return { start,end };
	}
};