2020.2.23更新，增加了数组模块

前言

小编由于报名了蓝桥杯Java组，所以日常做题从使用C/C++转变成使用Java。在转变的过程中，肯定会遇到很多大大小小的输入输出问题。小编打算总结下来，当做自己学习的材料，也分享给感兴趣的朋友。

文件名问题

在比赛提交的代码中，主类必须以public class Main来命名，而且不能带package语句否则会报出编译错误。

//去掉public或者不使用Main作为类名都会gg，亲测有效orz

基本的输入和输出

竞赛入门最经典的问题，莫过于A+B Problem，如果连最基本的输入输出都做不到，学了再多的算法也用不出来。

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int a, b;
		while (cin.hasNext()) {
			a = cin.nextInt();
			b = cin.nextInt();
			System.out.println(a + b);
		}
	}
}

上面代码展示了最基本的输入输出框架，输入类Scanner包含在java.util类包中，首先应该把它导入。

import java.util.*;

由于java的输入需要预先创建输入类对象，所以我们一般习惯在main函数的第一句先创建这个Scanner类对象，对象命名为cin算是表达对C/C++的热爱和怀念吧hhh
如果题目数据量比较大的话可以选择第二种初始化方法，运行效率会高上一些。

Scanner cin = new Scanner(System.in);
//or
Scanner cin = new Scanner(new BufferedInputStream(System.in));

由于题目说明“输入包括多组数据，到文件结尾为止”，类比C/C++的格式,我们很容易理解以下的这段java代码

while (cin.hasNext())  //当输入流中还有数据时
{
    a = cin.nextInt();
	b = cin.nextInt();
}

1.基本数据类型

这些类型在C/C++中基本上已经用烂了，一般过目一遍就会了。

int n = cin.nextInt();//读入一个整数
double d = cin.nextDouble();//读入一个双精度浮点数
long l = cin.nextLong();//读入一个长整型数

需要注意一点：由于Java的main方法是static类型，所以定义全局变量或者方法的时候就需要加上static关键字！

2.数组

关于数组的创建，Java和C/C++也有所不同，它在创建时需要使用new关键字来为其分配存储空间，不过也不会非常麻烦。

int arr[] = new int[Size];
//or
int []arr = new int[Size];

对于二维数组的初始化问题，可以看看我写的另一篇文章：Java 二维数组的初始化

3.字符&字符串

Scanner类中并没有提供单个字符char类型的读入方法，但是我们可以先调用next()方法读取只包含一个字符的字符串，然后用charAt(0)返回0号索引处的字符，即可得到读取到单个字符。

char ch = cin.next().charAt(0);

对于字符串，java中已经封装好了字符串String类，我们也可以用char数组在进行字符串存储。

String str1 = next(); //相当于C/C++中的scanf("%s",str);或cin>>str;
String str2 = nextLine();//相当于C/C++中的gets(str2);或者getline(cin,str2);

char s1[] = cin.next().toCharArray();//调用toCharArray()方法将其转化为char类型数组
char s2[] = cin.nextLine().toCharArray();//类比理解

但是要注意的是，我们不能像C++那样直接用数组下标去访问String类对象中的某号字符。 我们通常利用charAt(int index)方法来访问String类对象中的某号字符，或者不需要调用String类的其他方法的情况下，直接采用char类型数组来存储字符串。

4.输出

日常基本的输出：

System.out.println(); //相当于C++中的cout<<endl;
System.out.print();   //相当于C++中的cout<<"";

输出到文件中：
以下情况可能会用到输出到文件中

• 当数据量过于庞大，java的控制台都无法输出，需要输出到文件中。
• 用暴力法打表，需要按格式先输入到文件中。

try {
	BufferedWriter bw = new BufferedWriter(new FileWriter(new File("E://result.txt")));
	bw.write(str);//str表示写入文件的内容
	bw.flush();//立刻将缓存区的数据写入数据流
	bw.close();//将BufferedWriter流关闭
} catch (Exception e) {
	e.printStackTrace();
}

File(string pathname); 用于初始化文件类，pathname表示文件的路径
FileWriter(File file); 用于初始化文件写入类FileWriter，file表示文件类对象

未完待续…

旅行商TSP问题描述

旅行推销员问题（Travelling salesman problem, TSP）是这样一个问题：给定一组城市和每对城市之间的距离，问题是找到最短的可能路线，访问每个城市一次，然后返回起点。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。

注意哈密顿回路和TSP之间的区别。哈密顿回路问题是要找出是否存在一个旅游线路，每个城市访问一次。这里我们知道哈密顿回路存在（因为图是完整的），事实上存在许多这样的回路，问题是找到一个最小权重的哈密顿回路。

例如，考虑上面图中所示的内容。图中的TSP路线为：是-0>1->3->2->0。旅游费用为10+25+30+15，共80元。

哈密顿回路
哈密顿图（哈密尔顿图）（Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）。

算法分析

这里给出一种简单的算法实现。

将城市0（假设为第0个节点）作为起点和终点。由于路线是循环的，所以我们可以把任何一点作为起点。

以DFS方式开始从源到相邻节点的遍历。

计算每次遍历的成本，跟踪最小成本，并不断更新最小成本存储值。

以最低成本返回结果。

算法设计

package com.bean.algorithm.basic;

public class TravellingSalesmanProblem {

	static int tsp(int[][] graph, boolean[] v, int currPos, int n, int count, int cost, int ans) {

		if (count == n && graph[currPos][0] > 0) {
			ans = Math.min(ans, cost + graph[currPos][0]);
			return ans;
		}

		/*
		 * 回溯步骤（BACKTRACKING STEP） 
		 * 循环遍历currPos结点的邻接表，将计数增加1，并按graph[currPos][i]值增加成本
		 * cost + graph[currPos][i]
		 */

		for (int i = 0; i < n; i++) {
			if (v[i] == false && graph[currPos][i] > 0) {

				// 标记结点被访问过
				v[i] = true;
				ans = tsp(graph, v, i, n, count + 1, cost + graph[currPos][i], ans);

				// 标记结点没有被访问过
				v[i] = false;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		// 顶点（结点）的数量
		int n = 4;

		int[][] graph = { 
				{ 0, 10, 15, 20 }, 
				{ 10, 0, 35, 25 }, 
				{ 15, 35, 0, 30 }, 
				{ 20, 25, 30, 0 } 
				};

		// boolean类型的数组 v 用来标记一个城市结点是否被访问过
		boolean[] v = new boolean[n];

		// 标记第 0 个 结点已经被访问过，所以v[0]=true
		v[0] = true;
		int ans = Integer.MAX_VALUE;

		// 查找最小权重的汉密尔顿回路 Hamiltonian Cycle
		ans = tsp(graph, v, 0, n, 1, 0, ans);

		// 输出结果ans就是最小权重的汉密尔顿回路（ Hamiltonian Cycle）
		System.out.println(ans);

	}
}

程序运行结果：

80