cpp6.1

题目: 最大子数组和

题目描述
给定一个数组a[0,...,n-1],求其最大子数组(长度>=1)和
输入描述
第一行一个整数n(1<=n<=5000)，然后依次输入n个整数（每个整数范围[-5000, 5000]）
输出描述
输出一个整数表示最大子数组和
样例输入
5 1 -1 1 1 -1
样例输出
2

最大子数组和：
理解一下概念，连续，最大数。

Ans：
1.从第一个正数开始计算；
2.后面还是正数就加到sum里；
3.直到出现负数，记录第一个max1；
4.对之后出现的所有负数求和，如果大于max1，即计算到这里成负的了，那就舍掉这一段，只保留还留下的max1，然后重新进行1；
5.如果还是正的，就继续1步骤；
6.最后比较所有的max。

这算是一个比较线性的思维方式吧；

//cpp6.1

#include <iostream>
#include <iomanip>
#include <string.h>

using namespace std;

int main()
{
	int n;//输入要输入的数组数；
	cin >> n;
	int* num = new int;
	int* max = new int;//会有很多个max
	int sum = 0;//在计算的数据和
	int x = 0;
Again:
	cin >> *num;
	do
	{
		if (*num >= 0)
		{
			sum += *num++;
			n--;
		}
		else 
		{
			*max++ = sum;
			x++;
			sum += *num++;
			n--;
		}
	} while (sum >= 0 && n > 0&&cin >> *num);
	if (sum < 0&&n>0) {
		sum = 0;
		goto Again;
	}
	else {
		max -= x;
		for (int i = 0; i < x; i++)
		{
			int _a = *max;
			int _b = *(max + 1);
			*(max + 1) = _a > _b ? _a : _b;
			max++;
		}
		max--;
		int result = *max > sum ? *max : sum;
		cout << result;
	}
	return 0;
}

cpp6.2

题目: 数组极差

题目描述
给定一个整型数组 a[0, ..., n-1]，求数组元素的极差（即最大值与最小值的差）
输入描述
输入第一行为一个数 n (1 ≤ n ≤ 5000)
第二行为数组元素 ai (-5000 ≤ ai ≤ 5000)
输出描述
输出数组的极差
样例输入
4 1 2 3 4
样例输出
3

这道题倒是没有什么好说的，注意一下runtime error

#Runtime Error

比如说：
①除以零

②数组越界：int a[3]; a[10000000]=10;

③指针越界：int * p; p=(int *)malloc(5 * sizeof(int)); *(p+1000000)=10;

④使用已经释放的空间：int * p; p=(int *)malloc(5 * sizeof(int));free§; *p=10;

⑤数组开得太大，超出了栈的范围，造成栈溢出：int a[100000000];一般来说，在oj上做题都把数组设成全局变量，减少5出现的可能。

有的时候再出现这样的错误还会给提示

Runtime Error(ARRAY_BOUNDS_EXCEEDED) // array bounds exceed     数组越界

Runtime Error(DIVIDE_BY_ZERO) //divisor is nil                 除零

Runtime Error(ACCESS_VIOLATION) //illegal memory access         非法内存读取

Runtime Error(STACK_OVERFLOW) //stack overflow              系统栈过载

————————————————
引用：https://blog.csdn.net/dreambyday/article/details/54880616

//cpp6.2
#include <iostream>
#include <iomanip>
#include <string.h>

using namespace std;

int main()
{
	int max = -5000;
	int min = 5000;
	int num;
	cin >> num;
	int* a = new int[num];
	for (int i = 0; i < num; i++)
	{
		cin >> *a;
		min = min < *a ? min : *a;
		max = max > *a ? max : *a;
		a++;
	}
	cout << max - min << endl;
	return 0;
}

cpp6.3

题目: 数组第k小数

题目描述
给定一个整数数组a[0,...,n-1]，求数组中第k小数（最小数为第1小，次小数为第2小，以此类推。若有并列，比如有两个最小数1，则第1小和第2小数都是1.）
输入描述
首先输入数组长度n和k，其中1<=n<=5000, 1<=k<=n
然后输出n个整形元素，每个数的范围[1, 5000]
输出描述
该数组中第k小数
样例输入
4 2 1 2 3 4
样例输出
2

做题前想法：

大概率这道题是冒泡排序；
但没什么印象，也没学过，凭着记忆来写一个；

以7 9 10 19 1 7 3 5为例；
先是输入所有数组后，把1和2进行比较，如果1 < 2就不变，1 >= 2就交换顺序，再对2进行，依次进行到n - 1个数。
这时候是7 9 10 1 7 3 5 19
第i次进行会把第i大的数准确地放到n - i的位置上；
所以进行n次即可；
时间复杂度：O（n^2）;

//cpp6.3
#include <iostream>
#include <iomanip>
#include <string.h>

using namespace std;

int main()
{
	int n;
	cin >> n;
	int key;
	cin >> key;
	int m = n;
	int* num = new int[n];
	cin >> *(num++);
	int warp;
	while (--m, m > 0 && cin >> *(num++))
	{
		;
	}
	num -= n;
	for (int j = 0; j < n; j++) 
	{
		for (int i = 0; i < n - 1; i++)
		{
			if (*num <= *(num + 1) )
			{
			;}
			else {
				warp = *(num + 1);
				*(num + 1) = *num;
				*num = warp;
			}
			num++;
		}
		num -= n - 1;
	}
	cout << *(num + key-1) << endl;
	return 0;
}

cpp6.4

题目: 查找单独的数

题目描述
有一个由 n 个小于109 无序的正整数构成的数组，其中有且仅有一个数出现了一次，其他的数均出现了两次。请找出这个只出现一次的数。
输入描述
输入第一行为一个正整数 n (1 ≤ n ≤ 100)
下一行中有 n 个正整数 ai (1 ≤ ai≤ 109)
输出描述
输出只出现一次的数
样例输入
5 1 3 4 1 4
样例输出
3

需要注意的是检验时必须全部遍历；

//cpp6.4
#include <iostream>
#include <iomanip>
#include <string.h>

using namespace std;

int main()
{
 int n;
 cin >> n;
 int* num = new int[n];
 int ans = 0;
 int m = 0;
 for (int i = 0; i < n; i++)
 {
  cin >> *(num++);
 }
 num--;
 for (int j =n; j > 0; j--)
 {
  for (int k = 0; k < n; k++)
  {
   if ((k + 1 - j) != 0) {
    if (*num == *(num - j + 1 + k)) {
     m = 1; break;
    }
   }
   else { ; }
  }
  if (m != 1) 
  {
   ans = *num; 
   break;
  }
  else 
  {
   num--;
   m = 0;
  }
 }
 cout << ans << endl;
}

原文链接：https://blog.csdn.net/GHHTheAnswer/article/details/116429571