第 11 页 - 咕咕鸽爱学习

登录

最新发布

2025-03-21
linux服务器 llinux服务器（以debian为例）预先准备域名购买与解析购买：Low-Cost Domain Names & Hosting from $0.99 | NameSilo 教程：【服务器、域名购买】Namesilo优惠码和域名解析教程（附带服务器购买推荐和注意事项） | 爱玩实验室 DNS解析：可能需等待几分钟生效买的域名的r2studying.top 这里的HOSTNAME相当于二级域名，如npm.r2studying.top 现改为CloudFlare来做DNS解析，不用namesilo，它有两种模式： Proxied（橙色云朵）：当你将某个 DNS 记录设置为 Proxied 时，Cloudflare 会作为反向代理服务器处理该域名的 HTTP/HTTPS 流量。这样做有几个效果：隐藏真实 IP：用户访问时看到的是 Cloudflare 的 Anycast IP，而不是你服务器的真实 IP，从而提高安全性。提供 CDN 加速：Cloudflare 会缓存静态资源，并通过全球节点加速内容传输，提升网站响应速度。附加安全防护：包括 DDoS 防护和 Web 应用防火墙等功能。 DNS Only（灰色云朵）：如果你设置为 DNS Only，Cloudflare 只负责 DNS 解析，不会对流量进行代理或处理。也就是说，用户访问时会直接获取并连接到你服务器的真实 IP。安全组设置登录云服务器的控制台设置入站规则入站规则（Inbound Rules）是指防火墙中用来控制外部流量进入服务器的规则。通过这些规则，你可以指定允许或拒绝哪些类型的网络流量（例如特定协议、端口号、IP地址等）进入你的服务器。类型协议端口源地址描述 IPv4 TCP : 22 0.0.0.0/0 允许外部访问安全组内实例的SSH(22)端口，用于远程登录Linux实例。 IPv4 TCP : 3389 0.0.0.0/0 允许外部访问安全组内实例的RDP(3389)端口，用于远程登录Windows实例。 IPv4 TCP : 80 0.0.0.0/0 允许外部访问安全组内实例的HTTP(80)端口，用于通过HTTP协议访问网站。 IPv4 TCP : 443 0.0.0.0/0 允许外部访问安全组内实例的HTTPS(443)端口，用于通过HTTPS协议访问网站。 IPv4 TCP : 20-21 0.0.0.0/0 允许通过FTP上传和下载文件。 IPv4 ICMP: 全部 0.0.0.0/0 允许外部使用ping命令验证安全组内实例的网络连通性。出站规则出站规则（Outbound Rules）则是指控制服务器向外部发送流量的规则。你可以通过出站规则来限制服务器发出的数据包，比如限制服务器访问某些外部服务或 IP 地址。凡是服务正常启动但是浏览器上无法访问的，都首先想想防火墙端口是否打开！！！常用的命令 cat 用于查看文本文件的内容 head 查看前n行 head -n 100 文件名 touch 新建文本文件，如touch /home/hello.py 将在home 文件夹下新建hello.py ls 列出所有文件，但默认只是显示出最基础的文件和文件夹，如果需要更详细的信息，则使用ls -la，这将列出包括隐藏文件在内的所有文件和文件夹，并且给出对应的权限、大小和日期等信息。 zy123@hcss-ecs-588d:~$ ls -la total 44 drwxr-xr-x 6 zy123 zy123 4096 Feb 26 08:53 . drwxr-xr-x 3 root root 4096 Feb 24 16:33 .. -rw------- 1 zy123 zy123 6317 Feb 25 19:41 .bash_history -rw-r--r-- 1 zy123 zy123 220 Feb 24 16:33 .bash_logout -rw-r--r-- 1 zy123 zy123 3526 Feb 24 16:33 .bashrc drwx------ 3 zy123 zy123 4096 Feb 24 16:35 .config drwxr-xr-x 3 zy123 zy123 4096 Feb 24 16:36 .local -rw-r--r-- 1 zy123 zy123 807 Feb 24 16:33 .profile drwxr-xr-x 5 zy123 zy123 4096 Feb 26 08:53 zbparse drwxr-xr-x 3 root root 4096 Feb 26 08:54 zbparse_output 权限与文件类型（第一列）：第一个字符表示文件类型： “d”表示目录（directory） “-”表示普通文件（regular file） “l”表示符号链接（symbolic link）后续的9个字符分为3组，每组三个字符，分别代表所有者、所属组和其他用户的权限（读、写、执行）。硬链接数（第二列）：表示指向该文件的硬链接数量。对于目录来说，这个数字通常会大于1，因为“.”和“..”也算在内。所有者（第三列）：显示该文件或目录的拥有者用户名。所属组（第四列）：显示该文件或目录所属的用户组。文件大小（第五列）：以字节为单位显示文件的大小。对于目录，通常显示的是目录文件占用的磁盘空间（一般为4096字节）。最后修改日期和时间（第六列）：显示文件最后一次修改的日期和时间（可能包含月、日和具体时间或年份）。文件名或目录名（第七列）：显示文件或目录的名称。 cd 进入指定文件夹，如cd /home 将进入home目录。返回上层目录的命令是cd ..，返回刚才操作的目录的命令是cd - mkdir 新建文件夹，如mkdir /home/Python 将在home 文件夹下新建一个Python 文件夹。 mv 移动文件和文件夹，也可以用来修改名称，如： mv /home/hello.py /home/helloworld.py 将上文的hello.py重命名为helloworld.py， mv /home/helloworld.py /home/Python/helloworld.py 将helloworld.py 由home文件夹移动到了次级的Python文件夹。 mv /home/hello.py . 将/home/hello.py 移动到当前目录下 cp 复制文件 cp /home/Python/hellowrold.py /home/Python/HelloWorld.py 将helloworld.py复制为HelloWolrd.py。注意：Linux系统严格区分大小写，helloworld.py和HelloWolrd.py是两个文件。 rm 删除，即江湖传说中rm -rf ，r为递归，可以删除文件夹中的文件，f为强制删除。rm /home/Python/helloworld.py 可以删除刚才的helloworld.py 文件，而想删除包括Python 在内的所有文件，则是rm -rf /home/Python 。 du -h 查看当前文件夹下，各文件、文件夹的大小，h是让文件自动使用K/M/G显示而不是只有K。“disk usage”（磁盘使用情况） grep 是用于在文件或标准输入中搜索符合条件的行的命令。 grep "pattern" filename #pattern可以是一个正则表达式 -i忽略大小写 -n显示行号 awk 是一个功能强大的文本处理工具，它可以对文本文件进行分列处理、模式匹配和报告生成。它的语法类似一种简单的脚本语言。 awk 'pattern { action }' filename pattern：用于匹配文本的条件（可以省略，默认对所有行生效）。 action：在匹配的行上执行的操作。 $0：代表整行内容。 $1, $2, ...：代表各个字段（默认分隔符是空白字符，可以通过 -F 参数指定其他分隔符）。 awk '{print $1, $3}' filename #印指定列管道 | 是将一个命令的输出直接传递给另一个命令作为输入的一种机制。示例：将 grep 与 awk 联合使用：假设有一个日志文件 access.log，需要先用 grep 过滤出包含 "ERROR" 的行，再用 awk 提取时间字段： 127.0.0.1 27/Feb/2025:10:30:25 "GET /index.html HTTP/1.1" 200 1024 192.168.1.1 27/Feb/2025:10:31:45 "POST /login HTTP/1.1" 302 512 10.0.0.5 27/Feb/2025:10:32:10 "GET /error_page HTTP/1.1" 500 2048 ERROR grep 'ERROR' access.log | awk '{print $2}' 输出：27/Feb/2025:10:32:10 lsof"List Open Files"显示系统中当前打开的文件。 -i会显示所有正在使用网络连接的进程 lsof -i :80 #查看 80 端口上的进程,或者判断80端口是否被占用！ usermode 修改用户账户信息的命令 sudo usermod -aG docker zy123 #-aG一起用，添加zy123到group组 chmod 命令用于修改文件或目录的权限数字方式:数字方式使用三个（或四个）数字来表示所有者、组用户和其他用户的权限。每个数字代表读 (4)、写 (2)、执行 (1) 权限的和。 chmod 644 filename #所有者：读 + 写 = 6 组用户：读 = 4 其他用户：读 = 4 符号方式 chmod [用户类别][操作符][权限] filename 用户类别： u：所有者（user） g：组用户（group） o：其他用户（others） a：所有用户（all），等同于 u+g+o 操作符： +：增加权限 -：去掉权限 =：直接设置权限权限： r：读权限 w：写权限 x：执行权限 chmod u+x filename #为所有者增加执行权限文本编辑器 nano：Debian 11自带了简便易用的nano文本编辑器 nano /etc/apt/sources.list #打开sources.list文件 Ctrl+O:保存修改 ->弹出询问-> Y则保存，N则不保存,ctrl+c 取消操作。 Ctrl+X:退出 vim 普通模式（Normal Mode）：打开 Vim 后默认进入普通模式。在该模式下，可以执行移动光标、删除、复制、粘贴等命令。光标移动： 0：跳到当前行行首 $：跳到当前行行尾 gg: 将光标移到文件开头文本操作： dd：删除（剪切）整行 yy：复制（拷贝）整行 p：在光标后粘贴（把剪切或复制的内容贴上） u：撤销上一步操作 Ctrl + r：重做上一步撤销的操作插入模式（Insert Mode）：在普通模式下按 i、I、a、A 等键可进入插入模式，此时可以像普通编辑器那样输入文本。按 ESC 键退出插入模式，返回普通模式。可视模式（Visual Mode）：用于选中一段文本，自动进入可视模式。选中文本后可以进行复制、剪切等操作。在可视模式下选中后按 d 删除按 y 复制选中区域命令行模式（Command-Line Mode）：在普通模式下，输入 : 进入命令行模式，可以执行保存、退出、查找等命令。 :w：保存当前文件 :q：退出 Vim（如果有未保存的修改会警告） :wq 或 :x：保存文件并退出 :q!：不保存强制退出 :set number：显示行号 :set paste：适用于代码或格式敏感的文本，确保粘贴操作不会破坏原有的布局和缩进。 :%d: 删除全文抓包 sudo tcpdump -nn -i any port 1000 //查看请求端口1000的源 IP 地址 SSH 生成密钥 ssh-keygen -t rsa -b 4096 -C "your_email@example.com" 默认会在当前用户的主目录下的 ~/.ssh/ 文件夹中生成两个文件：私钥（id_rsa）：必须保存在本地，切勿泄露或放到服务器上。它是用来证明你身份的重要凭证。公钥（id_rsa.pub）：需要复制到目标服务器上，通常放入服务器用户主目录下的 ~/.ssh/authorized_keys 文件中，用于验证连接时与私钥匹配。根据我的理解： 1.服务器从github上通过ssh拉取代码时，需要把服务器的公钥放在github上，因为拉代码时，github需要认证服务器的身份，就要用服务器给它提供的公钥加密。 2.通过windows上的finalshell连接linux服务器时，需要在windows环境下生成一对密钥，私钥用于ssh登录的时候输入，公钥放在linux服务器的~/.ssh/authorized_keys文件中。因为ssh登录的时候服务器需要验证你的身份，需要用你提供给它的公钥加密。除此之外，还需要给文件和相关文件夹合适的权限： chmod 600 authorized_keys chmod 700 ~/.ssh 文件系统在 Linux 系统中，整个文件系统从根目录 / 开始，下面简单介绍一些主要目录及其存放的文件类型： /bin 存放系统启动和运行时必需的用户二进制可执行文件，如常用的 shell 命令（例如 ls、cp、mv 等）。 /boot 包含启动加载器（如 GRUB）的配置文件和内核映像（kernel image），这些文件用于系统启动过程。 /dev 包含设备文件，这些文件代表系统中的各种硬件设备（例如硬盘、终端、USB 设备等），以及一些伪设备。 /etc 存放系统范围内的配置文件，例如网络配置、用户账户信息、服务配置等。这些文件通常由管理员维护。 /home 为普通用户提供的家目录，每个用户在这里有一个独立的子目录，存放个人文件和配置。 /lib 和 /lib64 存放系统和应用程序所需的共享库文件，这些库支持 /bin、/sbin 及其他程序的运行。 /media 通常用于挂载移动介质，如光盘、U 盘或其他可移动存储设备。 /mnt 提供一个临时挂载点，一般供系统管理员在需要手动挂载文件系统时使用。 /opt 用于安装附加的应用程序软件包，通常是第三方提供的独立软件，不与系统核心软件混合。 /proc 这是一个虚拟文件系统，提供内核和进程信息，例如系统资源使用情况、硬件信息、内核参数等。这里的文件不占用实际磁盘空间。 /root 系统管理员（root 用户）的家目录，与普通用户的 /home 分开存放。 /run 存储系统启动后运行时产生的临时数据，比如 PID 文件、锁文件等，系统重启后会清空该目录。 /sbin 存放系统管理和维护所需的二进制文件（系统级命令），例如网络配置、磁盘管理工具等，这些通常只由 root 用户使用。 /srv 用于存放由系统提供的服务数据，如 FTP、HTTP 服务的数据目录等。 /tmp 用于存放临时文件，许多应用程序在运行时会将临时数据写入这里，系统重启后通常会清空该目录。 /usr 存放大量用户应用程序和共享资源，其子目录包括： /usr/bin：大部分用户命令和应用程序。 /usr/sbin：非基本系统维护工具，主要供系统管理员使用。 /usr/lib：程序库文件。 /usr/share：共享数据，如文档、图标、配置样本等。 /var 存放经常变化的数据，如日志文件、缓存、邮件、打印队列和临时应用数据等。 Bash #!/bin/bash # 定义变量，注意等号两边不能有空格 name="World" # 如果脚本传入了参数，则使用第一个参数覆盖默认值 if [ $# -ge 1 ]; then # $# 表示传入脚本的参数个数 name=$1 # $1 表示第一个参数。 fi # 输出问候语 echo "Hello, $name!" #变量引用时要用 $ 符号，如 $name。 # 循环示例：遍历1到5的数字 for i in {1..5}; do echo "当前数字：$i" done # 定义一个函数，函数名为greet greet() { echo "函数内问候: Hello, $1!" } # 调用函数，并传入变量name作为参数 greet $name 如何运行？赋予可执行权限 chmod +x hello_world.sh 执行 ./hello_world.sh 或者 ./hello_world.sh Alice #传参在 Linux 系统中，默认情况下当前目录（.）并不包含在 PATH 环境变量中。这意味着，如果你在终端中直接输入脚本名（例如 hello_world.sh），系统不会在当前目录下查找这个脚本，而是只在 PATH 中指定的目录中查找可执行程序。使用 ./hello_world.sh 表示“在当前目录下执行 hello_world.sh”，从而告诉系统正确的路径。如何设置定时任务？ sudo crontab -e #在里面添加： 10 0 * * * /path/toyour/xx.sh #让gpt写反向代理神器——Nginx Proxy Manager 【Docker系列】一个反向代理神器——Nginx Proxy Manager-我不是咕咕鸽概念正向代理是代理客户端的行为，即代理服务器代表客户端向目标服务器发出请求。客户端将自己的请求先发送给代理服务器，由代理服务器转发给真正的目标服务器，然后再将返回结果传递给客户端。特点：保护访问者（客户端）的信息：目标服务器只会看到代理服务器的请求，无法直接获知真正发起请求的客户端是谁。应用场景：当客户端出于隐私、访问控制或跨越网络限制的目的，需要隐藏自己的真实IP或身份时，会使用正向代理。反向代理是代理服务器代表目标服务器接收客户端请求，并将请求转发给内部的真实服务器，然后将结果返回给客户端。客户端只与代理服务器通信，而不知道背后实际处理请求的服务器。特点：保护服务器端的信息：客户端看不到真正的服务器细节，只知道代理服务器。这样可以隐藏真实服务器的 IP 和其他内部结构信息，从而增强安全性和负载均衡等功能。应用场景：在大型网站或应用中，为了防止恶意攻击或实现负载均衡，通常会在真实服务器前部署一个反向代理服务器。 docker 部署 version: '3' services: app: image: 'jc21/nginx-proxy-manager:latest' restart: unless-stopped ports: - '80:80' # 保持默认即可，不建议修改左侧的80 - '81:81' # 冒号左边可以改成自己服务器未被占用的端口 - '443:443' # 保持默认即可，不建议修改左侧的443 volumes: - ./data:/data # 冒号左边可以改路径，现在是表示把数据存放在在当前文件夹下的 data 文件夹中 - ./letsencrypt:/etc/letsencrypt # 冒号左边可以改路径，现在是表示把数据存放在在当前文件夹下的 letsencrypt 文件夹中 NPM后台管理网站运行在81号端口，NPM服务本身监听80(http)和443(https)端口工作原理用户访问网站（80/443端口）当用户访问 https://blog.test.com 时，请求到达服务器的443端口。 Nginx根据域名匹配代理规则（由NPM配置），将请求转发到后端服务（如 192.168.1.100:8080）。管理员访问后台（81端口）管理员通过 http://服务器IP:81 访问NPM管理界面，配置代理规则。配置完成后，NPM会自动生成Nginx配置文件并重启Nginx服务，使新规则生效。两种方法实现SSL安全连接 1. 开启橙云+Cloudflare Origin CA：网站SSL证书自动续期又又又失败了？试试CloudFlare的免费证书，15年有效期！-我不是咕咕鸽 cloudflare解析DNS，开启橙云 Cloudflare Full (strict)模式(灵活模式下无需以下步骤) 在 Nginx Proxy Manager（NPM）添加 Cloudflare Origin CA 配置 Proxy Host 使其使用选择刚刚添加的 Cloudflare Origin CA 证书选择 Force SSL（强制 HTTPS）启用 HTTP/2 支持 Cloudflare Origin CA作用:实现cloudflare与源服务器之间的流量加密 2.通配符SSL证书：【Docker系列】反向代理神器NginxProxyManager——通配符SSL证书申请-我不是咕咕鸽更推荐第二种！！！目前正在使用，但是3个月续签一次证书！浏览器 → (HTTPS) → NPM → (HTTP 或 HTTPS) → Gitea 这就是反向代理常见的工作流程。默认经常是 NPM 做 SSL 终止（内网用 HTTP 转发给 Gitea）。如果你想内外全程加密，就要让 NPM -> Gitea 这段也走 HTTPS，并在 Gitea 上正确配置证书。正向代理（用于拉取镜像）下载Clash客户端：Release Clash-Premium · DustinWin/proxy-tools 或者Index of /Linux/centOS/ 我是windows上下载clashpremium-release-linux-amd64.tar.gz 然后FTP上传到linux服务器上。下载配置文件config.yaml：每个人独一无二的 wget -O /home/zy123/VPN/config.yaml "https://illo1.no-mad-world.club/link/2zXAEzExPjAi6xij?clash=3" 类似这样： port: 7890 socks-port: 7891 allow-lan: false mode: Rule //Global log-level: info external-controller: 0.0.0.0:9090 unified-delay: true hosts: time.facebook.com: 17.253.84.125 time.android.com: 17.253.84.125 dns: enable: true use-hosts: true nameserver: - 119.29.29.29 - 223.5.5.5 - 223.6.6.6 - tcp://223.5.5.5 - tcp://223.6.6.6 - tls://dns.google:853 - tls://8.8.8.8:853 - tls://8.8.4.4:853 - tls://dns.alidns.com - tls://223.5.5.5 - tls://223.6.6.6 - tls://dot.pub - tls://1.12.12.12 - tls://120.53.53.53 - https://dns.google/dns-query - https://8.8.8.8/dns-query - https://8.8.4.4/dns-query - https://dns.alidns.com/dns-query - https://223.5.5.5/dns-query - https://223.6.6.6/dns-query - https://doh.pub/dns-query - https://1.12.12.12/dns-query - https://120.53.53.53/dns-query default-nameserver: - 119.29.29.29 - 223.5.5.5 - 223.6.6.6 - tcp://119.29.29.29 - tcp://223.5.5.5 - tcp://223.6.6.6 proxies: - {name: 🇭🇰 香港Y01, server: qvhh1-g03.hk01-ae5.entry.v50307shvkaa.art, port: 19273, type: ss, cipher: aes-256-gcm, password: 6e4124c4-456e-36a3-b144-c0e1a618d04c, udp: true} 注意，魔戒vpn给的是一个订阅地址！！！还需要解码简便方法：windows上将订阅链接导入，自动解析成yaml配置文件，然后直接把该文件传到服务器上！启动Clash ./CrashCore -d . & //后台启动为Clash创建服务 1.创建 systemd 服务文件 sudo vim /etc/systemd/system/clash.service 2.在文件中添加以下内容： [Unit] Description=Clash Proxy Service After=network.target [Service] ExecStart=/home/zy123/VPN/CrashCore -d /home/zy123/VPN WorkingDirectory=/home/zy123/VPN Restart=always User=zy123 Group=zy123 [Install] WantedBy=multi-user.target 这段配置将 Clash 配置为：在网络服务启动后运行。在启动时自动进入后台，执行 CrashCore 服务。如果服务意外停止，它将自动重启。以 zy123 用户身份运行 Clash。启动服务： sudo systemctl start clash 停止服务： sudo systemctl stop clash 查看服务状态： sudo systemctl status clash 配置YACD YACD 是一个基于 Clash 的 Web 管理面板，用于管理您的 Clash 配置、查看流量和节点信息等。直接用现成的：https://yacd.haishan.me/ 服务器上部署：目前是npm手动构建安装启动的。下载yacd git clone https://github.com/haishanh/yacd.git 安装npm 构建yacd cd ~/VPN/yacd pnpm install pnpm build 启动yacd nohup pnpm serve --host 0.0.0.0 & //如果不是0.0.0.0 不能在windows上打开停止进程 ps aux | grep pnpm kill xxx 通过http://124.71.159.195:4173/ 访问yacd控制面板。手动添加crash服务所在的ip:端口。如果连不上：yacd面板和crash都是http协议就行了。连接测试直连： curl -v https://www.google.com 使用代理：curl -x http://127.0.0.1:7890 https://www.google.com File Browser 文件分享 https://github.com/filebrowser/filebrowser Docker 部署 File Browser 文件管理系统_filebrowser docker-CSDN博客 1.创建数据目录 mkdir -p /data/filebrowser/{srv,config,db} 2.目录授权 chmod -R 777 /data/filebrowser/ 3.编辑 docker-compose.yaml 文件 version: '3' services: filebrowser: image: filebrowser/filebrowser:s6 container_name: filebrowser restart: always ports: - "2000:80" # 将容器的80端口映射到宿主机2000端口 volumes: - /data/filebrowser/srv:/srv #保存用户上传的文件 - /data/filebrowser/config:/config # 配置文件存储路径 - /data/filebrowser/db:/database #数据库存储路径调用API实现文件上传与下载登录： # 登录 → 获取 JWT token（原始字符串） curl -X POST "yourdomain/api/login" \ -H "Content-Type: application/json" \ -d '{ "username": "admin", "password": "123456" }' 响应: "eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9…" //jwt令牌上传： # 先把 token 保存到环境变量（假设你已经执行过 /api/login 并拿到了 JWT） export TOKEN="eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9…" # 定义要上传的本地文件和目标名称 FILE_PATH="/path/to/local/photo.jpg" OBJECT_NAME="photo.jpg" # 对远程路径做 URL 编码（保留斜杠） REMOTE_PATH="store/${OBJECT_NAME}" ENCODED_PATH=$(printf "%s" "${REMOTE_PATH}" \ | jq -sRr @uri \ | sed 's/%2F/\//g') # 发起上传请求（raw body 模式） curl -v -X POST "https://yourdomain/api/resources/${ENCODED_PATH}?override=true" \ -H "X-Auth: ${TOKEN}" \ -H "Content-Type: image/jpeg" \ # 根据文件后缀改成 image/png 等 --data-binary "@${FILE_PATH}" 获取分享链接url： # 假设已经执行过 /api/login 并把 JWT 保存在环境变量 TOKEN # 同样复用之前算好的 ENCODED_PATH 和 REMOTE_PATH # 调用分享接口（注意：POST，body 为空 JSON "{}"） curl -s -X POST "https://yourdomain/api/share/${ENCODED_PATH}" \ -H "X-Auth: ${TOKEN}" \ -H "Cookie: auth=${TOKEN}" \ -H "Content-Type: text/plain;charset=UTF-8" \ -d '{}' \ | jq -r '.hash' \ | xargs -I{} printf "https://yourdomain/api/public/dl/%s/%s\n" {} "${REMOTE_PATH}" Gitea Gitea Docker 安装与使用详解：轻量级自托管 Git 服务教程-CSDN博客 version: "3" services: gitea: image: gitea/gitea:latest container_name: gitea environment: - USER_UID=1000 - USER_GID=1000 restart: always ports: - "3000:3000" # 将宿主机的3000端口映射到容器的3000端口 volumes: - /data/gitea:/data # 持久化存储Gitea数据（包括仓库、配置、日志等） EasyImage 【好玩儿的Docker项目】10分钟搭建一个简单图床——Easyimage-我不是咕咕鸽 github地址：icret/EasyImages2.0: 简单图床 - 一款功能强大无数据库的图床 2.0版 sudo -i # 切换到root用户 apt update -y # 升级packages apt install wget curl sudo vim git # Debian系统比较干净，安装常用的软件 version: '3.3' services: easyimage: image: ddsderek/easyimage:latest container_name: easyimage ports: - '1000:80' environment: - TZ=Asia/Shanghai - PUID=1000 - PGID=1000 volumes: - '/root/data/docker_data/easyimage/config:/app/web/config' - '/root/data/docker_data/easyimage/i:/app/web/i' restart: unless-stopped 网页打开显示bug： cd /data/easyimage/config/config.php 这里添加上https 网站域名图片域名设置可以改变图片的url：IP或域名 picgo安装： Releases · Molunerfinn/PicGo 1.右下角小窗打开 2.插件设置，搜索web-uploader 1.1.1 （自定义web图床）旧版有搜索不出来的情况！建议直接安装最新版！ 3.配置如下，API地址从easyimage-设置-API设置中获取 typora设置左上角文件-偏好设置-图像-插入图片时{ 上传图片-picgo服务器-填写picgo安装路径 } ps:还可以选择上传到./assets，每个md文件独立或者上传到指定路径如/image，多个md文件共享 py脚本1：将所有md文件中的图片路径改为本地，统一保存到本地output文件夹中 py脚本2：将每个md文件及其所需图片单独保存，保存到本地，但每个md文件有自己独立的assets文件夹 py脚本3：将本地图片上传到easyimage图床并将链接返回替换md文件中的本地路径 Typecho 【好玩儿的Docker项目】10分钟搭建一个Typecho博客｜太破口！念念不忘，必有回响！-我不是咕咕鸽 typecho:https://github.com/typecho/typecho/ 注意：nginx一定要对typecho目录有操作权限！ sudo chmod 755 -R ./typecho services: nginx: image: nginx ports: - "4000:80" # 左边可以改成任意没使用的端口 restart: always environment: - TZ=Asia/Shanghai volumes: - ./typecho:/var/www/html - ./nginx:/etc/nginx/conf.d - ./logs:/var/log/nginx depends_on: - php networks: - web php: build: php restart: always expose: - "9000" # 不暴露公网，故没有写9000:9000 volumes: - ./typecho:/var/www/html environment: - TZ=Asia/Shanghai depends_on: - mysql networks: - web pyapp: build: ./markdown_operation # Dockerfile所在的目录 restart: "no" networks: - web env_file: - .env depends_on: - mysql mysql: image: mysql:5.7 restart: always environment: - TZ=Asia/Shanghai expose: - "3306" # 不暴露公网，故没有写3306:3306 volumes: - ./mysql/data:/var/lib/mysql - ./mysql/logs:/var/log/mysql - ./mysql/conf:/etc/mysql/conf.d env_file: - mysql.env networks: - web networks: web: 卸载： sudo -i # 切换到root cd /root/data/docker_data/typecho # 进入docker-compose所在的文件夹 docker-compose down # 停止容器，此时不会删除映射到本地的数据 cd ~ rm -rf /root/data/docker_data/typecho # 完全删除映射到本地的数据主题 Joe主题：https://github.com/HaoOuBa/Joe Joe再续前缘主题 - 搭建本站同款网站 - 易航博客自定义文章详情页的上方信息（如更新日期/文章字数第）： /typecho/usr/themes/Joe/functions.php中定义art_count，统计字数(粗略)。原始 Markdown → [1] 删除代码块/行内代码/图片/链接标记/标题列表标记/强调符号 → [2] strip_tags() + html_entity_decode() → [3] 正则保留 “文字+数字+标点”，去除其它 → 结果用 mb_strlen() 得到最终字数 typecho/usr/themes/Joe/module/single/batten.php <?php if (!defined('__TYPECHO_ROOT_DIR__')) { http_response_code(404); exit; } ?> <h1 class="joe_detail__title"><?php $this->title() ?></h1> <div class="joe_detail__count"> <div class="joe_detail__count-information"> <a href="<?php $this->author->permalink(); ?>"> <img width="38" height="38" class="avatar lazyload" src="<?php joe\getAvatarLazyload(); ?>" data-src="<?php joe\getAvatarByMail($this->author->mail) ?>" alt="<?php $this->author(); ?>" /> </a> <div class="meta ml10"> <div class="author"> <a class="link" href="<?php $this->author->permalink(); ?>" title="<?php $this->author(); ?>"><?php $this->author(); ?></a> </div> <div class="item"> <span class="text"> <?php echo $this->date('Y-m-d'); ?> /  <?php $this->commentsNum('%d'); ?> 评论 /  <?php echo joe\getAgree($this); ?> 点赞 /  <?php echo joe\getViews($this); ?> 阅读 /  <?php echo art_count($this->cid); ?> 字 </span> </div> </div> </div> </div> <div class="relative" style="padding-right: 40px;"> <i class="line-form-line"></i>  <div style="font-size: 1.0em; position: absolute; right: 20px; top: 50%; transform: translateY(-50%);"> 最后更新于 <?php echo date('m-d', $this->modified); ?> </div> <div class="flex ac single-metabox abs-right"> <div class="post-metas">  </div> <div class="clearfix ml6">  </div> </div> </div> 修改代码块背景色： typecho/usr/themes/Joe/assets/css/joe.global.css .joe_detail__article code:not([class]) { border-radius: var(--radius-inner, 4px); /* 可以设置一个默认值 */ background: #f5f5f5; /* 稍微偏灰的背景色 */ color: #000000; /* 黑色字体 */ padding: 2px 6px; /* 内边距可以适当增大 */ font-family: "SFMono-Regular", Consolas, "Liberation Mono", Menlo, Courier, monospace; word-break: break-word; font-weight: normal; -webkit-text-size-adjust: 100%; -webkit-font-smoothing: antialiased; white-space: pre-wrap; /* 保持代码换行 */ font-size: 0.875em; margin-inline-start: 0.25em; margin-inline-end: 0.25em; } 大坑：会显示为勾选框，无法正常进行latex公式解析，因为typecho/usr/themes/Joe/public/short.php中设置了短代码替换，在文章输出前对 $content 中的特定标记或短代码进行搜索和替换，从而实现一系列自定义功能。现已全部注释。 typecho/usr/themes/Joe/assets/js/joe.single.js原版：显示弹窗，点叉后消失 { document.querySelector('.joe_detail__article').addEventListener('copy', () => { autolog.log(`本文版权属于 ${Joe.options.title} 转载请标明出处！`, 'warn', false); }); } 显示5秒后消失： document.querySelector('.joe_detail__article').addEventListener('copy', () => { // 显示 autolog 消息 autolog.log(`本文版权属于 ${Joe.options.title} 转载请标明出处！`, 'warn', false); // 5 秒后删除该消息 setTimeout(() => { const warnElem = document.querySelector('.autolog-warn'); if (warnElem) { warnElem.remove(); // 或者使用 warnElem.style.display = 'none'; } }, 5000); }); markdown编辑与解析确保代码块```后面紧跟着语言，如```java，否则无法正确显示。 markdown编辑器插件：https://xiamp.net/archives/aaeditor-is-another-typecho-editor-plugin.html '开启公式解析！' markdown解析器插件：mrgeneralgoo/typecho-markdown: A markdown parse plugin for typecho. 关闭公式解析，仅开启代码解析！ slug为页面缩略名，在新增文章时可以传入，默认是index数字。 qBittorrent 【好玩的Docker项目】10分钟搭建你专属的下载神器——qbittorrent-我不是咕咕鸽 docker pull linuxserver/qbittorrent cd ~ mkdir /root/data/docker_data/qBittorrent #创建qbitorrent数据文件夹 cd /root/data/docker_data/qBittorrent mkdir config downloads #创建配置文件目录与下载目录 nano docker-compose.yml #创建并编辑文件 services: qbittorrent: image: linuxserver/qbittorrent container_name: qbittorrent environment: - PUID=1000 - PGID=1000 - TZ=Asia/Shanghai # 你的时区 - UMASK_SET=022 - WEBUI_PORT=8081 # 将此处修改成你欲使用的 WEB 管理平台端口 volumes: - ./config:/config # 绝对路径请修改为自己的config文件夹 - ./downloads:/downloads # 绝对路径请修改为自己的downloads文件夹 ports: # 要使用的映射下载端口与内部下载端口，可保持默认，安装完成后在管理页面仍然可以改成其他端口。 - 6881:6881 - 6881:6881/udp # 此处WEB UI 目标端口与内部端口务必保证相同，见问题1 - 8081:8081 restart: unless-stopped

自学

zy123 3月21日
0 5 0
2025-03-21
力扣Hot 100题力扣Hot 100题杂项最大值：Integer.MAX_VALUE 最小值：Integer.MIN_VALUE 数组集合比较 Arrays.equals(array1, array2) 用于比较两个数组是否相等（内容相同）。支持多种类型的数组（如 int[]、char[]、Object[] 等）。 int[] arr1 = {1, 2, 3}; int[] arr2 = {1, 2, 3}; boolean isEqual = Arrays.equals(arr1, arr2); // true Collections 类本身没有直接提供类似 Arrays.equals 的方法来比较两个集合的内容是否相等。不过，Java 中的集合类（如 List、Set、Map）已经实现了 equals 方法 List<Integer> list1 = Arrays.asList(1, 2, 3); List<Integer> list2 = Arrays.asList(1, 2, 3); List<Integer> list3 = Arrays.asList(3, 2, 1); System.out.println(list1.equals(list2)); // true System.out.println(list1.equals(list3)); // false（顺序不同）逻辑比较 boolean flag = false; if (!flag) { //! 是 Java 中的逻辑非运算符，只能用于对布尔值取反。 System.out.println("flag 是 false"); } if (flag == false) { //更常用！ System.out.println("flag 是 false"); } //java中没有 if(not flag) 这种写法！ Character好用的方法 Character.isDigit(char c)用于判断一个字符是否是一个数字字符 Character.isLetter(char c)用于判断字符是否是一个字母（大小写字母都可以）。 Character.isLowerCase(char c)判断字符是否是小写字母。 Character.toLowerCase(char c)将字符转换为小写字母。 Integer好用的方法 Integer.parseInt(String s)：将字符串 s 解析为一个整数（int）。 Integer.toString(int i)：将 int 转换为字符串。 Integer.compare(int a,int b) 比较a和b的大小，内部实现类似： public static int compare(int x, int y) { return (x < y) ? -1 : ((x == y) ? 0 : 1); } 避免了整数溢出的风险，在排序中建议使用Integer.compare(a,b)代替 a-b。注意，仅支持Integer[] arr，不支持int[] arr。位运算按位与 &：只有两个对应位都为 1 时，结果位才为 1。 int a = 5; // 0101₂ int b = 3; // 0011₂ int c = a & b; // 0001₂ = 1 System.out.println(c); // 输出 1 典型用途：清零低位：x & (~((1<<k)-1)) 清掉最低 k 位； (1<<3)-1 = 0000_0111 ~((1<<3)-1) = 1111_1000 判断奇偶：x & 1，若结果是 1 说明奇数，若 0 说明偶数；掩码提取：只保留想要的位置，其他位置置 0。按位或 |: 只要两个对应位有一个为 1，结果位就为 1。 int a = 5; // 0101₂ int b = 3; // 0011₂ int c = a | b; // 0111₂ = 7 System.out.println(c); // 输出 7 典型用途：置位：x | (1<<k) 把第 k 位置 1；合并标志：将两个掩码或在一起。按位异或 ^: 两个对应位不同则为 1，相同则为 0。 int a = 5; // 0101₂ int b = 3; // 0011₂ int c = a ^ b; // 0110₂ = 6 System.out.println(c); // 输出 6 算术左移 <<: 整体二进制左移 n 位，右侧补 0；相当于乘以 2ⁿ。(因为最高位可能走出符号位，结果符号可能翻转) int a = 3; // 0011₂ int b = a << 2; // 1100₂ = 12 System.out.println(b); // 输出 12 逻辑（无符号）右移>>>:在最高位一律补 0，不管原符号位是什么。 Random Random 是伪随机数生成器 nextInt() 任意 int Integer.MIN_VALUE … Integer.MAX_VALUE nextInt(bound) 0（含）至 bound（不含） [0, bound) import java.util.Random; import java.util.stream.IntStream; public class RandomDemo { public static void main(String[] args) { Random rnd = new Random(); // 随机种子 Random seeded = new Random(2025L); // 固定种子 // 1) 随机整数 int a = rnd.nextInt(); // 任意 int int b = rnd.nextInt(100); // [0,100) System.out.println("a=" + a + ", b=" + b); // 2) 随机浮点数与布尔 double d = rnd.nextDouble(); // [0.0,1.0) boolean flag = rnd.nextBoolean(); System.out.println("d=" + d + ", flag=" + flag); } } 常用数据结构 String 子串：字符串中连续的一段字符。子序列：字符串中按顺序选取的一段字符，可以不连续。异位词：字母相同、字母频率相同、顺序不同，如"listen" 和 "silent" 排序：需要String先转为char [] 数组，排序好之后再转为String类型！！ char[] charArray = str.toCharArray(); Arrays.sort(charArray); String sortedStr = new String(charArray); iter遍历,也要先转为char[]数组 int[]cnt=new int[26]; for (Character c : s.toCharArray()) { cnt[c-'a']++; } 取字符： charAt(int index) 方法返回指定索引处的 char 值。 char 是基本数据类型，占用 2 个字节，表示一个 Unicode 字符。 HashSet<Character> set = new HashSet<Character>(); 取子串： substring(int beginIndex, int endIndex) 方法返回从 beginIndex 到 endIndex - 1 的子字符串。返回的是 String 类型，即使子字符串只有一个字符。去除开头结尾空字符： trim() 分割字符串： split() 方法，可以用来分割字符串，并返回一个字符串数组。参数是正则表达式。 String str = "apple, banana, orange grape"; String[] fruits = str.split(",\\s*"); // 按逗号后可能存在的空格分割 // apple banana orange grape 仅用stringbuilder+substring: public static List<String> splitBySpace(String s) { List<String> words = new ArrayList<>(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c != ' ') { // 累积字母 sb.append(c); } else { // 遇到空格：如果 sb 里有内容，则构成一个单词 if (sb.length() > 0) { words.add(sb.toString()); sb.setLength(0); // 清空，准备下一个单词 } // 如果连续多个空格，则这里会跳过 sb.length()==0 的情况 } } // 循环结束后，sb 里可能还剩最后一个单词 if (sb.length() > 0) { words.add(sb.toString()); } return words; } StringBuilder StringBuffer 是线程安全的，它的方法是同步的 (synchronized)，这意味着在多线程环境下使用 StringBuffer 是安全的。 StringBuilder 不是线程安全的，它的方法没有同步机制，因此在单线程环境中，StringBuilder 的性能通常要比 StringBuffer 更好。它们都是 Java 中用于操作可变字符串的类，拥有相同的方法！ 1.append(String str) 向字符串末尾追加内容。 2.insert(int offset, String str) 在指定位置插入字符串。（有妙用，头插法可以实现倒序）insert(0,str) 3.delete(int start, int end) 删除从 start 到 end 索引之间的字符。（包括start，不包括end） 4.deleteCharAt(int index) 删除指定位置的字符。 5.replace(int start, int end, String str) 替换指定范围内的字符。 6.reverse() 将字符串反转。String未提供重要内容！！！！ 7.toString() 返回当前字符串缓冲区的内容，转换为 String 对象。 sb.toString()会创建并返回一个新的、独立的 String 对象，之后setLength(0)不会影响这个 String 对象 8.setLength(int newLength) 设置字符串的长度。 //sb.setLength(0); 用作清空字符串 9.charAt(int index) 返回指定位置的字符。 10.length() 返回当前字符串的长度。 StringBuffer 的 append() 方法不仅支持添加普通的字符串，也可以直接将另一个 StringBuffer 对象添加到当前的 StringBuffer。 StringBuffer 插入int类型的数字时，会自动转为字符串插入。 HashMap 基于哈希表实现，查找、插入和删除的平均时间复杂度为 O(1)。不保证元素的顺序。 import java.util.HashMap; import java.util.Map; public class HashMapExample { public static void main(String[] args) { // 创建 HashMap Map<String, Integer> map = new HashMap<>(); // 添加键值对 map.put("apple", 10); map.put("banana", 20); map.put("orange", 30); // 获取值 int appleCount = map.get("apple"); //如果获取不存在的元素，返回null System.out.println("Apple count: " + appleCount); // 输出 10 // 遍历 HashMap for (Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } // 输出： // apple: 10 // banana: 20 // orange: 30 // 检查是否包含某个键 boolean containsBanana = map.containsKey("banana"); System.out.println("Contains banana: " + containsBanana); // 输出 true // 删除键值对 map.remove("orange"); //删除不存在的元素也不会报错 System.out.println("After removal: " + map); // 输出 {apple=10, banana=20} } } 如何在创建的时候初始化？“双括号”初始化 Map<Integer, Character> map = new HashMap<>() {{ put(1, 'a'); put(2, 'b'); put(3, 'c'); }}; 记录二维数组中某元素是否被访问过，推荐使用： int m = grid.length; int n = grid[0].length; boolean[][] visited = new boolean[m][n]; // 访问 (i, j) 时标记为已访问 visited[i][j] = true; 而非创建自定义Pair二元组作为键用Map记录。统计每个字母出现的次数： int[] cnt = new int[26]; for (char c : magazine.toCharArray()) { cnt[c - 'a']++; } 修改键值对中的键值： Map<Character, Integer> counts = new HashMap<>(); counts.put(ch, counts.getOrDefault(ch, 0) + 1); HashSet 基于哈希表实现，查找、插入和删除的平均时间复杂度为 O(1)。不保证元素的顺序!!因此不太用iterator迭代，而是用contains判断是否有xx元素。 import java.util.HashSet; import java.util.Set; public class HashSetExample { public static void main(String[] args) { // 创建 HashSet Set<Integer> set = new HashSet<>(); // 添加元素 set.add(10); set.add(20); set.add(30); set.add(10); // 重复元素，不会被添加 // 检查元素是否存在 boolean contains20 = set.contains(20); System.out.println("Contains 20: " + contains20); // 输出 true // 遍历 HashSet for (int num : set) { System.out.println(num); } // 输出： // 20 // 10 // 30 // 删除元素 set.remove(20); System.out.println("After removal: " + set); // 输出 [10, 30] } } public void isHappy() { Set<Integer> set1 = new HashSet<>(List.of(1,2,3)); Set<Integer> set2 = new HashSet<>(List.of(2,3,1)); Set<Integer> set3 = new HashSet<>(List.of(3,2,1)); Set<Set<Integer>> sset = new HashSet<>(); sset.add(set1); sset.add(set2); sset.add(set3); } 这里最终sset的size为1 如何从List中初始化Set？ Set<String> set1 = new HashSet<>(wordList); //构造器直接初始化如何从Array中初始化？ Set<String> set1 = new HashSet<>(Arrays.asList(wordList)); //构造器直接初始化 PriorityQueue 基于优先堆（最小堆或最大堆）实现，元素按优先级排序。默认是最小堆，即队首元素是最小的。 new PriorityQueue<>(Comparator.reverseOrder());定义最大堆支持自定义排序规则，通过 Comparator 实现。常用方法： add(E e) / offer(E e)：功能：将元素插入队列。时间复杂度：O(log n) 区别 add：当队列满时会抛出异常。 offer：当队列满时返回 false，不会抛出异常。 remove() / poll()：功能：移除并返回队首元素。时间复杂度：O(log n) 区别 remove：队列为空时抛出异常。 poll：队列为空时返回 null。 element() / peek()：功能：查看队首元素，但不移除。时间复杂度：O(1) 区别 element：队列为空时抛出异常。 peek：队列为空时返回 null。 clear()：功能：清空队列。时间复杂度：O(n)（因为需要删除所有元素） import java.util.PriorityQueue; import java.util.Comparator; public class PriorityQueueExample { public static void main(String[] args) { // 创建 PriorityQueue（默认是最小堆） PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 添加元素 minHeap.add(10); minHeap.add(20); minHeap.add(5); // 查看队首元素 System.out.println("队首元素: " + minHeap.peek()); // 输出 5 // 遍历 PriorityQueue（注意：遍历顺序不保证有序） System.out.println("遍历 PriorityQueue:"); for (int num : minHeap) { System.out.println(num); } // 输出： // 5 // 10 // 20 // 移除队首元素 System.out.println("移除队首元素: " + minHeap.poll()); // 输出 5 // 再次查看队首元素 System.out.println("队首元素: " + minHeap.peek()); // 输出 10 // 创建最大堆（通过自定义 Comparator） PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); maxHeap.add(10); maxHeap.add(20); maxHeap.add(5); // 查看队首元素 System.out.println("最大堆队首元素: " + maxHeap.peek()); // 输出 20 // 清空队列 minHeap.clear(); System.out.println("队列是否为空: " + minHeap.isEmpty()); // 输出 true } } 自定义排序：按第二个元素的值构建小根堆如果比较器返回负数，则第一个数排在前面->优先级高->在堆顶 public class CustomPriorityQueue { public static void main(String[] args) { // 定义一个 PriorityQueue，其中每个元素是 int[]，并且按照数组第二个元素升序排列 PriorityQueue<int[]> minHeap = new PriorityQueue<>( (a, b) -> a[1] - b[1] ); // 添加数组 minHeap.offer(new int[]{1, 2}); minHeap.offer(new int[]{3, 4}); minHeap.offer(new int[]{0, 5}); // 依次取出元素，输出结果 while (!minHeap.isEmpty()) { int[] arr = minHeap.poll(); System.out.println(Arrays.toString(arr)); } } } 不用lambda版本： PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>() { @Override public int compare(int[] a, int[] b) { return a[1] - b[1]; } }); 自己实现小根堆：父节点：对于任意索引 i，其父节点的索引为 (i - 1) // 2。左子节点：索引为 i 的节点，其左子节点的索引为 2 * i + 1。右子节点：索引为 i 的节点，其右子节点的索引为 2 * i + 2。上滤与下滤操作上滤（Sift-Up）：用于插入操作。将新加入的元素与其父节点不断比较，若小于父节点则交换，直到满足堆序性质。下滤（Sift-Down）：用于删除操作或建堆。将根节点或某个节点与其子节点中较小的进行比较，若大于子节点则交换，直至满足堆序性质。建堆：从数组中最后一个非叶节点开始（索引为 heapSize/2 - 1），对每个节点执行下滤操作（sift-down）插入元素：将新元素插入到堆的末尾，然后执行上滤操作（sift-up），以保持堆序性质。弹出元素（删除堆顶）：弹出操作一般是删除堆顶元素（小根堆中即最小值），然后用堆尾元素替代堆顶，再进行下滤操作。 class MinHeap { private int[] heap; // 数组存储堆元素 private int size; // 当前堆中元素的个数 // 构造函数，初始化堆，capacity为堆的最大容量 public MinHeap(int capacity) { heap = new int[capacity]; size = 0; } // 插入元素：先将新元素添加到数组末尾，然后执行上滤操作恢复堆序性质 public void insert(int value) { if (size >= heap.length) { throw new RuntimeException("Heap is full"); } // 将新元素放到末尾 heap[size] = value; int i = size; size++; // 上滤操作：不断与父节点比较，若新元素小于父节点则交换 while (i > 0) { int parent = (i - 1) / 2; if (heap[i] < heap[parent]) { swap(heap, i, parent); i = parent; } else { break; } } } // 弹出堆顶元素：移除堆顶（最小值），用最后一个元素替换堆顶，然后下滤恢复堆序 public int pop() { if (size == 0) { throw new RuntimeException("Heap is empty"); } int min = heap[0]; // 将最后一个元素移到堆顶 heap[0] = heap[size - 1]; size--; // 对新的堆顶执行下滤操作，恢复堆序性质 minHeapify(heap, 0, size); return min; } // 建堆：将无序数组a构造成小根堆，heapSize为数组长度 public static void buildMinHeap(int[] a, int heapSize) { for (int i = heapSize / 2 - 1; i >= 0; --i) { minHeapify(a, i, heapSize); } } // 下滤操作：从索引i开始，将子树调整为小根堆 public static void minHeapify(int[] a, int i, int heapSize) { int l = 2 * i + 1, r = 2 * i + 2; int smallest = i; // 判断左子节点是否存在且比当前节点小 if (l < heapSize && a[l] < a[smallest]) { smallest = l; } // 判断右子节点是否存在且比当前最小节点小 if (r < heapSize && a[r] < a[smallest]) { smallest = r; } // 如果最小值不是当前节点，交换后继续对被交换的子节点执行下滤操作 if (smallest != i) { swap(a, i, smallest); minHeapify(a, smallest, heapSize); } } // 交换数组中两个位置的元素 public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } 改为大根堆只需要把里面 ''<'' 符号改为 ''>'' ArrayList 基于数组实现，支持动态扩展。访问元素的时间复杂度为 O(1)，在末尾插入和删除的时间复杂度为 O(1)。在指定位置插入和删除O(n) add(int index, E element) remove(int index) 复制链表(list set queue都有addAll方法，map是putAll)： List<Integer> list1 = new ArrayList<>(); // 假设 list1 中已有数据 List<Integer> list2 = new ArrayList<>(); list2.addAll(list1); //法一 List<Integer> list2 = new ArrayList<>(list1); //法二复制链表到数组：推荐老实遍历+添加。java自带方法有点复杂。清空(list set map queue map都有clear方法): List<Integer> list = new ArrayList<>(); // 清空 list list.clear(); import java.util.ArrayList; import java.util.List; public class ArrayListExample { public static void main(String[] args) { // 创建 ArrayList List<Integer> list = new ArrayList<>(); // 添加元素 list.add(10); list.add(20); list.add(30); int size = list.size(); // 获取列表大小 System.out.println("Size of list: " + size); // 输出 3 // 获取元素 int firstElement = list.get(0); System.out.println("First element: " + firstElement); // 输出 10 // 修改元素 list.set(1, 25); // 将第二个元素改为 25 System.out.println("After modification: " + list); // 输出 [10, 25, 30] // 遍历 ArrayList for (int num : list) { System.out.println(num); } // 输出： // 10 // 25 // 30 // 删除元素 list.remove(2); // 删除第三个元素 System.out.println("After removal: " + list); // 输出 [10, 25] } } 如果事先不知道嵌套列表的大小如何遍历呢？ import java.util.ArrayList; import java.util.List; int rows = 3; int cols = 3; List<List<Integer>> list = new ArrayList<>(); for (List<Integer> row : list) { for (int num : row) { System.out.print(num + " "); } System.out.println(); // 换行 } for (int i = 0; i < list.size(); i++) { List<Integer> row = list.get(i); for (int j = 0; j < row.size(); j++) { System.out.print(row.get(j) + " "); } System.out.println(); // 换行 } 数组（Array）数组是一种固定长度的数据结构，用于存储相同类型的元素。数组的特点包括：固定长度：数组的长度在创建时确定，无法动态扩展。快速访问：通过索引访问元素的时间复杂度为 O(1)。连续内存：数组的元素在内存中是连续存储的。 public class ArrayExample { public static void main(String[] args) { // 创建数组 int[] array = new int[5]; // 创建一个长度为 5 的整型数组 // 添加元素 array[0] = 10; array[1] = 20; array[2] = 30; array[3] = 40; array[4] = 50; // 获取元素 int firstElement = array[0]; System.out.println("First element: " + firstElement); // 输出 10 // 修改元素 array[1] = 25; // 将第二个元素改为 25 System.out.println("After modification:"); for (int num : array) { System.out.println(num); } // 输出： // 10 // 25 // 30 // 40 // 50 // 遍历数组 System.out.println("Iterating through array:"); for (int i = 0; i < array.length; i++) { System.out.println("Index " + i + ": " + array[i]); } // 输出： // Index 0: 10 // Index 1: 25 // Index 2: 30 // Index 3: 40 // Index 4: 50 // 删除元素（数组长度固定，无法直接删除，可以通过覆盖实现） int indexToRemove = 2; // 要删除的元素的索引 for (int i = indexToRemove; i < array.length - 1; i++) { array[i] = array[i + 1]; // 将后面的元素向前移动 } array[array.length - 1] = 0; // 最后一个元素置为 0（或其他默认值） System.out.println("After removal:"); for (int num : array) { System.out.println(num); } // 输出： // 10 // 25 // 40 // 50 // 0 // 数组长度 int length = array.length; System.out.println("Array length: " + length); // 输出 5 } } 复制数组： int[] source = {1, 2, 3, 4, 5}; int[] destination = Arrays.copyOf(source, source.length); int[] partialArray = Arrays.copyOfRange(source, 1, 4); //复制指定元素，不包括索引4 初始化： int double 数值默认初始化为0，boolean默认初始化为false int[] memo = new int[nums.length]; Arrays.fill(memo, -1); 二维数组 int rows = 3; int cols = 3; int[][] array = new int[rows][cols]; // 填充数据 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { array[i][j] = i * cols + j + 1; } } //创建并初始化 int[][] array = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; // 遍历二维数组，不知道几行几列 public void setZeroes(int[][] matrix) { // 遍历每一行 for (int i = 0; i < matrix.length; i++) { // 遍历当前行的每一列 for (int j = 0; j < matrix[i].length; j++) { // 这里可以处理 matrix[i][j] 的元素 System.out.print(matrix[i][j] + " "); } System.out.println(); // 换行，便于输出格式化 } } [[1, 0]] 是一行两列数组。 Queue 队尾插入，队头取！ import java.util.Queue; import java.util.LinkedList; public class QueueExample { public static void main(String[] args) { // 创建一个队列 Queue<Integer> queue = new LinkedList<>(); // 添加元素到队列中 queue.add(10); // 使用 add() 方法添加元素 queue.offer(20); // 使用 offer() 方法添加元素 queue.add(30); System.out.println("队列内容：" + queue); // 查看队头元素，不移除 int head = queue.peek(); System.out.println("队头元素（peek）： " + head); // 移除队头元素 int removed = queue.poll(); System.out.println("移除的队头元素（poll）： " + removed); System.out.println("队列内容：" + queue); // 再次移除队头元素 int removed2 = queue.remove(); System.out.println("移除的队头元素（remove）： " + removed2); System.out.println("队列内容：" + queue); } } Deque(双端队列+栈) 支持在队列的两端（头和尾）进行元素的插入和删除。这使得 **Deque 既能作为队列（FIFO）又能作为栈（LIFO）使用。**栈可以看作双端队列的特例，即使用一端。 LinkedList 是基于双向链表实现的，每个节点存储数据和指向前后节点的引用。 ArrayDeque 则基于动态数组实现，内部使用循环数组来存储数据。 ArrayDeque 在大多数情况下性能更好，因为数组在内存中连续，缓存友好，且操作（如 push/pop）开销更小。栈 Deque<Integer> stack = new ArrayDeque<>(); //Deque<Integer> stack = new LinkedList<>(); stack.push(1); // 入栈 Integer top1=stack.peek() Integer top = stack.pop(); // 出栈双端队列在队头操作 offerFirst(E e)：在队头插入元素，返回 true 或 false 表示是否成功。 peekFirst()：查看队头元素，不移除；队列为空返回 null。 pollFirst()：移除并返回队头元素；队列为空返回 null。在队尾操作 offerLast(E e)：在队尾插入元素，返回 true 或 false 表示是否成功。 peekLast()：查看队尾元素，不移除；队列为空返回 null。 pollLast()：移除并返回队尾元素；队列为空返回 null。添加元素：调用 offer(e) 时，实际上是调用 offerLast(e)，即在队尾添加元素。push(e)⇒ 等价于addFirst(e) 删除或查看元素：调用poll() 时，则是调用 pollFirst()，即在队头移除元素；同理， peek() 则是查看队头元素。 import java.util.Deque; import java.util.ArrayDeque; public class DequeExample { public static void main(String[] args) { // 使用 ArrayDeque 实现双端队列 Deque<Integer> deque = new ArrayDeque<>(); // 在队列头部添加元素 deque.addFirst(10); // 在队列尾部添加元素 deque.addLast(20); // 在队列头部插入元素（和 addFirst 类似，但失败时不会抛异常） deque.offerFirst(5); // 在队列尾部插入元素 deque.offerLast(30); System.out.println("双端队列内容：" + deque); // 查看队头和队尾元素，不移除 int first = deque.peekFirst(); int last = deque.peekLast(); System.out.println("队头元素：" + first); System.out.println("队尾元素：" + last); // 从队头移除元素 int removedFirst = deque.removeFirst(); System.out.println("移除队头元素：" + removedFirst); // 从队尾移除元素 int removedLast = deque.removeLast(); System.out.println("移除队尾元素：" + removedLast); System.out.println("双端队列最终内容：" + deque); } } Iterator HashMap、HashSet、ArrayList 和 PriorityQueue 都实现了 Iterable 接口，支持 iterator() 方法。 Iterator 接口中包含以下主要方法： hasNext()：如果迭代器还有下一个元素，则返回 true，否则返回 false。 next()：返回迭代器的下一个元素，并将迭代器移动到下一个位置。 remove()：从迭代器当前位置删除元素。该方法是可选的，不是所有的迭代器都支持。 import java.util.ArrayList; import java.util.Iterator; public class Main { public static void main(String[] args) { // 创建一个 ArrayList 集合 ArrayList<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); // 获取集合的迭代器 Iterator<Integer> iterator = list.iterator(); // 使用迭代器遍历集合并输出元素 while (iterator.hasNext()) { Integer element = iterator.next(); System.out.println(element); } } } 排序排序时间复杂度:O(nlog(n)) 求最大值：O(n) 快速排序基本思想：快速排序是一种基于“分治”思想的排序算法，通过选定一个“枢轴元素（pivot）”，将数组划分为左右两个子区间：左边都小于等于 pivot，右边都大于等于 pivot；然后对这两个子区间递归排序，最终使整个数组有序。 public class QuickSortWithSwap { // 交换数组中两个元素的位置 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static void quickSort(int[] arr, int low, int high) { if (low < high) { int pivotPos = partition(arr, low, high); // 划分 quickSort(arr, low, pivotPos - 1); // 递归排序左子表 quickSort(arr, pivotPos + 1, high); // 递归排序右子表 } } private static int partition(int[] arr, int low, int high) { int pivot = arr[low]; // 选取第一个元素作为枢轴 int left = low; // 左指针 int right = high; // 右指针 while (left < right) { // 从右向左找第一个小于枢轴的元素 while (left < right && arr[right] >= pivot) { right--; } // 从左向右找第一个大于枢轴的元素 while (left < right && arr[left] <= pivot) { left++; } // 交换这两个元素 if (left < right) { swap(arr, left, right); } } // 将枢轴放到最终位置 swap(arr, low, left); return left; // 返回枢轴的位置 } public static void main(String[] args) { int[] arr = {49, 38, 65, 97, 76, 13, 27, 49}; quickSort(arr, 0, arr.length - 1); System.out.println("\n排序后:"); for (int num : arr) { System.out.print(num + " "); } } } 冒泡排序基本思想：【每次将最小/大元素，通过依次交换顺序，放到首/尾位。】从后往前（或从前往后）两两比较相邻元素的值，若为逆序, 则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置）；下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置。 ……这样最多做n - 1趟冒泡就能把所有元素排好序。如若有一趟没有元素交换位置，则可提前说明已排好序。 public void bubbleSort(int[] arr){ //n-1 趟冒泡 for (int i = 0; i < arr.length-1; i++) { boolean flag=false; //冒泡 for (int j = arr.length-1; j >i ; j--) { if (arr[j-1]>arr[j]){ swap(arr,j-1,j); flag=true; } } //本趟遍历后没有发生交换，说明表已经有序 if (!flag){ return; } } } private void swap(int[] arr,int i,int j){ int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } 归并排序基本思想：将待排序的数组视为多个有序子表，每个子表的长度为 1，通过两两归并逐步合并成一个有序数组。实现思路分解：递归地将数组拆分成两个子数组，直到每个子数组只有一个元素。合并：将两个有序子数组合并为一个有序数组。时间复杂度： O(n log n)，无论最坏、最好、平均情况。 public class MergeSort { /** * 归并排序（入口函数） * @param arr 待排序数组 */ public static void mergeSort(int[] arr) { if (arr == null || arr.length <= 1) { return; // 边界条件 } int[] temp = new int[arr.length]; // 辅助数组 mergeSort(arr, 0, arr.length - 1, temp); } private static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = (right + left) / 2; mergeSort(arr, left, mid, temp); // 递归左子数组 mergeSort(arr, mid + 1, right, temp); // 递归右子数组 merge(arr, left, mid, right, temp); // 合并两个有序子数组 } } private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; // 左子数组起始指针 int j = mid + 1; // 右子数组起始指针 int t = 0; // 辅助数组指针 // 1. 按序合并两个子数组到temp while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { // 注意等号保证稳定性 temp[t++] = arr[i++]; } else { temp[t++] = arr[j++]; } } // 2. 将剩余元素拷贝到temp while (i <= mid) { temp[t++] = arr[i++]; } while (j <= right) { temp[t++] = arr[j++]; } // 3. 将temp中的数据复制回原数组 t = 0; while (left <= right) { arr[left++] = temp[t++]; } } } 数组排序默认升序： import java.util.Arrays; public class ArraySortExample { public static void main(String[] args) { int[] numbers = {5, 2, 9, 1, 5, 6}; Arrays.sort(numbers); // 对数组进行排序 System.out.println(Arrays.toString(numbers)); // 输出 [1, 2, 5, 5, 6, 9] } } Arrays.sort(nums, i + 1, n); 等价于把 nums[i+1] 到 nums[n-1] 这段做升序排序。自定义降序：注意：如果数组元素是对象（例如 Integer、String 或自定义类）那么可以利用 Arrays.sort() 方法配合自定义的比较器（Comparator）实现降序排序。例如，对于 Integer 数组，可以这样写： public class DescendingSortExample { public static void main(String[] args) { // 创建一个Integer数组 Integer[] arr = {5, 2, 9, 1, 5, 6}; // 使用Comparator进行降序排序（使用lambda表达式） Arrays.sort(arr, (a, b) -> Integer.compare(b, a)); // 或者使用Collections.reverseOrder()也可以： // 对下标 [1, 4) 的区间，也就是 {2,9,1}，按降序排序 Arrays.sort(arr, 1, 4, Collections.reverseOrder()); // 输出排序后的数组 System.out.println(Arrays.toString(arr)); } } 对于基本数据类型的数组（如 int[]、double[] 等），Arrays.sort() 方法仅支持升序排序，需要先对数组进行升序排序，然后反转数组元素顺序！。 public class DescendingPrimitiveSort { public static void main(String[] args) { int[] arr = {5, 2, 9, 1, 5, 6}; // 先排序（升序） Arrays.sort(arr); // 反转数组 for (int i = 0; i < arr.length / 2; i++) { int temp = arr[i]; arr[i] = arr[arr.length - 1 - i]; arr[arr.length - 1 - i] = temp; } // 输出结果 System.out.println(Arrays.toString(arr)); } } 集合排序 import java.util.ArrayList; import java.util.Collections; import java.util.List; public class ListSortExample { public static void main(String[] args) { // 创建一个 ArrayList 并添加元素 List<Integer> numbers = new ArrayList<>(); numbers.add(5); numbers.add(2); numbers.add(9); numbers.add(1); numbers.add(5); numbers.add(6); // 对 List 进行排序 Collections.sort(numbers); // 输出排序后的 List System.out.println(numbers); // 输出 [1, 2, 5, 5, 6, 9] } } 自定义排序要实现接口自定义排序，必须实现 Comparator<T> 接口的 compare(T o1, T o2) 方法。 Comparator 接口中定义的 compare(T o1, T o2) 方法返回一个整数（非布尔值！！），这个整数的正负意义如下：如果返回负数，说明 o1 排在 o2前面。如果返回零，说明 o1 等于 o2。如果返回正数，说明 o1 排在 o2后面。自定义比较器排序二维数组用Lambda表达式实现Comparator<int[]>接口 import java.util.Arrays; public class IntervalSort { public static void main(String[] args) { int[][] intervals = { {1, 3}, {2, 6}, {8, 10}, {15, 18} }; // 自定义比较器，先比较第一个元素，如果相等再比较第二个元素 Arrays.sort(intervals, (a, b) -> { if (a[0] != b[0]) { return Integer.compare(a[0], b[0]); } else { return Integer.compare(a[1], b[1]); } }); // 输出排序结果 for (int[] interval : intervals) { System.out.println(Arrays.toString(interval)); } } } 对象排序，不用lambda方式 import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; class Person { String name; int age; public Person(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return name + " (" + age + ")"; } } public class ComparatorSortExample { public static void main(String[] args) { // 创建一个 Person 列表 List<Person> people = new ArrayList<>(); people.add(new Person("Alice", 25)); people.add(new Person("Bob", 20)); people.add(new Person("Charlie", 30)); // 使用 Comparator 按姓名排序,匿名内部类形式 Collections.sort(people, new Comparator<Person>() { @Override public int compare(Person p1, Person p2) { return p1.name.compareTo(p2.name); // 按姓名升序排序 } }); // 使用 Comparator 按姓名排序，使用 lambda 表达式 //Collections.sort(people, (p1, p2) -> p1.name.compareTo(p2.name)); // 输出排序后的列表 System.out.println(people); // 输出 [Alice (25), Bob (20), Charlie (30)] } } 题型常见术语：子串（Substring）：子字符串是字符串中连续的非空字符序列回文串(Palindrome)：回文串是向前和向后读都相同的字符串。子序列（(Subsequence)）：可以通过删除原字符串中任意个字符（不改变剩余字符的相对顺序）得到的序列，不要求连续。例如 "abc" 的 "ac" 就是一个子序列。前缀 (Prefix) ：从字符串起始位置开始的连续字符序列，如 "leetcode" 的前缀 "lee"。字母异位词 (Anagram)：由相同字符组成但排列顺序不同的字符串。例如 "abc" 与 "cab" 就是异位词。子集、幂集：数组的子集是从数组中选择一些元素（可能为空）。例如，对于集合 S = {1, 2}，其幂集为： { ∅, {1}, {2}, {1, 2} }，子集有{1} 列表 “头插法”本质上就是把新节点“插”到已构建链表的头部 1.反转链表 2.从头开始构建链表（逆序插入） ListNode buildList(int[] arr) { ListNode head = null; for (int i = 0; i < arr.length; i++) { ListNode node = new ListNode(arr[i]); node.next = head; // 头插：新节点指向原 head head = node; // head 指向新节点 } return head; } // 结果链表的顺序是 arr 最后一个元素在最前面，如果你想保持原序，可以倒序遍历 arr。输入：arr[0] -> arr[1] -> … -> arr[n-1] 输出：arr[n-1]-> arr[n-2]-> …->arr[0] 哈希问题分析：确定是否需要快速查找或存储数据。判断是否需要统计元素频率或检查元素是否存在。适用场景快速查找：当需要频繁查找元素时，哈希表可以提供 O(1) 的平均时间复杂度。统计频率：统计元素出现次数时，哈希表是常用工具。去重：需要去除重复元素时，HashSet 可以有效实现。双指针题型：同向双指针：两个指针从同一侧开始移动，通常用于滑动窗口或链表问题。对向双指针：两个指针从两端向中间移动，通常用于有序数组或回文问题。重点是考虑移动哪个指针可能优化结果！！！快慢指针：两个指针以不同速度移动，通常用于链表中的环检测或中点查找。适用场景：有序数组的两数之和：在对向双指针的帮助下，可以在 O(n) 时间内找到两个数，使它们的和等于目标值。滑动窗口：用于解决子数组或子字符串问题，如同向双指针可以在 O(n) 时间内找到满足条件的最短或最长子数组。链表中的环检测：快慢指针可以用于检测链表中是否存在环，并找到环的起点。回文问题：对向双指针可以用于判断字符串或数组是否是回文。合并有序数组或链表：双指针可以用于合并两个有序数组或链表，时间复杂度为 O(n)。前缀和前缀和的定义定义前缀和 preSum[i] 为数组 nums 从索引 0 到 i 的元素和，即 $$ \text{preSum}[i] = \sum_{j=0}^{i} \text{nums}[j] $$ 子数组和的关系对于任意子数组 nums[i+1..j]（其中 0 ≤ i < j < n），其和可以表示为 $$ \text{sum}(i+1,j) = \text{preSum}[j] - \text{preSum}[i] $$ 当这个子数组的和等于 k 时，有 $$ \text{preSum}[j] - \text{preSum}[i] = k $$ 即 $$ \text{preSum}[i] = \text{preSum}[j] - k $$ $\text{preSum}[j] - k$表示 "以当前位置结尾的子数组和为k" 利用哈希表存储前缀和我们可以使用一个哈希表 prefix 来存储每个前缀和出现的次数。初始时，prefix[0] = 1，表示前缀和为 0 出现一次（对应空前缀）。遍历数组，每计算一个新的前缀和 preSum，就查看 preSum - k 是否在哈希表中。如果存在，则说明之前有一个前缀和等于 preSum - k，那么从该位置后一个位置到当前索引的子数组和为 k，累加其出现的次数。时间复杂度该方法只需要遍历数组一次，时间复杂度为 O(n)。遍历二叉树递归法中序 public void inOrderTraversal(TreeNode root, List<Integer> list) { if (root != null) { inOrderTraversal(root.left, list); // 遍历左子树 list.add(root.val); // 访问当前节点 inOrderTraversal(root.right, list); // 遍历右子树 } } 迭代法中序 public void inOrderTraversalIterative(TreeNode root, List<Integer> list) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { // 一路向左入栈 while (curr != null) { stack.push(curr); // push = addFirst curr = curr.left; } // 弹出栈顶并访问 curr = stack.pop(); // pop = removeFirst list.add(curr.val); // 转向右子树 curr = curr.right; } } 迭代法前序 public void preOrderTraversalIterative(TreeNode root, List<Integer> list) { if (root == null) return; Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); list.add(node.val); // 先访问当前节点 // 注意：先压右子节点，再压左子节点 // 因为栈是“后进先出”的，先弹出的是左子节点 if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } } 层序遍历BFS public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(level); } return result; } 回溯法回溯算法用于搜索一个问题的所有的解，即爆搜（暴力解法），通过深度优先遍历的思想实现。核心思想是： 1.逐步构建解答：回溯算法通过逐步构造候选解，当构造的部分解满足条件时继续扩展；如果发现当前解不符合要求，则“回溯”到上一步，尝试其他可能性。 2.剪枝（Pruning）：在构造候选解的过程中，算法会判断当前部分解是否有可能扩展成最终的有效解。如果判断出无论如何扩展都不可能得到正确解，就立即停止继续扩展该分支，从而节省计算资源。 3.递归调用回溯通常通过递归来实现。递归函数在每一层都尝试不同的选择，并在尝试失败或达到终点时返回上一层重新尝试其他选择。例：以数组 [1, 2, 3] 的全排列为例。先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列（注意：递归结构体现在这里）；再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。 public class Permute { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); // 用来标记数组中数字是否被使用 boolean[] used = new boolean[nums.length]; List<Integer> path = new ArrayList<>(); backtrack(nums, used, path, res); return res; } private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) { // 当path中元素个数等于nums数组的长度时，说明已构造出一个排列 if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; } // 遍历数组中的每个数字 for (int i = 0; i < nums.length; i++) { // 如果该数字已经在当前排列中使用过，则跳过 if (used[i]) { continue; } // 选择数字nums[i] used[i] = true; path.add(nums[i]); // 递归构造剩余的排列 backtrack(nums, used, path, res); // 回溯：撤销选择，尝试其他数字 path.remove(path.size() - 1); used[i] = false; } } } 大小根堆题目描述：给定一个整数数组 nums 和一个整数 k，返回出现频率最高的前 k 个元素，返回顺序可以任意。解法一：大根堆（最大堆）思路：使用 HashMap 统计每个元素的出现频率。构建一个大根堆（PriorityQueue + 自定义比较器），根据频率降序排列。将所有元素加入堆中，弹出前 k 个元素即为答案。适合场景：实现简单，适用于对全部元素排序后取前 k 个。时间复杂度：O(n log n)，因为需要将所有 n 个元素都加入堆。解法二：小根堆（最小堆）思路：使用 HashMap 统计频率。构建一个小根堆，堆中仅保存前 k 个高频元素。遍历每个元素：如果堆未满，直接加入。如果当前元素频率大于堆顶（最小频率），则弹出堆顶，加入当前元素。最终堆中保存的就是前 k 个高频元素。方法适合场景时间复杂度空间复杂度大根堆 k ≈ n，简单易写 O(n log n) O(n) 小根堆 k ≪ n，更高效 O(n log k) O(n) 动态规划解题步骤：确定 dp 数组以及下标的含义（很关键！不跑偏）目的：明确 dp 数组中存储的状态或结果。关键：下标往往对应问题中的一个“阶段”或“子问题”，而数组的值则表示这一阶段的最优解或累计结果。示例：在背包问题中，可以设 dp[i] 表示前 i 个物品能够达到的最大价值。确定递推公式目的：找到状态之间的转移关系，表明如何从已解决的子问题求解更大规模的问题。关键：分析每个状态可能来源于哪些小状态，写出数学或逻辑表达式。示例：对于 0-1 背包问题，递推公式通常为 $$ dp[i]=max⁡(dp[i],dp[i−weight]+value) $$ dp 数组如何初始化目的：给定初始状态，为所有可能情况设置基础值。关键：通常初始化基础的情况（如 dp[0]=0），或者用极大或极小值标示未计算状态。示例：在求最短路径问题中，可以用较大值（如 infinity）初始化所有状态，然后设定起点状态为 0。确定遍历顺序目的：按照正确的顺序计算每个状态，确保依赖的子问题都已经计算完毕。关键：遍历顺序需要与递推公式保持一致，既可以是正向（从小到大）也可以是反向（从大到小），取决于问题要求。示例：对背包问题，为避免重复计算，每个物品的更新通常采用反向遍历。举例推导 dp 数组目的：通过一个具体例子来演示递推公式的应用，直观理解每一步计算。关键：选择简单案例，从初始化、更新到最终结果展示整个过程。示例：对一个简单的路径问题，展示如何从起点逐步更新 dp 数组，最后得到终点的最优解。例题题目： 746. 使用最小花费爬楼梯 (MinCostClimbingStairs) 描述：给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。示例 2：输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。链接：https://leetcode.cn/problems/min-cost-climbing-stairs/ 1.确定dp数组以及下标的含义 dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。 2.确定递推公式可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。 dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。 dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); 3.dp数组如何初始化看一下递归公式，dp[i]由dp[i - 1]，dp[i - 2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]、dp[1]推出。由“你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” =》初始化 dp[0] = 0，dp[1] = 0 4.确定遍历顺序因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。 5.举例推导dp数组拿示例：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：背包问题总结：背包问题不仅可以求能装的物品的最大价值，还可以求背包是否可以装满，还可以求组合总和。背包是否可以装满示例说明假设背包容量为 10，物品的重量分别为 [3, 4, 7]。我们希望判断是否可以恰好填满容量 10。其中 dp[j] 表示在容量 j 下，能装入的最大重量（保证不超过 j）。如果dp[10]=10，代表能装满 public boolean canFillBackpack(int[] weights, int capacity) { // dp[j] 表示在不超过背包容量 j 的前提下，能装入的最大重量 int[] dp = new int[capacity + 1]; // 初始状态: 背包容量为0时，能够装入的重量为0，其他位置初始为0 // 遍历每一个物品（0/1背包，每个物品只能使用一次） for (int i = 0; i < weights.length; i++) { // 逆序遍历背包容量，防止当前物品被重复使用 for (int j = capacity; j >= weights[i]; j--) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + weights[i]); } } // 如果 dp[capacity] 恰好等于 capacity，则说明背包正好被装满 return dp[capacity] == capacity; } 求组合总和统计数组中有多少种组合（子集）使得其和正好为 P ？ dp[j] 表示从数组中选取若干个数，使得这些数的和正好为 j 的方法数。状态转移：对于数组中的每个数字 numnumnum，从 dp 数组后向前（逆序）遍历，更新： dp[j]=dp[j]+dp[j−num] 这里的意思是：如果不选当前数字，方法数保持不变；如果选当前数字，那么原来凑出和 j−num 的方案都可以扩展成凑出和 j 的方案。初始条件： dp[0] = 1，代表凑出和为 0 只有一种方式，即不选任何数字。代码随想录完全背包是01背包稍作变化而来，即：完全背包的物品数量是无限的。 0/1背包（一）描述：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 1.确定dp数组以及下标的含义因为有两个维度需要分别表示：物品和背包容量，所以 dp为二维数组。即 dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。 2. 确定递推公式考虑dp[i][j]，有两种情况：不放物品i：背包容量为j，里面不放物品i的最大价值是 dp[i - 1][j]。放物品i：背包空出物品i的容量后，背包容量为 j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 3. dp数组如何初始化（1）首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。（2）由状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。此时就看存放编号0的物品的时候，各个容量的背包所能存放的最大价值。（3）其他地方初始化为0 4.确定遍历顺序都可以，但推荐先遍历物品 // weight数组的大小就是物品个数 for(int i = 1; i < weight.size(); i++) { // 遍历物品 for(int j = 0; j <= bagweight; j++) { // 遍历背包容量 if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } } 5.举例推导dp数组略代码： public int knapsack(int[] weight, int[] value, int capacity) { int n = weight.length; // 物品的总个数 // 定义二维 dp 数组： // dp[i][j] 表示从下标为 [0, i] 的物品中任意选择，放入容量为 j 的背包中，能够获得的最大价值 int[][] dp = new int[n][capacity + 1]; // 1. 初始化第 0 行：只考虑第 0 个物品的情况 // 当背包容量 j >= weight[0] 时，可以选择放入第 0 个物品，价值为 value[0]；否则为 0 for (int j = 0; j <= capacity; j++) { if (j >= weight[0]) { dp[0][j] = value[0]; } else { dp[0][j] = 0; } } // 2. 状态转移：从第 1 个物品开始，逐步填表 // 遍历物品，物品下标从 1 到 n-1 for (int i = 1; i < n; i++) { // 遍历背包容量，从 0 到 capacity for (int j = 0; j <= capacity; j++) { // 情况一：不放第 i 个物品，则最大价值不变，继承上一行的值 dp[i][j] = dp[i - 1][j]; // 情况二：如果当前背包容量 j 大于等于物品 i 的重量，则考虑放入当前物品 if (j >= weight[i]) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]); } } } // 返回考虑所有物品，背包容量为 capacity 时的最大价值 return dp[n - 1][capacity]; } 0/1背包（二）可以将二维 dp 优化为一维 dp 的典型条件包括： 1.状态转移只依赖于之前的状态（例如上一行或上一个层次），而不是当前行中动态更新的状态。例如在 0/1 背包问题中，二维 dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i-1][j - weight[i]]。 2.存在确定的遍历顺序（例如逆序或正序）能够确保在更新一维 dp 时，所依赖的值不会被当前更新覆盖。逆序遍历：例如 0/1 背包问题，为了防止同一个物品被重复使用，需要对容量 j 从大到小遍历，确保 dp[j - weight] 的值还是上一轮（上一行）的。正序遍历：在一些问题中，如果状态更新不会导致当前状态被重复利用（例如完全背包问题），可以顺序遍历。 3.状态数足够简单，不需要记录多维信息，仅一个维度的状态即可准确表示和转移问题状态。 1.确定 dp 数组以及下标的含义使用一维 dp 数组 dp[j] 表示「在当前考虑的物品下，背包容量为 j 时能够获得的最大价值」。 2.确定递推公式当考虑当前物品 i（重量为 weight[i]，价值为 value[i]）时，有两种选择：不选当前物品 i：此时的最大价值为 dp[j]（即前面的状态没有变化）。选当前物品 i：当背包容量至少为 weight[i] 时，如果选择物品 i，剩余容量变为 j - weight[i]，则最大价值为 dp[j - weight[i]] 加上 value[i]。因此，状态转移方程为： $$ dp[j]=max⁡(dp[j], dp[j−weight[i]]+value[i]) $$ **3.dp 数组如何初始化** dp[0] = 0，表示当背包容量为 0 时，能获得的最大价值自然为 0。对于其他容量 dp[j]，初始值也设为 0，dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。确保值不被初始值覆盖即可。 4.一维dp数组遍历顺序外层遍历物品：从第一个物品到最后一个物品，依次做决策。内层遍历背包容量（逆序遍历）：遍历容量从 capacity 到当前物品的重量，进行状态更新。逆序遍历的目的在于确保当前物品在更新过程中只会被使用一次，因为 dp[j - weight[i]] 代表的是上一轮（当前物品未使用前）的状态，不会被当前物品更新后的状态覆盖。假设物品 $w=2$, $v=3$，背包容量 $C=5$。错误的正序遍历（$j=2 \to 5$） $j=2$: $dp[2] = \max(0, dp[0]+3) = 3$ $\Rightarrow dp = [0, 0, 3, 0, 0, 0]$ $j=4$: $dp[4] = \max(0, dp[2]+3) = 6$ $\Rightarrow$ 错误：物品被重复使用两次！ 5.举例推导dp数组略代码： public int knapsack(int[] weight, int[] value, int capacity) { int n = weight.length; // 定义 dp 数组，dp[j] 表示背包容量为 j 时的最大价值 int[] dp = new int[capacity + 1]; // 初始化：所有 dp[j] 初始为0，dp[0] = 0（无须显式赋值） // 外层：遍历每一个物品 for (int i = 0; i < n; i++) { // 内层：逆序遍历背包容量，保证每个物品只被选择一次 for (int j = capacity; j >= weight[i]; j--) { // 更新状态：选择不放入或者放入当前物品后的最大价值 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } // 返回背包总容量为 capacity 时获得的最大价值 return dp[capacity]; } 完全背包(一) 完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。例：背包最大重量为4，物品为：物品重量价值物品0 1 15 物品1 3 20 物品2 4 30 1. 确定dp数组以及下标的含义 dp[i][j] 表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。 2. 确定递推公式不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值递推公式： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]); 01背包中是 dp[i - 1][j - weight[i]] + value[i]) 因为在完全背包中，物品是可以放无限个，所以即使空出物品1空间重量，那背包中也可能还有物品1，所以此时我们依然考虑放物品0 和物品1 的最大价值即： dp[1][1]，而不是 dp[0][1]。而0/1背包中，既然空出物品1，那背包中也不会再有物品1，即dp[0][1]。 for (int i = 1; i < n; i++) { for (int j = 0; j <= capacity; j++) { // 不选物品 i，价值不变 dp[i][j] = dp[i - 1][j]; // 如果当前背包容量 j 能放下物品 i，则考虑选取物品 i（完全背包内层循环正序或逆序都可以，但这里通常建议正序） if (j >= weight[i]) { // 注意：这里选取物品 i 后仍然可以继续选取物品 i， // 所以状态转移方程为 dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]) dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i]] + value[i]); } } } 3. dp数组如何初始化如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。由递推公式，有一个方向 i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。即：存放编号0的物品的时候，各个容量的背包所能存放的最大价值。 for (int j = 0; j <= capacity; j++) { // 当 j 小于第 0 个物品重量时，无法选取，所以价值为 0 if (j < weight[0]) { dp[0][j] = 0; } else { // 完全背包允许多次使用物品 0，所以递归地累加 dp[0][j] = dp[0][j - weight[0]] + value[0]; } } 4. 确定遍历顺序先物品或先背包容量都可，但推荐先物品。完全背包（二）压缩成一维dp数组，也就是将上一层拷贝到当前层。将上一层dp[i-1] 的那一层拷贝到当前层 dp[i] ，那么递推公式由 dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]) 变成： dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]) 压缩成一维，即dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) 根据题型选择先遍历物品或者背包，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。组合不强调元素之间的顺序，排列强调元素之间的顺序。内层循环正序，不要逆序！因为要利用已经更新的dp数组，允许同一物品重复使用！注意，完全背包和0/1背包的一维dp形式的递推公式一样，但是遍历顺序不同！！多重背包有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。重量价值数量物品0 1 15 2 物品1 3 20 3 物品2 4 30 2 把每种物品按数量展开，就转化为0/1背包问题了！相当于物品0-a 物品0-b 物品1-a ....，每个只能用一次。 public int multipleKnapsack(int V, int[] weight, int[] value, int[] count) { // 将每件物品按数量展开成 0/1 背包的多个物品 List<Integer> wList = new ArrayList<>(); List<Integer> vList = new ArrayList<>(); for (int i = 0; i < weight.length; i++) { for (int k = 0; k < count[i]; k++) { wList.add(weight[i]); vList.add(value[i]); } } // 0/1 背包 DP int[] dp = new int[V + 1]; int N = wList.size(); for (int i = 0; i < N; i++) { int wi = wList.get(i); int vi = vList.get(i); for (int j = V; j >= wi; j--) { dp[j] = Math.max(dp[j], dp[j - wi] + vi); } } return dp[V]; } 并查集 for (int i = 0; i < 26; i++) { parent[i] = i; //初始化 } public void union(int[] parent, int index1, int index2) { // 先分别找到 index1 和 index2 的根节点，再把 root(index1) 的父指针指向 root(index2) parent[find(parent, index1)] = find(parent, index2); } //查找 index 元素所在集合的根节点（同时做路径压缩） public int find(int[] parent, int index) { // 当 parent[index] == index 时，说明已经是根节点 while (parent[index] != index) { // 路径压缩：将当前节点直接挂到它父节点的父节点上 // 这样可以让树变得更扁平，后续查找更快 parent[index] = parent[parent[index]]; // 跳到上一级，继续判断是否到根 index = parent[index]; } // 循环结束时，index 即为根节点下标 return index; } ACM风格输入输出 ** * 题目描述 * * 给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。 * * 输入描述 * * 第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。 * 输入示例： * 5 * 1 * 2 * 3 * 4 * 5 * 0 1 * 1 3 *输出： * 3 * 9 * 输出每个指定区间内元素的总和。 */ import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { // 快速 IO BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(System.out); String line; // 1）读数组长度 line = br.readLine(); if (line == null) return; int n = Integer.parseInt(line.trim()); // 2）读数组元素并构造前缀和 long[] prefix = new long[n + 1]; for (int i = 0; i < n; i++) { line = br.readLine(); if (line == null) throw new IOException("Unexpected EOF when reading array"); prefix[i + 1] = prefix[i] + Long.parseLong(line.trim()); } // 3）依次读查询直到 EOF // 每行两个整数 a, b (0 ≤ a ≤ b < n) while ((line = br.readLine()) != null) { line = line.trim(); if (line.isEmpty()) continue; StringTokenizer st = new StringTokenizer(line); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); // 区间和 = prefix[b+1] - prefix[a] long sum = prefix[b + 1] - prefix[a]; out.println(sum); } out.flush(); } } line.trim() 是把原 line 首尾的所有空白字符（空格、制表符、换行符等）都去掉之后的结果。 StringTokenizer st = new StringTokenizer(line);把一整行字符串 line 按默认的分隔符（空格、制表符、换行符等）拆成一个一个的“词”（token） StringTokenizer st = new StringTokenizer(line, ",;"); 第二个参数 ",;" 中的每个字符都会被当作分隔符；如果想把空白也当分隔符，可以在里边加上空格 " ,; "

自学

zy123 3月21日
0 2 0
2025-03-15
欢迎使用 Typecho 如果您看到这篇文章,表示您的 blog 已经安装成功.

默认分类

zy123 3月15日
1 9 0