双指针技巧在LeetCode中的应用：数组排序与字符串匹配
在算法学习中，双指针技巧是一种非常实用的方法，尤其在处理数组排序和字符串匹配问题时。双指针技巧的核心思想是使用两个指针分别指向数组的两端或特定位置，通过比较、移动指针来解决问题。本文将围绕这一主题，结合LeetCode上的经典题目，探讨双指针技巧在数组排序和字符串匹配中的应用。
数组排序
1. 快速排序（Quick Sort）
快速排序是一种高效的排序算法，其基本思想是选取一个基准值，将数组分为两部分，一部分比基准值小，另一部分比基准值大，然后递归地对这两部分进行快速排序。
python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
示例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)
2. 双指针技巧在快速排序中的应用
在快速排序中，我们可以使用双指针技巧来优化基准值的选取和数组的划分过程。
python
def partition(arr, low, high):
pivot = arr[low]
left = low + 1
right = high
while True:
while left <= right and arr[left] <= pivot:
left += 1
while left <= right and arr[right] >= pivot:
right -= 1
if left > right:
break
arr[left], arr[right] = arr[right], arr[left]
arr[low], arr[right] = arr[right], arr[low]
return right
def quick_sort(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
示例
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr, 0, len(arr) - 1)
print(arr)
字符串匹配
1. KMP算法（Knuth-Morris-Pratt）
KMP算法是一种高效的字符串匹配算法，其核心思想是构建一个部分匹配表（也称为“失败函数”），用于在匹配失败时，快速跳过已匹配的部分。
python
def kmp_search(s, p):
m = len(p)
n = len(s)
lps = [0] m
compute_lps(p, m, lps)
i = 0
j = 0
while i < n:
if p[j] == s[i]:
i += 1
j += 1
if j == m:
return i - j
elif i < n and p[j] != s[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
def compute_lps(p, m, lps):
length = 0
i = 1
while i < m:
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
示例
s = "ABABDABACDABABCABAB"
p = "ABABCABAB"
index = kmp_search(s, p)
print(index)
2. 双指针技巧在KMP算法中的应用
在KMP算法中，双指针技巧主要用于构建部分匹配表和字符串匹配过程。
python
def kmp_search(s, p):
m = len(p)
n = len(s)
lps = [0] m
compute_lps(p, m, lps)
i = 0
j = 0
while i < n:
if p[j] == s[i]:
i += 1
j += 1
if j == m:
return i - j
elif i < n and p[j] != s[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
def compute_lps(p, m, lps):
length = 0
i = 1
while i < m:
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
示例
s = "ABABDABACDABABCABAB"
p = "ABABCABAB"
index = kmp_search(s, p)
print(index)
总结
本文介绍了双指针技巧在数组排序和字符串匹配中的应用，通过LeetCode上的经典题目，展示了双指针技巧在实际问题中的优势。在实际编程中，熟练掌握双指针技巧，可以帮助我们更高效地解决各种问题。
Comments NOTHING