LJZの博客
type: channel
link: https://oini.de/
description: 欢迎来到我的个人博客！这里是我分享思考和创作的地方。在这个平台上，我记录了自己在技术、生活、学习上的一些点滴。无论是工作中的经验、个人的成长故事，还是一些日常的感悟和兴趣，我都会在这里与大家分享。
items: ✨ 恋风画廊（www.luvbree.com）— 打造属于你的专属壁纸空间
items: Typecho-handsome主题-添加服务器状态栏
items: 如何给Typecho博客增加AI摘要
items: 数据结构与算法——排序算法-插入排序
items: 数据结构与算法——排序算法-选择排序
items: 数据结构与算法——排序算法-冒泡排序
items: 数据结构和算法——递归-八皇后问题（回溯算法）
items: 数据结构与算法——递归-迷宫问题
items: 数据结构与算法——初谈递归
items: 数据结构与算法——栈（五）中缀表达式转后缀表达式
items: 数据结构与算法——栈（四）逆波兰计算器-后缀表达式

✨ 恋风画廊（www.luvbree.com）— 打造属于你的专属壁纸空间
type: item
date: 2025-06-24T07:35:29+00:00
description: AI摘要 恋风画廊是一个提供高质量、无水印、风格多样壁纸资源的网站，支持手机和电脑壁纸，具有高清无水印、持续更新、多设备适配和极简设计等特点。网站鼓励用户分享和反馈，以提供更好的壁纸体验。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 💡 你是否正在寻找一个高质量、无水印、风格多样的壁纸资源站？欢迎来到我们倾力打造的壁纸平台 —— 恋风画廊！🌈 关于恋风画廊恋风画廊 是一个专注于分享高质量高清壁纸的网站，我们希望为用户带来：视觉上的美感享受操作上的极简体验更新上的持续丰富无论你是手机党、桌面党，还是壁纸收藏控，都能在这里找到灵感与满足。🔥 我们的特色✅ 高清无水印所有壁纸均为高清资源，拒绝水印干扰，美感不打折。✅ 持续更新定期会有新内容上线，涵盖多个风格与场景，保持新鲜。✅ 多设备适配支持手机与电脑壁纸，涵盖多种主流分辨率，一键下载即用。✅ 极简设计，纯净体验无注册限制，访问即看，下载即用。❤️ 给用户的一封信我们始终相信，一张好的壁纸，不只是装点桌面，更能点亮生活的灵感。如果你喜欢恋风画廊，欢迎将我们分享给朋友、收藏网址，参与共建与反馈！📬 有任何建议或合作意向，欢迎联系：[love@oini.de]

Typecho-handsome主题-添加服务器状态栏
type: item
date: 2025-05-06T06:46:00+00:00
description: AI摘要 本文介绍了如何在Typecho的handsome主题中添加服务器状态栏。首先，通过修改headnav.php文件，添加服务器状态栏的HTML代码。然后，在主题设置中添加自定义的JavaScript代码，用于动态显示服务器状态信息。最后，创建serverInfo.php文件，用于提供服务器状态数据。通过这些步骤，可以在网站页面上实时显示服务器的CPU占用、内存使用、磁盘使用等信息。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 效果图：文件修改 headnav.php 文件路径：usr/themes/handsome/component/headnav.php，具体位置如下图，位于两个 中间[collapse status="false" title="展开查看详情"] <polyline points="22 12 18 12 15 21 9 3 6 12 2 12"></polyline> 运行状态 CPU占用 占用内存 磁盘占用 内存缓存 内存缓冲 系统负载 网络状态 IO 实时IO 网络 实时网络 服务器时间 <?php echo $_SERVER['SERVER_SOFTWARE']; ?> WEB服务器 <?php echo $_SERVER['SERVER_PROTOCOL']; ?> 通信协议 <?php echo PHP_VERSION;?> PHP版本 访客信息 持续运行 您的IP 网络地址 浏览器信息 您的设备 <?php echo $_SERVER['REQUEST_METHOD'];?> 请求方法 <?php echo $_SERVER['HTTP_ACCEPT_LANGUAGE'];?> 服务语言 您的设备时间 [/collapse]主题设置 - 开发者设置 - 自定义输出body 尾部的HTML代码[collapse status="false" title="展开查看详情"] [/collapse]上述修改完毕之后，在网站的根目录新建 serverInfo.php 文件[collapse status="false" title="展开查看详情"]<?php /** * 获取当前Unix时间戳 * */ $unixTimestamp = time(); /** * 获取服务器总的运行时长 * */ $serverUptime = getUpTime(); /** * 获取服务器负载 以及CPU使用信息 * */ $serverLoad = GetLoad(); $cpuUsage = GetCPUInfo(); /** * 获取服务器内存信息 * */ $memoryInfo = GetMem(); // 处理IP信息请求 if(isset($_GET['action']) && $_GET['action'] == 'getip') { // 获取用户真实IP地址 $ip = ''; if(!empty($_SERVER['HTTP_CLIENT_IP'])){ $ip = $_SERVER['HTTP_CLIENT_IP']; }elseif(!empty($_SERVER['HTTP_X_FORWARDED_FOR'])){ $ip = $_SERVER['HTTP_X_FORWARDED_FOR']; }else{ $ip = $_SERVER['REMOTE_ADDR']; } // 简单过滤掉非法IP $ip = filter_var($ip, FILTER_VALIDATE_IP) ? $ip : '未知'; // 获取地理位置信息（只对公网IP有效） $location = ''; // 检查是否是内网IP if(!filter_var($ip, FILTER_VALIDATE_IP, FILTER_FLAG_NO_PRIV_RANGE | FILTER_FLAG_NO_RES_RANGE)) { $location = '内网IP'; } else { // 方法1：使用太平洋IP库（覆盖较全面，国内外都支持） $url = "http://whois.pconline.com.cn/ipJson.jsp?ip={$ip}&json=true"; $ch = curl_init(); curl_setopt($ch, CURLOPT_URL, $url); curl_setopt($ch, CURLOPT_RETURNTRANSFER, true); curl_setopt($ch, CURLOPT_TIMEOUT, 3); curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, false); curl_setopt($ch…

如何给Typecho博客增加AI摘要
type: item
date: 2025-05-04T07:19:00+00:00
description: AI摘要 本文介绍了如何为Typecho博客添加AI摘要功能。作者选择了AISummary插件，并尝试了阿里千问和Kimi两个平台，最终选择了Kimi。作者还提供了自定义CSS样式和HTML代码，以改善AI摘要的显示效果。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 网上冲浪时看到很多博主的博客的文章都有一个ai摘要功能，秉着别人有的，我也想要的原则。于是特意去了解给博客增加ai摘要的方法。通过对接一个第三方ai平台，将文章内容发送给ai让其生成摘要，然后作为文章的附属字段。有的为了更加灵活，提供了实时生成摘要，但是本质都是对接第三方ai平台。经过查询和对比，最后选择的插件是：AISummary从插件提供的配置来看，使用方式是很简单的只需要确定对接的ai平台。填入模型名称，sk-密钥基本就可以了。这里博主尝试了两个平台，都提供免费使用sk的，亲测是可用的。一个是阿里千问，一个Kimi。经过对比后，博主选择的是Kimi。最后，插件提供的生成的默认样式不太好看，所以这里针对主题样式写了一个自定义ai摘要的样式效果。最终的效果如下：自定义样式（打印机效果）： 正文摘要前后固定文字： <path stroke="none" d="M0 0h24v24H0z" fill="none"/> <path d="M3 10a4 4 0 0 1 4 -4h10a4 4 0 0 1 4 4v6a4 4 0 0 1 -4 4h-10a4 4 0 0 1 -4 -4v-6z" /> <path d="M8 3l2 3" /> <path d="M16 3l-2 3" /> <path d="M9 13v-2" /> <path d="M15 11v2" /> AI摘要 {{text}} 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结

数据结构与算法——排序算法-插入排序
type: item
date: 2025-05-03T16:08:00+00:00
description: AI摘要 插入排序是一种简单的排序算法，通过将待排序元素插入到已排序序列中的适当位置来实现排序。它的时间复杂度在最好情况下为O(n)，最坏情况下为O(n^2)。文章通过动图和代码示例详细解释了插入排序的工作原理和实现过程，并测试了其在大量数据排序时的性能。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 基本介绍插入排序（Insertion Sorting）属于内部排序法，是对于欲排序的元素以 插入的方式寻找该元素的适当位置，以达到排序的目的。该 插入排序 又被称为 直接插入排序 或 简单插入排序。基本思想插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素 看成 为一个 有序表 和 无序表开始时，有序表中只包含一个元素，无序表中包含有 n - 1 个 元素排序过程中每次 从无序表中取出第一个元素，把它的排序码 依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。举个例子：插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。思路分析动图：如上图，插入排序一共有 数据大小 - 1 轮排序第一个元素作为初始的有序表，剩下的其他作为无序表当第一次比较时：无序表中的第一个元素 取出来与 有序表倒数第一个元素 比较（从小到大），发现 44 大于 3，于是插入到有序表中适当的位置以此类推，直到比较完成。代码实现为了简单分析，使用这样一个场景：假设有一群小牛，考试成绩分别是 101、34、119、1，从小到大排序 /** * 为了更好的理解，将插入排序演变过程演示出来，逐步推导的方式演示 */ @Test public void processDemo() { int arr[] = {101, 34, 119, 1}; System.out.println("原始数组：" + Arrays.toString(arr)); processSelectSort(arr); } private void processSelectSort(int[] arr) { // 第 1 轮： // 有序表：101 // 无序表：34, 119, 1 // 值的注意的是：不一定就要分两个数组来操作，这样想，就想太复杂了。只是看成两段 int currentInsertValue = arr[1]; // 当前要找位置插入的数 int insertIndex = 1 - 1; // 要插入的数与有序表中最后一个开始比较（存储的是下标）。也就是当前数的上一个开始比较 while (insertIndex >= 0 // 保证插入数组不越界 // 当前与有序列表中的数据进行对比 // 如果小于：则说明有序表中的该值需要向后移动 // 例如：101, 34, 119, 1 中, 34 < 101, 移动后变成 101, 101, 119, 1 // currentInsertValue = 34，insertIndex = -1 这看不懂的往下面看，看懂这个while循环 && currentInsertValue < arr[insertIndex] ) { arr[insertIndex + 1] = arr[insertIndex]; // 向后移动一位 insertIndex--; // 并将下一次要比较的有序列表的下标往前一位 } // 当退出循环后：要么 insertIndex = -1, 说明应该插入到有序列表中的第一个位置 // 要么 就找到了合适的位置，所以无论哪一种情况， insertIndex + 1，才是当前数要插入的位置 arr[insertIndex + 1] = currentInsertValue; System.out.println("第 1 轮排序后：" + Arrays.toString(arr)); // 第 2 轮： // 有序表：34, 101 // 无序表：119, 1 currentInsertValue = arr[2]; // 当前要找位置插入的数：119 insertIndex = 2 - 1; // 当前的上一个开始 while (insertIndex >= 0 // 保证插入数组不越界 // 当前与有序列表中的数据进行对比 // 如果小于：则说明有序表中的该值需要向后移动 // 例如：34, 101, 119, 1 , 119 > 101, 这里不满足，则退出 // currentInsertValue…

数据结构与算法——排序算法-选择排序
type: item
date: 2025-05-03T16:06:22+00:00
description: AI摘要 选择排序是一种简单直观的排序方法，其基本思想是从数组中选取最小值，与数组的第一个元素交换，然后从剩余的元素中继续寻找最小值，与数组的第二个元素交换，以此类推，直到所有元素均排序完毕。选择排序的时间复杂度为O(n²)，因为包含一个嵌套循环。尽管冒泡排序和选择排序的时间复杂度相同，但由于选择排序在每一步中只有一次交换，所以它通常比冒泡排序更高效。文章还提供了选择排序的Java代码实现，包括基本实现、优化版本和支持升序及降序排序的函数封装。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 基本介绍选择排序（select sorting）也属于内部排序法，是从欲排序的数据中，按指定的规则选出来某个元素，再依规定交换位置后达到排序的目的。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。基本思想选择排序（select sorting）也是一种简单直观的排序方法。基本思想为：注：n 是数组大小第一次从 arr[0]~arr[n-1] 中选取最小值，与 arr[0] 交换第二次从 arr[1]~arr[n-1] 中选取最小值，与 arr[1] 交换第 i 次从 arr[i-1]~arr[n-1] 中选取最小值，与 arr[i-1] 交换依次类图，总共通过 n - 1 次，得到一个按排序码从小到大排列的有序序列思路分析动图：说明：选择排序一共有数组大小 - 1 轮排序每 1 轮排序，又是一个循环，循环的规则①先假定当前这轮循环的第一个数是最小数②然后和后面每个数进行比较，如果发现有比当前数更小的数，则重新确定最小数，并得到下标③当遍历到数组的最后时，就得到本轮最小的数④和当前循环的第一个数进行交换代码实现要求：假设有一群牛，颜值分别是 101,34,119,1 ，请使用选中排序从低到高进行排序演变过程使用逐步推导的方式，进行讲解排序，容易理解。推导每一步的演变过程，便于理解。​ 这是一个很重要的思想：​ 一个算法：先简单 --> 做复杂：​ 就是可以把一个复杂的算法，拆分成简单的问题 -> 逐步解决 @Test public void processDemo() { int arr[] = {101, 34, 119, 1}; System.out.println("原始数组：" + Arrays.toString(arr)); processSelectSort(arr); } public void processSelectSort(int[] arr) { // 第 1 轮： // 原始数组：101, 34, 119, 1 // 排序后： 1, 34, 119, 101 int min = arr[0]; // 先假定第一个数为最小值 int minIndex = 0; for (int j = 0 + 1; j < arr.length; j++) { // 挨个与最小值对比，如果小于，则进行交换 if (min > arr[j]) { // 如果后面的值比当前的 min 小，则重置min为这个数 min = arr[j]; minIndex = j; } } // 第 1 轮结束后，得到了最小值 // 将这个最小值与 arr[0] 交换 arr[minIndex] = arr[0]; arr[0] = min; System.out.println("第 1 轮排序后：" + Arrays.toString(arr)); // 第 2 轮 // 当前数组：1, 34, 119, 101 // 排序后： 1, 34, 119, 101 min = arr[1]; minIndex = 1; // 第二轮，与第 3 个数开始比起 for (int j = 0 + 2; j < arr.length; j++) { // 挨个与最小值对比，如果小于，则进行交换 if (min > arr[j]) { // 如果后面的值比当前的 min 小，则重置min为这个数 min = arr[j]; minIndex = j; } } // 第 2 轮结束后，得到了最小值 // 将这个最小值与 arr[1] 交换 arr[minIndex] = arr[1]; arr[1] = min; System.out.println("第 2 轮排序后：" + Arrays.toString(arr)); // 第 3 轮 // 当前数组：1, 34, 119, 101 // 排序后： 1, 34, 101, 119 min = arr[2]; minIndex = 2; // 第二轮，与第 4…

数据结构与算法——排序算法-冒泡排序
type: item
date: 2025-05-03T16:04:21+00:00
description: AI摘要 冒泡排序是一种简单的排序算法，通过比较相邻元素并交换逆序元素，使较大元素逐渐向后移动。该算法时间复杂度为O(n²)，但可以通过设置标志判断元素是否进行过交换来优化，减少不必要的比较。文章通过图解和代码示例详细解释了冒泡排序的演变过程、优化方法和封装算法，并测试了大量数据排序的时间消耗。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 基本介绍冒泡排序（Bubble Sorting）（时间复杂度为 O(n²)）的基本思想：通过对待排序序列 从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的旗袍一样逐渐向上冒。优化点：因为排序过程中，个元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志判断元素是否进行过交换。从而减少不必要的比较。（该优化点可以在完成基本的冒泡排序之后再做）图解冒泡排序算法的过程动图：冒泡排序小结：共进行 数组大小 - 1 次大的循环每一趟排序的次数在逐渐的减少优化：如果发现在某趟排序中，没有发生一次交换，则可以提前结束冒泡排序。代码实现演变过程为了容易理解，先演示冒泡排序的演变过程 /** * 为了更好的理解，这里把冒泡排序的演变过程演示出来 */ @Test public void processDemo() { int arr[] = {3, 9, -1, 10, -2}; // 第 1 趟排序：将最大的数排在最后 // 总共排序：arr.length - 1 int temp = 0; // 临时变量，交换的时候使用 for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.out.println("第 1 趟排序后的数组"); System.out.println(Arrays.toString(arr)); // 第 2 趟排序：将第 2 大的数排在倒数第 2 位 // 总共排序：arr.length - 1 - 1 ； // 从头开始排序，其他没有变化，只是将排序次数减少了一次 for (int i = 0; i < arr.length - 1 -1; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.out.println("第 2 趟排序后的数组"); System.out.println(Arrays.toString(arr)); // 第 3 趟排序：将第 3 大的数排在倒数第 3 位 // 总共排序：arr.length - 1 - 2 ； // 从头开始排序，其他没有变化，只是将排序次数减少了 2 次 for (int i = 0; i < arr.length - 1 -2; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.out.println("第 3 趟排序后的数组"); System.out.println(Arrays.toString(arr)); // 第 4 趟排序：将第 4 大的数排在倒数第 4 位 // 总共排序：arr.length - 1 - 3 ； // 从头开始排序，其他没有变化，只是将排序次数减少了 3 次 for (int i = 0; i < arr.length - 1 -3; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.out.println("第 4 趟排序后的数组"); System.out.println(Arrays.toString(arr)); // 第 5 趟没有必要，因为这里有 5 个数字，确定了 4 个数字，剩下的那一个就已经出来了 }测试输出第 1 趟排序后的数组 [3, -1, 9, -2, 10] 第 2 趟排序后的数组 [-1, 3, -2, 9, 10] 第 3 趟排序后的数组 [-1, -2, 3, 9, 10] 第 4 趟排序后的数组 [-2, -1, 3, 9, 10]从上述的 4 趟排序过程来看，循环体都是一…

数据结构和算法——递归-八皇后问题（回溯算法）
type: item
date: 2025-05-03T16:00:44+00:00
description: AI摘要 八皇后问题是一个经典的回溯算法问题，要求在8x8的棋盘上放置八个皇后，使得它们互不攻击。本文通过递归回溯算法详细解释了如何求解八皇后问题，包括算法思路、代码实现和细节分析。算法的核心是使用一维数组代替二维棋盘，并通过递归尝试所有可能的放置位置，同时检查是否违反规则。最终，算法能够找到所有可能的解决方案，并打印出每种摆法的坐标。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 看完 数据结构与算法——递归-迷宫问题 后，我们对递归和回溯算法有了一个基本的认识，本篇将讲解 一个著名的问题：八皇后问题，能让我们对递归和回溯有一个更深刻的认识。八皇后问题，是一个古老而著名的问题，是 回溯算法 的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有 76 种方案。1854年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。计算机发明后，有多种计算机语言可以解决此问题。可以去百度搜索下这个小游戏，自己玩几下感受下，还是很难的八皇后思路分析用递归回溯算法找出八皇后有多少种摆法，其实就是暴力穷举，思路如下：第一个皇后先放第一行第一列第二个皇后放在第二行第一列，然后判断是否符合规则，如果不符合规则，则继续放在第 2 列，依次的测试下去，直到符合规则后，放第三个皇后。继续第 3 个皇后，直到 8 个皇后都放到了棋盘上，并且没有违反规则，就算是一个解答当得到一个正确解时，记录下棋盘上的皇后的所有坐标（在每一次放皇后符合规则后都会记录本坐标），方便我们打印查看结果，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后放在第一列的所有正确解全部拿到然后回头继续第一个皇后放第二列，后面继续循环执行前面 4 步，以此类推，当求完第一行的皇后在每个列上的所有答案，就是全部解了（一共92种）如果这里读不明白，就继续往下看，结合后面的细节分析和代码注释 看懂代码，就好理解了。理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}，这个是存储结果，数组下标表示第几行，对应的值则为在那一列上摆放着/** * 八皇后问题： * * 规则：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击， * 即：任意 两个皇后 都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 * */ public class Queue8 { // 共有多少个皇后 int max = 8; /** * 存放皇后位置的结果 * * 下标：表示棋盘中的某一行 * 对应的值：表示在这一行上，该皇后摆放在哪一列 * 比如：array[0] = 1，表示在第 1 行的第 2 列上摆放了一个皇后 * * 由于规则，一行只能有一个皇后，所以可以使用一维数组来代替二维数组的棋盘结果 * */ int[] array = new int[max]; int count = 0; // 统计有多少个结果 public static void main(String[] args) { Queue8 queue8 = new Queue8(); queue8.check(0); // 从第 1 行开始放置 } /** * 放置第 n 个（行）皇后 *特别注意： check 是 每一次递归时，进入到check中都有 for(int i = 0; i < max; i++)，因此会有回溯 * @param n */ private void check(int n) { // n = 8，那么表示放第 9 个皇后，8 个皇后已经放完了（n 从0开始计数的） // 表示找到了一个正确的结果，打印这个结果，并返回 if (n == max) { count++; print(); return; } // 开始暴力对比，从该行的第一列开始尝试放置皇后，直到与前面所放置的不冲突 for (int i = 0; i < max; i++) { // 在该行的第 i 列上放置一个皇后 array[n] = i; // 检测与已经放置的是否冲突 if (judge(n)) { // 如果不冲突，则表示该行的皇后放置没有问题 // 开始进入下一行的皇后放置 check(n + 1); } // 如果冲突，这里什么也不做 // 因为是从第一列开始放置，如果冲突，则尝试放置到第 2 列上，直到放置成功 } } /** * 按游戏规则要求，判定要放置的这一个皇后，和前面已经摆放的位置是否冲突 * * @pa…

数据结构与算法——递归-迷宫问题
type: item
date: 2025-05-03T15:59:27+00:00
description: AI摘要 文章介绍了递归在解决迷宫问题中的应用。通过Java代码实现了一个迷宫求解程序，使用递归回溯的方法找到小球从迷宫起点到终点的路径。代码中定义了一个二维数组模拟迷宫，通过递归函数尝试不同的路径，直到找到出口。文章还展示了不同找路策略对路径选择的影响，并强调了递归算法的奇妙之处。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 迷宫问题（回溯），对上图说明：红色的方块是围墙，是小球不能够走的白色的方块是小球可以活动的范围左上角是小球的起点，移动到右下角，就算走出了迷宫那么在这个场景中，就用到了递归（Recursion），下面使用代码来实现小球走出迷宫的路径。下面用数字矩阵来模拟迷宫，重要的是学习其思想，懂得下次遇到类似的可以灵活运用。代码实现如果看一次看不懂，多琢磨几次。/** * * 迷宫问题求解 * */ public class MiGong { public static void main(String[] args) { // 先创建一个二维数组，模拟迷宫 // 地图 int[][] map = new int[8][7]; // 使用1 表示墙 // 上下全部置为1 for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } // 左右全部置为1 for (int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } //设置挡板, 1 表示 /* * 1 1 1 1 1 1 1 * 1 0 0 0 0 0 1 * 1 0 0 0 0 0 1 * 1 1 1 0 0 0 1 * 1 0 0 0 0 0 1 * 1 0 0 0 0 0 1 * 1 0 0 0 0 0 1 * 1 1 1 1 1 1 1 */ map[3][1] = 1; map[3][2] = 1; // map[1][2] = 1; // map[2][2] = 1; //如果打开上面两个注释，地图就为 /* 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 */ //这个地图是为了体验回溯 // 输出没有开始走的地图 System.out.println("地图的情况"); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } //使用递归回溯给小球找路 setWay(map, 1, 1); //setWay2(map, 1, 1); //体验不同找路策略走出来的路 //输出新的地图, 小球走过，并标识过的递归 System.out.println("小球走过，并标识过的 地图的情况"); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } } //使用递归回溯来给小球找路 //说明 //1. map 表示地图 //2. i,j 表示从地图的哪个位置开始出发 (1,1) //3. 如果小球能到 map[6][5] 位置（终点），则说明通路找到. //4. 约定： 当map[i][j] 为 0 表示该点没有走过 当为 1 表示墙 ； 2 表示通路可以走 ； 3 表示该点已经走过，但是走不通，死路 //5. 在走迷宫时，需要确定一个策略(方法)，也就是当你站在一个点的时候，你从哪一个方向开始探索，这里规定探索的方向为： 下->右->上->左 , 如果该点走不通，再回溯 /** * * @param map 表示地图 * @param i 从哪个位置开始找 * @param j * @return 如果找到通路，就返回true, 否则返回false */ public static boolean setWay(int[][] map, int i, int j) { if(map[6][5] == 2) { // 通路已经找到ok return true; } else { if(map[i][j] == 0) { //如果当前这个点还没有走过 //按照策略 下->右->上->左 走 map[i][j] = 2; // 假定该点是可以走通. if(setWay(map, i…

数据结构与算法——初谈递归
type: item
date: 2025-05-03T15:55:40+00:00
description: AI摘要 本文介绍了递归的概念、应用场景、调用机制以及使用规则。递归是一种方法自己调用自己的编程技巧，可以简化复杂问题的代码实现。文章通过迷宫问题、打印问题和阶乘问题等案例，详细解释了递归的工作原理和调用过程。递归在解决数学问题和算法实现中具有广泛应用，但使用时必须遵守一定的规则，以避免无限递归和栈溢出错误。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 一、递归的简单应用场景迷宫问题（回溯），上图说明：红色的方块是围墙，是小球不能够走的白色的方块是小球可以活动的范围左上角是小球的起点，移动到右下角，就算走出了迷宫那么在这个场景中，就用到了递归（Recursion）二、递归的概念简单说：递归就是方法自己调用自己，每次调用时 传入不同的变量递归有助于编程者解决复杂的问题，同时可以让代码变简单。tip：当传入的数据是引用类型 例如：数组，String等，则递归程序是一起操作同一个数据，共享这个数据。因为引用类型的传递是地址传递。三、递归调用机制使用两个小案例，来帮助理解递归的调用机制：打印问题阶乘问题打印问题有下面一段代码，请问打印出什么信息？public static void main(String[] args) { test(4); } public static void test(int n) { if (n > 2) { test(n - 1); } System.out.println("n=" + n); }下图是一个虚拟机内存区域简单划分如上图所示：当程序执行到一个方法时，就会开辟一个独立的空间（栈空间）man 方法先执行，执行到 test(4)，就开辟可一个空间由于test()方法中有判定 n > 2 时，再次调用 test() 方法，所以会不断开辟空间，直到不再满足调用 test() 方法的条件到了最顶端的空间区域，不满足条件，就会开始打印信息一个区域执行完代码后，就会回到上一个调用它的那个空间，继续执行剩下的代码那么直到所有代码运行完成，就如下图所示了从最顶端开始返回执行剩余代码，也就是打印信息，直到退出程序。那么结果就是上图所示的控制台中的信息。运行上面的程序，也会输出一样的结果n=2 n=3 n=4阶乘问题public static void main(String[] args) { System.out.println(factorial(5)); } /** * * 阶乘问题：传递一个数值, 从 1 开始乘以 2，再乘以 3，一直到 N，的结果， * 比如从 1 阶乘到 5，也就是计算 1 * 2 * 3 * 4 * 5 的结果，如下所示 * 1 * 2 = 2 * 2 * 3 = 6 * 6 * 4 = 24 * 24 * 5 = 120 * 结果是 120 * * * @return */ public static int factorial(int n) { if (n == 1) { return 1; } else { return factorial(n - 1) * n; } }那么这里的输出结果就是 120。想要复原这个计算过程，可以使用如下代码public static int factorial2(int n) { if (n == 1) { return 1; } else { int factorial = factorial2(n - 1); // 按照递归调用原则，这里我们使用的是 n-1,返回条件是 n==1 // 所以，当 n = 1 时，也就是 factorial = 1 时，这里的语句最最先开始执行 // 然后把执行结果返回到上一个独立空间，并继续执行计算 System.out.printf("%d * %d = %d \n", factorial, n, factorial * n); return factorial * n; } }这里输出信息是1 * 2 = 2 2 * 3 = 6 6 * 4 = 24 24 * 5 = 120四、递归能解决什么样的问题各种数学问题，如：8皇后问题 、汉诺塔、阶乘问题、迷宫问题、球和篮子的问题（google 编程大赛里面的题目）各种算法中也会使用到递归，比如：快排、归并排序、二分查找、分治算法等将用栈解决的问题，可以用递归代码实现，比较简洁五、* 递归需要遵守的规则执行一个方法时，就创建一个新的受保护的独立空间（栈空间）方法的局部变量是独立的，不会相互影响，比如 n 变量，但是如果是引用类型变量（比如数组），就会共享该引用类型的数据递归 必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError ，死龟了:)当一个方法执行完毕，或则遇到 return，就会返回，遵守谁调用…

数据结构与算法——栈（五）中缀表达式转后缀表达式
type: item
date: 2025-05-03T15:53:48+00:00
description: AI摘要 本文介绍了如何将中缀表达式转换为后缀表达式，并提供了完整的逆波兰计算器代码实现。中缀转后缀的步骤包括初始化两个栈、从左到右扫描中缀表达式、遇到操作数或运算符时的处理规则以及遇到括号时的处理规则。文章还提供了Java代码实现，包括将中缀表达式解析成单个元素的List、中缀表达式List转为后缀表达式List、计算操作符号优先级的类以及完整版逆波兰计算器。测试输出显示了中缀表达式转换为后缀表达式的过程和最终的计算结果。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 通过数据结构与算法——栈（四）逆波兰计算器-后缀表达式的代码实现，可以看到：后缀表达式对于计算机来说很方便，但是对于我们人来说，后缀表达式却不是那么容易写出来的。所以本篇就是来讲解怎么实现中缀表达式转换成后缀表达式,以及完成完整版的逆波兰计算器。[TOC]* 中缀表达式转后缀表达式步骤初始化两个栈：运算符栈：s1中间结果栈：s2从左到右扫描中缀表达式遇到操作数时，将其压入 s2遇到运算符时比较 它 与 s1 栈顶运算符的优先级：​ （1）如果 s1 为空，或则栈顶运算符号为 ( ，则将其压入符号栈 s1​ （2）否则，若优先级比栈顶运算符 高，也将其压入符号栈 s1​ （3）否则，若优先级比栈顶运算符 低 或 相等，将 s1 栈顶的运算符 弹出，并压入到 s2 中再重复第 4.1 步骤，与新的栈顶运算符比较（因为 4.3 将 s1 栈顶运算符弹出了）这里重复的步骤在实现的时候有点难以理解，下面进行解说：​ 如果 s1 栈顶符号 优先级比 当前符号 高或则等于，那么就将其 弹出，压入 s2 中（循环做，是只要 s1 不为空），如果栈顶符号为 (，这里不把(当作运算符，所以碰到了就不用作比较了，(也不用弹出，直接 把当前运算符压入即可。但如果当前运算符为左括号 ( 或者 右括号 ) 呢？那就看下面的 第5点遇到括号时：​ （1）如果是左括号 ( ：则直接压入 s1​ （2）如果是右括号 )： 则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到 左括号 (为止，此时将这一对括号【 即当前的右括号 )和碰到的第一个 栈顶的左括号 ( 】丢弃。重复步骤 2 到 5，直到表达式最右端后将 s1 中的运算符依次弹出并压入 s2依次弹出 s2 中的元素并输出，结果的 逆序 即为：中缀表达式转后缀表达式下面进行举例说明：将中缀表达式：1+((2+3)*4)-5 转换为后缀表达式扫描到的元素s2 （栈底 -> 栈顶）s1（栈底 -> 栈顶）说明11空遇到操作数，将其压入 s2+1+s1 栈为空，将其压入 s1(1+ (是左括号，直接压入 s1(1+ ( (是左括号，直接压入 s121 2+ ( (遇到操作数，将其压入 s2+1 2+ ( ( +遇到操作符：与 s1 栈顶运算符比较，栈顶为 (，直接将其压入 s131 2 3+ ( ( +遇到操作数，将其压入 s2)1 2 3 ++ (遇到右括号：弹出运算符直至遇到左括号，这里弹出 s1 中的 + 压入 s2 中，这里去掉这一对小括号*1 2 3 ++ ( *遇到操作符：与 s1 栈顶比较，栈顶为 (，直接将其压入 s1 栈41 2 3 + 4+ ( *遇到操作数：将其压入 s2)1 2 3 + 4 *+遇到右括号：弹出运算符直至遇到左括号，这里弹出 s1 中的 * 压入 s2 中，这里去掉这一对小括号-1 2 3 + 4 * +-遇到操作符：与 s1 栈顶比较，优先级一致，将 s1 中的 + 弹出，并压入 s2 中，再将-压入s151 2 3 + 4 * + 5-遇到操作数：将其压入 s2到达最右端1 2 3 + 4 * + 5 -空解析完毕，将 s1 中的符号弹出并压入 s2 中由于 s2 是一个栈，弹出是从栈顶弹出，因此逆序后结果就是 1 2 3 + 4 * + 5 -我的疑问你怎么知道这个中缀表达式转后缀表达式的思路是这样的？在学习和使用上有两个层次：应用层次：别人发明出来的东西，你学习、理解它，并灵活运用它自创：你自己发明一个东西出来，并使用它那么这里的中缀转后缀表达式的思路步骤，则属于第一个层次，相关的计算机专家之类的，发明出来了。我们要理解它并灵活运用它。等你能力达到一定层度时，有可能发明出来一个算法。再比如：绝世武功 -> 降龙十八掌，别人已经创造出来了，你不去学习理解它，如何加以改进并自创？如果没有人教你，你怎么能学会降龙十八掌？代码实现/** * 中缀表达式转后缀表达式 */ public class InfixToSuffix { public static void main(String[] args) { InfixToSuffix infixToSuffix = new Infix…

数据结构与算法——栈（四）逆波兰计算器-后缀表达式
type: item
date: 2025-05-03T15:52:58+00:00
description: AI摘要 本文介绍了如何使用Java实现一个逆波兰计算器，即后缀表达式计算器。文章首先解释了逆波兰表达式的概念，并指出实现逆波兰计算器的难点在于将中缀表达式转换为后缀表达式。接着，文章提供了一个Java实现的逆波兰计算器示例代码，该代码使用JDK自带的Stack类来实现。代码首先将后缀表达式转换为List，然后遍历List，使用栈进行计算。最后，文章展示了几个测试用例及其输出结果。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 完成一个逆波兰计算器，需求如下：输入一个 逆波兰表达式，使用栈 Stack（JDK 自带），计算器结果支持 小括号 和 多位数主要这里是讲解数据结构，因此简化为只对整数计算关于前缀、中缀、后缀表达式可以去看我的这篇博文数据结构与算法——栈（三）有关栈的三种表达式 —— 前缀、中缀、后缀表达式注意咯：知道逆波兰表达式是什么后，相对来说，实现还是比较容易的，难点其实是在于中缀表达式如何转换为后缀表达式，因为这涉及到运算符的优先级问题。在前面我们实现的时候，其实就是这个运算符优先级问题很刺手。而前缀、后缀表达式里面表达式的优先级，在形成这个表达式时就已经确定了。关于中缀表达式转为后缀表达式的详细讲解请看博客 数据结构与算法——栈（四）逆波兰计算器-后缀表达式。这里为什么使用 JDK 自带的Stack呢，其实在实现中缀表达式的计算器时，博客 数据结构与算法——栈（二）【使用栈来实现综合计算器-中缀表达式】 中是把计算器相关运算和方法都放在栈类中的，这只是为了方便操作数据，最终目的还是为了能让我们理解栈这个数据结构，所以实际上，只是利用了栈的数据结构，并非是什么都需要写在栈中的。实现思路：从前面后缀表达式求值过程来看，由于没有了优先级问题，全程只是在顺序获取元素，然后进行计算。先将后缀表达式转成一个 List（这里的后缀表达式中的数字和运算符用空格隔开，具体看代码，只是为了方便解析来添加集合元素）对这个 List 进行遍历，然后利用栈进行计算public class ReversePolishCalculator { public static void main(String[] args) { ReversePolishCalculator calculator = new ReversePolishCalculator(); // (3+4)*5-6 => 对应的后缀表达式 `3 4 + 5 * 6 -` 用空格作为分隔符 String postfixExpression = "3 4 + 5 * 6 -"; System.out.println("(3+4)*5-6 = " + calculator.cal(postfixExpression)); // (30+4)*5-6 => 对应的后缀表达式 `30 4 + 5 * 6 -` postfixExpression = "30 4 + 5 * 6 -"; System.out.println("(30+4)*5-6 = " + calculator.cal(postfixExpression)); // 4*5-8+60+8/2 => 对应的后缀表达式 `4 5 * 8 - 60 + 8 2 / +` postfixExpression = "4 5 * 8 - 60 + 8 2 / +"; System.out.println("4*5-8+60+8/2 = " + calculator.cal(postfixExpression)); // (3+4)-(3-4)*10，对应后缀表达式为：3 4 + 10 3 4 - * - postfixExpression = "3 4 + 10 3 4 - * -"; System.out.println("(3+4)-(3-4)*10 = " + calculator.cal(postfixExpression)); } /** * 计算一个后缀表达式的值 * * @param postfixExpression * @return */ public int cal(String postfixExpression) { return start(convert(postfixExpression)); } /** * 将后缀表达式转换成 list * @param postfixExpression * @return */ private List<String> convert(String postfixExpression) { //表达式中的每个元素都用空格隔开，是为了方便；这里重点不在于怎么去解析出每一个元素了 return Arrays.asList(postfixExp…