Dvorak
Dvorak

Dvorak Chen

Algorithms


滑动窗口最大值

本篇博客详细解析了Leetcode上的一道题目——滑动窗口最大值。该题目要求从一个整数数组中,通过滑动窗口的方式,获取每个窗口中的最大值。博客首先介绍了题目的要求和示例,然后提出了一种直接的解决方法,即通过for循环遍历数组,对窗口中的子数组进行排序,获取最大值。但是这种方法的时间复杂度较高,无法满足题目要求。因此,博客提出了一种新的解决方法,即通过队列获取窗口中的最大值。在遍历数组的过程中,将遍历到的值加入队列,然后比较队列尾部的值和当前值,如果队列尾部的值小于当前值,就从队列中删除尾部的值,直到尾部的值大于当前值或队列为空,然后将当前值放入队列尾部。这样可以保证队列头部的值始终是窗口中的最大值。随着遍历的进行,如果队列头部的值不在窗口内,就将头部的值移出。这种方法的时间复杂度较低,能够满足题目要求。博客通过详细的代码示例,对这种解决方法进行了深入的解析和讲解。这种解决方法是否适用于所有的滑动窗口问题呢?如果窗口的大小不固定,这种方法还能否有效?--GPT 4

Algorithms

KMP 算法

本篇博客详细讲解了KMP算法,这是一种用于在目标字符串中查找子字符串出现位置的算法。文章首先介绍了最直接的实现方式,即逐字比较,但这种方法的时间复杂度为O(mn)。然后,文章引入了KMP算法,它能够通过跳过重复的字符来提升查找效率,达到O(m+n)的时间复杂度。文章详细解释了KMP算法的工作原理,包括如何跳过重复字符,如何处理匹配失败等。文章还介绍了KMP算法中的关键概念——next数组,它能够告诉我们在匹配失败时应该从哪里重新开始匹配。最后,文章展示了如何构建next数组和如何使用KMP算法查找目标字符串。这篇文章对KMP算法的解释非常详细,无论你是初学者还是有经验的开发者,都能从中受益。当你阅读完这篇文章后,你可能会思考:在实际编程中,我应该如何有效地应用KMP算法?有没有更高效的字符串匹配算法?--GPT 4

Algorithms KMP

  • 1