阿烫的后花园

烫烫烫烫烫烫

发表于 更新于 分类于

马上就要迎来崭新的2019年了，回想过去的22年，基本都是学生生涯，学习也并没有什么作为，有点苦涩。大学时期，也从未有过什么长期的计划，当一天和尚撞一天钟。但新的一年里，我已经开始工作了，我觉得有必要制定一个比较长远的目标和计划。

主要目标

  • 深入学习java、jvm、多线程、高并发等
  • 三年内存款满意 第一年及格线5w，满意6w，第二年及格线10w，满意13w，第三年及格线13w，满意16w。总计：及格线28w 满意35w
  • 健身，可视化的腹肌、胸肌
  • 摄影，虽然没有女朋友，但我觉得我热****爱它
  • 写字，作为一项兴趣爱好，可能练习行楷
阅读全文 »

发表于 更新于 分类于

原码、补码、反码是计算机中最基础的知识,但一直没熟练掌握，经常忘，这里做个记录。

原码

最高位是符号位，其余位用来表示这个数的绝对值。
例如 在32位数中：

 +1的原码是0000,0001；
 +5的原码是0000,0101;
 -17的原码是1001,0001;

如果这个世界只有正数，那么我们只需要原码就够了，但还有负数…

阅读全文 »

发表于 更新于 分类于

自从租了新房子交了网费之后，却一直没有网线，中介要我自己从路由器那拉…

路由器在隔壁妹子的屋里，拖延了很久之后，中介总算在那户人家的门上打了个小孔，买的网线还不能插进去，只能剪断，拉进去之后再自己压个水晶头。

好就好在这里! 从来没有压过水晶头，百度了下八根网线的排列顺序就自己动手了。根据以往焊电路板的经验，总归要先去电线皮的吧！于是给每根线剥了个皮，但是真的不好剥，线太细了，还容易剥断…剥断了8根线就不一样长了，大家不一起长还不好插进水晶头。

阅读全文 »

发表于 更新于 分类于

Prim算法用来解决在一个无向图中找一棵最小生成树的问题，在这之前需要了解一些概念

  • 连通图：在一个无向图中，任意两个顶点都有一条路径连通，那么称该无向图是连通图
  • 强连通图：在一个有向图中，任意两个顶点都有路径相通，那么该有向图是强连通图
  • 连通网：即带权连通图，图的每条边都对应一个权值，权是连接两个顶点的代价。
  • 生成树：能连接图中所有顶点而又不产生回路的任何子图都是该图的生成树。
  • 连通图：代价最小的生成树，即边上的权值之和最小

如果之前看过求最短路径的Dijkstra算法，那么prim算法是相当容易理解的，两者差距很小。
Prim算法和Dijkstra算法一样，对每个顶点保留一个dv和pv以及一个flag，标识该顶点是已知的还是未知的。dv是连接当前顶点v到已知顶点的最短边的权，pv是导致dv改变的最后的顶点。算法的其余部分一模一样，只有一点不同，因为dv的定义不同，因此它的更新法则也不同，它的法则更简单了。

阅读全文 »

发表于 更新于 分类于

最近在忙于重写自己的博客，springboot+vue，前后端分离，虽然还有完成，但也一定要记下这个坑。

由于文章、标签、分类等业务逻辑并无巨大改动，无非是改改接口名称，规范化url地址。但重写打算增加一些与文件相关的接口，例如修改、删除、重命名等。前台与后台在本地测试都无问题，于是打算将后台打包放在服务器上再进行测试。

问题就发生在了这里，不知什么时候开始，前端查询文件列表的时候，竟然发生了跨域请求错误，但后台拦截器中已经在header中设置好了允许跨域，而且其余的接口都没出现问题，这点让人很困惑，而且后台放在服务器上才会出现这个问题，本地啥事没有。

开始查找是否是后台的问题，虽然可能性不大，但还是仔细看了一遍，实在找不到什么问题。

阅读全文 »

发表于 更新于 分类于

上一篇我们使用了Dijkstra算法来解决最短路径问题，但这个算法有一个局限性，图不能存在负值边，因为Dijkstra算法的策略是贪心算法。

使用Dijkstra算法得到错误的解

贪心算法对于问题只需考虑当前局部信息，然后就要做出决策，也就是说使用贪心算法的前提是“局部最优策略能导致产生全局最优解”。因此该算法具有局限性, 若应用不当, 不能保证求得问题的最佳解（正确解）。例如，下面的图存在负边，那么贪心算法将可能得不到正确的解。

阅读全文 »

发表于 更新于 分类于

Dijkstra算法使用了广度优先搜索解决了赋权有向图或无向图的单源最短路径问题。算法采用了贪心策略，分阶段的求解这个问题，这篇文章，我们进行详细的介绍。

这篇文章中，我们以图1.1中的赋权图作为示例。箭头上的数字为权值，圆圈中的字母为顶点中的数据，这里用一个字母表示。

1534060079132.png

我们依旧使用邻接表来表示图，那么上图中的有向图可以表示为图1.2的样子，如果不理解，可以看上篇拓扑排序中的内容。

1534060198241.png

实现步骤

首先，我们需要对每个顶点进行标记，每个顶点标记为Known（已知）的，或者标记为unKnown（未知的）。同时，每个顶点需要保留一个临时距离 dv 。这个距离实际上是使用已知顶点作为中间顶点从开始顶点 s 到 v 的最短路径的长。最后，我们记录 pv ，它是引起 dv 变化的最后的一个顶点。假如开始顶点 s 是 a ，那么用于Dijkstra算法的表的初始配置应当如图2.1所示。

1534064213351.png

Dijkstra算法按阶段进行，在每个阶段，Dijkstra算法选择一个顶点 v ，它在所有未知顶点中具有最小的dv，同时算法声明从 s 到 v 的最短路径是已知的。阶段的其余部分由dw值的更新工作组成。

图2.1表示我们初始配置，且开始节点为 s 为 a。

第一个选择的顶点是 a ，因为它在所有未知的顶点中具有最小的 dv ，dv 为0。将 a 标记为已知。既然 a 已知，那么某些表项就需要调整。观察图1.1，发现邻接到 a 的顶点有 b 和 d 。那么这两个顶点的项需要调整，调整后如图2.2所示。

1534065162883.png

继续选择一个未知的且具有最小 dv 的顶点，也就是 d ，顶点  c，e，f，g 是邻接的顶点，而且它们实际上都需要调整，如图2.3所示。

1534065701993.png

下一个被选取的顶点是 b ，其值为 2。d 是邻接的点，但已经是已知的，因此不必做对其做工作了。 e 也是邻接的点但不需要调整，因为结果 b 的值为 2+10=12。大于 e 已知的长度为3的路径。图 2.4指出这些顶点被选取以后的表。

1534066134468.png

下一个被选取的点为 c，其值为3 ，a 是邻接的点，但已知，不需要处理了。f 是邻接的点，因为 3+5<9,所以需要进行调整，如图 2.5所示。

1534066489981.png

下一个被选取的点是 e ，g 是唯一的邻接顶点，但不需要调整，因为 3+6>5。结果如图 2.6所示。

1534066684105.png

接着我们选取 g 。邻接的顶点只有 f ，因为 5+1<8，所以对 f 的距离需要下调到 6 。结果如图 2.7所示。

1534066812531.png

最后，我们选择顶点 f ，但其余所有顶点都已知，算法终止。最后的表在图 2.8中表出。

1534066911842.png

图3通过图形演示了在Dijkstra算法期间各边是如何标记为已知的以及顶点是如何更新的。顶点染成黄色说明此顶点标记为已知。

1534077874692.png

在算法结束后，我们最终得到了一张表（图 2.8）。在这张表里面，我们可以得到我们想得到的一切。例如 a 到 f 的最短路径为6。那么如何得到 a 到 f 的实际路径呢？我们可以编写一个递归来跟踪 pv 留下的痕迹。引起 f 的 dv 变化的最后的一个顶点是 g ，那么查询 g ；引起 g 的 dv 变化的最后的一个顶点是 d ，继续查 d ；引起 d 的 dv 变化的最后的一个顶点是 a ，也就是我们的开始节点，不需要继续查了， a 到 f 的最短路径就是 a->d->g->f 。 

代码实现

首先是图的顶点结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef string vertex;
struct Node
{
	vertex data;
	int weight = 0;
	Node *next = NULL;

	Node(vertex data,int weight, Node *next = NULL)
	{
		this-&gt;data = data;
		this-&gt;weight = weight;
		this-&gt;next = next;
	}
};

其次，我们还需要维护一个像上面的表，有known，dv，和pv。
表 不考虑负边

1
2
3
4
5
6
7
const int INFINITE = -1;  //距离 定义无限大
struct Box
{
	bool known = false;
	int dv = INFINITE;
	vertex path;
};

和上一篇拓扑排序中使用的方法一致，还是使用map来存储，比较方便。

直接给出代码，关键地方都已经打好注释

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
map<vertex, Box> Dijkstra(vertex v,map<vertex, Node> graph)
    {
    	map<vertex, Box> boxs = initBox(v, graph);
    	while (1)
    	{
    		map<vertex, Box>::iterator it = boxs.begin();
    		int min = 99999999;
    		//key为当前阶段应当标记为已知的顶点
    		vertex key;
    		int flag = 0;
    		while (it != boxs.end())
    		{
    			if (it->second->known==false&amp;&amp; it-&gt;second-&gt;dv!= INFINITE &amp;&amp;it-&gt;second-&gt;dv &lt; min)
    			{
    				min = it-&gt;second-&gt;dv;	//记录最短路径
    				key = it-&gt;first;		//记录最小路径的key
    				flag = 1;				//将flag置为1，说明，还有known为false的
    			}
    			it++;
    		}
    		//所有known都是true ，算法结束
    		if (flag == 0)
    		{
    			return boxs;
    		}

    		boxs[key]-&gt;known = true;		//将最小的顶点known置为true

    		//将所有与此顶点相邻接的点进行更新
    		Node* n = graph[key];
    		while (n != NULL)
    		{
    			//如果此顶点是已知的，就不虚要再处理了
    			if (boxs[n-&gt;data]-&gt;known == true)
    			{
    				n = n-&gt;next;
    				continue;
    			}
    			//此顶点计算出来到it2的路径
    			int d_new = boxs[key]-&gt;dv + n-&gt;weight;
    			//原本it2的路径长度
    		int d_old = boxs[n-&gt;data]-&gt;dv;

    			//需要更新
    			if (d_old == INFINITE || d_new &lt; d_old)
    			{
    		boxs[n-&gt;data]-&gt;dv = d_new;
    				boxs[n-&gt;data]-&gt;path = key;
    			}
    			n = n-&gt;next;
    		}
    	}
    }`</pre>

    输出算法的结果
    <pre>`string printp(vertex p, map&lt;vertex, Box*&gt; boxs)
    {
    	if (boxs[p]-&gt;dv == 0)
    	{
    		return p+"";
    	}
    	return printp(boxs[p]-&gt;path, boxs) + "-&gt;" + p;
    }
    //输出算法的结果
    map&lt;vertex, string&gt; printfDijkstra(map&lt;vertex, Box*&gt; boxs)
    {
    	//用来存放输出的内容
    	map&lt;vertex, string&gt; outs;
    	vertex aim;
    	//找到起点
    	map&lt;vertex, Box*&gt;::iterator it = boxs.begin();
    	while (it != boxs.end())
    	{
    		if (boxs[it-&gt;first]-&gt;dv == 0) {
    			aim = it-&gt;first;
    			break;
    }
    		it++;
    	}
    	it = boxs.begin();
    	while (it != boxs.end())
    	{
    		if (it-&gt;first != aim)
    		{
    			string path = printp(boxs[it-&gt;first]-&gt;path, boxs) + "-&gt;" + it-&gt;first;
    			outs.insert(pair&lt;vertex, string&gt;(it-&gt;first, path));
    	}

    		it++;
    	}
    	//outs已经存放好所有路径了
    	//打印数据
    	it = boxs.begin();
    	while (it != boxs.end())
    	{
    		if (it-&gt;first != aim)
    		{
    			cout &lt;&lt; it-&gt;first + "\t最短路径：" + to_string(boxs[it-&gt;first]-&gt;dv) + "\t路径：" + outs[it-&gt;first] &lt;&lt; endl;
    		}
    		it++;
    	}
    	return outs;
    }

1534089759880.png

完整测试代码

0%