【重修Python】滑动窗口算法
原创【重修Python】滑动窗口算法
原创
前言
在Leet code刷算法题时，经常能遇到一种题型，他们的名字如下格式求xxx子串，xxx子数组。解法也都有统一的模版，因为他的图解形态像是一个方块，在一个方向上移动，所以我们也称这种算法叫做滑动窗口（slide window）。
案例
本算法其实并不是一种正规的解题思路，是在暴力解题的一种优化，或者说双指针的一种特殊情况。
题目描述
以力扣在本月15号的每日一题来说。
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。(case参考上边图)
链表的定义如下
# 链表定义
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
- case 1
head = [1,2,3,3,4,4,5] 输出结果：[1,2,5]
- case 2
head = [1,1,1,2,3] 输出结果：[2,3]
题目拆解
拿到题目之后，我习惯先看case，因为有时中文的翻译有时有点古怪。不过正常来说，还是对题目进行关键词解构。
这样简化后，问题就来到了，删除重复数字的节点。并且因为已经排好序，所以只要做下一个的判断就好。
对于链表删除，其实就是改变指向，没有节点指向它。见下图
解题代码
# 定义链表
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 算法题解，删除重复节点
def deleteDuplicates(head: ListNode) -> ListNode:
# 判断空节点
if not head:
return head
# 哨兵节点，防止头接点会被删除
dummy = ListNode(0, head)
# 当前指针
cur = dummy
while cur.next and cur.next.next:
# 相等则开始遍历，直到不等，指向到不等的节点
if cur.next.val == cur.next.next.val:
x = cur.next.val
while cur.next and cur.next.val == x:
cur.next = cur.next.next
# 不相等则移动指针
else:
cur = cur.next
# 返回哨兵节点的结果
return dummy.next
# 辅助数组转链表
def createList(arr):
if not arr:
return None
head = ListNode(arr[0])
cur = head
for i in range(1, len(arr)):
cur.next = ListNode(arr[i])
cur = cur.next
return head
# 测试case
case_1 = [1,2,3,3,4,4,5]
case_2 = [1,1,1,2,3]
# 测试结果
result_1 = deleteDuplicates(createList(case_1))
result_2 = deleteDuplicates(createList(case_2))
# 输出结果
print("result_1: ", end=' ')
while result_1:
print(str(result_1.val) + " ", end=' ')
result_1 = result_1.next
print()
print("result_2: ", end=' ')
while result_2:
print(str(result_2.val) + " ", end=' ')
result_2 = result_2.next输出结果
result_1: 1 2 5 result_2: 2 3
时间复杂度：O（n） 只需要遍历一遍链表
空间复杂度：O（1）
部分图解
其他应用
除了在序列上（字符串、数组等数据结构）上寻找子序列的时候经常用到外，在网络发包检测也会遇到，比如TCP上，为了控制数据包丢失和拥塞，会这样一段一段的检查（事实上，比这要更复杂一些）
总结
看到这里，相信您对滑动窗口这种算法以及python的实现语法都有了一定了解。不如趁热打铁，举一反三，尝试一下变种，不删除重复节点，而是保留一个。（提示：修改下核心的指向即可）
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。