`
ZeaLoVe
  • 浏览: 89471 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

第一篇博客 记百度实习生测试开发 电话面试题

 
阅读更多
忽然决定慢慢记录自己的一点点心得,只是为了不过于快的忘记这些曾经的思考。恩,没有别的目的。第一篇博客就献给这两个不怎么难的题目吧。缘由是自己正准备一个内推面试,所以问了确定去百度实习的一个同学,他说到他在电话面试中遇到的这两个问题,确实,因为电话面试的原因,这两题不难,所以回来我就顺手写写解决下。
先说题目,第一题:给出一组数字,求这组数字的平衡数,平衡数的定义是,该数字左边所有数字的和与右边所有数字的和相等。
我的思路是拿一个数组sum ,sum[i]记录的是从0-i 所有给定数组的和,然后,从给定数组的尾部(除去最后一个)开始遍历sum数组,同时拿一个值记录从尾部相加的和,但这个和等于Sum中对应位置的值时候,这个点就是平衡点了
我目测过了 00000 这样的数据,有负数也没问题。但如果中间结果累加起来的和大于最大整形的值,那我就崩溃了。。

	int i,n;
	int a[100];
	int sum[100];
	cin>>n;
	cin>>a[0];
	sum[0]=a[0];
	for( i = 1 ; i < n ; ++i )
	{
		cin>>a[i];
		sum[i]=a[i] + sum[i-1];
	}

	int ReserveSum=a[n-1];
	for( i = n-2 ; i > 0 ; --i )//从倒2个开始 到第二个数字
	{
         ReserveSum+= a[i];
         if( sum[i] == ReserveSum )
         {
        	 cout<<"Num in index: "<<i<<" is balance number!"<<endl;
         }
	}

(补充一个该题变种)一个整数数组,有n个整数,如何找其中m个数的和等于另外n-m个数的和?
是不感觉基本一样呢。。其实只要修改一个地方就可以了,sum[i] == ReserveSum 改成sum[i-1] == ReserveSum 完成。

第二题:输入是一串字符,输出其中重复的字符(出现超过一次的)。
这个思路是遍历字符串,用一个数组记录某个字符串出现的次数,由于字符串本质是8位的数字,所以其实ASCII字符集合的大小也就256以内。这个原理类似于散列表。输入完毕后,遍历这个256大的数组,输出大于1的字符即可。
    int i;
	string a;
	cin>>a;
	int count[257];
	for(i=0;i<256;i++)
	{
		count[i]=0;
	}
    for(i=0;i<a.size();i++)
    {
 	    count[ a[i] ]+=1;
    }
    cout<<endl;
	for(i=0;i<256;i++)
	{
	      if( count[i] >1 ){cout<<char(i)<<" ";}
	}	
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics