真题集P123---2011年真题(包括力扣662)

第三题

思路

注意：
1、sqrt得到的是double数据类型，一定切记切记
2、求a^b(a的b次幂)，用函数pow(a,b)
3、动态产生长度，动态维护最大值就行

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int point[10][2];
double getMaxLength(int n) {
	double ans = -1;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			double tmp = sqrt(pow(point[i][0] - point[j][0], 2) + pow(point[i][1] - point[j][1], 2));
			ans = max(ans, tmp);
		}
	}
	return ans;
}
int main()
{
	int three_n = 10;
	for (int i = 0; i < three_n; i++) {
		cin >> point[i][0] >> point[i][1];
	}
	cout << getMaxLength(three_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
27
28

第四题

根据题目要求，只要把二维数组排序即可，就一定满足他的要求。

思路

1、不要被二维数组给骗了，因为其在电脑中的存储地址是连续的：
*(基地址+该元素前面的元素个数)
就可以访问任意一个二维数组的元素，所以就等效于把二维数组降为一维处理
2、共n^2个元素，最后一个元素表示为 *(基地址+n^2-1)，因为要两两交换，所以枚举到 n^2-2

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
//第四题
//如果排序之后满足行列都是递增，则必然满足题意，所以本题就是二维数组排序问题。
//一维数组，直接用下标寻址，二维数组用，(基地址+前方元素数)可以模拟出一维寻址效果，进而使用一维的冒泡排序
int four[5][5];
void bubbleSort(int n) {
	bool flag = true;
	int * base_address = &four[0][0];//基地址
	while (flag) {
		flag = false;
		for (int i = 0; i < n*n - 1; i++) {//枚举间隔数，比如a[0][1]，前面有一个元素，间隔数为1，所以(基地址+1)就是它 
			if (*(base_address + i) > *(base_address + i + 1)) {
				flag = true;
				int tmp = *(base_address + i);
				*(base_address + i) = *(base_address + i + 1);
				*(base_address + i + 1) = tmp;
			}
		}
	}
}
int main()
{
	int four_n = 5;
	for (int i = 0; i < four_n; i++) {
		for (int j = 0; j < four_n; j++) {
			cin >> four[i][j];
		}
	}
	bubbleSort(four_n);

	cout << endl;
	for (int i = 0; i < four_n; i++) {
		for (int j = 0; j < four_n; j++) {
			cout << four[i][j] << ' ';
		}
		cout << endl;
	}
	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

第七题

我们这里写一下更有难度的力扣:662. 二叉树最大宽度
这道题是卷子上的加强版，卷子上的题目未统计空节点。

思路

一、定注意审题：
1、宽度定义为，每层的最左侧的节点，和最右侧节点之间，包括空节点在内，有多少节点，宽度就是多少
2、这棵树可视为满二叉树

二、理解运用满二叉树
一定明白啥叫满二叉树，满二叉树上面节点都是有"编号"的，所以因为层序遍历，每次就是找子节点，所以左子节点2i,右子节点2i+1，所以，只需要知道每层最小的编号，和最大的编号，就可以知道中间有多少个节点了(max-min+1)

三、只给存在的节点分配编号
1、只需要维护每层的存在的节点就行，用这种满二叉树编号算法，只维护存在的节点，虽然没显式维护空节点，但是相当于为之留下位置了，这就是题目中这个条件的关键所在，为我们节省了大量操作。
2、找到该层所有存在的节点之后，找到最小编号和最大编号(动态维护即可)。

四、整体写法
就是二叉树层次遍历–每次处理一层，作为大骨架即可

五、边界

这种情况，就会出现在一次遍历中，最小编号和最大编号的值为变化，说明此次没有任何一个节点加入队列，此次为多余的循环，直接返回答案就行

代码

注意：
1、本题算编号时，数据量极大极大，long long 会越界，所以用unsigned long long
2、用这个数据类型时候，切记<1>初始化最下为0 、<2>0-ULLONG_MAX=1，所以二者的值未变化，一定不要用这俩直接减，会出错

#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) {}
};
class Solution {
public:
	int widthOfBinaryTree(TreeNode* root) {
		if (root->left == nullptr&&root->right == nullptr) {//特殊情况
			return 1;
		}
		unsigned long long ans = 1;

		queue<TreeNode*> help;//非空节点队列
		queue<unsigned long long> number;//与上面一一对应的编号队列
		//初始化
		help.push(root);
		number.push(1);
		int level_num = 1;//每层节点数量

		while (!help.empty()) {
			int tmp_levelNum = 0;//记录下一层节点数量
			unsigned long long min_num = ULLONG_MAX;//动态维护的最小/最大编号
			unsigned long long max_num = 0;

			for (int i = 0; i < level_num; i++) {
				unsigned long long item = number.front();
				TreeNode* tmp = help.front();
				help.pop();
				number.pop();
				
				if (tmp->left != nullptr) {
					help.push(tmp->left);
					number.push((unsigned long long)item * 2);
					tmp_levelNum++;
					min_num = min(min_num, (unsigned long long)item * 2);
					max_num = max(max_num, (unsigned long long)item * 2);
				}
				if (tmp->right != nullptr) {
					help.push(tmp->right);
					number.push((unsigned long long)item * 2 + 1);
					tmp_levelNum++;
					min_num = min(min_num, (unsigned long long)item * 2 + 1);
					max_num = max(max_num, (unsigned long long)item * 2 + 1);
				}
			}
			level_num = tmp_levelNum;
			if (max_num == 0 && min_num == ULLONG_MAX) {//如果二者没变化，不能直接用下面的式子，会出错，切记，二者直接减值为1
				return ans;//此次循环为无用循环，直接返回答案
			}
			else {
				ans = max(ans, (max_num - min_num + 1));
			}
		}
		return ans;
	}
};

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
64
65
66
67
68
69