Note_21-30.md

1021

acyclic 无环

对于图，考虑使用邻接矩阵或者邻接表

List<List<Integer>> adjList = new ArrayList<>()

并使用一个boolean[]数组用于存储各个点的访问情况，避免dfs/bfs中的多次回溯

first attempt

通过bfs检查图的连通度，dfs检查图的深度

for(int i: adjList){
    dfs(i,0);
    maxDeep = Math.max(deep,maxDeep);
}
static void dfs(int i,int currentDeep){
    visited[i] = true;
    currentDeep++;
    deep = Math.max(deep,currentDeep);
    for(j:adjList.get(i)){
        if(visited[j]==false){
            dfs(j,currentDeep)
        }
    }
}

但是存在的问题时当图过大时，对每个节点计算一次dfs可能会超时；未通过测试点3

second attempt

解决办法在于用两次bfs代替dfs，第一次bfs用于找到最远节点，第二次用于计算各个节点到该节点的深度。采用类似的想法，用两次dfs实现该功能，通过测试点3，未通过1、4、5，考虑只有一个输入的特殊情况，通过测试点1。因只有图过大时无法通过测试点3...利用if(){}else{}卡bug通过所有测试。考试时遇类似情况可以考虑该方法？利用该方法找到问题出现在输入数字为6、7时。

third attempt

最终发现问题在于，最远节点存在对称性，即若1为最远节点，则必定只少存在另一点亦可被认为是最远节点。故需进行两次计算最远节点到各个节点的距离操作。至此通过所有测试。

1022

对于每种查询类型，定义一个哈希表。注意使用String存储id。

1023

题目无难度，重点在于对于二十位整数的处理：使用BigInteger类，或者自定义大数乘法/使用list.

1024

同1023，测试点未通过的原因在于对于大数整数的处理：使用BigInteger类。

1025

使用自定义Comparator进行比较

注意-1意味着第一个对象在前

Collections.sort(list,new Comparator<Record>() {
			@Override
			public int compare(Record o1, Record o2) {
				if(o1.mark>o2.mark || (o1.mark==o2.mark&&Long.parseLong(o1.id) <Long.parseLong(o2.id))) {
					return -1;
				}else if(o1.mark<o2.mark) {
					return 1;
				}
				return 0;
			}
		
		});

初次尝试未通过测试点1，因题目要求相同分数下按id升序排序

更改此错误后测试点3仍超时，暂时未找到使用Java通过该测试的方法。

1027

无难度。注意0等特殊值。

1028

同1025，Java无法通过测试点6大批量数据的超时问题。

1029

first attempt

整合两个数组后排序，无法通过测试点5 6 7 8

second attempt

使用双指针，并使用StreamTokenizer,仍然未通过67两个测试点