1.数组求和
如果只是普通求和会简单，但是只能使用一行代码该怎么办呢？
int sum(int *a,int n)
{
return n ==0 ? 0 : sum(a,n-1) + a[n-1];
}
2.寻找发帖水王
int Find(int *a,int n)
{
int times = 0;
int value;
for (int i = 0;i < n;++i)
{
if (times == 0)
{
value = a[i];
times = 1;
}
else
{
if (a[i] == value)
{
times++;
}
else
times--;
}
}
return value;
}
int main()
{
int a[10] = {1,1,1,7,8,1,1,1,2,4};
cout <<Find(a,10) <<endl;
return 0;
}
3.求最大值和最小值
void arrmax(int *a,int n)
{
max = 0;
min = 0;
for (int i = 0;i < n;++i)
{
if (a[i] >max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
}
4.最大值和次大值
void arrmax(int *a,int n)
{
max = 0;
min = 0;
for (int i = 0;i < n;++i)
{
if (a[i] >max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
}
5.求数组中最短两个元素之间的距离
因为最短距离只可能是相邻元素之间的距离，所以转化为排序问题，时间复杂度O(N*logN);
6.找出两个数组的共同元素
void arrmax(int *a,int *b,int n)
{
int i = 0;
int j = 0;
while(i <n && j <n)
{
if (a[i] < b[j])
{
i++;
}
else if (a[i] == b[j])
{
cout << a[i] <<endl;
i++;
j++;
}
else
{
j++;
}
}
}
int main()
{
int a[5] = {0,1,2,3,4};
int b[5] = {1,3,5,7,9};
arrmax(a,b,5);
return 0;
}
7.找出数组中唯一重复的元素
给定含有1001个元素的数组，其中存放了1-1000之内的整数，只有一个整数是重复的，请找出这个数
先对这个数组进行求和，然后减去1到1000的和。
8.找出出现奇数次的数
给定一个含有n个元素的整型数组a，其中只有一个元素出现奇数次，找出这个元素
因为对于任意一个数k，有k ^ k = 0，k ^ 0 = k，所以将a中所有元素进行异或，那么个数为偶数的元素异或后都变成了0，只留下了个数为奇数的那个元素。
int findOdd(int *a,int n)
{
int r = a[0];
for (int i = 1;i < n;++i)
{
r^= a[i];
}
return r;
}
int main()
{
int a[11] = {1,1,4,3,4,6,8,8,9,3,6};
cout << findOdd(a,11)<<endl;
return 0;
}
9.找出数组中给定值的数对
有两种情况，一种是经过排序的，一种是没有经过排序的
没有经过排序的需要用一个额外的数组做标记。然后对判断下标进行操作。这里的下标就是数组里的数。
void findSum(int *a,int n,int sum)
{
int ahead = n -1;
int behind = 0;
int curSum = 0;
while(behind < ahead)
{
curSum = a[ahead] + a[behind];
if (curSum == sum)
{
cout << a[ahead] << "," <<a[behind] <<endl;
break;
}
else if (curSum > sum)
{
ahead--;
}
else
{
behind++;
}
}
}
int main()
{
int a[10] = {1,2,4,6,8,9,12,13,15,19};
findSum(a,10,18);
return 0;
}
10.找出数组最大字段和
int findSum(int *a,int n)
{
int cur = 0;
int sum = 0;
for (int i = 0;i < n;++i)
{
cur = a[i] +cur;
if (cur < 0)
{
cur = 0;
}
if (cur > sum)
{
sum = cur;
}
}
return sum;
}
int main()
{
int a[8] = {1,-2,3,10,-4,7,2,-5};
cout << findSum(a,8);
return 0;
}
11.数组最大字段乘积
// 子数组的最大乘积
int MaxProduct(int *a, int n)
{
int maxProduct = 1; // max positive product at current position
int minProduct = 1; // min negative product at current position
int r = 1; // result, max multiplication totally
for (int i = 0; i < n; i++)
{
if (a[i] > 0)
{
maxProduct *= a[i];
minProduct = min(minProduct * a[i], 1);
}
else if (a[i] == 0)
{
maxProduct = 1;
minProduct = 1;
}
else // a[i] < 0
{
int temp = maxProduct;
maxProduct = max(minProduct * a[i], 1);
minProduct = temp * a[i];
}
r = max(r, maxProduct);
}
return r;
}