当前位置: 首页 > news >正文

利用前缀树获取最小目录

一、任务名:

开发最小目录工具

二、任务描述

开发工具,从桶清单文件中列举出所有最小目录,并列举出每一个最小目录中包含的文件总数与文件总量。
最小目录的解释:

有以下几个目录
a/b/1.txt
a/b/2/txt
a/3.txt
a/b/c/
则,最小目录有:
a/b
a/
最小目录包含的对象数为:
a/b:2
a/:1

三、开发思路

这个工作实际上属于目录解析的范畴,与目录解析相关的问题可以通过前缀树来解决

1)前缀树节点开发

有树要先有节点,每一级目录可以视为一个节点。
这个节点包含接下来要去往的目录节点,而这种目录节点可能有很多个,我们必须能快速通过目录名来查找节点,因此选则HashMap,将目录名作为Key,目录节点作为value,nexts=HashMap<Key,Node>。
又因为,每一个目录节点均有可能称为最小目录,那么我们遍历节点的时候应该能够拿出节点中的文件数和文件总大小,故这两个属性也要设置
最后,你不能只知道下面的名字,而不知道自己的名字,所以每个节点也应该有自己的Name
因此Node的构建为PrefixTreeNode:

import java.util.HashMap;/*** @author sq* @date 2023/8/28* @Description ${}*/
public class PrefixTreeNode {String Name;//该节点名称long file_num = 0l;//该节点叶子结点个数long file_size = 0l;//该节点叶子接地点总大小HashMap<String, PrefixTreeNode> nexts = null; //该节点的子节点列表public PrefixTreeNode() {}public String getName() {return Name;}public void setName(String name) {Name = name;}public long getFile_num() {return file_num;}public void setFile_num(long file_num) {this.file_num = file_num;}public long getFile_size() {return file_size;}public void setFile_size(long file_size) {this.file_size = file_size;}public HashMap<String, PrefixTreeNode> getNexts() {return nexts;}public void setNexts(HashMap<String, PrefixTreeNode> nexts) {this.nexts = nexts;}public PrefixTreeNode(String name, HashMap<String, PrefixTreeNode> nexts) {Name = name;this.nexts = nexts;}
}

2)前缀树开发

前缀树其实只需要有一个节点,然后写出构建函数和遍历函数,基本上就可以使用了
①前缀树的构建是将输入的目录字符串通过"/"进行分解,得到字符串数组。
在分解之前就可以判断一下是不是最小目录,如果最后不是以/结尾,那么到文件所在的目录就是最小目录。文件不用加入前缀树。

②前缀树的遍历就是树的正常遍历,用DFS(Depth First Search)比较容易做,遍历每一个节点,如果有文件数和文件大小就输出,没有就去下一层,直到没有下一层

前缀树的代码如下所示:

/*** @author sq* @date 2023/8/28* @Description ${}*/import java.io.FileWriter;
import java.io.IOException;
import java.io.UnsupportedEncodingException;
import java.net.URLDecoder;
import java.util.HashMap;
import java.util.List;public class PrefixTree {PrefixTreeNode root = null;long sum_num = 0l;long sum_size = 0l;//构建前缀树public PrefixTree() {}public PrefixTree(PrefixTreeNode root) {this.root = root;}public PrefixTreeNode getRoot() {return root;}public void setRoot(PrefixTreeNode root) {this.root = root;}public long getSum_num() {return sum_num;}public void setSum_num(long sum_num) {this.sum_num = sum_num;}public long getSum_size() {return sum_size;}public void setSum_size(long sum_size) {this.sum_size = sum_size;}//构建前缀树函数public void InsertToPrefixTree(String filePath, long fileSize, PrefixTreeNode root) throws UnsupportedEncodingException {//0. size如果为0 则为目录(可优化的点)//1.对filePath进行URL解码String decodedFilePath = URLDecoder.decode(filePath, "UTF-8");//2.识别filePath是否以“/”结尾,如果是说明该路径仅为目录,没有文件对象。boolean contains_file_flag = false;if (!decodedFilePath.endsWith("/")) {contains_file_flag = true;}//3.将目录进行拆分String[] split = decodedFilePath.split("/");//“/”//4.对split数组进行遍历,构建前缀树PrefixTreeNode head = root;if (split.length == 1 && contains_file_flag == true) {//当该函数为文件节点时,不加入目录的前缀树,但对当前节点的file_num与file_size进行修改head.file_num++;head.file_size += fileSize;return;}//5.如果是目录则安好一般情况处理for (int i = 0; i < split.length; i++) {if (head.nexts == null) {//初始化一个hashmaphead.nexts = new HashMap<>();}if (!head.nexts.containsKey(split[i])) {//若前缀树中不存在该节点,加入该节点PrefixTreeNode newNode = new PrefixTreeNode();head.nexts.put(split[i], newNode);}//获取下一个节点对该节点进行一些操作//将该节点名称进行设置head.nexts.get(split[i]).Name = split[i];//判断该目录的下一个节点是不是文件对象,如果是,则该节点为一个最小目录if (i + 1 == split.length - 1 && contains_file_flag == true) {head.nexts.get(split[i]).file_num++;head.nexts.get(split[i]).file_size += fileSize;break;//不需要加入叶子节点}//去遍历下一个节点head = head.nexts.get(split[i]);}}//遍历前缀树函数public void TraversePrefixTreeWriteToFile(PrefixTreeNode root, StringBuffer Name, FileWriter writer) throws IOException {//遍历节点的nextsif (root.nexts == null) {//如果该目录下没有nexts,则直接返回return;}HashMap<String, PrefixTreeNode> nexts = root.nexts;for (String s : nexts.keySet()) {StringBuffer directoryName = new StringBuffer(Name);if (!String.valueOf(directoryName).equals("")) {directoryName.append("/");}directoryName.append(s);//1.如果该目录下包含文件,则输出该目录上级所有目录,并输出该目录下filenum: file_sizeif (nexts.get(s).file_num != 0) {//2.将结果写入文件,去掉最开头的/writer.write(directoryName + "," + nexts.get(s).file_num + "," + String.valueOf(nexts.get(s).file_size));writer.write("\n");System.out.println(directoryName + "," + nexts.get(s).file_num + "," + String.valueOf(nexts.get(s).file_size));}//3.以该节点为根节点进行遍历TraversePrefixTreeWriteToFile(nexts.get(s), directoryName, writer);}}public void TraversePrefixTree(PrefixTreeNode root, StringBuffer Name) {//遍历节点的nextsif (root.nexts == null) {//如果该目录下没有nexts,则直接返回return;}HashMap<String, PrefixTreeNode> nexts = root.nexts;for (String s : nexts.keySet()) {StringBuffer directoryName = new StringBuffer(Name);if (!String.valueOf(directoryName).equals("")) {directoryName.append("/");}directoryName.append(s);//1.如果该目录下包含文件,则输出该目录上级所有目录,并输出该目录下filenum: file_sizeif (nexts.get(s).file_num != 0) {//2.将结果写入文件,去掉最开头的/System.out.println(directoryName + "/ 目录包含" + String.valueOf(nexts.get(s).file_num) + "个文件,总大小:" + String.valueOf((double) nexts.get(s).file_size / 1024) + " MB");}//3.以该节点为根节点进行遍历TraversePrefixTree(nexts.get(s), directoryName);}}public void TraversePrefixTreeValid(PrefixTreeNode root, StringBuffer Name) throws IOException {//遍历节点的nextsif (root.nexts == null) {//如果该目录下没有nexts,则直接返回return;}HashMap<String, PrefixTreeNode> nexts = root.nexts;for (String s : nexts.keySet()) {StringBuffer directoryName = new StringBuffer(Name);if (!String.valueOf(directoryName).equals("")) {directoryName.append("/");}directoryName.append(s);//1.如果该目录下包含文件,则输出该目录上级所有目录,并输出该目录下filenum: file_sizeif (nexts.get(s).file_num != 0) {//2.将结果写入文件,去掉最开头的/sum_num += nexts.get(s).file_num;sum_size += nexts.get(s).file_size;System.out.println(directoryName + "/ 目录包含" + String.valueOf(nexts.get(s).file_num) + "个文件,总大小:" + String.valueOf((double) nexts.get(s).file_size / 1024) + " MB");}//3.以该节点为根节点进行遍历TraversePrefixTreeValid(nexts.get(s), directoryName);}}}

3)对所构建的前缀树进行测试

从csv文件中读取每一行的目录名,和文件大小,按行调用前缀树的构建。总体代码如下:

import com.obs.prefixTree.PrefixTree;
import com.obs.prefixTree.PrefixTreeNode;import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;/*** @author sq* @date 2023/8/28* @Description ${}*/
public class PrefixTreeBuilderfromCsvTest {public static void main(String[] args) throws IOException {//获取要处理的桶清单文件以及要写入的文件String csvFile = "0000018A3A73BC14454759A9F377424D_1.csv";String fileName = "result.csv";//1.初始化前缀树//1.1创建一颗只有根节点的树PrefixTree tree=new PrefixTree(new PrefixTreeNode("",null));//2.按行遍历csv文件String line = "";String csvSplitBy = ",";boolean header_flag = true;int key_index = -1;int size_index = -1;int bucket_index=-1;try (BufferedReader br = new BufferedReader(new FileReader(csvFile))) {while ((line = br.readLine()) != null) {String[] data = line.split(csvSplitBy);if (header_flag) {for (int i=0;i<data.length;i++) {if(data[i].equals("Bucket")){bucket_index=i;}if(data[i].equals("Key")){key_index=i;}if(data[i].equals("Size")){size_index=i;}}header_flag = false;continue;}tree.getRoot().setName(data[bucket_index]);//如果不是第一行,则按照正常数据处理构造前缀树tree.InsertToPrefixTree(data[key_index],Long.parseLong(data[size_index]),tree.getRoot());}} catch (IOException e) {e.printStackTrace();}//3.遍历前缀树FileWriter writer = new FileWriter(fileName);//3.1加入表头writer.write("Directory" +","+ "FileNumber"+","+"FileSize"); // 写入内容writer.write("\n"); // 换行//3.2记录根节点对象数,对象大小//3.2.1写入到文件writer.write(tree.getRoot().getName() +","+ tree.getRoot().getFile_num()+","+tree.getRoot().getFile_size()); // 写入内容writer.write("\n"); // 换行//3.2.2输出到控制台System.out.println(tree.getRoot().getName() +","+ tree.getRoot().getFile_num()+","+tree.getRoot().getFile_size());//3.3 遍历前缀树写入文件tree.TraversePrefixTreeWriteToFile(tree.getRoot(), new StringBuffer(tree.getRoot().getName()), writer);//4.关闭写入流writer.close();}}

最后想说一下,树的构建和遍历都不要死记硬背,隶属与递归的问题,都可以使用自然智慧,在尝试中得到普遍逻辑。

相关文章:

利用前缀树获取最小目录

一、任务名&#xff1a; 开发最小目录工具 二、任务描述 开发工具&#xff0c;从桶清单文件中列举出所有最小目录&#xff0c;并列举出每一个最小目录中包含的文件总数与文件总量。 最小目录的解释&#xff1a; 有以下几个目录 a/b/1.txt a/b/2/txt a/3.txt a/b/c/ 则&…...

Java【手撕双指针】LeetCode 18. “四数之和“, 图文详解思路分析 + 代码

文章目录 前言一、四数之和1, 题目2, 思路分析3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: &#x1f4d5; JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 &#x1f4d7; Java数据结构: 顺序表, 链表, 堆…...

OpenCV处理图像和计算机视觉任务时常见的算法和功能

当涉及到OpenCV处理图像和计算机视觉任务时&#xff0c;有许多常见的具体算法和功能。以下是一些更具体的细分&#xff1a; 图像处理算法&#xff1a; 图像去噪&#xff1a;包括均值去噪、高斯去噪、中值滤波等&#xff0c;用于减少图像中的噪声。 直方图均衡化&#xff1a;用…...

Flutter实现StackView

1.让界面之间可以嵌套且执行动画。 2.界面的添加遵循先进后出原则。 3.需要使用AnimateView&#xff0c;请看我上一篇博客。 演示&#xff1a; 代码&#xff1a; Stack: import package:flutter/cupertino.dart;///栈&#xff0c;先进后出 class KqWidgetStack {final Lis…...

c++ future与promise

C11 标准中 头文件中包含了以下几个类和函数&#xff1a; Providers 类&#xff1a;std::promise, std::package_taskFutures 类&#xff1a;std::future, shared_future.Providers 函数&#xff1a;std::async()其他类型&#xff1a;std::future_error, std::future_errc, st…...

在x86机器上的Docker运行arm64容器

1. 引言 工作中常用电脑主机CPU为x86架构&#xff0c;有时由于产品需要&#xff0c;我们需要编译aarch64架构的SDK或者应用程序供使用或者测试。 一种比较快捷的方式是使用aarch64的CPU构建相应操作系统&#xff0c;实现真机运行。但在无arm架构CPU环境下&#xff0c;我们可否…...

centos7删除乱码文件

centos7删除乱码文件1. 小白教程&#xff0c;一看就会&#xff0c;一做就成。 1.解释 当文件名为乱码的时候&#xff0c;无法通过键盘输入文件名&#xff0c;所以在终端下就不能直接利用rm&#xff0c;mv等命令管理文件了。 但是每个文件都有一个i节点号&#xff0c;可以通过…...

uni-app里使用webscoket

实现思路和vue中是一样的。如果想看思路可以看这篇文章&#xff1a;websocket 直接上可以运行的代码&#xff1a; 一、后端nodeJS代码&#xff1a; 1、新建项目文件夹 2、初始化项目&#xff1a; npm init -y 3、项目里安装ws npm i ws --save 4、nodeJS代码&#xff1…...

jdk17+springboot使用webservice,踩坑记录

这几天wms对接lbpm系统&#xff0c;给我的接口是webservice的&#xff0c;老实说&#xff0c;这个技术很早&#xff0c;奈何人家只支持这个。 环境说明&#xff1a;JDK17 springboot2.6.6。网上很多教程是基于jdk8的&#xff0c;所以很多在17上面跑不起来。折腾两天&#xff0c…...

计算机网络文件拆分—视频流加载、断点续传

视频流加载 视频流加载的原理是通过网络传输和播放器解码来实现的。 首先&#xff0c;视频文件会被分成一系列小的数据包&#xff0c;通常是以流的形式传输&#xff0c;这些数据包通过网络传输到用户设备。在传输过程中&#xff0c;可以采用各种协议&#xff0c;如HTTP、RTSP…...

JVM 给对象分配内存空间

指针碰撞空闲列表TLAB 为对象分配空间的任务实际上便等同于把一块确定大小的内存块从Java堆中划分出来。 指针碰撞&#xff1a;&#xff08;Bump The Pointer&#xff09; 堆的内存是绝对规整的&#xff0c;内存主要分为两部分&#xff0c;所有使用过的内存被放在一边&#x…...

Excel·VBA二维数组组合函数、组合求和

目录 1&#xff0c;二维数组组合函数举例 2&#xff0c;组合求和 之前的文章《ExcelVBA数组组合函数、组合求和》和《ExcelVBA数组排列函数》&#xff0c;都是针对一维数组的组合和排列 二维数组组合&#xff1a;对一个m行*n列的二维数组&#xff0c;每行抽取1个元素进行组合&a…...

调用自实现MyGetProcAddress获得CreateFileA函数并调用创建写入文件

写文件如下 #include <iostream> #include <Windows.h>typedef HANDLE(WINAPI* CreateFileAFunc)(LPCSTR, DWORD, DWORD, LPSECURITY_ATTRIBUTES, DWORD, DWORD, HANDLE);DWORD MyGetProcAddress(_In_ HMODULE hModule,_In_ LPCSTR lpProcName ){PIMAGE_DOS_HEADE…...

Leetcode 191.位1的个数

编写一个函数&#xff0c;输入是一个无符号整数&#xff08;以二进制串的形式&#xff09;&#xff0c;返回其二进制表达式中数字位数为 1 的个数&#xff08;也被称为汉明重量&#xff09;。 提示&#xff1a; 请注意&#xff0c;在某些语言&#xff08;如 Java&#xff09;中…...

安防监控视频平台EasyCVR视频汇聚平台调用接口出现跨域现象的问题解决方案

视频监控汇聚EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等&#xff0c;以及厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等&#xff0c;能对外分发RTSP、RTMP、FLV、HLS、WebRTC等格式的视…...

Python中的一些常用操作

文章目录 一. Python操作之-- 使用Python 提取PDF文件中的表格数据&#xff01;二&#xff1a;三&#xff1a; Python中的 staticmethodclassmethod方法四&#xff1a; 反斜杠 \五&#xff1a; 终端的解释器提示符号修改六&#xff1a; python使用json.dumps输出中文七&#xf…...

go语言调用python脚本

文章目录 代码gopython 在 go语言中调用 python 程序&#xff0c;你可能会用到 代码 亲测 go 测试 go 文件 func TestR(t *testing.T) {// 设置要执行的Python脚本和参数scriptPath : "../nansen.py"arg1 : "nansen"// 执行Python脚本cmd : exec.Comm…...

2.3 【MySQL】命令行和配置文件中启动选项的区别

在命令行上指定的绝大部分启动选项都可以放到配置文件中&#xff0c;但是有一些选项是专门为命令行设计的&#xff0c;比方说defaults-extra-file 、 defaults-file 这样的选项本身就是为了指定配置文件路径的&#xff0c;再放在配置文件中使用就没啥意义了。 如果同一个启动选…...

外部库/lib/maven依赖项 三者关系

外部库(存放项目初始配置的jar包)(它的文件夹里并没有包含lib文件夹的引的外部的依赖的jar包) lib(存放外部导入到项目的依赖的jar包) maven依赖项(管理项目所有的jar包依赖) 三者存放jar包的关系 项目所依赖的全部的jar包 maven依赖项的jar包 外部库中的jar包 lib中的…...

在线制作作息时间表

时光荏苒&#xff0c;岁月如梭&#xff0c;人们描述时光易逝的句子&#xff0c;多如星河。 一寸光阴一寸金&#xff0c;寸金难买寸光阴。 人生就是一段时间而已&#xff0c;所以我明白了一个道理 人生之中最大的浪费就是时间的浪费 因此我想我们教给我们孩子重要的一课应该也是…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...