寒夜雨 - 算法
type: channel
link: https://www.coderlock.site/index.php/tag/%E7%AE%97%E6%B3%95/
items: 【算法】滑窗算法
items: 【算法】链表
items: 【算法】双指针
items: 【算法】二分法
items: 【算法】算法设计与分析

【算法】滑窗算法
type: item
date: 2025-08-25T15:17:24+00:00
description: 前言滑窗算法常用于序列的连续子序列的处理。通过两个指针维护一个窗口，通过一些逻辑对这个窗口——亦即一个连续的子序列——进行处理。简单的例子：最长无公共字母的子串这道题可以通过LeetCode 3访问，一个AC解是：class Solution: def lengthOfLongestSubstring(self, s: str) -> int: d = {} res = 0 l, r = 0, 0 while r < len(s): while l < r and s[r] in d: d.pop(s[l]) l += 1 d[s[r]] = 1 res = max(r-l+1, res) r += 1 return res这道题通过左右指针+哈希表的结构维护一个区间，哈希表记录这个区间内的字母的出现次数。右指针不断移动，迭代每一个字母，如果右指针的移动带来了字母的重复，就移动左指针，直到没有重复字母为止。滑窗算法的步骤通常是：编写维护连续区间的逻辑：这要求预先判断出，题目涉及到连续子序列的操作，可以通过滑窗求解。具体考虑时，需要考虑该怎么维护，单纯的滑窗？滑窗加上一些外部数据结构？迭代过程的处理：思考边界条件是什么？两个指针在什么条件下移动？简单的例子：模式串的排列匹配这道题可以通过LeetCode 567访问，一个AC解是：class Solution: def isSameDict(self, d1, d2): if len(d1) != len(d2): return False for k1 in d1.keys(): if k1 not in d2: return False if d2[k1] != d1[k1]: return False return True def checkInclusion(self, s1: str, s2: str) -> bool: if len(s1) > len(s2): return False d1, d2 = {}, {} for c1 in s1: if c1 in d1: d1[c1] += 1 else: d1[c1] = 1 l, r = 0, len(s1) - 1 for idx in range(r+1): c2 = s2[idx] if c2 in d2: d2[c2] += 1 else: d2[c2] = 1 while r < len(s2): if self.isSameDict(d1, d2): return True if d2[s2[l]] == 1: d2.pop(s2[l]) else: d2[s2[l]] -= 1 l += 1 r += 1 if r == len(s2): break if s2[r] in d2: d2[s2[r]] += 1 else: d2[s2[r]] = 1 return False这道题通过滑窗+哈希表的结构维护区间内部的信息。通过题干，很容易发现是连续序列的处理，那么字母的排列不会影响长度，就代表滑窗的窗口大小固定了。依次迭代，发现字母出现的次数与模式串一致，就代表匹配成功了。简单的例子：替换后可出现的最长单字母串这道题可通过LeetCode 424访问，一个AC解是：class Solution: def getMinDiffCharTime(self, d): if len(d) <= 1: return 0 maxi = 0 total = 0 for v in d.values(): maxi = max(maxi, v) total += v return total - maxi def characterReplacement(self, s: str, k: int) -> int: d = {} l = 0 result = 0 for r in range(len(s)): d[s[r]] = d[s[r]] + 1 if s[r] in d else 1 while l < r and self.getMinDiffCharTime(d) > k: if d[s[l]] == 1: d.pop(s[l]) else: d[s[l]] -= 1 l += 1 result = max(result, r-l+1) return result这道题的答案我并没有优化，完全可以通过定长list优化哈希表。不过，这道题依然是通过哈希表+滑窗进行序列的维护。

【算法】链表
type: item
date: 2025-08-24T02:51:07+00:00
description: 前言链表是一个不常使用在日常软件开发中的数据结构，但是，却经常会被用于出算法题，这是因为，链表的两个元素之间是通过next指针相连，如果没有维护好这个指针信息，就会导致无法访问到某一元素。我们一般使用单向链表，其中每个元素的结构包括一个data变量和一个next指针，前者用于存储数据，后者用于记录下一个元素的地址，C语言的表示为：typedef struct LinkedListNode { int data; struct LinkedListNode* next; } LLN;简单的例子：反转链表这道题可以通过LeetCode 206访问，这道题的一个AC解是：/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { if(head == NULL || head->next == NULL) { return head; } struct ListNode* prev = NULL; struct ListNode* curr = head; struct ListNode* neno = head->next; while(curr != NULL) { //neno = curr->next; curr->next = prev; prev = curr; curr = neno; neno = (neno == NULL) ? NULL : neno->next; } return prev; }在循环内，neno的赋值选择注释掉的一行还是未注释的一行都可以。只涉及$O(1)$空间复杂度的链表反转，重要之处在于如何维护next节点的信息。因为，当反转链表时，由于next指向的问题，如果不维护下一个节点的信息，那么下一次迭代就没有办法访问了。所以这道题的逻辑是这样的：下一个节点的维护：记录当前节点的下一个节点。主要逻辑：反转当前节点的下一节点指向。为下一次迭代做准备：即prev和curr节点的赋值。只要是涉及链表的算法，最重要的就是如何维护下一个节点的信息。简单的例子：合并两个排好序的链表这道题可以通过LeetCode 21访问，这道题的一个AC解是：/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode)); head->val = 0; head->next = NULL; struct ListNode* curr = head; struct ListNode* p1 = list1; struct ListNode* p2 = list2; while(p1 != NULL || p2 != NULL) { if(p2 == NULL) { curr->next = p1; p1 = p1->next; } else if(p1 == NULL) { curr->next = p2; p2 = p2->next; } else { if(p1->val >= p2->val) { curr->next = p2; p2 = p2->next; } else { curr->next = p1; p1 = p1->next; } } curr = curr->next; } return head->next; }值得注意的是，我不推荐任何人使用C去进行LeetCode的作答，比如malloc后的赋值操作，对于算法没有任何影响，但是删除这两句，便无法AC。这道题就很好体现了我们之前说的三个步骤：下一个节点的维护：划分不同条件，根据空指针、值大小判断当前节点接续什么节点。主要逻辑：接续的过程。为下一次迭代做准备：将curr节点变作它的下一个节点。中等的例子：快慢指针这道题可以通过LeetCode 141访问，一个AC解是：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * L…

【算法】双指针
type: item
date: 2025-08-21T14:26:32+00:00
description: 前言双指针是一种用于解决区间问题的算法，这类算法通常的复杂度都是$\Theta(n)$。其实，我们可以将二分看作一种特殊的双指针，每次筛选掉一半的数据。同样的，双指针也可以看作一种特殊的二分，只不过每次通常筛选掉一个数据。简单的例子：回文串的判断这道题可以通过LeetCode 125访问，这道题的一个AC解是：class Solution: def isPalindrome(self, s: str) -> bool: left, right = 0, len(s) - 1 while left < right: while not (s[left].isalpha() or s[left].isnumeric()) and left < right: left += 1 while not (s[right].isalpha() or s[right].isnumeric()) and left < right: right -= 1 if s[left].lower() != s[right].lower(): return False left += 1 right -= 1 return True这道题的思想很简单，每次判断左右两个字符，如果一致，就左指针右移一位，右指针左移一位，判断下一个字符。这道题体现了双指针的基本写法，在区间上，首先将指针置于左右两侧，然后进行必要的操作，随后移动两个指针（或某一个指针），满足$O(n)$的复杂度。双指针算法的重要之处在于指针的移动方法。简单的例子：二和问题这道题可以通过LeetCode 167访问，这道题的一个AC解是：class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: left, right = 0, len(numbers) - 1 while left < right: curr_sum = numbers[left] + numbers[right] if curr_sum < target: left += 1 elif curr_sum > target: right -= 1 else: return [left+1, right+1]由于这道题已经排好序了，所以我们完全可以应用双指针算法来解决这个问题，左右指针对着的值相加，然后判断这个值的大小，如果这个值过大了，证明我们需要缩小，就将右指针左移；如果值太小，就要左指针右移。这里是双指针的一个另一个特点——它对具有一定单调性的区间效果很好。对于回文串，这个单调性是通过回文串的性质来体现的，即每个字母只和中央对称过去的字母有关。在这道题中，由于序列排好序了，那么通过指针移动的方向，就能够判断出指针所指向值的和的变化方式。中等的例子：接雨水青春版这道题可以通过LeetCode 11访问，这道题的一个AC解是：class Solution: def maxArea(self, height: List[int]) -> int: l, r = 0, len(height)-1 result = 0 while l < r: result = max(result, min(height[r], height[l]) * (r-l)) if height[l] == height[r]: l += 1 r -= 1 elif height[l] < height[r]: l += 1 else: r -= 1 return result这道题的单调性就没有那么显然——是通过接雨水的原理体现的。接雨水需要两个边，这两个边之中的最小值为实际的接雨水的高，宽则是两个边的“横坐标”之差。此外，由于左右指针是从外向内收缩的，那么接雨水的宽是单调递减的。那么，当我们双指针指向两条边的时候，其中对于短边来说，当前情况是这条短边参与组合的所有的容器中，接的雨水最多的。这个时候需要长边指针向内收。这个说法一定正确吗？我们来证明一下，最开始假设：两条指针指向的边长度为$d_1, d_2$，坐标为$x_1, x_2$，那么假设二者中间有一条更长或者更短的边，其长度为$d$，坐标为$x$，那么它所参与的左右两个容器的容积分别为$(x-x_1)\min(d,d_1)$和$(x_2-x)\min(d,d_2)$，我们知道：$$ (x-x_1)<x_2-x_1,(x_2-x)<x_2-x_1 $$并且左、右边容器的高最高分别也就是$d_1$和$d_2$，所以左右两个容器的容积必然小于总容积，那么“对于短边来说，当前情况是这条短边参与组合的所有的容器中，接的雨水最多的”这句话是成立的。随着指针变化，又会怎么变化呢？其实，结论也是成立的，因为挪动的…

【算法】二分法
type: item
date: 2025-08-20T05:19:05+00:00
description: 前言分治法的通用步骤是：划分-求解-合并。将一个比较大的问题拆分成若干小问题，然后分别求解。分治法和动态规划的区别在于，分治法通常求解子问题之间彼此独立的场景，而动态规划用于求解子问题之间不独立的场景。这一区别将在动态规划一节中阐述。分治法最常用的算法为二分法，也就是将问题分割为两个子问题，分别求解之后进行合并。简单的例子：归并排序用Python语言的归并排序实现如下所示：def merge_sort(arr): if len(arr) <= 1: return arr divide_point = len(arr) // 2 left = merge_sort(arr[:divide_point]) right = merge_sort(arr[divide_point:]) return merge(left, right) def merge(left_arr, right_arr): result = [] while len(left_arr) > 0 and len(right_arr) > 0: if left_arr[0] < right_arr[0]: result.append(left_arr.pop(0)) else: result.append(right_arr.pop(0)) while len(left_arr) > 0: result.append(left_arr.pop(0)) while len(right_arr) > 0: result.append(right_arr.pop(0)) return result if __name__ == "__main__": arr1 = [1,2,3,4,5,6,7,8,9] arr2 = [9,8,7,6,5,4,3,2,1] arr3 = [1,3,5,7,9,2,4,6,8] print(merge_sort(arr1)) print(merge_sort(arr2)) print(merge_sort(arr3))其中，merge_sort函数控制着整个排序过程，在这个过程中，首先将待排序的list对半分，分为两个部分，分别对左右两个部分排序后，再进行合并操作。合并操作的过程受merge函数控制。如您所见，分治算法的划分过程，是将大问题（排序整个list）分割为不相关的小问题（排序左右两个list，且这两个排序过程彼此独立），求解的过程，是处理最小的、能够直接解决的小问题（当分割的list中只有一个元素）的过程，合并的过程，则是对子问题进行综合处理，得到大问题的解（将两个排好序的list合并）。“在写分治算法的过程时，不要过度关心分解该怎么做，而是关心该如何分解”。这是一个非常微妙的描述，更具体来说，就是不要关心分解之后的问题经历了什么，而是要关心如何分割问题，分治算法的关键在于最小问题的处理方法以及合并的方法。简单的例子：二分查找基础二分查找一个更能分治法的算法是二分查找，二分查找的目的是在给定一个排好序的序列中，寻找到想要的值的下标。这个算法的复杂度达到了惊人的$\Theta(\log n)$。这个算法通过对半划分，每次查找能筛选掉一半的候选项，所以这个算法的复杂度实际上是$\Theta(\log_2n)$。一个Python实现如下：if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] target = 4 left = 0 right = len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: print(mid) break elif arr[mid] < target: left = mid + 1 else: right = mid - 1这个函数的划分方式不如归并排序那样清晰，不过我们能够从循环中能看出来：每次搜索，首先判断数列中间的值，如果这个值比目标值大，那么就表明，中间这个值在目标值的右边，就搜索中间值左边的子数列；如果这个值比目标值小，那么就表明，中间这个值在目标值的左边，就搜索中间值右边的子数列。这里，值得注意的是while left <= right这句代码。这一行代码中的=体现了分治算法中，考虑“最小问题的处理方法”的重要性。添加了一个等号，就表明数列没有元素时，也要进行判断，这个时候判断的是left和right同时指向的位置的值。如果不加=，那么算法需要被改写：if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] target = 4 left = 0 righ…

【算法】算法设计与分析
type: item
date: 2025-08-19T07:01:11+00:00
description: 前言本系列记录我对于各种算法的理解。本篇改自我本科课程“算法设计与分析”的笔记。本篇不通过例子讨论具体的算法。算法复杂度分析的数学工具算法是为了解决问题而生的，它必须有这样几个性质：可终止、有确定性、正确性、有输入/输出。算法的复杂度分析通常从两个方面来入手——时间复杂度分析和空间复杂度分析。时间复杂度分析通常以操作的个数衡量。对于一个特定的输入来说，算法的时间复杂性是对该输入产生结果所需要的原子操作数。一个算法的时间复杂度是关于输入大小的函数，记作$T(n)$，其中$n$是输入的大小。空间复杂度分析通常以占据的存储空间大小来衡量。对于一个特定的输入来说，算法的空间复杂度是该算法对该输入产生结果所需要的存储空间大小，记作$S(n)$。接下来我们来讨论一下分析复杂性的工具，其实用于分析的基本工具很简单，只有这么几个：同阶函数集合、低阶函数集合、高阶函数集合和严格低/高阶函数。对于同阶函数来说，最重要的是观察函数的主导项，比如$f(x)=x^2+3x+4$这个函数，其同阶函数集合就可以表示为$\Theta(n^2)$，因为这个函数的主要增长项是$x^2$，这个时候，要忽略低阶项和常系数。一个形式化的表达是：$$ \Theta(g(n))=\\{f(n)|\exists c_1,c_2>0,n_0,\forall n>n_0,c_1g(n)\leq f(n) \leq c_2g(n) \\} $$低阶函数集合用于描述一个函数的上界，用$O(n)$格式来表示，其形式化定义是：$$ O(g(n))=\\{f(n)|\exists c>0, n_0, \forall n>n_0, 0\leq f(n)\leq cg(n)\\} $$高阶函数集合用于描述一个函数的下届，在算法领域，用于描述最优情况的复杂度，用$\Omega(n)$的格式来表示。在这个基础上，我们有一个重要的分析工具——递归方程。比如对于归并排序，就有如下的公式：$$ T(1)=O(1) $$$$ T(n)=2T(\frac{1}{2}n)+O(n) $$这个时候，我们该如何求得$T(n)$的同阶函数集合呢？完全可以用迭代法，也就是通过数列迭代的基本关系求解，比如：$$ T(n)=2T(\frac{1}{2}n)+cn=4T(\frac{1}{4}n)+2cn=\cdots $$由此可见，这个公式的结构是：$$ T(n)=2^kT(\frac{1}{2^k}n)+kcn $$当$\frac{1}{2^k}n=1$时，有$k=\log_2n$，这个时候有：$$ T(n)=n+cn\log_2n $$由此可知，$T(n)=\Theta(n\log n)$。当然，也可以用主定理来快速求解，主定理的内容是，当递归方程形式为$T(n)=aT(\frac{n}{b})+f(n)$且$a\geq 1,b>1$时，若：存在$\epsilon>0$，有$f(n)=O(n^{\log_ba-\epsilon})$，则$T(n)=\Theta(n^{\log_ba})$。存在$\epsilon\geq0$，有$f(n)=\Theta(n^{\log_ba}\log^\epsilon n)$，则$T(n)=\Theta(n^{\log_ba}\log^{\epsilon +1}n)$。存在$\epsilon > 0$，有$f(n)=\Omega(n^{\log_ba+\epsilon})$，且存在$c<1$和一个足够大的$n$，满足$af(\frac{n}{b})\leq cf(n)$，则$T(n)=\Theta(f(n))$。分治法分治法的基础是“划分-求解-合并”，其递归方程的格式为：$$ T(n)=aT(\frac{n}{b})+D(n)+C(n) $$其中字母的含义是：将问题分解为$a$个部分，$D(n)$是划分的耗时，$C(n)$是合并的复杂度。动态规划动态规划所适用的问题是，大问题的计算过程中，会重复计算很多子问题，造成不必要的开销。如果从子问题求解，并记住子问题的结果，就能够节省重复计算子问题的开销，其递归方程没有一个具体的通常格式，需要根据不同问题进行分析。贪心算法贪心算法的核心思想是，每一步的决策都做出当前的局部最优决策。这种算法的证明通常是通过归纳法以及交换论证法证明的。交换论证法通常是假定一个最优解，然后将所谓的最优决策换为贪心决策，最终得到更优的贪心解。后记具体的算法流程将在后续讲述。这门课我觉得最大的收获便是算法复杂度分析的数学工具。