23.11.24

题目：

image

思路：

找到符合要求的，从后往前查询就行了

题解：

均在代码注释中

代码：

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
70
71
72
73
#include <iostream>
#include <map> 
#include <vector>
using namespace std;
//用map构造伪链表 
int main(){
	map <int ,int> p2;
	map <int ,int> p3;
	int n;
	cin>>n;
	vector <int> x;
	int y=0;
	while(n--){
		int a,b,c;
		cin>>a>>b>>c; 
		if(c==-1){
			/*
			由于可能有多个结束地址为-1
			那么将接受到的第一个-1设为-1
			接受到的第二个-1设为-2
			.....依次向下，方便后续操作 
			*/ 
			y=y-1;
			/*
			起到两个作用：
			1.存储结束地址，因为后续要用末尾地址查
			  而末尾地址是-1的才值得去查，所以才有
			  上方操作，将每个结束地址设成唯一
			2.可以得到 x 的长度，也就是 x.size()
			  也就是说，我们可以得到的有效的链表
			  的个数，因为题目中说明只有结束地址为
			  -1的链表才有效 
			*/ 
			x.push_back(y); 
			p2[y]=b;
			p3[y]=a;
		}else{
			p2[c]=b;//p2[结束地址]=值 
			p3[c]=a;//p3[结束地址]=起始地址
		}	
	}
	//用来存放每个有效链表的值总和
	vector <int> sum(x.size()); 
	//用来存放每个有效链表的长度
	vector <int> length(x.size());
	//遍历每个有效链表 
	for(int i =0 ;i<x.size() ;i++){
		//向左找头 （也就是从结束地址找起始地址）
		//判断p3中是否有这一key,有返回1，无返回0 
		while(p3.count(x[i])){
			sum[i] = sum[i] + p2[x[i]];
			length[i] = length[i] + 1;
			//通过p3[结束地址]=起始地址去找到上一地址 
			x[i] = p3[x[i]];
		}
	}
	int M = -1;//最大长度
	int J;//下标 
	//因为题中定义要找出最大长度 
	for(int i = 0 ;i<length.size();i++){
		if(length[i]>M){
			M = length[i];
			J = i;
		}else if(length[i]==M){//在长度一样时才比较和的大小 
			if(sum[J]<sum[i]){
				M = length[i];
				J = i;
			}
		} 
	}
	cout<<length[J]<<" "<<sum[J]<<endl;	
	return 0;
}

运行结果：

image

image

image

优化：

其实还有十分多的地方值得优化。

比如里面的 x 完全没有必要设置，可以通过y来得出其下标（如果y是-1，那么x.size()==1,如果y是-2，那么x.size()==2）且 x 里面存的也是y。

再比如，完全可以把最后的判断长度与和的大小放入计算完长度与和的while循环后

等等……

心得：

这个代码第一版写出的时候十分粗糙，可以说能跑出某些数据就是机缘巧合。当然值得吹嘘的是第一版的思路与现思路一模一样。但却忽视了很多细节上的问题。比如没有做当长度一样时判断和的大小。等等……

同时我也十分庆幸，我找出了这些BUG。也更加鉴定了我继续写Blog的决心，因为我并不单纯的将这些Blog当作某些笔记。而是将其当作一种复盘的思路，我会将我所有写的，我做的再去思考一遍，做到一个查漏补缺。

感想：

最近再学Spring boot 和Vue。同时的，当学的东西越多好像感觉自己学的又很少，总感觉自己还有很多不会，而时间却是实打实的减少。有时候很纠结究竟要去学什么，似乎什某个技术都还没有学明白，就已经要被更好的技术给取代了。很无奈捏，视乎科班的教学根本无法与外界的相匹配。可能这也是为什么对于程序猿这一职业会有大量的培训班的原因吧。

杂谈：

大环境不好啊！虽然这行不是什么夕阳行业，但也确是不容乐观。但我也相信，在没有好的技术的前提下一切都是在扯淡。目前的我就只有一个想法，通过不断地学习技术来应对这种改变，可能若干年后也还是个loser。md太nm焦虑了。

明天最高温度15度，半个月后还有考试与课程设计。阳光啤酒什么的是没有了，女孩更不可能了，真是操蛋的人生！！！