真题集P127---2018年真题

第一题

思路

就是在考学生，如何快速求解最大公约数问题
<1>从mn中选较小的数开始向下枚举，一直到2为止，第一个能同时整除m,n的即为所求(暴力枚举不推荐)
<2>！！！！！！！！！辗转相除法！！！！！！！！！！！
除数和余数反复做除法运算(除数/余数)，当余数为 0 时，取当前算式除数为最大公约数

辗转相除法代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int gcd(int a, int b) {//寻找最大公约数
	return b == 0 ? a : gcd(b, a%b);//b作为每次的余数，a作为每次的除数
}
void getSimplest_two(int m, int n) {
	int d = gcd(m, n);
	m /= d;
	n /= d;
	cout << m << '/' << n;
}
int main()
{
	int m = 0, n = 0;
	cin >> m >> n;
	getSimplest_two(m, n);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第三题

思路

1、快速排序中的分划思路是极其重要的一种想法：
在经历过一次的分划之后，保证base左侧都属于一种属性，Base右侧又都属于另一种属性，所以在处理"把数组两极分化(且各在数组两边分布)"的操作之时，我们就可以使用快排的分划思路，经过一次分划之后，base左右侧就是所求的两极属性。
2、所以本题要求前半部分是偶数，后半部分是奇数，且升序排列。所以先分划一次，base左侧都是偶数，右侧都是奇数(base本身单独加判断)，最后再对两部分快排即可。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int item[10];
int devidePosition(int left, int right) {//分划函数
	int base = item[left];
	while (left < right) {
		while (left < right && (item[right] % 2 != 0)) {
			right--;
		}
		item[left] = item[right];
		while (left < right && (item[left] % 2 == 0)) {
			left++;
		}
		item[right] = item[left];
	}
	item[left] = base;
	return (base % 2 == 0) ? left : left - 1;//对base单独判断，保证返回的数是最后一个偶数的位置
}
void quickSort(int left, int right) {//快速排序
	if (left >= right) {
		return;
	}
	int base = item[left];
	int low = left;
	int high = right;
	while (low < high) {
		while (low < high&&item[high] >= base) {
			high--;
		}
		item[low] = item[high];
		while (low < high&&item[low] <= base) {
			low++;
		}
		item[high] = item[low];
	}
	item[low] = base;
	quickSort(left, low - 1);
	quickSort(low + 1, right);
	return;
}
int main()
{
	//第三题
	//1 4 3 2 5 9 7 8 10 99
	for (int i = 0; i < 10; i++) {
		cin >> item[i];
	}
	int mid = devidePosition(0, 9);
	quickSort(0, mid);
	quickSort(mid + 1, 9);
	for (int i = 0; i < 10; i++) {
		cout << item[i] << ' ';
	}
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

第六题

思路

题目很简单，就是一个回溯法遍历二叉树就行。
1、但是！！！！注意边界值处理，当是叶子节点(左右都是空节点)返回1，但是还会出现空节点情况！！！，所以空节点返回0
2、所以考试时候拿不准，宁可多写一点边界判定，千万别少了。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
int findLeafNode(TreeNode* root) {
	if (root == nullptr) {//边界值弄清楚，写全
		return 0;
	}
	if (root->left == nullptr&&root->right == nullptr) {
		return 1;
	}
	int left = findLeafNode(root->left);
	int right = findLeafNode(root->right);
	return left + right;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29