Java实现洛谷 P1738 洛谷的文件夹

题目描述

kkksc03是个非凡的空想家！在短时间内他设想了大量网页，然后总是交给可怜的lzn去实现。

洛谷的网页端，有很多文件夹，文件夹还套着文件夹。

例如：/luogu/application/controller表示根目录下有一个名称为luogu的文件夹，这个文件夹下有一个名称application的文件夹，其中还有名为controller的文件夹。

每个路径的第1个字符总是’/’，且没有两个连续的’/’，最后的字符不是’/’。所有名称仅包含数字和小写字母。

目前根目录是空的。kkksc03想好了很多应该有的文件夹路径名。问题是，需要是使这些文件夹都存在，需要新建几个文件夹呢？

输入输出格式

输入格式：

输入文件第1行为一个正整数N。

接下来N行，每行为一个描述路径的字符串，长度均不超过100。

输出格式：

输出应包含N行，每行1个正整数，第i行输出若要使第1个路径到第i个路径存在，最少需要新建多少个文件夹。

输入样例#1：

2

/luogu/application/controller

/luogu/application/view

输出样例#1：

3

4

输入样例#2：

3

/chicken

/chicken/egg

/chicken

输出样例#2：

1

2

2

输入样例#3：

4

/a

/a/b

/a/c

/b/b

输出样例#3：

1

2

3

5

import java.util.ArrayList;

import java.util.Collections;

import java.util.Scanner;

public class 洛谷的文件夹 {

	public static void main(String[] args) {

		int count=0;						//计算新建文件夹次数

		Scanner sc =new Scanner(System.in);

		ArrayList<String>  list = new ArrayList<String>();

		ArrayList<String> list1 = new ArrayList<String>();

		int n = sc.nextInt();

		for (int i = 0; i < n; i++) {

			String s = sc.next();

			list.add(s);					//把每一个路径都保存为String放入list里面

		}

		Collections.sort(list);				//把这些路径按照字典序排序

			//排完序就会把相同路径或者相似路径的放在一起  可以比对这一个和下一个的不同来计算

			//不用再去记录以前建过的文件夹

		String sss = list.get(0);

		String [] num3 = sss.substring(1).split("/");

		for (int i = 0; i < num3.length; i++) {

			list1.add(num3[i]);

			count++;

		}				//先把第一个保存下来

		for (int i = 0; i <list.size()-1; i++) {

			System.out.println(count);

			String s = list.get(i);

			String ss = list.get(i+1);

			String  [] num1 = s.substring(1).split("/"); //这里是为了拆分使用，来匹配相对位置的文件夹是不是被建过

			String [] num2 = ss.substring(1).split("/");

			int min = Math.min(num1.length, num2.length);//保存最小长度的

			int temp=-1;								//这里是用第一个当基础来与第二个的比较

			if(num1.length<num2.length){ 				//如果第二个长度大，就先保存一下

				temp=num1.length;

			}

			for (int j = 0; j < min; j++) {

				if (num1[j].equals(num2[j])) {			//第一个相同

					if (!list1.contains(num1[j])) {		//   list1 这里是list1  看看是否有这个文件夹

						count++;						//这里主要是  看看这两个路径里有几个相同的  防止加上相同的文件夹

						list1.add(num1[j]);				//没有就加上这个文件夹   count记录次数

					}

				}

				else {									//如果这两个不相等

					temp=j;								//就保存下标  结束掉

					break;

				}

			}

			if (temp!=-1) {								//如果有不相同的 或者第二个数组长的

				list1 = new ArrayList<String>(); 		//list清空  重新录入

			for (int j = 0; j < num2.length; j++) {  //前面第一个已经录好了  这里录入第二个

				list1.add(num2[j]);

				if(j>=temp){						//当录入到下标的地方，就开始添加次数

					count++;

				}

			}

			}

		}

		System.out.println(count);

	}

}

巴特西

Java实现洛谷 P1738 洛谷的文件夹

最新文章

热门文章

巴特西

Java实现 洛谷 P1738 洛谷的文件夹

最新文章

热门文章

Java实现洛谷 P1738 洛谷的文件夹