数据结构—排序、查找、图论和字符串算法之Java实例

一:引言

在编程的海洋中,算法是程序员的灵魂之光。它们不仅指引着代码的前进方向,更能解决难题,提升效率。虽然各式各样的算法琳琅满目,但其中有一些却是每位程序员必定会遇到且应当深刻掌握的。本文将带您走进这些至关重要的算法世界,一探究竟!

二:常见算法介绍

1. 排序算法

排序算法是数据整理的利器,它们能将混乱的数据有序化。快速排序、归并排序、插入排序和选择排序等是常见的排序算法。以下是各排序的Java示例代码:

// 快速排序
public void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high); // 分区操作,找到基准元素的正确位置quickSort(arr, low, pivotIndex - 1); // 对基准元素左边的子数组进行递归排序quickSort(arr, pivotIndex + 1, high); // 对基准元素右边的子数组进行递归排序}
}private int partition(int[] arr, int low, int high) {int pivot = arr[high]; // 选择数组的最后一个元素作为基准元素int i = low - 1; // i 指向比基准元素小的元素的最后位置for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j); // 交换元素,将比基准元素小的元素放在左侧}}swap(arr, i + 1, high); // 将基准元素放到正确的位置上return i + 1; // 返回基准元素的索引
}// 归并排序
public void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid); // 递归排序左半部分mergeSort(arr, mid + 1, right); // 递归排序右半部分merge(arr, left, mid, right); // 合并两个有序子数组}
}// 合并两个有序子数组的操作
private void merge(int[] arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int[] leftArr = new int[n1];int[] rightArr = new int[n2];for (int i = 0; i < n1; i++) {leftArr[i] = arr[left + i];}for (int j = 0; j < n2; j++) {rightArr[j] = arr[mid + 1 + j];}int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k++] = leftArr[i++];} else {arr[k++] = rightArr[j++];}}while (i < n1) {arr[k++] = leftArr[i++];}while (j < n2) {arr[k++] = rightArr[j++];}
}// 插入排序
public void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j]; // 移动大于当前元素的元素j--;}arr[j + 1] = key; // 插入当前元素到正确位置}
}// 选择排序
public void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j; // 找到最小元素的索引}}swap(arr, i, minIndex); // 将最小元素放到当前位置}
}// 交换数组中两个元素的位置
private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

2. 查找算法

查找算法用于在数据集中寻找特定元素。二分查找是常见的高效算法,以下是其Java示例代码:

// 二分查找算法
public int binarySearch(int[] arr, int target) {int low = 0; // 左边界int high = arr.length - 1; // 右边界while (low <= high) {int mid = low + (high - low) / 2; // 计算中间元素的索引if (arr[mid] == target) {return mid; // 找到目标元素,返回索引} else if (arr[mid] < target) {low = mid + 1; // 目标在右侧,调整左边界} else {high = mid - 1; // 目标在左侧,调整右边界}}return -1; // 目标元素未找到
}

3. 图论算法

图论算法处理图结构,如社交网络和地图。广度优先搜索(BFS)和深度优先搜索(DFS)是基础算法,以下是DFS的Java示例代码:

import java.util.*;public class Graph {private Map<Integer, List<Integer>> graph = new HashMap<>();public void addEdge(int vertex, int neighbor) {graph.putIfAbsent(vertex, new ArrayList<>());graph.get(vertex).add(neighbor);}// 深度优先搜索算法public void dfs(int start) {boolean[] visited = new boolean[graph.size()];dfsUtil(start, visited);}private void dfsUtil(int vertex, boolean[] visited) {visited[vertex] = true; // 标记当前顶点为已访问System.out.print(vertex + " ");for (int neighbor : graph.getOrDefault(vertex, Collections.emptyList())) {if (!visited[neighbor]) {dfsUtil(neighbor, visited); // 递归访问未访问的邻居顶点}}}public static void main(String[] args) {Graph graph = new Graph();graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(2, 0);graph.addEdge(2, 3);graph.addEdge(3, 3);System.out.println("深度优先遍历结果:");graph.dfs(2); // 从顶点2开始深度优先遍历}
}

在这里插入图片描述

4. 字符串算法

字符串算法处理文本数据,如搜索、匹配和替换。KMP算法是高效的字符串匹配算法,以下是其Java示例代码:

public class KMPAlgorithm {// KMP算法public void kmpSearch(String text, String pattern) {int m = text.length();int n = pattern.length();int[] lps = new int[n]; // 长度为n的部分匹配表computeLPSArray(pattern, lps); // 构建部分匹配表int i = 0, j = 0;while (i < m) {if (pattern.charAt(j) == text.charAt(i)) {i++;j++;}if (j == n) {System.out.println("Pattern found at index " + (i - j));j = lps[j - 1];} else if (i < m && pattern.charAt(j) != text.charAt(i)) {if (j != 0) {j = lps[j - 1];} else {i++;}}}}private void computeLPSArray(String pattern, int[] lps) {int length = 0; // 用于记录最长公共前后缀的长度int i = 1;lps[0] = 0; // 首位不可能存在公共前后缀while (i < pattern.length()) {if (pattern.charAt(i) == pattern.charAt(length)) {length++;lps[i] = length;i++;} else {if (length != 0) {length = lps[length - 1]; // 回退到前一个公共前后缀的长度} else {lps[i] = 0;i++;}}}}public static void main(String[] args) {KMPAlgorithm kmp = new KMPAlgorithm();String text = "ABABDABACDABABCABAB";String pattern = "ABABCABAB";System.out.println("KMP 算法结果:");kmp.kmpSearch(text, pattern);}
}

在这里插入图片描述

三:重点算法总结

掌握这些核心算法是每个程序员的必然选择。它们不仅在计算机领域有广泛应用,还培养了抽象思维和问题解决能力。通过学习和实践,你可以在编程领域中展现出色的技能。

无论是排序、查找、图论还是字符串算法,它们都是你在编程之旅中的得力助手。勇敢地面对挑战,将这些算法娴熟地融入你的工具箱,成为编程世界的探险家和创造者!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/355290.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

信息打点-协议应用_内网资产_CDN_WAF_负载均衡_防火墙

服务信息获取-协议应用&内网资产 常见端口默认对应的服务&#xff1a; 特殊服务端口&#xff1a; 端口扫描工具&#xff1a; 旁注查询 旁注查询&#xff0c;又称为旁站查询或同服务器网站查询&#xff0c;是一种信息安全和网络侦查技术&#xff0c;主要用于发现与目标网站…

java实现一个LRU缓存算法。

//LRU&#xff08;Least Recently Used&#xff09;缓存算法是一种常见的缓存淘汰策略&#xff0c; // 它的基本思想是保留最近被访问过的数据&#xff0c;淘汰最久未被访问的数据。下面是一个使用Java实现的简单LRU缓存算法&#xff1a; import java.util.LinkedHashMap; impo…

电脑上使用备忘录怎么查看编辑时间?能显示时间的备忘录

在快节奏的生活中&#xff0c;很多人喜欢使用备忘录来记录日常事项和重要信息。备忘录不仅能帮助我们捕捉灵感&#xff0c;还能确保重要任务不被遗漏。然而&#xff0c;有时候我们需要知道某条记录的编辑时间&#xff0c;以便于回溯和整理信息。如果备忘录不能显示编辑时间&…

SpringBoot复习

第一章 SpringBoot开发入门 1.Springboot的优点。 ① 可快速构建独立的Spring应用。 ② 直接嵌入Tomcat、Jetty和Undertow服务器&#xff08;无须部署WAR文件&#xff09; ③ 通过依赖启动器简化构建配置 ④ 自动化配置Spring和第三方库 ⑤ 提供生产就绪功能 ⑥ 极少的代码生成…

【Mybatis-plus】查询及更新为null或空字符串

前言 查询为 null 或者 空字符串时&#xff0c;可以使用 or() 关键字。 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 查询 使用 LambdaQueryWrapper 查询 parentCode 为 null 或者 空字符串 的数据。 LambdaQueryWrapper<CompanyEntity> qu…

视频集市新增支持多格式流媒体拉流预览

流媒体除了常用实时流外还有大部分是以文件的形式存在&#xff0c;做融合预览必须要考虑多种兼容性能力&#xff0c;借用现有的ffmpeg生态可以迅速实现多种格式的支持&#xff0c;现在我们将按需拉流预览功能进行了拓展&#xff0c;正式支持了ffmpeg的功能&#xff0c;可快捷方…

探索FlowUs息流:个人和团队知识管理解决方案|FlowUs稳定保障你的笔记安全无忧

FlowUs息流&#xff1a;稳定运营保障你的笔记安全无忧 在知识管理工具的选择上&#xff0c;稳定性是用户最关心的问题之一。FlowUs息流以其稳定的运营记录&#xff0c;为用户提供了一个可靠的工作环境。我们深知&#xff0c;一个知识管理平台的稳定性直接影响到团队的生产力和…

后端不提供文件流接口,前台js使用a标签实现当前表格数据(数组非blob数据)下载成Excel

前言&#xff1a;开发过程中遇到的一些业务场景&#xff0c;如果第三方不让使用&#xff0c;后端不提供接口&#xff0c;就只能拿到table数据(Array)&#xff0c;实现excel文件下载。 废话不多说&#xff0c;直接上代码&#xff0c;方法后续自行封装即可&#xff1a; functio…

Retrofit类型安全的HTTP客户端库

简介 Retrofit是Square公司开发的一个类型安全的HTTP客户端库&#xff0c;用于Android和Java平台&#xff0c;它使得与Web服务的交互变得更加简单快捷。Retrofit将HTTP API转换成Java接口&#xff0c;让你可以用更简洁的代码形式调用RESTful API&#xff0c;Android网络编程重点…

物联网设备安装相关知识整理

拓扑图 对于ADAM-4150先接设备的整体的供电。 ADAM-4150就涉及到几个电子元器件的连接&#xff0c;一个是485-232的转换器&#xff0c;一个是将RS-232转换为USB的转接口&#xff0c;因为现在的计算机很多都去掉了RS-232接口而使用USB接口。 4150右侧有个拨码&#xff0c;分别两…

无需科学上网:轻松实现国内使用Coze.com平台自己创建的Bot(如何实现国内免费使用GPT-4o/Gemini等最新大模型)

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 如何在国内使用 Coze.com 创建的 Bot 📒📝 创建Bot📝 实现国内使用📝 测试⚓️ 相关链接 ⚓️📖 介绍 📖 Coze.com 是一个强大的平台,允许用户创建各种类型的 Bot。然而,许多国内用户可能会遇到访问问题,导致无法…

100多个ChatGPT指令提示词分享

当前&#xff0c;ChatGPT几乎已经占领了整个互联网。全球范围内成千上万的用户正使用这款人工智能驱动的聊天机器人来满足各种需求。然而&#xff0c;并不是每个人都知道如何充分有效地利用ChatGPT的潜力。其实有许多令人惊叹的ChatGPT指令提示词&#xff0c;可以提升您与ChatG…

健康与生活助手:Kompas AI的高效应用

一、引言 在现代社会&#xff0c;随着生活节奏的加快和工作压力的增加&#xff0c;人们的健康问题日益凸显。健康管理已经成为每个人关注的重点。Kompas AI作为一款智能助手&#xff0c;通过其先进的人工智能技术&#xff0c;为用户提供全面的健康管理服务&#xff0c;帮助用户…

解锁5G新营销:视频短信的优势与全方位推广策略

随着5G时代的全面来临&#xff0c;企业的数字化转型步伐日益加快&#xff0c;视频短信作为新兴的数字营销工具&#xff0c;正逐步展现出其巨大的潜力。视频短信群发以其独特的形式和内容&#xff0c;将图片、文字、视频、声音融为一体&#xff0c;为用户带来全新的直观感受&…

React实现H5手势密码

监测应用进入前后台 在JavaScript中&#xff0c;监听H5页面是否在前台或后台运行&#xff0c;主要依赖于Page Visibility API。这个API在大多数现代浏览器中都是支持的&#xff0c;包括苹果的Safari和谷歌的Chrome&#xff08;也就基本覆盖了Android和iOS平台&#xff09;。下…

第三十三篇-Ollama+AnythingLLM基本集成

AnythingLLM AnythingLLM专属私有知识库,可以使用本地OllamaLLM模型&#xff0c;可以上传文件&#xff0c;基于文件回答问题 启动ollama 参考 第二十五篇-Ollama-离线安装 第二十四篇-Ollama-在线安装 下载安装AnythingLLM https://useanything.com/downloadAnythingLLMDe…

我们是否需要AI服务器?推动人工智能繁荣发展的AI服务器

揭穿人工智能服务器的炒作 人工智能的研究已经有几十年了&#xff0c;早在 1960 年代&#xff0c;生成式人工智能就已应用于聊天机器人。然而&#xff0c;2022 年 11 月 30 日发布的 ChatGPT 聊天机器人和虚拟助手席卷了 IT 界&#xff0c;让 GenAI 成为家喻户晓的术语&#x…

vue3 + vite + js 配置Eslint + prettier_vite+js+vue3配置eslint

plugins: [ ‘vue’ ], rules: { } } ##### 第三步 安装 vite-plugin-eslint// 该包是用于配置vite运行的时候自动检测eslint规范&#xff0c;不符合页面会报错 pnpm add vite-plugin-eslintlatest -D // 安装最新版eslint-plugin-vue pnpm add eslint-plugin-vuelatest -D ###…

论文阅读--Cross-view Transformers for real-time Map-view Semantic Segmentation

一种新的2D维度的bev特征提取方案&#xff0c;其通过引入相机先验信息&#xff08;相机内参和外参&#xff09;构建了一个多视图交叉注意力机制&#xff0c;能够将多视图特征映射为BEV特征。 cross view attention&#xff1a;BEV位置编码由根据相机标定结果&#xff08;内参和…

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 密码解密(100分) - 三语言AC题解(Python/Java/Cpp)

&#x1f36d; 大家好这里是清隆学长 &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f497; &#x1f…