0%

ubuntu22.04为k8s部署NFS

在本篇博客中,我将介绍如何在 Ubuntu 系统中部署 NFS 服务,并在 Kubernetes 节点之间共享存储。

1. 安装 NFS 服务

k8s-master 节点上,我们需要先安装 nfs-kernel-server。可以通过以下命令安装:

1
2
root@k8s-master:~# cd /opt
root@k8s-master:/opt# sudo apt install -y nfs-kernel-server

安装过程中,系统会提示安装一些必要的依赖包,例如 keyutilsnfs-commonrpcbind 等。

安装完成后,使用以下命令检查 NFS 服务是否已启动:

1
2
root@k8s-master:/opt# sudo systemctl start nfs-kernel-server
root@k8s-master:/opt# sudo systemctl enable nfs-kernel-server

2. 配置共享目录

这个根据实际配置,我这里在 k8s-master 上创建共享目录 k8s_store,并修改权限:

1
2
root@k8s-master:/opt# mkdir k8s_store
root@k8s-master:/opt# chmod 777 k8s_store/

查看目录内容:

1
root@k8s-master:/opt# ll -a

然后编辑 /etc/exports 文件,添加共享目录的配置:

1
root@k8s-master:/opt# vim /etc/exports

在文件末尾添加共享目录位置,我设置了以下行:

1
/opt/k8s_store  *(rw,sync,no_root_squash,no_subtree_check)

应用配置:

1
root@k8s-master:/opt# sudo exportfs -a

3. 启动 NFS 服务

启动并使 NFS 服务在系统启动时自动启动:

1
2
root@k8s-master:/opt# sudo systemctl start nfs-kernel-server
root@k8s-master:/opt# sudo systemctl enable nfs-kernel-server

4. 在客户端安装 NFS

接下来,在 k8s-node1 节点上安装 NFS 客户端:

1
root@k8s-node1:~# sudo apt install -y nfs-common

安装过程中,系统会提示安装一些依赖包,例如 rpcbind 等。

安装完成后,创建挂载点并挂载 NFS 共享目录:

1
2
root@k8s-node1:~# sudo mkdir -p /opt/k8s_store
root@k8s-node1:~# mount -t nfs 192.168.126.160:/opt/k8s_store /opt/k8s_store

完成

ubuntu22.04部署k8s1.23.6

Kubernetes 集群部署学习笔记(一):基础环境准备

记录时间:2026-02-19
系统环境:Ubuntu 22.04
本节内容:系统初始化与内核参数配置


一、切换 root 用户

1
sudo -i

后续操作大多涉及系统级修改,直接使用 root 用户进行。


二、关闭 Swap(必须)

Kubernetes 要求关闭 swap,否则 kubelet 无法正常启动。

1. 临时关闭

1
swapoff -a

2. 永久关闭

编辑 /etc/fstab

1
vi /etc/fstab

原内容中 swap 行:

1
# /swapfile                                 none            swap    sw              0       0

确保 swap 行被注释(前面加 #)。

查看确认:

1
cat /etc/fstab

三、加载内核模块

Kubernetes 网络依赖以下两个模块:

  • overlay
  • br_netfilter

创建配置文件:

1
2
3
4
cat <<EOF | tee /etc/modules-load.d/k8s.conf
overlay
br_netfilter
EOF

手动加载模块:

1
2
modprobe overlay
modprobe br_netfilter

查看是否加载成功:

1
2
lsmod | grep overlay
lsmod | grep br_netfilter

四、关闭防火墙(实验环境)

1
ufw disable

注意:生产环境不建议直接关闭防火墙,应配置规则放行端口。


五、设置时区与时间同步

统一所有节点时间非常重要,否则证书和集群通信可能出问题。

设置时区:

1
timedatectl set-timezone Asia/Shanghai

重启时间同步服务:

1
systemctl restart systemd-timesyncd.service

查看当前时间:

1
date

六、修改主机名

为不同节点设置独立主机名:

1
2
hostnamectl set-hostname k8s-node2
exec bash

七、配置 /etc/hosts

为了方便节点之间解析主机名,编辑:

1
vim /etc/hosts

内容示例:

1
2
3
4
5
6
127.0.0.1   localhost
127.0.1.1 k8s-node2

192.168.126.160 k8s-master
192.168.126.161 k8s-node1
192.168.126.162 k8s-node2

八、配置内核转发参数

Kubernetes 网络需要开启 IP 转发。

创建配置文件:

1
2
3
cat <<EOF | sudo tee /etc/sysctl.d/k8s.conf
net.ipv4.ip_forward = 1
EOF

如果有需要,可以同时加入

1
2
net.bridge.bridge-nf-call-iptables = 1
net.bridge.bridge-nf-call-ip6tables = 1

使配置生效:

1
sysctl --system

验证:

1
sysctl net.ipv4.ip_forward

输出应为:

1
net.ipv4.ip_forward = 1

九、本阶段小结

本节完成内容:

  • 关闭 swap
  • 加载关键内核模块
  • 关闭防火墙(实验环境)
  • 统一时区
  • 配置主机名
  • 设置 hosts 互相解析
  • 开启 IP 转发

这些属于 Kubernetes 部署前的基础系统准备工作。

下一步将进入容器运行时安装与 Kubernetes 组件安装。

Kubernetes 1.23.6 部署记录(二)——组件安装与镜像问题排查

系统环境:

  • Ubuntu 22.04.5 LTS
  • 内核版本:6.8.0-94-generic
  • 主机名:k8s-master
  • Kubernetes 版本:1.23.6

一、配置 Docker

kubelet的 cgroup driver 默认为 systemd,为了保证 Kubernetes 正常运行,需要将 Docker 的 cgroup driver 设置为 systemd。

创建或修改 /etc/docker/daemon.json

1
2
3
4
5
6
7
8
9
10
cat <<EOF | sudo tee /etc/docker/daemon.json
{
"exec-opts": ["native.cgroupdriver=systemd"],
"log-driver": "json-file",
"log-opts": {
"max-size": "10m"
},
"storage-driver": "overlay2"
}
EOF

重启并设置开机自启:

1
2
systemctl restart docker
systemctl enable docker

二、配置 Kubernetes 阿里云软件源

添加 apt key(虽然提示 deprecated,但当前仍可使用):

1
curl https://mirrors.aliyun.com/kubernetes/apt/doc/apt-key.gpg | apt-key add -

添加软件源:

1
echo "deb https://mirrors.aliyun.com/kubernetes/apt kubernetes-xenial main" >> /etc/apt/sources.list

更新索引:

1
apt-get update

会看到 legacy trusted.gpg 的警告,目前不影响安装。


三、安装指定版本 Kubernetes 组件

必须指定版本号,否则会安装最新版本。

1
apt-get install -y kubelet=1.23.6-00 kubeadm=1.23.6-00 kubectl=1.23.6-00

安装过程中会自动安装:

  • cri-tools
  • kubernetes-cni
  • conntrack
  • ebtables
  • socat

安装完成后锁定版本,防止自动升级:

1
apt-mark hold kubelet kubeadm kubectl

四、提前拉取控制面镜像

使用阿里云镜像仓库拉取 Kubernetes 所需镜像:

1
2
kubeadm config images pull \
--image-repository registry.cn-hangzhou.aliyuncs.com/google_containers

输出显示:

  • kube-apiserver
  • kube-controller-manager
  • kube-scheduler
  • kube-proxy
  • pause
  • etcd
  • coredns

提示远程版本较新,但自动回退到 stable-1.23,是正常现象。


五、Docker 拉取镜像失败问题

测试拉取:

1
docker pull nginx

报错:

1
context deadline exceeded

说明当前环境无法直接访问 Docker Hub。


六、配置 Docker 镜像加速/代理

编辑 /etc/docker/daemon.json,增加 registry-mirrors 字段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
"exec-opts": ["native.cgroupdriver=systemd"],
"log-driver": "json-file",
"log-opts": {
"max-size": "10m"
},
"storage-driver": "overlay2",
"registry-mirrors": [
"https://dockerproxy.com",
"https://docker.m.daocloud.io",
"https://hub.rat.dev",
"https://docker.xuanyuan.me",
"https://docker.1ms.run"
]
}

重新加载并重启:

1
2
sudo systemctl daemon-reload
sudo systemctl restart docker

验证配置是否生效:

1
docker info

确认:

  • Cgroup Driver: systemd
  • Storage Driver: overlay2
  • Registry Mirrors 已加载

再次执行:

1
docker pull nginx

仍然出现:

1
Get "https://registry-1.docker.io/v2/": context deadline exceeded

即使配置了镜像加速器,仍可能出现 docker pull nginx 超时(如 context deadline exceeded)。这通常由以下原因导致:

  • 加速器地址失效或网络不通
  • 节点网络出口受限(如防火墙、代理限制)
  • DNS 解析问题

解决方法

  • 尝试更换其他可用的加速器地址
  • 或者采用离线镜像分发方案(见部署记录(四))

如果加速器无效可以给docker配置代理:

① 创建 systemd 目录(如已存在可忽略)

1
sudo mkdir -p /etc/systemd/system/docker.service.d

② 创建 Docker 代理配置文件

1
sudo nano /etc/systemd/system/docker.service.d/proxy.conf

写入以下内容(代理服务器地址需要允许局域访问):

1
2
3
4
[Service]
Environment="HTTP_PROXY=http://192.168.1.100:7890"
Environment="HTTPS_PROXY=http://192.168.1.100:7890"
Environment="NO_PROXY=localhost,127.0.0.1,192.168.0.0/16,10.0.0.0/8,10.244.0.0/16,10.96.0.0/12,.cluster.local"

其中 NO_PROXY 配置非常关键,用于避免集群内部流量被错误地转发到代理。

如果未正确配置 NO_PROXY,可能导致以下问题:

  • Pod 内部访问异常
  • Kubernetes API Server 访问异常
  • Cilium 等 CNI 组件通信异常

上述问题通常表现为网络不可达或组件反复重启,严重时会导致集群不可用。

③ 重载 systemd 并重启 Docker 服务

1
2
sudo systemctl daemon-reload
sudo systemctl restart docker

④ 验证 Docker 是否已加载代理环境变量

1
systemctl show --property=Environment docker

期望看到类似输出:

1
2
HTTP_PROXY=http://192.168.1.100:7890
HTTPS_PROXY=http://192.168.1.100:7890

⑤ 拉取镜像进行验证

1
docker pull cr.fluentbit.io/fluent/fluent-bit:4.2.2

镜像能够成功拉取,说明 Docker 代理配置生效。

Kubernetes 1.23.6 部署记录(三)——初始化集群与安装 Cilium

一、初始化 Kubernetes 集群(跳过 kube-proxy)

由于后续使用 Cilium 并启用 kubeProxyReplacement,因此在初始化阶段跳过 kube-proxy 的安装。

执行:

1
2
3
4
5
kubeadm init \
--apiserver-advertise-address=192.168.126.160 \
--pod-network-cidr=10.244.0.0/16 \
--skip-phases=addon/kube-proxy \
--image-repository registry.cn-hangzhou.aliyuncs.com/google_containers

关键说明:

  • --apiserver-advertise-address:指定 apiserver 对外通信地址
  • --pod-network-cidr:指定 Pod 网段
  • --skip-phases=addon/kube-proxy:跳过 kube-proxy
  • --image-repository:使用阿里云镜像仓库

初始化成功后会提示:

1
Your Kubernetes control-plane has initialized successfully!

二、配置 kubectl 访问权限

根据提示执行:

1
2
3
mkdir -p $HOME/.kube
sudo cp -i /etc/kubernetes/admin.conf $HOME/.kube/config
sudo chown $(id -u):$(id -g) $HOME/.kube/config

验证节点状态:

1
kubectl get nodes

输出:

1
k8s-master   NotReady   control-plane,master   v1.23.6

此时 NotReady 是正常现象,因为尚未安装 CNI 网络插件。

查看系统 Pod:

1
kubectl get pods -n kube-system

可以看到:

  • apiserver、controller-manager、scheduler、etcd 均 Running
  • coredns 为 Pending

原因:尚未安装网络插件。


三、安装 Helm

使用官方脚本安装 Helm:

1
curl https://raw.githubusercontent.com/helm/helm/main/scripts/get-helm-3 | bash

验证:

1
helm version

四、使用 Helm 安装 Cilium

添加仓库:

1
2
helm repo add cilium https://helm.cilium.io/
helm repo update

安装 Cilium(版本 1.12.6):

1
2
3
4
5
6
helm install cilium cilium/cilium --version 1.12.6 \
--namespace kube-system \
--set k8sServiceHost=192.168.126.160 \
--set k8sServicePort=6443 \
--set kubeProxyReplacement=strict \
--set ipam.mode=kubernetes

参数说明:

  • k8sServiceHost:API Server 地址
  • k8sServicePort:API Server 端口
  • kubeProxyReplacement=strict:完全替代 kube-proxy
  • ipam.mode=kubernetes:使用 Kubernetes IPAM

安装成功后提示:

1
STATUS: deployed

五、验证集群状态

查看所有 Pod:

1
kubectl get po -A

结果:

  • cilium Pod Running
  • coredns 由 Pending 变为 Running
  • control-plane 组件正常

当前有一个 Pod 未就绪:

1
cilium-operator-xxxx   0/1   Pending

原因分析:

本实验环境为一主二从集群,目前仅有一个主节点。
Cilium Operator 默认存在 Pod 反亲和性规则,不允许调度到同一节点。
因此在只有一个节点时,会有一个副本 Pending。

当工作节点加入后,该 Pod 会自动调度并恢复正常。


六、加入工作节点

在从节点上执行初始化阶段输出的 join 命令,注意:token 默认有效期为 24 小时,如果之后需要添加新节点,请重新生成 token(kubeadm token create --print-join-command)。:

1
2
kubeadm join 192.168.126.160:6443 --token 5bhnb8.b0f6uopwwqb0t2xg \
--discovery-token-ca-cert-hash sha256:287c9c4ab79974eebecc5ddd1c36c033ac52c7c718cf3ab1f36365bb25db673c

加入成功后,在主节点查看:

1
kubectl get nodes

待节点 Ready 后,再查看:

1
kubectl get pods -n kube-system

此前 Pending 的 cilium-operator 将恢复为 Running。


当前阶段状态

  • control-plane 初始化完成
  • kube-proxy 已跳过
  • Cilium 已部署
  • CoreDNS 正常运行
  • 等待工作节点加入完成集群规模扩展

Kubernetes 1.23.6 部署记录(四)——Cilium 镜像离线分发处理

一、问题背景

在安装 Cilium 后,发现从节点拉取 quay.io/cilium/cilium 镜像速度极慢,导致:

  • Pod 长时间处于 Init 状态
  • Cilium 启动时间过久
  • 集群整体 Ready 时间被拖慢

因此采用离线镜像分发方式处理。


二、主节点导出 Cilium 镜像

在主节点确认镜像存在后,将镜像导出为 tar 包:

1
docker save quay.io/cilium/cilium:v1.12.6@sha256:454134506b0448c756398d3e8df68d474acde2a622ab58d0c7e8b272b5867d0d -o cilium.tar

查看文件:

1
ls

三、通过 scp 传输到从节点

首次执行:

1
scp *.tar root@192.168.126.161:/root/

报错:

1
ssh: connect to host 192.168.126.161 port 22: Connection refused

原因:从节点未安装或未启动 SSH 服务。


四、安装并启动 SSH 服务

在节点上执行:

1
2
sudo apt update
sudo apt install -y openssh-server

启动并设置开机自启:

1
2
sudo systemctl start ssh
sudo systemctl enable ssh

五、测试 SSH 连接

测试 root 登录:

1
ssh root@192.168.126.161

出现:

1
Permission denied (publickey,password)

说明 root 登录被禁用(默认安全策略)。

改用普通用户:

1
ssh user@192.168.126.161 "echo 'SSH connection successful'"

成功输出:

1
SSH connection successful

六、分发镜像文件

传输到两个从节点:

1
2
scp *.tar user@192.168.126.161:~
scp *.tar user@192.168.126.162:~

传输完成后,在对应从节点用户目录可以看到:

1
cilium.tar

七、从节点加载镜像

在每个从节点执行:

1
docker load -i cilium.tar

验证:

1
docker images | grep cilium

确认镜像已成功导入。


八、效果

加载完成后:

  • Cilium Pod 不再从公网拉取镜像
  • Init 时间明显缩短
  • 网络组件更快进入 Running 状态
  • 集群整体 Ready 时间提升

小结

当网络环境不稳定或镜像仓库访问缓慢时,可以采用:

  1. 主节点提前拉取镜像
  2. 使用 docker save 导出
  3. 使用 scp 分发
  4. 从节点 docker load 导入

这种方式适用于:

  • 内网环境
  • 无公网环境
  • 大规模节点初始化场景
  • 镜像拉取频繁超时场景

Kubernetes 集群部署验证与优雅关闭实践

一、集群功能验证

集群部署完成后,使用 nginx 进行功能验证。

创建 Deployment:

1
kubectl create deployment nginx --image=nginx

暴露为 NodePort 服务:

1
kubectl expose deployment nginx --port=80 --type=NodePort

查看资源状态:

1
kubectl get pod,svc

初始状态:

  • Pod 处于 ContainerCreating
  • Service 分配 NodePort 端口(例如 30795)

查看调度情况:

1
kubectl get pods -o wide

可以看到:

  • Pod 被调度到某个工作节点(如 k8s-node2)
  • 分配到 Pod 网段 IP(如 10.244.x.x)
  • 状态 Running

说明:

  • Cilium 网络正常
  • Pod 调度正常
  • Service 正常创建

二、优雅关闭集群脚本设计

目标:

  • 依次排空节点
  • 停止 kubelet 与 Docker
  • 最终安全关机

脚本依赖条件:

  • 已配置 SSH 免密登录
  • 已配置 sudo 免密码

脚本内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#!/bin/bash
# 优雅关闭 Kubernetes 集群脚本(使用 SSH 密钥认证)

SSH_USER="user"
MASTER_NODE="k8s-master"
WORKER_NODES=("k8s-node1" "k8s-node2")
ALL_NODES=("k8s-master" "k8s-node1" "k8s-node2")
SSH_OPTS="-o ConnectTimeout=10 -o ServerAliveInterval=5 -o StrictHostKeyChecking=no"

check_ssh() {
local node=$1
ssh -o BatchMode=yes -o ConnectTimeout=5 $SSH_USER@$node "exit" 2>/dev/null
if [ $? -ne 0 ]; then
echo "错误:无法免密登录到 $node"
exit 1
fi
}

echo "开始优雅关闭集群"

for node in "${ALL_NODES[@]}"; do
check_ssh "$node"
done

for node in "${WORKER_NODES[@]}"; do
kubectl drain "$node" --ignore-daemonsets --delete-emptydir-data
done

kubectl drain "$MASTER_NODE" --ignore-daemonsets --delete-emptydir-data

SERVICES="kubelet docker.socket docker"

for node in "${ALL_NODES[@]}"; do
ssh $SSH_OPTS $SSH_USER@$node "sudo systemctl stop $SERVICES"
done

echo "集群服务已停止"

三、SSH 免密配置

主节点生成密钥:

1
ssh-keygen -t rsa -b 4096 -N "" -f ~/.ssh/id_rsa

分发公钥:

1
2
3
ssh-copy-id user@k8s-master
ssh-copy-id user@k8s-node1
ssh-copy-id user@k8s-node2

四、配置 sudo 免密码

在每个节点执行:

1
2
echo "user ALL=(ALL) NOPASSWD: ALL" | sudo tee /etc/sudoers.d/user-nopasswd
sudo chmod 440 /etc/sudoers.d/user-nopasswd

五、Terminating 状态处理

如果存在 Pod 卡在 Terminating 状态,kubectl drain 可能会阻塞。

例如:

1
cilium-operator-xxxxx   Terminating

可以强制删除:

1
kubectl -n kube-system delete pod <pod-name> --force --grace-period=0

注意:

  • 这是立即删除
  • 可能存在残留资源
  • 仅在必要时使用

六、脚本执行效果

执行:

1
./close-claster.sh

执行过程:

  1. 校验 SSH 连接
  2. 依次 cordon + drain 工作节点
  3. 排空主节点
  4. 停止 kubelet 和 docker
  5. 输出关闭完成提示

验证服务状态:

1
2
systemctl status kubelet
systemctl status docker

状态应为:

1
Active: inactive (dead)

说明:

  • kubelet 已停止
  • docker 已停止
  • 容器已清理
  • 卷已卸载

七、最终关机

确认所有节点服务停止后:

1
shutdown -h now

至此集群已安全关闭。


本阶段总结

本阶段完成:

  • 集群功能验证
  • NodePort 服务验证
  • 优雅关闭流程设计
  • SSH 免密与 sudo 免密配置
  • Terminating Pod 异常处理

整体流程验证无误,可作为日常实验环境启停的标准操作流程。

Ubuntu 22.04 配置静态 IP

本文记录一次在 Ubuntu 22.04 系统中配置静态 IP 的过程。作为初学者,整理操作步骤与关键点,便于后续复现和排查问题。


一、环境说明

  • 系统版本:Ubuntu 22.04
  • 主机名:node0
  • 网卡名称:ens33
  • 配置目标:将 DHCP 修改为静态 IP

二、修改 Netplan 配置文件

Ubuntu 18.04 及以后版本默认使用 Netplan 管理网络配置,相关文件位于:

1
/etc/netplan/

编辑之前,可选使用cp指令备份原文件。

1. 编辑配置文件

1
root@node0:/etc/netplan# vim 01-network-manager-all.yaml

配置内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
network:
ethernets:
ens33: # 网卡名称
dhcp4: false
addresses:
- 192.168.126.160/24 # 静态IP

routes:
- to: default
via: 192.168.126.2 # 网关

nameservers:
addresses: [8.8.8.8,114.114.114.114,192.168.126.2]
version: 2
renderer: NetworkManager

2. 参数说明

  • dhcp4: false:关闭 IPv4 DHCP
  • addresses:设置静态 IP 地址及子网掩码
  • routes:配置默认网关
  • nameservers:设置 DNS 服务器
  • renderer:指定网络管理方式

需要注意,YAML 文件对缩进要求严格,只能使用空格,不能使用 Tab。


三、生成并应用配置

1
2
root@node0:/etc/netplan# netplan generate
root@node0:/etc/netplan# netplan apply

若无报错信息,说明配置语法正确。

  • netplan generate:根据 /etc/netplan/ 目录下的 YAML 配置文件生成后端(NetworkManager)可用的实际配置文件,相当于“编译”配置但尚未应用。
  • netplan apply:将生成的配置立即应用到系统中,包括重启网络服务、重新配置网络接口,使静态 IP 等设置生效。

四、启动并检查网卡状态

1. 启动网卡

1
root@node0:/etc/netplan# ip link set ens33 up

2. 查看网卡状态

1
root@node0:/etc/netplan# ip link show ens33

输出信息中若包含 UP,表示网卡已正常启用。


五、验证 IP 配置结果

1
root@node0:/etc/netplan# ip a

可以看到如下内容:

1
inet 192.168.126.160/24 brd 192.168.126.255 scope global noprefixroute ens33

说明静态 IP 已成功生效。


六、测试网络连通性

1
root@node0:/etc/netplan# ping baidu.com

结果显示:

1
3 packets transmitted, 3 received, 0% packet loss

说明 DNS 解析正常,网关配置正确,网络可以正常访问外部地址。


七、问题记录

  1. YAML 缩进错误会导致 netplan apply 执行失败。
  2. 配置前应先通过 ip a 确认实际网卡名称。

八、小结

通过本次实践,了解了 Ubuntu 22.04 使用 Netplan 进行网络管理的基本方法。静态 IP 配置主要涉及 IP 地址、网关和 DNS 三部分内容。实际操作中需特别注意配置文件格式与缩进问题。

本文作为个人操作记录,供后续参考。

原地标记

题目要求原地完成,因此不能直接额外开两个数组记录哪些行和哪些列要置零。一个常见做法是把第一行和第一列当作标记位来使用。

先单独记录第一行是否原本就含有 $0$,记为 firstRow。随后遍历除第一行之外的所有位置,如果 matrix[i][j] == 0,就把 matrix[i][0]matrix[0][j] 置为 $0$,分别表示第 $i$ 行和第 $j$ 列最终都要变成 $0$。

最后再倒序遍历整个矩阵。对于非第一行元素,只要所在行或所在列的标记为 $0$,就将当前位置置零;对于第一行,则根据 firstRow 决定是否全部置零。之所以倒序处理,是为了避免过早修改第一行和第一列中的标记,影响后续判断。

时间复杂度 $O(mn)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int firstRow = 1;
for (int j = 0; j < n; ++j) {
firstRow = matrix[0][j] == 0 ? 0 : firstRow;
}
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (i == 0) {
if (firstRow == 0) {
matrix[i][j] = 0;
}
} else {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
}
}
}

矩阵转置

顺时针旋转 $90^\circ$ 可以拆成两步来做。

第一步先沿主对角线转置,也就是交换 $matrix[i][j]$ 和 $matrix[j][i]$。这样原来的行就变成了列。第二步再将每一行左右翻转,就完成了顺时针旋转。

例如转置后,矩阵元素的位置关系已经接近目标结果,再通过每行反转把列顺序调整过来,最终就得到顺时针旋转后的矩阵。整个过程都在原数组上进行,满足题目要求的原地操作。

时间复杂度 $O(n^2)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; ++j) {
int tmp = matrix[j][i];
matrix[j][i] = matrix[i][j];
matrix[i][j] = tmp;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; ++j) {
int tmp = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = matrix[i][j];
matrix[i][j] = tmp;
}
}
}
}

模拟

螺旋遍历本质上就是按照右、下、左、上的顺序不断前进,当走到边界时再转向。

因此可以维护当前方向,以及当前还能走的上下左右边界。每次先尝试沿当前方向继续走,如果下一步越界,就说明这一圈对应方向已经走完了,需要切换方向,同时收缩对应边界。之后继续前进并记录答案,直到遍历完全部元素。

时间复杂度 $O(mn)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[] ans = new int[m * n];
int dir = 3, idx = 0;
int left = -1, ceil = 0, right = n - 1, floor = m - 1;
int x = 0, y = -1;
while (idx < ans.length) {
int nx = x + DIRS[dir][0];
int ny = y + DIRS[dir][1];
if (nx < ceil || ny > right || nx > floor || ny < left) {
dir = (dir + 1) % 4;
if (nx < ceil) {
left++;
} else if (ny > right) {
ceil++;
} else if (nx > floor) {
right--;
} else {// ny < left
floor--;
}
}
x = x + DIRS[dir][0];
y = y + DIRS[dir][1];
ans[idx] = matrix[x][y];
idx++;
}
return Arrays.stream(ans) // 将int数组转换为IntStream流
.boxed() // 将基本int类型自动装箱为Integer对象
.collect(Collectors.toList()); // 将流收集到List<Integer>中
}
}

按层遍历

也可以把矩阵看成一层一层的“环”。

每一轮依次遍历当前最上面一行、最右边一列、最下面一行、最左边一列,然后收缩上下左右四个边界,继续处理下一层。需要注意的是,当矩阵只剩下一行或一列时,要额外判断边界是否仍然有效,避免重复加入元素。

这种写法更直观,也更符合手动模拟螺旋遍历的过程。

时间复杂度 $O(mn)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int i = left; i <= right; i++) {
ans.add(matrix[top][i]);
}
top++;
for (int i = top; i <= bottom; i++) {
ans.add(matrix[i][right]);
}
right--;
if (top <= bottom) {
for (int i = right; i >= left; i--) {
ans.add(matrix[bottom][i]);
}
bottom--;
}

if (left <= right) {
for (int i = bottom; i >= top; i--) {
ans.add(matrix[i][left]);
}
left++;
}
}
return ans;
}
}

模拟

题目只要求判断当前数独是否合法,不要求真的解出数独。因此只需要按规则检查每个已经填入的数字是否重复出现即可。

数独的合法性有三条约束:同一行不能重复,同一列不能重复,同一个 $3 \times 3$ 宫内也不能重复。遍历棋盘时,遇到数字就分别检查它在对应的行、列、宫中是否已经出现过,如果出现过则直接返回 false;否则标记为已出现。

其中第几个宫可以通过公式 $k = (i / 3) \times 3 + j / 3$ 计算得到。

时间复杂度 $O(1)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public boolean isValidSudoku(char[][] board) {
int[][][] map = new int[3][10][10];// 行 列 块 - 第k个 - 数字是否出现
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
continue;
}
int num = board[i][j] - '0';
int k = (i / 3) * 3 + j / 3; // or (i - i % 3) + j / 3
if (map[0][i][num] > 0 || map[1][j][num] > 0 || map[2][k][num] > 0) {
return false;
}
map[0][i][num]++;
map[1][j][num]++;
map[2][k][num]++;
}
}
return true;
}
}

滑动窗口

题目要求的是最长的不含重复字符的子串,看到“子串”并且需要维护一段连续区间时,通常可以考虑滑动窗口。

用两个指针维护当前窗口 $[left, right)$,并用数组记录每个字符在窗口中是否出现过。每次将右端字符加入窗口前,若发现它已经在窗口内出现过,就不断移动左指针并删除左侧字符,直到这个重复字符被移出窗口。这样可以保证任意时刻窗口内都没有重复字符。

随后用当前窗口长度更新答案即可。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, right = 0, n = s.length();
int ans = 0;
int[] map = new int[128];
while (right < n) {
char cur = s.charAt(right);
right++;

while (map[cur] == 1) {
map[s.charAt(left)]--;
left++;
}
map[cur]++;

ans = Math.max(ans, right - left);
}
return ans;
}
}

滑动窗口

由于数组中的元素全部都是正整数,这意味着当右端点向右移动时,窗口和只会增大;当左端点向右移动时,窗口和只会减小。这个单调性非常适合使用滑动窗口。

用两个指针维护一个区间 $[left, right]$,不断扩大右端点,把当前元素加入窗口和中。一旦窗口和已经大于等于 $target$,就说明当前窗口是一个合法解,此时尝试不断收缩左端点,看看能否在仍然满足条件的前提下把长度变得更短。整个过程中更新最小长度即可。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0, n = nums.length;
int ans = Integer.MAX_VALUE, curSum = 0;
while (right < n) {
curSum += nums[right];
right++;
while (curSum >= target) {
ans = Math.min(ans, right - left);
curSum -= nums[left];
left++;
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}

排序+双指针

题目要求找出所有和为 $0$ 的不重复三元组。一个很自然的想法是先固定一个数,再去剩余部分中寻找两个数,使三者和为 $0$。

为了高效寻找这两个数,可以先对数组排序。这样在固定 $nums[k]$ 后,就能在区间 $[0, k - 1]$ 中使用双指针查找两数之和是否等于 $-nums[k]$。如果当前和偏小,就让左指针右移;如果当前和偏大,就让右指针左移;如果恰好相等,就记录答案。

排序之后还可以方便地去重。固定的第三个数如果和上一次相同,就直接跳过;找到一组合法答案后,也要分别跳过左侧和右侧的重复元素,避免加入重复三元组。

时间复杂度 $O(n^2)$

空间复杂度 $O(\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for (int k = nums.length - 1; k >= 2; k--) {
if (k < nums.length - 1 && nums[k] == nums[k + 1]) {
continue;
}
int i = 0, j = k - 1;
while (i < j) {
if (nums[i] + nums[j] == -nums[k]) {
ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
while (i < j && nums[i] == nums[i + 1]) {
i++;
}
while (i < j && nums[j] == nums[j - 1]) {
j--;
}
j--;
i++;
} else if (nums[i] + nums[j] < -nums[k]) {
i++;
} else {
j--;
}
}
}
return ans;
}
}