根据哈工大战德臣老师的计算机专业导论，用Python和贪心算法，解TSP问题，并且分析。

概念

TSP 问题

摘自维基百科：

• 行商问题（最短路径问题）（英語：travelling salesman problem, TSP）
• 给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。
• 它是组合优化中的一个NP困难问题

贪心算法

今朝有救今朝醉 - 每次面临选择的时候，选择眼前最优，而不考虑整体是否最优。
使用贪心算法，使其转化为P问题。

最近看的一个教程里，提到了汉诺塔的问题，参考别人的代码自己用python实现了一番。

4层的效果是这样：

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

A:[4, 3, 2, 1]
B:[]
C:[]
start moving:
move 1 from A to B.
move 2 from A to C.
move 1 from B to C.
move 3 from A to B.
move 1 from C to A.
move 2 from C to B.
move 1 from A to B.
move 4 from A to C.
move 1 from B to C.
move 2 from B to A.
move 1 from C to A.
move 3 from B to C.
move 1 from A to B.
move 2 from A to C.
move 1 from B to C.
A:[]
B:[]
C:[4, 3, 2, 1]

This post includes:

• use python to get labels from GMail API
• deploy python package to AWS Lambda
• setup a AWS gateway API to get labels

基本概念

什么是数据结构？

以某种特定的布局存储数据，以便高效操作。

时间复杂度：

对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

空间复杂度：

是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

Bsic

Summary

DateFormat

get date string in specific format

1
2
3
4

Date date = new Date();
DateFormat dateFormat = new SimpleDateFormat("dd-MMM-yyyy");
String dateString = dateFormat.format(date);
System.out.println(dateString); // 05-Mar-2019

get date from date string

1
2
3
4
5
6
7
8
9

String dateString2 = "2019-03-05";
DateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd");
Date date2 = null;
try {
	date2 = dateFormat2.parse(dateString2);
} catch (ParseException e) {
	e.printStackTrace();
}
System.out.println(date2); // Tue Mar 05 00:00:00 SGT 2019

两件事情：

• 发现无用的对象
• 回收占用的空间

JVM的内存分为三个区域：

• 栈 stack
• 堆 heap
• 方法区 method area

Java集合的一些基础知识。

Array

An array stores a sequence of values

• same type
• primary type and String
• fixed size

用 Servlet 生成随机的验证码图片。

1. 创建 image对象和 graphic对象
2. 设置背景颜色
3. 设置边框
4. 画随机干扰线
5. 写入随机颠倒数字

代码如下：