字符串算法总结|双指针的总结

发布时间:2024年01月19日

在字符串旋转操作中主要是运用多次反转,最后得到结果。

例如反转字符串里的单词:可以先进行整体反转,最后进行单词反转。

例如从字符串的倒数第k位开始反转,此时可以先整体反转,在局部反转,在反转时可以用到algorithm库中的reverse函数。

双指针操作:

例如在字符串的替换中,将一个单词替换成某个单词,因为空间会增加,我们将字符串扩容,一个指针负责遍历,另一个指针负责赋值,此时从后往前遍历和从后往前赋值。因为空间足够。

例如在删除数组的重复项时,一个指针负责遍历,另一个指针负责赋值。

例如在进行二分查找时,开始我们将left和right分别指向第一个和最后一个元素,如果查找的元素大于中间元素,我们将left=mid+1,反之,right=mid-1,直到找到为止。

例如在进行快速排序时,left指向第一个元素,right指向第二个元素,当right指向元素的值小于基准时,left+1,并且left+1,和right位置的元素交换位置,当right走到结尾时,将left指向的元素和开头做交换。目的是保证改变基准,因为基准选的是第一个元素。

例如另一种快速排序的方法,left指向最左边元素,right指向最右边元素。right--指向元素小于基准时,将left指向的值改为right指向的值,之后left++,当left指向的值大于等于基准时,将right指向的值改为left指向的值。知道left<=right(意味着此时划分到一个元素,此时数据肯定有序)

例如环形链表,快指针走一次走两步,慢指针一次走一步,当慢指针和快指针相遇时证明有环出现。

文章来源:https://blog.csdn.net/weixin_62518305/article/details/135707071
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。