Algorithms - Dvorak Chen

JAN

滑动窗口最大值

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

Algorithms

MAY

KMP 算法

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

Algorithms KMP