AI摘要 恋风画廊是一个提供高质量、无水印、风格多样壁纸资源的网站，支持手机和电脑壁纸，具有高清无水印、持续更新、多设备适配和极简设计等特点。网站鼓励用户分享和反馈，以提供更好的壁纸体验。 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结 💡 你是否正在寻找一个高质量、无水印、风格多样的壁纸资源站？欢迎来到我们倾力打造的壁纸平台 —— 恋风画廊！🌈 关于恋风画廊恋风画廊 是一个专注于分享高质量高清壁纸的网站，我们希望为用户带来：视觉上的美感享受操作上的极简体验更新上的持续丰富无论你是手机党、桌面党，还是壁纸收藏控，都能在这里找到灵感与满足。🔥 我们的特色✅ 高清无水印所有壁纸均为高清资源，拒绝水印干扰，美感不打折。✅ 持续更新定期会有新内容上线，涵盖多个风格与场景，保持新鲜。✅ 多设备适配支持手机与电脑壁纸，涵盖多种主流分辨率，一键下载即用。✅ 极简设计，纯净体验无注册限制，访问即看，下载即用。❤️ 给用户的一封信我们始终相信，一张好的壁纸，不只是装点桌面，更能点亮生活的灵感。如果你喜欢恋风画廊，欢迎将我们分享给朋友、收藏网址，参与共建与反馈！📬 有任何建议或合作意向，欢迎联系：[love@oini.de]
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, CURLOPT_SSL_VERIFYHOST, false); curl_setopt($ch, CURLOPT_USERAGENT, 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/89.0.4389.114 Safari/537.36'); curl_setopt($ch, CURLOPT_ENCODING, 'gzip,deflate'); $response = curl_exec($ch); $errno = curl_errno($ch); curl_close($ch); if($response && !$errno) { // 太平洋的接口返回的是GB2312编码，需要转换 $response = mb_convert_encoding($response, 'UTF-8', 'GBK'); $data = json_decode($response, true); if($data && isset($data['pro']) && isset($data['city'])) { $region = ''; if(!empty($data['pro'])) { $region .= $data['pro']; } if(!empty($data['city']) && $data['city'] != $data['pro']) { $region .= ' ' . $data['city']; } // 根据IP段判断运营商 $carrier = judgeCarrier($ip); if($carrier) { $region .= ' ' . $carrier; } $location = $region ? $region : '未知区域'; } } // 方法2：使用IpInfo API（国外IP支持较好） if(empty($location)) { $url = "https://ipinfo.io/{$ip}/json"; $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, CURLOPT_SSL_VERIFYHOST, false); curl_setopt($ch, CURLOPT_USERAGENT, 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/89.0.4389.114 Safari/537.36'); $response = curl_exec($ch); curl_close($ch); if($response) { $data = json_decode($response, true); if($data && isset($data['region']) && isset($data['city'])) { $region = ''; if(!empty($data['country'])) { $region .= getCountryName($data['country']); } if(!empty($data['region'])) { $region .= ' ' . $data['region']; } if(!empty($data['city'])) { $region .= ' ' . $data['city']; } if(!empty($data['org'])) { $region .= ' ' . preg_replace('/^AS\d+\s+/', '', $data['org']); } else { // 补充运营商信息 $carrier = judgeCarrier($ip); if($carrier) { $region .= ' ' . $carrier; } } $location = $region ? $region : '未知区域'; } } } // 方法3：使用IPIP.net的免费接口（国内移动网络支持较好） if(empty($location)) { $url = "https://freeapi.ipip.net/{$ip}"; $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, CURLOPT_SSL_VERIFYHOST, false); curl_setopt($ch, CURLOPT_USERAGENT, 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/89.0.4389.114 Safari/537.36'); $response = curl_exec($ch); curl_close($ch); if($response && $response != '{}') { $data = json_decode($response, true); if(is_array($data) && count($data) >= 4) { // IPIP.net返回格式：["中国","福建","厦门","","移动"] $region = ''; if(!empty($data[1])) { $region .= $data[1]; // 省份 } if(!empty($data[2]) && $data[2] != $data[1]) { $region .= ' ' . $data[2]; // 城市 } if(!empty($data[4])) { $region .= ' ' . $data[4]; // 运营商 } else { // 补充运营商信息 $carrier = judgeCarrier($ip); if($carrier) { $region .= ' ' . $carrier; } } $location = $region ? $region : '未知区域'; } } } // 方法4：使用淘宝IP库（作为备用） if(empty($location)) { $url = "https://ip.taobao.com/outGetIpInfo?ip=".$ip."&accessKey=alibaba-inc"; $opts = array( 'http' => array( 'method' => "GET", 'timeout' => 3, ) ); $context = stream_context_create($opts); $response = @file_get_contents($url, false, $context); if($response !== false) { $data = json_decode($response, true); if(isset($data['data']) && $data['data']) { $result = $data['data']; $region = ''; if(!empty($result['region'])) { $region .= $result['region']; } if(!empty($result['city']) && $result['city'] != $result['region']) { $region .= ' ' . $result['city']; } if(!empty($result['isp'])) { $region .= ' ' . $result['isp']; } else { // 补充运营商信息 $carrier = judgeCarrier($ip); if($carrier) { $region .= ' ' . $carrier; } } $location = $region ? $region : '未知区域'; } } } // 方法5：极速数据网络IP库（移动网络特别友好） if(empty($location)) { $url = "http://ip.jisuapi.com/api/ip/geo?ip={$ip}"; $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, CURLOPT_SSL_VERIFYHOST, false); $response = curl_exec($ch); curl_close($ch); if($response) { $data = json_decode($response, true); if(isset($data['result']) && $data['result']) { $result = $data['result']; $region = ''; if(!empty($result['province'])) { $region .= $result['province']; } if(!empty($result['city']) && $result['city'] != $result['province']) { $region .= ' ' . $result['city']; } if(!empty($result['isp'])) { $region .= ' ' . $result['isp']; } else { // 补充运营商信息 $carrier = judgeCarrier($ip); if($carrier) { $region .= ' ' . $carrier; } } $location = $region ? $region : '未知区域'; } } } // 方法6：仅使用IP段进行精准匹配（最后保障） if(empty($location)) { // 根据IP段匹配位置信息 $ipLocation = getIpLocation($ip); if($ipLocation) { $location = $ipLocation; } else { // 至少返回运营商信息 $carrier = judgeCarrier($ip); if($carrier) { $location = $carrier; } else { $location = "公网IP"; } } } } // 返回IP信息 echo json_encode(['ip' => $ip, 'location' => $location]); exit; } /** * 根据IP地址判断归属运营商 * @param string $ip IP地址 * @return string 运营商名称 */ function judgeCarrier($ip) { // 特殊IP段映射 $special_ip_carriers = [ // 移动特殊段 '39.128.' => '中国移动', '39.129.' => '中国移动', '39.130.' => '中国移动', '39.131.' => '中国移动', '39.132.' => '中国移动', '39.133.' => '中国移动', '39.134.' => '中国移动', '39.135.' => '中国移动', '39.136.' => '中国移动', '39.137.' => '中国移动', '39.138.' => '中国移动', '39.139.' => '中国移动', '39.140.' => '中国移动', '39.141.' => '中国移动', '39.142.' => '中国移动', '39.143.' => '中国移动', '39.144.' => '中国移动', '39.145.' => '中国移动', '39.146.' => '中国移动', '39.147.' => '中国移动', '39.148.' => '中国移动', '39.149.' => '中国移动', '39.150.' => '中国移动', '39.151.' => '中国移动', '39.152.' => '中国移动', '39.153.' => '中国移动', '39.154.' => '中国移动', '39.155.' => '中国移动', '39.156.' => '中国移动', '39.157.' => '中国移动', '39.158.' => '中国移动', '39.159.' => '中国移动', '39.176.' => '中国移动', '40.128.' => '中国移动', '40.129.' => '中国移动', '40.130.' => '中国移动', '41.128.' => '中国移动', '42.128.' => '中国移动', '43.128.' => '中国移动', // 联通特殊段 '44.128.' => '中国联通', '45.128.' => '中国联通', '46.128.' => '中国联通', // 电信特殊段 '48.128.' => '中国电信', '49.128.' => '中国电信', '50.128.' => '中国电信', '51.128.' => '中国电信', ]; // 检查特殊IP段映射 foreach ($special_ip_carriers as $prefix => $carrier) { if (strpos($ip, $prefix) === 0) { return $carrier; } } // 移动 $china_mobile = [ '39', '40', '41', '42', '43', // 新的移动段 '47.0', '47.1', '47.2', '47.3', // 兼容部分联通和移动混用 '178.', '180.', '182.', '183.', '184.', '157.', '158.', '159.', '165.', '172.', '120.204.', '120.205.', '120.206.', '120.207.', '120.208.', '120.209.', '120.210.', '120.211.', '120.212.', '120.213.', '120.214.', '120.215.', '221.130.', '221.131.', '221.132.', '221.133.', '221.134.', '221.135.', '221.136.', '221.137.', '221.138.', '221.139.', '211.103.', '211.137.', ]; // 联通 $china_unicom = [ '44', '45', '46', // 新的联通段 '47.4', '47.5', '47.6', '47.7', '47.8', '47.9', // 兼容部分联通和移动混用 '130.', '131.', '132.', '155.', '156.', '186.', '145.', '146.', '166.', '175.', '171.', '175.', '176.', '185.', '186.', '166.', '120.64.', '120.65.', '120.66.', '120.67.', '120.68.', '120.69.', '120.70.', '120.71.', '120.72.', '120.73.', '120.74.', '120.75.', '120.76.', '120.77.', '120.78.', '120.79.', '120.80.', '120.81.', '121.76.', '121.77.', '121.78.', '121.79.', '121.80.', '121.81.', '218.100.', '218.104.', '218.108.', '211.90.', '211.91.', '211.92.', '211.93.', '211.94.', '211.95.', '211.96.', '211.97.', '211.98.', '211.99.', '211.100.', '211.101.', '211.102.', ]; // 电信 $china_telecom = [ '48', '49', '50', '51', // 新的电信段 '133.', '153.', '173.', '177.', '180.', '181.', '189.', '199.', '120.128.', '120.129.', '120.130.', '120.131.', '120.132.', '120.133.', '120.134.', '120.135.', '120.136.', '120.137.', '120.138.', '120.139.', '120.140.', '120.141.', '120.142.', '120.143.', '120.144.', '120.145.', '113.64.', '113.65.', '113.66.', '113.67.', '113.68.', '113.69.', '113.70.', '113.71.', '113.72.', '113.73.', '113.74.', '113.75.', '125.64.', '125.65.', '125.66.', '125.67.', '125.68.', '125.69.', '125.70.', '125.71.', '125.72.', '125.73.', '125.74.', '125.75.', '210.5.', '210.12.', '210.14.', '210.21.', '210.32.', '210.51.', '210.52.', '210.77.', '210.192.', ]; // 铁通/广电/其他 $china_other = [ '36', '37', '38', // 其他杂段 '1700', '1705', '1709', // 虚拟运营商 ]; // 特定省份IP段 $province_ip_map = [ // 河南移动IP段范围 '39.144.25' => '河南 南阳 中国移动', '39.144.26' => '河南 南阳 中国移动', '39.144.27' => '河南 南阳 中国移动', // 福建电信IP段范围 '120.32.2' => '福建 厦门 中国电信', '120.32.3' => '福建 厦门 中国电信', '120.32.4' => '福建 厦门 中国电信', ]; // 检查特定省份IP段映射 foreach ($province_ip_map as $prefix => $location) { if (strpos($ip, $prefix) === 0) { return $location; } } foreach ($china_mobile as $prefix) { if (strpos($ip, $prefix) === 0) { return '中国移动'; } } foreach ($china_unicom as $prefix) { if (strpos($ip, $prefix) === 0) { return '中国联通'; } } foreach ($china_telecom as $prefix) { if (strpos($ip, $prefix) === 0) { return '中国电信'; } } foreach ($china_other as $prefix) { if (strpos($ip, $prefix) === 0) { return '其他运营商'; } } return ''; } /** * 根据IP前缀识别地理位置 * @param string $ip IP地址 * @return string 地理位置 */ function getIpLocation($ip) { // 特定地区IP段映射表 $ip_location_map = [ // 河南移动 '39.144.2' => '河南 中国移动', '39.144.25' => '河南 南阳 中国移动', '39.144.26' => '河南 南阳 中国移动', // 福建电信 '120.32.2' => '福建 厦门 中国电信', '120.32.3' => '福建 厦门 中国电信', // 北京联通 '111.200.' => '北京 中国联通', '111.201.' => '北京 中国联通', // 上海电信 '180.166.' => '上海 中国电信', '180.167.' => '上海 中国电信', // 广东移动 '120.231.' => '广东 中国移动', '120.232.' => '广东 中国移动', // 浙江电信 '115.192.' => '浙江 杭州 中国电信', '115.193.' => '浙江 杭州 中国电信', ]; // 逐段检查，从最长前缀到最短 $segments = explode('.', $ip); // 检查前三段 (如 192.168.1) if(count($segments) >= 3) { $prefix3 = $segments[0].'.'.$segments[1].'.'.$segments[2]; if(isset($ip_location_map[$prefix3])) { return $ip_location_map[$prefix3]; } } // 检查前两段 (如 192.168) if(count($segments) >= 2) { $prefix2 = $segments[0].'.'.$segments[1]; if(isset($ip_location_map[$prefix2])) { return $ip_location_map[$prefix2]; } } // 检查第一段 (如 192) if(count($segments) >= 1) { $prefix1 = $segments[0]; if(isset($ip_location_map[$prefix1])) { return $ip_location_map[$prefix1]; } } return ''; } /** * 获取国家名称（将ISO代码转为中文名称） * @param string $code 国家代码 * @return string 国家名称 */ function getCountryName($code) { $countries = [ 'CN' => '中国', 'US' => '美国', 'JP' => '日本', 'KR' => '韩国', 'GB' => '英国', 'DE' => '德国', 'FR' => '法国', 'RU' => '俄罗斯', 'CA' => '加拿大', 'AU' => '澳大利亚', 'HK' => '香港', 'TW' => '台湾', ]; return isset($countries[$code]) ? $countries[$code] : $code; } // 定义要输出的内容 $serverInfo = array( 'serverTime' => date('Y-m-d H:i:s', $unixTimestamp), 'serverUptime' => array( 'days' => $serverUptime['days'], 'hours' => $serverUptime['hours'], 'mins' => $serverUptime['mins'], 'secs' => $serverUptime['secs'] ), 'serverUtcTime' => date('Y/m/d H:i:s', $unixTimestamp), 'diskUsage' => array( 'value' => disk_total_space(__FILE__) - disk_free_space(__FILE__), 'max' => disk_total_space(__FILE__) ) ); $serverStatus = array( 'sysLoad' => array($serverLoad['1m'], $serverLoad['5m'], $serverLoad['15m']), 'cpuUsage' => array( 'user' => $cpuUsage['user'], 'nice' => $cpuUsage['nice'], 'sys' => $cpuUsage['sys'], 'idle' => $cpuUsage['idle'], 'cores' => $cpuUsage['cores'] ), 'memRealUsage' => array( 'value' => $memoryInfo['mRealUsed'], 'max' => $memoryInfo['mTotal'] ), 'memBuffers' => array( 'value' => $memoryInfo['mBuffers'], 'max' => $memoryInfo['mTotal'] ), 'memCached' => array( 'value' => $memoryInfo['mCached'], 'max' => $memoryInfo['mTotal'] ), 'swapUsage' => array( 'value' => $memoryInfo['swapUsed'], 'max' => $memoryInfo['swapTotal'] ), 'swapCached' => array( 'value' => $memoryInfo['swapCached'], 'max' => $memoryInfo['swapTotal'] ) ); $networkStats = array( 'networks' => GetNetwork() ); // 将以上内容合并为一个数组 $output = array( 'serverInfo' => $serverInfo, 'serverStatus' => $serverStatus, 'networkStats' => $networkStats ); // 将数组转换为JSON字符串并输出 echo json_encode($output); /** * 获取系统运行时长 * * @return array */ function getUpTime() { $uptime = (float) @file_get_contents("/proc/uptime"); $days = floor($uptime / 86400); $hours = floor(($uptime % 86400) / 3600); $minutes = floor((($uptime % 86400) % 3600) / 60); $seconds = ($uptime % 3600) % 60; //$time = $days.":".$hours.":".$minutes.":".$seconds; return array( 'days' => $days, 'hours' => $hours, 'mins' => $minutes, 'secs' => $seconds ); } /** * 获取系统负载 * * @return array|false|string[] */ function GetLoad() { if (false === ($str = file_get_contents("/proc/loadavg"))) return []; $loads = explode(' ', $str); if ($loads) { return [ '1m' => $loads[0], '5m' => $loads[1], '15m' => $loads[2], ]; } return []; } function GetCPUInfo() { $load = sys_getloadavg(); $user = $load[0]; $nice = $load[1]; $sys = $load[2]; $idle = 100 - ($user + $nice + $sys); // 获取CPU核心数 - 多种方法尝试 $cores = 1; // 默认值 // 方法1：通过/proc/cpuinfo if (file_exists('/proc/cpuinfo')) { $cpuInfo = file_get_contents('/proc/cpuinfo'); $cores = substr_count($cpuInfo, 'processor'); } // 方法2：通过sys_getloadavg if ($cores == 0) { $load = sys_getloadavg(); $cores = max(1, ceil($load[0])); // 至少1个核心 } // 方法3：通过PHP函数 if ($cores == 0 && function_exists('shell_exec')) { $cores = (int)shell_exec('nproc'); } // 确保至少返回1个核心 $cores = max(1, $cores); return [ 'user' => $user, 'nice' => $nice, 'sys' => $sys, 'idle' => $idle, 'cores' => $cores ]; } /** * 内存信息 * * @param bool $bFormat 格式化 * * @return array */ function GetMem(bool $bFormat = false) { if (false === ($str = file_get_contents("/proc/meminfo"))) return []; preg_match_all("/MemTotal\s{0,}\:+\s{0,}([\d\.]+).+?MemFree\s{0,}\:+\s{0,}([\d\.]+).+?Cached\s{0,}\:+\s{0,}([\d\.]+).+?SwapTotal\s{0,}\:+\s{0,}([\d\.]+).+?SwapFree\s{0,}\:+\s{0,}([\d\.]+)/s", $str, $mems); preg_match_all("/Buffers\s{0,}\:+\s{0,}([\d\.]+)/s", $str, $buffers); $mtotal = $mems[1][0] * 1024; $mfree = $mems[2][0] * 1024; $mbuffers = $buffers[1][0] * 1024; $mcached = $mems[3][0] * 1024; $stotal = $mems[4][0] * 1024; $sfree = $mems[5][0] * 1024; $mused = $mtotal - $mfree; $sused = $stotal - $sfree; $mrealused = $mtotal - $mfree - $mcached - $mbuffers; //真实内存使用 $rtn['mTotal'] = !$bFormat ? $mtotal : $this->size_format($mtotal, 1); $rtn['mFree'] = !$bFormat ? $mfree : $this->size_format($mfree, 1); $rtn['mBuffers'] = !$bFormat ? $mbuffers : $this->size_format($mbuffers, 1); $rtn['mCached'] = !$bFormat ? $mcached : $this->size_format($mcached, 1); $rtn['mUsed'] = !$bFormat ? ($mtotal - $mfree) : $this->size_format($mtotal - $mfree, 1); $rtn['mPercent'] = (floatval($mtotal) != 0) ? round($mused / $mtotal * 100, 1) : 0; $rtn['mRealUsed'] = !$bFormat ? $mrealused : $this->size_format($mrealused, 1); $rtn['mRealFree'] = !$bFormat ? ($mtotal - $mrealused) : $this->size_format($mtotal - $mrealused, 1);//真实空闲 $rtn['mRealPercent'] = (floatval($mtotal) != 0) ? round($mrealused / $mtotal * 100, 1) : 0; //真实内存使用率 $rtn['mCachedPercent'] = (floatval($mcached) != 0) ? round($mcached / $mtotal * 100, 1) : 0; //Cached内存使用率 $rtn['swapTotal'] = !$bFormat ? $stotal : $this->size_format($stotal, 1); $rtn['swapFree'] = !$bFormat ? $sfree : $this->size_format($sfree, 1); $rtn['swapUsed'] = !$bFormat ? $sused : $this->size_format($sused, 1); $rtn['swapPercent'] = (floatval($stotal) != 0) ? round($sused / $stotal * 100, 1) : 0; $rtn['swapCached'] = $mbuffers; return $rtn; } /** * 获取网络数据 * * @param bool $bFormat * * @return array */ function GetNetwork(bool $bFormat = false) { $rtn = []; $netstat = file_get_contents('/proc/net/dev'); if (false === $netstat) { return []; } $bufe = preg_split("/\n/", $netstat, -1, PREG_SPLIT_NO_EMPTY); foreach ($bufe as $buf) { if (preg_match('/:/', $buf)) { list($dev_name, $stats_list) = preg_split('/:/', $buf, 2); $dev_name = trim($dev_name); $stats = preg_split('/\s+/', trim($stats_list)); $rtn[$dev_name]['name'] = $dev_name; $rtn[$dev_name]['rx'] = !$bFormat ? $stats[0] : $this->netSize($stats[0]); $rtn[$dev_name]['in_packets'] = $stats[1]; $rtn[$dev_name]['in_errors'] = $stats[2]; $rtn[$dev_name]['in_drop'] = $stats[3]; $rtn[$dev_name]['tx'] = !$bFormat ? $stats[8] : $this->netSize($stats[8]); $rtn[$dev_name]['out_packets'] = $stats[9]; $rtn[$dev_name]['out_errors'] = $stats[10]; $rtn[$dev_name]['out_drop'] = $stats[11]; } } return $rtn; } [/collapse]
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}} 此内容根据文章生成，不代表个人观点，仅用于文章内容的解释与总结
数据结构与算法——排序算法-插入排序
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 = 119，insertIndex = 1 && currentInsertValue < arr[insertIndex] ) { arr[insertIndex + 1] = arr[insertIndex]; // 向后移动一位 insertIndex--; // 并将下一次要比较的有序列表的下标往前一位 } // 当退出循环后：这一轮，则是当前数大于有序表中的最后一个，不用换位置 // 那么 1 + 1 = 2，下标和当前的数是相同的，就算这里替换了，数组还是保持不变的 // 这里可以判断下是否相同，不相同再赋值，也是可以的，当作优化 arr[insertIndex + 1] = currentInsertValue; System.out.println("第 2 轮排序后：" + Arrays.toString(arr)); // 第 3 轮： // 有序表：34, 101, 119 // 无序表：1 currentInsertValue = arr[3]; // 当前要找位置插入的数：1 insertIndex = 3 - 1; // 当前的上一个开始 while (insertIndex >= 0 // 保证插入数组不越界 // 当前与有序列表中的数据进行对比 // 如果小于：则说明有序表中的该值需要向后移动 // 例如：34, 101, 119, 1 , 1 < 119, 移动后：34, 101, 119, 119 // currentInsertValue = 1，insertIndex = 2 // 然后继续下一个比较： 34, 101, 119, 119， 1 < 101 , 移动后：34, 101, 101, 119 // currentInsertValue = 1，insertIndex = 1 // 然后继续下一个比较： 34, 101, 101, 119， 1 < 34 , 移动后：34, 34, 101, 119 // currentInsertValue = 1，insertIndex = -1 && currentInsertValue < arr[insertIndex] ) { arr[insertIndex + 1] = arr[insertIndex]; // 向后移动一位 insertIndex--;// 并将下一次要比较的有序列表的下标往前一位 } // 当退出循环后：这一轮，则是 insertIndex = -1，退出循环，把当前的数插入到有序表的开头 arr[insertIndex + 1] = currentInsertValue; System.out.println("第 3 轮排序后：" + Arrays.toString(arr)); }测试输出原始数组：[101, 34, 119, 1] 第 1 轮排序后：[34, 101, 119, 1] 第 2 轮排序后：[34, 101, 119, 1] 第 3 轮排序后：[1, 34, 101, 119]从上述推导过程，我们发现了规律：循环体和赋值都是一样的不同的是当前待插入的数，和要比较的有序表下标那么可以改写成如下方式： @Test public void processDemo2() { int arr[] = {101, 34, 119, 1}; System.out.println("原始数组：" + Arrays.toString(arr)); processSelectSort2(arr); } private void processSelectSort2(int[] arr) { for (int i = 1; i < arr.length; i++) { // 只是将这两句代码（代表当前要插入的下标）用外循环的变量来代替了 int currentInsertValue = arr[i]; int insertIndex = i - 1; while (insertIndex >= 0 && currentInsertValue < arr[insertIndex] ) { arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } arr[insertIndex + 1] = currentInsertValue; System.out.println("第 " + i + " 轮排序后：" + Arrays.toString(arr)); } }大量数据耗时测试排序随机生成的 8 万个数据 /** * 大量数据排序时间测试 */ @Test public void bulkDataSort() { int max = 80_000; int[] arr = new int[max]; for (int i = 0; i < max; i++) { arr[i] = (int) (Math.random() * 80_000); } Instant startTime = Instant.now(); selectSort(arr); // System.out.println(Arrays.toString(arr)); Instant endTime = Instant.now(); System.out.println("共耗时：" + Duration.between(startTime, endTime).toMillis() + " 毫秒"); }多次测试输出共耗时：825 毫秒 共耗时：976 毫秒 共耗时：818 毫秒平均耗时在 900 毫秒左右时间复杂度在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为
数据结构与算法——排序算法-选择排序
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 个数开始比起 for (int j = 0 + 3; j < arr.length; j++) { // 挨个与最小值对比，如果小于，则进行交换 if (min > arr[j]) { // 如果后面的值比当前的 min 小，则重置min为这个数 min = arr[j]; minIndex = j; } } // 第 3 轮结束后，得到了最小值 // 将这个最小值与 arr[2] 交换 arr[minIndex] = arr[2]; arr[2] = min; System.out.println("第 3 轮排序后：" + Arrays.toString(arr)); }测试输出原始数组：[101, 34, 119, 1] 第 1 轮排序后：[1, 34, 119, 101] 第 2 轮排序后：[1, 34, 119, 101] 第 3 轮排序后：[1, 34, 101, 119]从上述的演变过程来看，发现了规律：循环体都是相同的，只是每一轮排序所假定的最小值的下标在递增。因此可以改写成如下方式 @Test public void processDemo2() { int arr[] = {101, 34, 119, 1}; System.out.println("原始数组：" + Arrays.toString(arr)); processSelectSort2(arr); } public void processSelectSort2(int[] arr) { // 把之前假定当前最小值的地方，使用变量 i 代替了 // 由于需要 arr.length -1 轮，所以使用外层一个循环，就完美的解决了这个需求 for (int i = 0; i < arr.length - 1; i++) { int min = arr[i]; // 先假定第一个数为最小值 int minIndex = i; for (int j = i + 1; j < arr.length; j++) { // 挨个与最小值对比，如果小于，则进行交换 if (min > arr[j]) { // 如果后面的值比当前的 min 小，则重置min为这个数 min = arr[j]; minIndex = j; } } // 第 i 轮结束后，得到了最小值 // 将这个最小值与 arr[i] 交换 arr[minIndex] = arr[i]; arr[i] = min; System.out.println("第 " + (i + 1) + " 轮排序后：" + Arrays.toString(arr)); } }测试输出原始数组：[101, 34, 119, 1] 第 1 轮排序后：[1, 34, 119, 101] 第 2 轮排序后：[1, 34, 119, 101] 第 3 轮排序后：[1, 34, 101, 119]由此可以得到，选择排序的时间复杂度是 o(n²)，因为是一个嵌套 for 循环结果是一样的，但是你会发现，在第 1 轮和第 2 轮的序列是一样的，但是代码中目前也进行了交换，可以优化掉这一个点优化 public void processSelectSort2(int[] arr) { // 把之前假定当前最小值的地方，使用变量 i 代替了 // 由于需要 arr.length -1 轮，所以使用外层一个循环，就完美的解决了这个需求 for (int i = 0; i < arr.length - 1; i++) { int min = arr[i]; // 先假定第一个数为最小值 int minIndex = i; for (int j = i + 1; j < arr.length; j++) { // 挨个与最小值对比，如果小于，则进行交换 if (min > arr[j]) { // 如果后面的值比当前的 min 小，则重置min为这个数 min = arr[j]; minIndex = j; } } // 第 i 轮结束后，得到了最小值 // 将这个最小值与 arr[i] 交换 //但如果minIndex没有改变，也就是最小值未发生改变，则不需要执行后面的交换了 if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; } System.out.println("第 " + (i + 1) + " 轮排序后：" + Arrays.toString(arr)); } }测试输出原始数组：[101, 34, 119, 1] 第 1 轮排序后：[1, 34, 119, 101] 第 3 轮排序后：[1, 34, 101, 119]则可以看到，第二轮就跳过了交换这一个步骤，从而优化了这个算法所要花费的时间。算法函数封装@Test public void selectSortTest() { int arr[] = {101, 34, 119, 1}; System.out.println("升序"); System.out.println("原始数组：" + Arrays.toString(arr)); selectSort(arr, true); System.out.println("排序后：" + Arrays.toString(arr)); System.out.println("降序"); System.out.println("原始数组：" + Arrays.toString(arr)); selectSort(arr, false); System.out.println("排序后：" + Arrays.toString(arr)); } /** * 选择排序算法封装 * * @param arr 要排序的数组 * @param asc 升序排列，否则降序 */ public void selectSort(int[] arr, boolean asc) { // 把之前假定当前最小值的地方，使用变量 i 代替了 // 由于需要 arr.length -1 轮，所以使用外层一个循环，就完美的解决了这个需求 for (int i = 0; i < arr.length - 1; i++) { int current = arr[i]; // 先假定第一个数为最小值 int currentIndex = i; for (int j = i + 1; j < arr.length; j++) { // 挨个与最小值对比，如果小于，则进行交换 if (asc) { if (current > arr[j]) { // 如果后面的值比当前的 min 小，则重置min为这个数 current = arr[j]; currentIndex = j; } } else { if (current < arr[j]) { // 如果后面的值比当前的 min 大，则重置为这个数 current = arr[j]; currentIndex = j; } } } // 第 i 轮结束后，得到了最小/大值 // 将这个值与 arr[i] 交换 //但如果minIndex没有改变，也就是最小值未发生改变，则不需要执行后面的交换了 if (currentIndex == i) { arr[currentIndex] = arr[i]; arr[i] = current; } } }测试输出升序 原始数组：[101, 34, 119, 1] 排序后：[1, 34, 101, 119] 降序 原始数组：[1, 34, 101, 119] 排序后：[119, 101, 34, 1]大量数据耗时测试排序随机生成的 8 万个数据 @Test public void bulkDataSort() { int max = 80_000; int[] arr = new int[max]; for (int i = 0; i < max; i++) { arr[i] = (int) (Math.random() * 80_000); } Instant startTime = Instant.now(); selectSort(arr, true); // System.out.println(Arrays.toString(arr)); Instant endTime = Instant.now(); System.out.println("共耗时：" + Duration.between(startTime, endTime).toMillis() + " 毫秒"); }多次运行测试输出共耗时：2983 毫秒 共耗时：3022 毫秒冒泡排序和选择排序的时间复杂度虽然都是 o(n²)，但由于冒泡排序每一步有变化都要交换位置，导致了消耗了大量的时间，所以选择排序相对冒泡排序所花费的时间要更少。关于冒泡排序请看 数据结构与算法——排序算法-冒泡排序
数据结构与算法——排序算法-冒泡排序
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 趟排序过程来看，循环体都是一样的，只是每次循环的次数在减少，那么就可以如下简化@Test public void processDemo2() { int arr[] = {3, 9, -1, 10, -2}; // 总共排序：arr.length - 1 int temp = 0; // 临时变量，交换的时候使用 for (int j = 0; j < arr.length - 1; j++) { for (int i = 0; i < arr.length - 1 - j; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.out.println("第 " + (j + 1) + " 趟排序后的数组"); System.out.println(Arrays.toString(arr)); } }测试输出第 1 趟排序后的数组 [3, -1, 9, -2, 10] 第 2 趟排序后的数组 [-1, 3, -2, 9, 10] 第 3 趟排序后的数组 [-1, -2, 3, 9, 10] 第 4 趟排序后的数组 [-2, -1, 3, 9, 10]优化对于优化，减少排序次数 @Test public void processDemo3() { int arr[] = {3, 9, -1, 10, 20}; // 总共排序：arr.length - 1 int temp = 0; // 临时变量，交换的时候使用 boolean change = false;// 标识变量，表示是否进行过交换 for (int j = 0; j < arr.length - 1; j++) { for (int i = 0; i < arr.length - 1 - j; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; change = true; } } if(!change){ // 如果有 1 轮下来，都没有进行排序，则可以提前退出 break; }else{ change = false; // 重置 change!!!, 进行下次判断 } System.out.println("第 " + (j + 1) + " 趟排序后的数组"); System.out.println(Arrays.toString(arr)); } }测试输出：第 1 趟排序后的数组 [3, -1, 9, 10, 20] 第 2 趟排序后的数组 [-1, 3, 9, 10, 20]这里更改了原始数组，因为优化的点，得看你这个数组原来的排序 和 元素组成，算是一种概率问题，并不是在任何情况下都可以被优化封装算法 /** * 把排序算法封装成一个方法，方便被复用 * * @param arr */ public static void bubbleSort(int[] arr) { // 总共排序：arr.length - 1 int temp = 0; // 临时变量，交换的时候使用 boolean change = false; for (int j = 0; j < arr.length - 1; j++) { for (int i = 0; i < arr.length - 1 - j; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; change = true; } } if(!change){ // 如果有 1 轮下来，都没有进行排序，则可以提前退出 break; }else{ change = false; // 重置 change!!!, 进行下次判断 } } }测试调用 /** * 测试封装后的算法 */ @Test public void bubbleSortTest() { int[] arr = {3, 9, -1, 10, 20}; System.out.println("排序前：" + Arrays.toString(arr)); bubbleSort(arr); System.out.println("排序后：" + Arrays.toString(arr)); } 测试输出排序前：[3, 9, -1, 10, 20] 排序后：[-1, 3, 9, 10, 20]大量数据耗时测试排序随机生成的 8 万个数据 /** * 大量数据排序时间测试 */ @Test public void bulkDataSort() { int max = 80000; int[] arr = new int[max]; for (int i = 0; i < max; i++) { arr[i] = (int) (Math.random() * 80000); } Instant startTime = Instant.now(); bubbleSort(arr); // System.out.println(Arrays.toString(arr)); Instant endTime = Instant.now(); System.out.println("共耗时：" + Duration.between(startTime, endTime).toMillis() + " 毫秒"); }测试输出运行几次，差不多在 13 秒左右 共耗时：14656 毫秒 共耗时：13853 毫秒
数据结构和算法——递归-八皇后问题（回溯算法）
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 列上，直到放置成功 } } /** * 按游戏规则要求，判定要放置的这一个皇后，和前面已经摆放的位置是否冲突 * * @param n 第 n 个皇后 * @return */ private boolean judge(int n) { for (int i = 0; i < n; i++) { if ( /* 如果他们的摆放位置一样，说明是在同一列 注：图是从下往上看 x ....... x ....... */ array[i] == array[n] /* 检测是否是同一斜列 array[下标] = 值 下标: 代表的是第几行 值：代表的是第几列 注：图是从下往上看 . x . . . . . . n = 1,value = 1 x . . . . . . . i = 0,value = 0 Math.abs(n - i) = 1 Math.abs(array[n] - array[i]) = 1 . . x . . . . . n = 1,value = 2 . x . . . . . . i = 0,value = 1 Math.abs(n - i) = 1 Math.abs(array[n] - array[i]) = 1 注：这里运用了角的斜率问题，如果斜率为1，则角就是45°，所以两点在一斜列上。 想不明白可以画图看看，如果两点在一斜列上的话，就会组成一个正方形。很巧妙 */ || Math.abs(n - i) == Math.abs(array[n] - array[i]) ) { return false; } } return true; } /** * 打印皇后的位置 */ private void print() { System.out.printf("第 %02d 个结果 ：", count); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } /** * 下面是对于判定是否是同行，同列、同一斜列的分步骤测试，比较好理解 */ @Test public void judgeTest() { //注：图是从下往上看 /* * . . . . . . . . * x . . . . . . . */ Queue8 queue8 = new Queue8(); queue8.array[0] = 0; //======== 放置第 1 个皇后 // 判断是否是同一列 /* * x . . . . . . . // 计划放到这里 * x . . . . . . . */ queue8.array[1] = 0; // 从第一列开始放置 System.out.println("同一列，是否通过：" + queue8.judge(1)); /* * . x . . . . . . // 计划放到这里 * x . . . . . . . */ queue8.array[1] = 1; // 第一列不行，放置到第 2 列上 System.out.println("同一斜列，是否通过：" + queue8.judge(1)); /* * . . x . . . . . // 计划放到这里 * x . . . . . . . */ queue8.array[1] = 2; // 第 2 列不行，放置到第 3 列上,这个肯定是可以的 System.out.println("同一列或同一斜列，是否通过：" + queue8.judge(1)); //======== 放置第 3 个皇后 /* * x . . . . . . . // 计划放到这里 * . . x . . . . . * x . . . . . . . */ queue8.array[2] = 0; // 与第一行的在同一列上了 System.out.println("同一列，是否通过：" + queue8.judge(2)); /* * . x . . . . . . // 计划放到这里 * . . x . . . . . * x . . . . . . . */ queue8.array[2] = 1; // 第一列不行，放置到第 2 列 // 这里与第 2 行的同一斜列了，也是不行的 System.out.println("同一斜列，是否通过：" + queue8.judge(2)); } }输出结果如下第 01 个结果 ：0 4 7 5 2 6 1 3 第 02 个结果 ：0 5 7 2 6 3 1 4 第 03 个结果 ：0 6 3 5 7 1 4 2 第 04 个结果 ：0 6 4 7 1 3 5 2 第 05 个结果 ：1 3 5 7 2 0 6 4 第 06 个结果 ：1 4 6 0 2 7 5 3 第 07 个结果 ：1 4 6 3 0 7 5 2 第 08 个结果 ：1 5 0 6 3 7 2 4 第 09 个结果 ：1 5 7 2 0 3 6 4 第 10 个结果 ：1 6 2 5 7 4 0 3 第 11 个结果 ：1 6 4 7 0 3 5 2 第 12 个结果 ：1 7 5 0 2 4 6 3 第 13 个结果 ：2 0 6 4 7 1 3 5 第 14 个结果 ：2 4 1 7 0 6 3 5 第 15 个结果 ：2 4 1 7 5 3 6 0 第 16 个结果 ：2 4 6 0 3 1 7 5 第 17 个结果 ：2 4 7 3 0 6 1 5 第 18 个结果 ：2 5 1 4 7 0 6 3 第 19 个结果 ：2 5 1 6 0 3 7 4 第 20 个结果 ：2 5 1 6 4 0 7 3 第 21 个结果 ：2 5 3 0 7 4 6 1 第 22 个结果 ：2 5 3 1 7 4 6 0 第 23 个结果 ：2 5 7 0 3 6 4 1 第 24 个结果 ：2 5 7 0 4 6 1 3 第 25 个结果 ：2 5 7 1 3 0 6 4 第 26 个结果 ：2 6 1 7 4 0 3 5 第 27 个结果 ：2 6 1 7 5 3 0 4 第 28 个结果 ：2 7 3 6 0 5 1 4 第 29 个结果 ：3 0 4 7 1 6 2 5 第 30 个结果 ：3 0 4 7 5 2 6 1 第 31 个结果 ：3 1 4 7 5 0 2 6 第 32 个结果 ：3 1 6 2 5 7 0 4 第 33 个结果 ：3 1 6 2 5 7 4 0 第 34 个结果 ：3 1 6 4 0 7 5 2 第 35 个结果 ：3 1 7 4 6 0 2 5 第 36 个结果 ：3 1 7 5 0 2 4 6 第 37 个结果 ：3 5 0 4 1 7 2 6 第 38 个结果 ：3 5 7 1 6 0 2 4 第 39 个结果 ：3 5 7 2 0 6 4 1 第 40 个结果 ：3 6 0 7 4 1 5 2 第 41 个结果 ：3 6 2 7 1 4 0 5 第 42 个结果 ：3 6 4 1 5 0 2 7 第 43 个结果 ：3 6 4 2 0 5 7 1 第 44 个结果 ：3 7 0 2 5 1 6 4 第 45 个结果 ：3 7 0 4 6 1 5 2 第 46 个结果 ：3 7 4 2 0 6 1 5 第 47 个结果 ：4 0 3 5 7 1 6 2 第 48 个结果 ：4 0 7 3 1 6 2 5 第 49 个结果 ：4 0 7 5 2 6 1 3 第 50 个结果 ：4 1 3 5 7 2 0 6 第 51 个结果 ：4 1 3 6 2 7 5 0 第 52 个结果 ：4 1 5 0 6 3 7 2 第 53 个结果 ：4 1 7 0 3 6 2 5 第 54 个结果 ：4 2 0 5 7 1 3 6 第 55 个结果 ：4 2 0 6 1 7 5 3 第 56 个结果 ：4 2 7 3 6 0 5 1 第 57 个结果 ：4 6 0 2 7 5 3 1 第 58 个结果 ：4 6 0 3 1 7 5 2 第 59 个结果 ：4 6 1 3 7 0 2 5 第 60 个结果 ：4 6 1 5 2 0 3 7 第 61 个结果 ：4 6 1 5 2 0 7 3 第 62 个结果 ：4 6 3 0 2 7 5 1 第 63 个结果 ：4 7 3 0 2 5 1 6 第 64 个结果 ：4 7 3 0 6 1 5 2 第 65 个结果 ：5 0 4 1 7 2 6 3 第 66 个结果 ：5 1 6 0 2 4 7 3 第 67 个结果 ：5 1 6 0 3 7 4 2 第 68 个结果 ：5 2 0 6 4 7 1 3 第 69 个结果 ：5 2 0 7 3 1 6 4 第 70 个结果 ：5 2 0 7 4 1 3 6 第 71 个结果 ：5 2 4 6 0 3 1 7 第 72 个结果 ：5 2 4 7 0 3 1 6 第 73 个结果 ：5 2 6 1 3 7 0 4 第 74 个结果 ：5 2 6 1 7 4 0 3 第 75 个结果 ：5 2 6 3 0 7 1 4 第 76 个结果 ：5 3 0 4 7 1 6 2 第 77 个结果 ：5 3 1 7 4 6 0 2 第 78 个结果 ：5 3 6 0 2 4 1 7 第 79 个结果 ：5 3 6 0 7 1 4 2 第 80 个结果 ：5 7 1 3 0 6 4 2 第 81 个结果 ：6 0 2 7 5 3 1 4 第 82 个结果 ：6 1 3 0 7 4 2 5 第 83 个结果 ：6 1 5 2 0 3 7 4 第 84 个结果 ：6 2 0 5 7 4 1 3 第 85 个结果 ：6 2 7 1 4 0 5 3 第 86 个结果 ：6 3 1 4 7 0 2 5 第 87 个结果 ：6 3 1 7 5 0 2 4 第 88 个结果 ：6 4 2 0 5 7 1 3 第 89 个结果 ：7 1 3 0 6 4 2 5 第 90 个结果 ：7 1 4 2 0 6 3 5 第 91 个结果 ：7 2 0 5 1 4 6 3 第 92 个结果 ：7 3 0 2 5 1 6 4 可以在百度找到 8皇后 这个游戏，随便选一两个数据测试正确性，如果你想全部测试我没意见，结果是对的，你开心就好。细节分析一定要理解它这个 回溯 机制，比如拿其中这两个来分析（依据上面代码）第 06 个结果 ：1 4 6 0 2 7 5 3 第 07 个结果 ：1 4 6 3 0 7 5 2 从第 1 行，到最后的第 8 行，这时 n+1 进入到第 9 行，发现已经放完 8 个皇后了，拿到一个完整的结果，就返回到第 8 行的那个check()方法中的check(n+1)哪里，因为第 8 行放置结果是 3 是一个正确解，那么回到这里来的时候，就会尝试剩下没有测试的列，比如第 4 列从结果来看，肯定不满足，就一直会尝试直到，第 8 行的 3 变成 7（从0开始计数），这个 check 方法尝试完了，都没有出一个结果，就自动退出这个方法回到了第 7 行的第 5 列这个结果上，又继续尝试，像第 2 步和第 3 步那样从结果上来看，直到回到了第 4 行上，将 0 变成了 3，才发现这个位置与之前的不冲突，然后往下，进入到第 5 个皇后的放置上，重复递归操作依次类推其实这里递归的原理就是穷举法一样的思想，挨个的尝试，直到把所有的可能都尝试完。就像手机密码忘了，你一个一个去尝试，暴力破解。*有一个 细节需要知道，这里的 不同行、不同列、不同斜列，不要求非连续的，也就是说，即使不是连续的斜列也算x . . . . . . . . . . . . . . . . . x . . . . . 这样不连续的斜列，也算是在一条斜线上。一定要明白这个规则，才能使用那个判定斜列的算法小结重点 1 ：判定是否在棋盘是符合规则：是否是同一列、同一行（同行实际上是不存在的，所以不用做判断）、同一斜列这里使用一维数组，来保存二维数组中的点的位置，使用如下的算法，来检验这个规则，这里设置的很巧妙 /* 如果他们的摆放位置一样，说明是在同一列 注：图是从下往上看 x ....... x ....... */ array[i] == array[n] /* 检测是否是同一斜列 array[下标] = 值 下标: 代表的是第几行 值：代表的是第几列 注：图是从下往上看 . x . . . . . . n = 1,value = 1 x . . . . . . . i = 0,value = 0 Math.abs(n - i) = 1 Math.abs(array[n] - array[i]) = 1 . . x . . . . . n = 1,value = 2 . x . . . . . . i = 0,value = 1 Math.abs(n - i) = 1 Math.abs(array[n] - array[i]) = 1 注：这里运用了角的斜率问题，如果斜率为1，则角就是45°，所以两点在一斜列上。 想不明白可以画图看看，如果两点在一斜列上的话，就会组成一个正方形。很巧妙 */ || Math.abs(n - i) == Math.abs(array[n] - array[i])重点 2：递归的回溯流程，一定要明白是怎么回溯的
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+1, j)) {//向下走 return true; } else if (setWay(map, i, j+1)) { //向右走 return true; } else if (setWay(map, i-1, j)) { //向上 return true; } else if (setWay(map, i, j-1)){ // 向左走 return true; } else { //说明该点是走不通，是死路 map[i][j] = 3; return false; } } else { // 如果map[i][j] != 0 , 可能是 1， 2， 3 return false; } } } //修改找路的策略，改成 上->右->下->左，体验不同找路策略走出来的路 public static boolean setWay2(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(setWay2(map, i-1, j)) {//向上走 return true; } else if (setWay2(map, i, j+1)) { //向右走 return true; } else if (setWay2(map, i+1, j)) { //向下 return true; } else if (setWay2(map, i, j-1)){ // 向左走 return true; } else { //说明该点是走不通，是死路 map[i][j] = 3; return false; } } else { // 如果map[i][j] != 0 , 可能是 1， 2， 3 return false; } } } }我们先来看这个测试用例 setWay(map, 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 小球走过，并标识过的 地图的情况 1 1 1 1 1 1 1 1 2 0 0 0 0 1 1 2 2 2 0 0 1 1 1 1 2 0 0 1 1 0 0 2 0 0 1 1 0 0 2 0 0 1 1 0 0 2 2 2 1 1 1 1 1 1 1 1这里看不出来有回溯的痕迹，其实根据我们的这个策略 下 -> 右 -> 上 -> 左，进入方法就打印 map 分布图，你就会发现，他去判断了墙壁的时候，回溯了一小步。但是还是不明显。下面看一个回溯明显的示例在设置一面墙map[1][2] = 1;map[2][2] = 1 把路都封死，可以看到下面的输出，一开始把原点标为2（走过了），往下走后把脚下的点标为2（走过了），后发现该点上下左右都走不了就把该点改标为3（死路），然后它又回到上一点，又发现上下左右走不了，又把该点改标为3（死路），最后终止程序。如果看一次看不懂，多琢磨几次。地图的情况 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 小球走过，并标识过的 地图的情况 1 1 1 1 1 1 1 1 3 1 0 0 0 1 1 3 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 体验一下不同找路策略，走出来的路地图的情况 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 小球走过，并标识过的 地图的情况 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 0 0 0 0 2 1 1 1 1 0 0 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 1 1 1 1 1 1 可以看到，不同的找路策略走出来的路也是不同的。到这里是不是觉得递归真的很奇妙，像是发现新大陆一样，算法就是这么的有趣，虽然在学的过程中会很痛苦，但痛并快乐着。
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，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕
数据结构与算法——栈（五）中缀表达式转后缀表达式
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 InfixToSuffix(); // 目标：1+((2+3)*4)-5 转为 1 2 3 + 4 * + 5 - // 1. 将中缀表达式转成 List，方便在后续操作中获取数据 String infixExpression = "1+((2+3)*4)-5"; List<String> infixList = infixToSuffix.toInfixExpressionList(infixExpression); System.out.println(infixList); // [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] // 2. 将中缀表达式转成后缀表达式 List<String> suffixList = infixToSuffix.parseSuffixExpreesionList(infixList); System.out.println(suffixList); // [1, 2, 3, +, 4, *, +, 5, -] } /** * 将中缀表达式解析成单个元素的 List， * * @param s * @return 1+((2+3)*4)-5 -> [1,+,(,(,2,+,3,),*,4,),5] */ //方法：将 中缀表达式转成对应的List // s="1+((2+3)×4)-5"; public static List<String> toInfixExpressionList(String s) { //定义一个List,存放中缀表达式 对应的内容 List<String> ls = new ArrayList<String>(); int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串 String str; // 对多位数的拼接 char c; // 每遍历到一个字符，就放入到c do { //如果c是一个非数字，我需要加入到ls if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) { ls.add("" + c); i++; //i需要后移 } else { //如果是一个数，需要考虑多位数 str = ""; //先将str 置成"" '0'[48]->'9'[57] while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) { str += c;//拼接 i++; } ls.add(str); } } while (i < s.length()); return ls;//返回 } /** * 中缀表达式 List 转为后缀表达式 List * * @param ls * @return */ //即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–] //方法：将得到的中缀表达式对应的List => 后缀表达式对应的List public static List<String> parseSuffixExpreesionList(List<String> ls) { //定义两个栈 Stack<String> s1 = new Stack<String>(); // 符号栈 //说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出 //因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2 //Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2 List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2 //遍历ls for (String item : ls) { //如果是一个数，加入s2 if (item.matches("\\d+")) { s2.add(item); } else if (item.equals("(")) { s1.push(item); } else if (item.equals(")")) { //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 while (!s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop();//!!! 将 ( 弹出 s1栈， 消除小括号 } else { //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较 //问题：我们缺少一个比较优先级高低的方法。 下面创建了priority类，用来比较优先级 //这里比较权限的时候，可能在比较过程中取到括号，但是问题不大，因为方法规定了，不符合运算符的默认优先级为0 while (s1.size() != 0 && priority.getValue(s1.peek()) >= priority.getValue(item)) { s2.add(s1.pop()); } //还需要将item压入栈 s1.push(item); } } //将s1中剩余的运算符依次弹出并加入s2 while (s1.size() != 0) { s2.add(s1.pop()); } return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List } } /** * 计算操作符号优先级，暂时只支持 + - * / * * @return 优先级越高，数值越大 */ //编写一个类 priority 可以返回一个运算符 对应的优先级 class priority { private static int ADD = 1;//加 private static int SUB = 1;//减 private static int MUL = 2;//乘 private static int DIV = 2;//除 //写一个静态方法，返回对应的优先级数字 public static int getValue(String operation) { int result = 0; switch (operation) { case "+": result = ADD; break; case "-": result = SUB; break; case "*": result = MUL; break; case "/": result = DIV; break; default: System.out.println("不存在该运算符" + operation); break; } return result; } }测试输出[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] 不存在该运算符( 不存在该运算符( [1, 2, 3, +, 4, *, +, 5, -] 可以看到，已经变成后缀表达式的顺序了。下面结合前面实现的逆波兰计算器整合中缀表达式转后缀表达式。完整版逆波兰计算器public class PolandNotation { public static void main(String[] args) { //完成将一个中缀表达式转成后缀表达式的功能 //说明 //1. 1+((2+3)×4)-5 => 转成 1 2 3 + 4 × + 5 – //2. 因为直接对str 进行操作，不方便，因此 先将 "1+((2+3)×4)-5" =》 中缀的表达式对应的List // 即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] //3. 将得到的中缀表达式对应的List => 后缀表达式对应的List // 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–] String expression = "1+((2+3)*4)-5";//注意表达式 List<String> infixExpressionList = toInfixExpressionList(expression); System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList); System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–] System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ? } //即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–] //方法：将得到的中缀表达式对应的List => 后缀表达式对应的List public static List<String> parseSuffixExpreesionList(List<String> ls) { //定义两个栈 Stack<String> s1 = new Stack<String>(); // 符号栈 //说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出 //因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2 //Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2 List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2 //遍历ls for (String item : ls) { //如果是一个数，加入s2 if (item.matches("\\d+")) { s2.add(item); } else if (item.equals("(")) { s1.push(item); } else if (item.equals(")")) { //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 while (!s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop();//!!! 将 ( 弹出 s1栈， 消除小括号 } else { //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较 //问题：我们缺少一个比较优先级高低的方法 while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) { s2.add(s1.pop()); } //还需要将item压入栈 s1.push(item); } } //将s1中剩余的运算符依次弹出并加入s2 while (s1.size() != 0) { s2.add(s1.pop()); } return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List } //方法：将 中缀表达式转成对应的List // s="1+((2+3)×4)-5"; public static List<String> toInfixExpressionList(String s) { //定义一个List,存放中缀表达式 对应的内容 List<String> ls = new ArrayList<String>(); int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串 String str; // 对多位数的拼接 char c; // 每遍历到一个字符，就放入到c do { //如果c是一个非数字，我需要加入到ls if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) { ls.add("" + c); i++; //i需要后移 } else { //如果是一个数，需要考虑多位数 str = ""; //先将str 置成"" '0'[48]->'9'[57] while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) { str += c;//拼接 i++; } ls.add(str); } } while (i < s.length()); return ls;//返回 } //完成对逆波兰表达式的运算 /* * 1)从左至右扫描，将3和4压入堆栈； 2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈； 3)将5入栈； 4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； 5)将6入栈； 6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果 */ public static int calculate(List<String> ls) { // 创建给栈, 只需要一个栈即可 Stack<String> stack = new Stack<String>(); // 遍历 ls for (String item : ls) { // 这里使用正则表达式来取出数 if (item.matches("\\d+")) { // 匹配的是多位数 // 入栈 stack.push(item); } else { // pop出两个数，并运算， 再入栈 int num2 = Integer.parseInt(stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; if (item.equals("+")) { res = num1 + num2; } else if (item.equals("-")) { res = num1 - num2; } else if (item.equals("*")) { res = num1 * num2; } else if (item.equals("/")) { res = num1 / num2; } else { throw new RuntimeException("运算符有误"); } //把res 入栈 stack.push("" + res); } } //最后留在stack中的数据是运算结果 return Integer.parseInt(stack.pop()); } } //编写一个类 Operation 可以返回一个运算符 对应的优先级 class Operation { private static int ADD = 1; private static int SUB = 1; private static int MUL = 2; private static int DIV = 2; //写一个方法，返回对应的优先级数字 public static int getValue(String operation) { int result = 0; switch (operation) { case "+": result = ADD; break; case "-": result = SUB; break; case "*": result = MUL; break; case "/": result = DIV; break; default: System.out.println("不存在该运算符" + operation); break; } return result; } }测试输出中缀表达式对应的List=[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] 不存在该运算符( 不存在该运算符( 后缀表达式对应的List[1, 2, 3, +, 4, *, +, 5, -] expression=16