1.问，以下代码在x86平台下输出啥？

int main(void) {         int a[4] = {1, 2, 3, 4};    int *ptr1=(int *)(&a+1);          int *ptr2=(int *)((int)a+1);          printf("%x, %x\n", ptr1[-1], *ptr2);          return 0;  }

解答：00000004，02000000

2. 来自于此博客的一些题目，代码不是抄过来的，是自己实现。

  （1）给定一个含有n个元素的整型数组a，求a中所有元素的和。这道题要求用递归法，只用一行代码。

    解答：

int sum(int*a,int n){   return (n-1==0)?a[n-1]:(a[n-1] + sum(a,n-1)); }

    (2)给定一个含有n个元素的整型数组a，找出其中的最大值和最小值.

     解答：     

void MaxandMin(int *a,int n,int *max,int *min){	int max1,min1;		if(n == 1)	{		*max = *min = a[n-1];		return;	}	else if(n == 2)	{		if(a[n-1] >= a[n-2])		{			*max = a[n-1];			*min = a[n-2];		}		else		{			*max = a[n-1];			*min = a[n-2];		}		return;	}	else	{		MaxandMin(a,n/2,&max1,&min1);		*max = max1;*min = min1;		MaxandMin(a+n/2,n-n/2,&max1,&min1);		*max = (*max > max1)?(*max):max1;		*min = (*min < min1)?(*min):min1;	}	return;}

（3）给定一个含有n个元素的整型数组，求其最大值和次大值。

解答：（该解答在遇到 1 2 2 3 3 3这样的数组时，返回3,3而不是3,2）

#include 
    
     void MaxTwo(int *a, int n, int *max, int *max2){	if(n == 1) 	{		*max = a[n-1];                *max2 = INT_MIN;		return;	}	else if(n == 2)	{		*max = (a[n-1]>a[n-2])?a[n-1]:a[n-2];		*max2 = a[n-1]+a[n-2]-*max;		return;	}	int max1 = 0,max21 = 0;	MaxTwo(a,n/2,&max1,&max21);	*max = max1;*max2 = max21;	MaxTwo(a+n/2,n-n/2,&max1,&max21);	*max = (*max > max1)?(*max):max1;	if(*max != max1)		*max2 = (*max2> max1)?(*max2):max1;	else		*max2 = (*max2> max21)?(*max2):max21;	return;}int main(){	int a[7] = {1,2,3,4,9,6,7};	int max,max2;	MaxTwo(a,7,&max,&max2);		printf("max = %d,max2 = %d\n",max,max2);}
    

(4) 给定一个n个整型元素的数组a，其中有一个元素出现次数超过n / 2，求这个元素。据说是百度的一道题。

  该题目类似于编程之美上寻找发帖水王，最直接的办法是对数组排序，该元素必然会出现在数

组中间位置。

不采用排序的方法，按照编程之美所介绍，可以每次删掉两个不同元素，删到最后剩下的一定

是该出现次数超过一半的元素。（每次删掉两个不同元素，极限情况即使每次都删掉一个该元素，

由于其超过一半，最后也一定会剩下）。代码如下：

#include 
    
     int Find(int *s, int N){	int candidate;	int ntimes,i;	for(i = ntimes = 0 ; i < N; i++)	{		if(ntimes == 0)		{			candidate = s[i];			ntimes = 1;		}		else 		{			if(candidate != s[i])				ntimes--;			else				ntimes++;		}	}	return candidate;}int main(){	int s[7] = {1,1,3,3,3,3,4};	printf("%d \n",Find(s,7));}
    

（5）给定一个含有n个元素的整型数组，找出数组中的两个元素x和y使得abs(x - y)值最小。

先对数组排序，再遍历一遍：

#include 
    
     void QuickSort(int *s,int N){	if(N <= 1) return ;	if(N == 2)	{		if(s[0] > s[1])		{			s[0] = s[0]+s[1];			s[1] = s[0]-s[1];			s[0] = s[0]-s[1];		}		return;	}	int num = 0;	int max,min,m = N/2;		max = (s[m]>=s[N-1]?m:N-1);	min = (s[m]<=s[N-1]?m:N-1);	if(s[num] >= s[max])		num = max;	else if(s[num] < s[min])		num = min;	if(num != N-1)	{		s[num] = s[num] + s[N-1];		s[N-1] = s[num] - s[N-1];		s[num] = s[num] - s[N-1];		num = N-1;	}	int i = 0,j = N-2;	for(; i
     
      = s[num])			j--;		if( (s[i]>=s[num]) && (s[j]
      
       < min)?tmp:min;	}	return min;}int main(){	int a[7] = {9,3,7,8,2,1,4};	printf("%d\n",Find(a,7));}
      
     
    

（6）给定两个含有n个元素的有序（非降序）整型数组a和b，求出其共同元素，比如

a = 0, 1, 2, 3, 4

b = 1, 3, 5, 7, 9

输出 1, 3

#include 
    
     void Find(int *a,int *b,int an, int bn){	int i,j;	for(i = 0,j =0; ((i
     
    

（7）给定三个含有n个元素的整型数组a,b和c，求他们最小的共同元素

解答：采用排序和二分搜索

（8）给定含有1001个元素的数组，其中存放了1-1000之内的整数，只有一个整数是重复的，请找出这个数。

解答：求出这1001个元素的和，然后减去1-1000的整数的和。 

（9）给定一个含有n个元素的整型数组a，其中只有一个元素出现奇数次，找出这个元素。

因为对于任意一个数k，有k ^ k = 0，k ^ 0 = k，所以将a中所有元素进行异或，那么个数为偶数的元素异或后都变成了0，只留下了个数为奇数的那个元素。

#include 
    
     int Find(int *s, int n){	int r=0,i;	for(i = 0; i < n; i++)		r = r^s[i];	return r;}int main(){	int a[15] = {1,2,3,4,5,6,7,9,7,5,6,4,3,1,2};	printf("%d\n",Find(a,15));}
    

（10） 给定两个有序整型数组a和b，各有n个元素，求两个数组中满足给定和的数对，即对a中元素i和b中元素j，满足i + j = d(d已知)

（11）给定一个含有n个元素的整型数组a，从中任取m个元素，求所有组合。比如下面的例子

a = 1, 2, 3, 4, 5

m = 3

输出

1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5

2 3 4, 2 3 5, 2 4 5

3 4 5

解答：

3.这几天总是遇到的一个题目，求数组的子序列的最大和和最大积问题。

（1）求子数组最大和。

解答：对于数组A，其要求子序列为以下三种情况：

<1>A[0]就是最大和子序列；

<2>A[0]是最大和序列的一个元素；

<3>A[0]不是最大和子序列的元素。

设A[i...j]的最大和子序列为ALL[i]，包含A[i]的最大和子序列为S[i]，S[i] = max()则A[0..N]的最大和子序列可以定义为

max(S[i],ALL[i])；

显然我们可以从最后一个元素向前搜索，得出最大和子序列，复杂度为O(N)。

#include 
    
     int max(int a, int b){	return a>b ? a : b;}int Find(int *A, int N){	int i;	int ALL,S;	ALL = A[N-1];	S = A[N-1];	for(i = N-2; i >= 0; i--)	{		S = max(A[i],A[i]+S);		ALL = max(S,ALL);	}	return ALL;}int main(){	int a[6] = {1,-2,3,5,-3,2};	printf("%d\n",Find(a,6));}
    

(2)寻找子序列的最大积。麻烦之处在于有负数的情况。

定义两个值，max和min；max代表当前遍历的子序列的最大值，遇到某个数，这个数使乘积为负数和0时，将max置为1；当遇到负数时，当前乘积若为负数，将这个负数赋值给min，这样再次遇到负数时，min乘以这个负数，若变为正数，就将其赋值给max。

中秋节无聊思及下面代码，突然想到出现0,0,-1,0,0或全0这样的序列，如下代码还是返回1.

#include 
    
     #define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))int Find(int *s,int n){		int max = 1,min = 1;	int i,r=1;	for(i = 0; i < n; i++)	{		if(s[i] > 0)		{			max = max*s[i];			min = Min(min*s[i],1);		}		else if(s[i] == 0)		{			max = 1;			min = 1;		}		else		{			int tmp = max;			max = Max(min*s[i],1);			min = Min(tmp*s[i],1);		}		r = Max(r,max);	}	return r;}int main(){	int a[7] = {1,2,0,-2,12,7,-1};	printf("%d\n",Find(a,7));}
    

修改后的代码如下:

#include 
    
     #define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))int Find(int *s,int n){		int max = 1,min = 1;	int i,r=1;        int zero_num = 0, neg_num = 0;	for(i = 0; i < n; i++)	{		if(s[i] > 0)		{			max = max*s[i];			min = Min(min*s[i],1);		}		else if(s[i] == 0)		{			max = 1;			min = 1;                        zero_num++;		}		else		{			int tmp = max;			max = Max(min*s[i],1);			min = Min(tmp*s[i],1);                        neg_num++;		}		r = Max(r,max);	}        if(neg_num+zero_num == N)        {                for(i = 2; i < N-1; i--)                {                        if((s[i]*s[i-1])||(s[i]*s[i+1]))return r;                }                return 0;        }	return r;}int main(){	int a[7] = {1,2,0,-2,12,7,-1};	printf("%d\n",Find(a,7));}
    

还是求最大积的问题，前天小*科技笔试最后一题，不同的是数组不是整型的而是浮点型的，这样一来，上面代码中，将max，min置为1就不妥了。

4. 将一个含有n个元素的数组向右循环移动k位，要求时间复杂度是O(n)，且只能使用两个额外的变量，这是在微软的编程之美上看到的一道题。

#include 
    
     void Reverse(int *s,int b, int e){	for(; b < e; b++,e--)	{		s[b] = s[e] + s[b];		s[e] = s[b] - s[e];		s[b] = s[b] - s[e];	}}void RightShift(int *s, int n,int k){	Reverse(s,n-k,n-1);	Reverse(s,0,n-k-1);	Reverse(s,0,n-1);}int main(){	int i;	int a[9] = {6,7,8,9,1,2,3,4,5};	RightShift(a,9,5);	for(i = 0 ; i < 9 ; i++)		printf("%d ",a[i]);	printf("\n");	return 0;}