算法模式:双指针

算法模式:双指针

D瓜哥
在上一篇文章 算法模式:区间合并 介绍了合并区间所用的算法模式。本篇文章,介绍一个即可以用在数组,又可以用在链表中的算法模式:双指针。 双指针 双指针是这样的模式:两个指针朝着左右方向移动(双指针分为同向双指针和异向双指针),直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如,你需要去比较数组中每个元素和其他元素的关系时,你就需要用到双指针了。 需要双指针的原因是:如果你只用一个指针的话,你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了 — 这是考虑算法的复杂度分析的时候的重要概念。虽然 Brute F orce 一个指针的解法可能会奏效,但时间复杂度一般会是 \$O(n^2)\$。在很多情况下,双指针能帮助我们找到空间或是时间复杂度更低的解。 识别使用双指针的招数: 一般来说,数组或是链表是排好序的,你得在里头找一些组合满足某种限制条件 这种组合可能是一对数,三个数,或是一个子数组 LeetCode 15. 三数之和 LeetCode - 15. 三数之和 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 示例 1: 输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] 解释: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意,输出的顺序和三元组的顺序并不重要。
算法模式:快慢指针

算法模式:快慢指针

D瓜哥
在上一篇文章 算法模式:双指针 介绍了双指针模式。本篇文章,再介绍一个即可以用在数组,又可以用在链表中的算法模式:快慢指针。快慢指针,其实是双指针模式的一个变种。所以,两者在很多地方有相通之处。 快慢指针 快慢指针模式,有一个非常出名的名字,叫龟兔赛跑。大家肯定都知道龟兔赛跑啦。但还是再解释一下快慢指针:这种算法的两个指针的在数组上(或是链表上,序列上)的移动速度不一样。还别说,这种方法在解决有环的链表和数组时特别有用。 通过控制指针不同的移动速度(比如在环形链表上),这种算法证明了他们肯定会相遇的。快的一个指针肯定会追上慢的一个(可以想象成跑道上面跑得快的人套圈跑得慢的人)。 咋知道需要用快慢指针模式勒? 问题需要处理环上的问题,比如环形链表和环形数组 当你需要知道链表的长度或是某个特别位置的信息的时候 那啥时候用快慢指针而不是上面的双指针呢? 有些情形下,咱们不应该用双指针,比如我们在单链表上不能往回移动的时候。一个典型的需要用到快慢指针的模式的是当你需要去判断一个链表是否是回文的时候。 LeetCode 141. 环形链表 LeetCode - 141. 环形链表 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。 如果链表中存在环 ,则返回 true 。 否则,返回 false 。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。 示例 2: 输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。 示例 3: 输入:head = [1], pos = -1 输出:false 解释:链表中没有环。
算法模式:区间合并

算法模式:区间合并

D瓜哥
在上一篇文章 算法模式:改进的二分查找 介绍了二分查找以及相关变种。本篇文章,继续介绍数组相关的算法模式:区间合并。 区间合并 区间合并模式是一个用来处理有区间重叠的很高效的技术。在涉及到区间的很多问题中,通常咱们需要要么判断是否有重叠,要么合并区间,如果他们重叠的话。这个模式是这么起作用的。 给两个区间,一个是 a,另外一个是 b。别小看就两个区间,他们之间的关系能跑出来6种情况。详细的就看图啦。 图 1. 区间关系 观察这六种排序,明显后三种排序是前三种排序的一个“变种”:对区间根据起点和终点进行排序,就是剩下前三种排序了。再对其进行合并就很简单了: 没有重叠,则直接开启新区间。 有重叠,起点和终点分别取最大值和最小值即可:由于区间已经排序,则相邻两个区间的起点是前面区间的起点,重点则是两个区间终点的最大值。 LeetCode 56. 合并区间 LeetCode - 56. 合并区间 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 示例 1: 输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。 提示: 1 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti<= endi<= 104 思路分析 上面已经分析过解题思路,这里直接上代码:
算法模式:改进的二分查找

算法模式:改进的二分查找

D瓜哥
在上一篇文章 算法模式:前缀和 介绍了前缀和的算法模式。本篇文章,继续介绍数组相关的算法模式:改进的二分查找。 二分查找 二分查找相比每一个学过计算机算法的小伙伴都了解,时间复杂度是: \$\log_2N\$,是一个非常高效的数组查找算法。当然,前提是数组必须有序。过程如下: 图 1. 二分查找 LeetCode 704. 二分查找 就是一个标准的二分查找的算法题。代码如下: /** * @author D瓜哥 · https://www.diguage.com * @since 2024-09-14 19:52:26 */ public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } 除了在排序数组中查找特定的值,二分查找还可以用于找边界和在旋转数组中查值。 找边界:LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 LeetCode - 34. 在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 \$log_2n\$ 的算法解决此问题。 示例 1: 输入:nums = [5,7,7,8,8,10], target = 8 输出:[3,4] 示例 2: 输入:nums = [5,7,7,8,8,10], target = 6 输出:[-1,-1] 示例 3: 输入:nums = [], target = 0 输出:[-1,-1]
算法模式:前缀和

算法模式:前缀和

D瓜哥
在上一篇文章 算法模式:差分数组,本篇文章,继续介绍数组相关的算法模式:前缀和。 前缀和 前缀和可以简单理解为「数列的前 n 项的和」。具体过程如图所示: 图 1. 前缀和 这是一种重要的预处理方式,也就是需要额外的空间并且提前计算好这些值。如果使用得当,能大大降低查询的时间复杂度。 LeetCode 303. 区域和检索 - 数组不可变 LeetCode - 303. 区域和检索 - 数组不可变 给定一个整数数组 nums,处理以下类型的多个查询: 计算索引 left 和 right (包含 left 和 right)之间的 nums 元素的 和 ,其中 left <= right 实现 NumArray 类: NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的元素的 总和,包含 left 和 right 两点(也就是 nums[left] + nums[left + 1] + …​ + nums[right] )
算法模式:差分数组

算法模式:差分数组

D瓜哥
Christopher Alexander 在 《建筑的永恒之道》 中说:“每一个模式描述了一个在我们周围不断重复发生的问题,以及该问题的解决方案的核心。这样,你就能一次又一次地使用该方案而不必做重复劳动。”受此影响,GoF 总结经验,写出了著名的 《设计模式》。 在算法中,也有很多类似设计模式这样的解决方案。D瓜哥称其为“算法模式”。后面,慢慢写文章一一介绍一下。由浅及深,今天先来介绍最简单的一个模式:差分数组。 差分数组 差分数组:差分数组就是原始数组相邻元素之间的差。举例如下: 下标 0 1 2 3 4 5 原始数组 5 9 2 6 5 3 差分数组 5 4 -7 4 -1 -2 差分数组是从原始数组构造出来的一个辅助数组,表示相邻元素直接的差值。可用于解决需要对数组一个区间内同时做加减的操作。比如:随着公交站各个站台上下车,判断公交车是否超载。 LeetCode 370. 区间加法 LeetCode - 370. 区间加法 假设你有一个长度为 n 的数组,初始情况下所有的数字均为 0,你将会被给出 k 个更新的操作。
玩转 Kubernetes(一):离线安装 Kubernetes 2

玩转 Kubernetes(一):离线安装 Kubernetes 2

D瓜哥
在 玩转 Kubernetes(一):离线安装 Kubernetes 1 中,D瓜哥基于 Kubespray 进行魔改的脚本搭建起来容器镜像仓库。但是,每次都魔改着实麻烦,所以,探索 Kubespray 原生支持才是更为委托的长久之计。 经过多次探索,终于,可以几乎无需魔改就可以利用 Kubespray 原生支持进行 Kubernetes 的离线安装。 以下是在 Mac 上的操作,在 Linux 等系统上操作类似。 按照 Python 依赖 在 Mac 的虚拟机离线安装 Kubernetes,使用 Mac 当做容器镜像服务器和二进制安装文件下载服务器是一个非常好的选择。为此,需要在完成一些基本的操作。 由于运行 Kubespray,需要一个 Python 环境以及相关依赖,所以,就需要先安装相关依赖。 # 配置 Python 镜像 pip config set global.index-url https://mirrors.tuna.tsinghua.edu.cn/pypi/web/simple # 进入 Kubespray 的上层目录 cd /PATH/TO/kubespray/.. # 按照 Python 相关依赖 VENVDIR=kubespray-venv KUBESPRAYDIR=kubespray python3 -m venv $VENVDIR source $VENVDIR/bin/activate cd $KUBESPRAYDIR pip install -U -r requirements.txt 生成镜像列表及二进制文件列表 安装完相关依赖,就需要生成相关文件列表: # 生成镜像列表以及相关二进制文件列表 cd /PATH/TO/kubespray/contrib/offline ./generate_list.sh 注意:大多数情况下,我们的安装目标是 Linux。所以,建议这步操作在 Linux 上完成,这样得到的下载文件列表是 Linux 格式的。在 Mac 上完成,那么部分文件的格式就是 Mac 的,不能用于 Linux 的安装。
玩转 Kubernetes(一):离线安装 Kubernetes 1

玩转 Kubernetes(一):离线安装 Kubernetes 1

D瓜哥
在 基于 Docker 搭建开发环境(三):链路追踪 等几篇文章中,D瓜哥分享了如何使用 Docker Compose 在本地搭建起来一套应用可观测性环境。感觉还不够好玩,毕竟正在在企业中,Kubernetes 已经是绝对的主流。要玩就玩最具挑战性的东西,玩最符合企业所需的技能和工具。所以,打算将上面那套简易玩具,按照企业级的要求,搬到 Kubernetes 上去。 如果想玩 Kubernetes,首先面临的一个问题就是 Kubernetes 集群的搭建。本来是一个非常简单的事情,但是由于众所周知的原因,变得非常具有挑战性。经过各种探索和多次试验,发现一种“离线”安装方式,感觉是一个不错的方式。 本方法是基于 Kubespray 的一种安装办法,Kubespray 是由 Kubernetes SIG 小组来负责维护的一整套安装方式。既可以支持在裸机环境上安装,也支持云上环境安装。而且,只需要简单几行可以复制粘贴的命令,即可完成安装工作。非常适合入门玩耍使用。 本安装方法所需的软件,D瓜哥都已经上传到 GitHub,如果需要下载,请移步: Kubespray-2.26.0 安装包大全。 搭建服务器集群 这里推荐使用 Vagrant 搭建集群。搭配 VirtualBox,只需要一个配置文件,就可以轻轻松松搭建一个 Linux 服务器集群。搭建集群的配置文件 Vagrantfile 如下: # -*- mode: ruby -*- # vi: set ft=ruby : # @author D瓜哥 · https://www.diguage.com/ # All Vagrant configuration is done below. The "2" in Vagrant.configure # configures the configuration version (we support older styles for # backwards compatibility). Please don't change it unless you know what # you're doing. Vagrant.configure("2") do |config| # The most common configuration options are documented and commented below. # For a complete reference, please see the online documentation at # https://docs.vagrantup.com # 三节点集群 (1..3).each do |i| config.vm.define "node#{i}" do |node| # Every Vagrant development environment requires a box. You can search for # boxes at https://vagrantcloud.com/search node.vm.box = "alvistack/ubuntu-24.04" node.vm.box_version = "20250210.0.0" # 设置虚拟机的主机名 node.vm.hostname = "node#{i}" config.vm.boot_timeout = 600 # Disable automatic box update checking. If you disable this, then # boxes will only be checked for updates when the user runs # `vagrant box outdated`. This is not recommended. # config.vm.box_check_update = false # Create a forwarded port mapping which allows access to a specific port # within the machine from a port on the host machine. In the example below, # accessing "localhost:8080" will access port 80 on the guest machine. # NOTE: This will enable public access to the opened port # config.vm.network "forwarded_port", guest: 80, host: 8080 # Create a forwarded port mapping which allows access to a specific port # within the machine from a port on the host machine and only allow access # via 127.0.0.1 to disable public access # config.vm.network "forwarded_port", guest: 80, host: 8080, host_ip: "127.0.0.1" # Create a private network, which allows host-only access to the machine # using a specific IP. # 设置虚拟机的IP node.vm.network "private_network", ip: "10.0.2.#{20+i}", auto_config: true # Create a public network, which generally matched to bridged network. # Bridged networks make the machine appear as another physical device on # your network. # config.vm.network "public_network" # Share an additional folder to the guest VM. The first argument is # the path on the host to the actual folder. The second argument is # the path on the guest to mount the folder. And the optional third # argument is a set of non-required options. # 设置主机与虚拟机的共享目录,根据需要开启 node.vm.synced_folder "/path/to/#{i}", "/data" # Disable the default share of the current code directory. Doing this # provides improved isolation between the vagrant box and your host # by making sure your Vagrantfile isn't accessible to the vagrant box. # If you use this you may want to enable additional shared subfolders as # shown above. # config.vm.synced_folder ".", "/vagrant", disabled: true # Provider-specific configuration so you can fine-tune various # backing providers for Vagrant. These expose provider-specific options. # Example for VirtualBox: node.vm.provider "virtualbox" do |vb| # 设置虚拟机的名称 # vb.name = "node#{i}" # if node.vm.hostname == "node1" # # Display the VirtualBox GUI when booting the machine # vb.gui = true # end # Customize the amount of memory on the VM: vb.memory = "6144" # 设置虚拟机的CPU个数 vb.cpus = 2 end # View the documentation for the provider you are using for more # information on available options. # Enable provisioning with a shell script. Additional provisioners such as # Ansible, Chef, Docker, Puppet and Salt are also available. Please see the # documentation for more information about their specific syntax and use. # config.vm.provision "shell", inline: <<-SHELL # sudo yum makecache --refresh # sudo yum install -y tcpdump # sudo yum install -y nc # sudo yum install -y net-tools # SHELL end end end
killercoda CKA:Troubleshooting - 3

killercoda CKA:Troubleshooting - 3

D瓜哥
1. Troubleshooting - Service account, role, role binding Issue Troubleshooting - Service account, role, role binding Issue You have a service account named dev-sa, a Role named dev-role-cka, and a RoleBinding named dev-role-binding-cka. we are trying to create list and get the pods and services. However, using dev-sa service account is not able to perform these operations. fix this issue. # @author D瓜哥 · https://www.diguage.com $ kubectl get serviceaccounts dev-sa -o yaml apiVersion: v1 kind: ServiceAccount metadata: creationTimestamp: "2025-01-22T09:48:06Z" name: dev-sa namespace: default resourceVersion: "2270" uid: 48b68f34-8c19-4477-9631-4f368f6ecc66 $ kubectl get role dev-role-cka NAME CREATED AT dev-role-cka 2025-01-22T09:48:06Z $ kubectl get role dev-role-cka -o yaml apiVersion: rbac.authorization.k8s.io/v1 kind: Role metadata: creationTimestamp: "2025-01-22T09:48:06Z" name: dev-role-cka namespace: default resourceVersion: "2271" uid: 7a011481-8edd-4417-a1b8-8d15290d3e9f rules: - apiGroups: - "" resources: - secrets verbs: - get $ kubectl get rolebindings dev-role-binding-cka -o yaml apiVersion: rbac.authorization.k8s.io/v1 kind: RoleBinding metadata: creationTimestamp: "2025-01-22T09:48:07Z" name: dev-role-binding-cka namespace: default resourceVersion: "2272" uid: 888af489-86b6-4d38-a723-a8ff13656d2b roleRef: apiGroup: rbac.authorization.k8s.io kind: Role name: dev-role-cka subjects: - kind: ServiceAccount name: dev-sa namespace: default # 将 Role 删掉,重建即可 $ kubectl delete role dev-role-cka --force --grace-period 0 Warning: Immediate deletion does not wait for confirmation that the running resource has been terminated. The resource may continue to run on the cluster indefinitely. role.rbac.authorization.k8s.io "dev-role-cka" force deleted $ kubectl create role dev-role-cka --resource=pods,services --verb=create,list,get role.rbac.authorization.k8s.io/dev-role-cka created $ kubectl get role dev-role-cka -o yaml apiVersion: rbac.authorization.k8s.io/v1 kind: Role metadata: creationTimestamp: "2025-01-22T09:49:46Z" name: dev-role-cka namespace: default resourceVersion: "2414" uid: b3d7fc62-f029-4f4b-88a5-99ee9840af05 rules: - apiGroups: - "" resources: - pods - services verbs: - create - list - get
killercoda CKA:Troubleshooting - 2

killercoda CKA:Troubleshooting - 2

D瓜哥
1. Troubleshooting - Persistent Volume, Persistent Volume Claim - Issue Troubleshooting - Persistent Volume, Persistent Volume Claim - Issue my-pvc Persistent Volume Claim is stuck in a Pending state, fix this issue, make sure it is in Bound state # @author D瓜哥 · https://www.diguage.com $ kubectl get pvc my-pvc -o wide NAME STATUS VOLUME CAPACITY ACCESS MODES STORAGECLASS VOLUMEATTRIBUTESCLASS AGE VOLUMEMODE my-pvc Pending standard <unset> 38s Filesystem $ kubectl get pv my-pv -o wide NAME CAPACITY ACCESS MODES RECLAIM POLICY STATUS CLAIM STORAGECLASS VOLUMEATTRIBUTESCLASS REASON AGE VOLUMEMODE my-pv 100Mi RWO Retain Available standard <unset> 51s Filesystem $ kubectl get pvc my-pvc -o yaml | tee pv.yaml apiVersion: v1 kind: PersistentVolumeClaim metadata: annotations: kubectl.kubernetes.io/last-applied-configuration: | {"apiVersion":"v1","kind":"PersistentVolumeClaim","metadata":{"annotations":{},"name":"my-pvc","namespace":"default"},"spec":{"accessModes":["ReadWriteMany"],"resources":{"requests":{"storage":"150Mi"}},"storageClassName":"standard"}} creationTimestamp: "2025-01-20T13:08:41Z" finalizers: - kubernetes.io/pvc-protection name: my-pvc namespace: default resourceVersion: "2002" uid: a4c6c044-4118-47a4-97b9-ceb69fac3bc2 spec: accessModes: - ReadWriteMany resources: requests: storage: 150Mi storageClassName: standard volumeMode: Filesystem status: phase: Pending $ kubectl get pv my-pv -o yaml apiVersion: v1 kind: PersistentVolume metadata: annotations: kubectl.kubernetes.io/last-applied-configuration: | {"apiVersion":"v1","kind":"PersistentVolume","metadata":{"annotations":{},"name":"my-pv"},"spec":{"accessModes":["ReadWriteOnce"],"capacity":{"storage":"100Mi"},"hostPath":{"path":"/mnt/data"},"persistentVolumeReclaimPolicy":"Retain","storageClassName":"standard"}} creationTimestamp: "2025-01-20T13:08:41Z" finalizers: - kubernetes.io/pv-protection name: my-pv resourceVersion: "2003" uid: 85a371c4-0931-4b57-87ea-fc1fceb674c1 spec: accessModes: - ReadWriteOnce capacity: storage: 100Mi hostPath: path: /mnt/data type: "" persistentVolumeReclaimPolicy: Retain storageClassName: standard volumeMode: Filesystem $ vim pv.yaml # 两个问题: # 1、 PVC 和 PV 的 accessModes 不一致,改为 ReadWriteOnce即可 # 2、 PVC 的存储是 150Mi,而 PV 只有 100Mi,也改为 100Mi 即可。 $ kubectl delete -f pv.yaml --force --grace-period 0 Warning: Immediate deletion does not wait for confirmation that the running resource has been terminated. The resource may continue to run on the cluster indefinitely. persistentvolumeclaim "my-pvc" force deleted $ kubectl apply -f pv.yaml persistentvolumeclaim/my-pvc created $ kubectl get pvc my-pvc -o wide NAME STATUS VOLUME CAPACITY ACCESS MODES STORAGECLASS VOLUMEATTRIBUTESCLASS AGE VOLUMEMODE my-pvc Bound my-pv 100Mi RWO standard <unset> 10s Filesystem