python双指针法,python 指针操作

　　1.导读最近业务在leetcode上刷了一些问题，遇到了很多可以通过双指针技术快速解决的问题。这里总结一下双指针技术，方便后续的查漏补缺。

　　废话少说，我们开始吧！

　　2.双指针的介绍双指针技术是一种允许我们通过使用一些排序的数据来优化算法的运行时间和空间效率的技术。它通常应用于数组和链表。该技术可以概括为以下三个步骤：

　　初始化：我们的指针可以在初始状态的任何地方，这主要取决于我们需要实现什么。行动：这一步决定了我们如何更接近解决方案。通常，两个指针可以向同一个方向或相反的方向移动。终止条件：这决定了我们何时停止指针的移动。为了加深大家的理解，下面我们来看一些具体的例子！

　　3.判断回文字符串标题描述：

　　给我们一个字符串作为输入，如果是回文字符串，返回true，否则返回false。回文是单词、数字、短语或其他发音相同的字符的序列。

　　解决方案：

　　定义isPalindrome(str):

　　i=0

　　j=len(str) -1

　　而我j:

　　if str[i]！=str[j]:

　　返回False

　　i=1

　　j -=1

　　false我们通过使用双指针的思想解决了上述问题。上述三个步骤如下：

　　初始化：在前2行中，我们定义了两个指针的初始位置，I在开始，J在结束。移动：在第6行和第7行，我们的两个指针将向相反的方向移动，第一个指针I向前移动，第二个指针J向相反的方向移动。终止条件：当i j时，遍历将停止，因为当I增加，J减少时，I从起点开始，J在终点。当I在数组中间时，I将大于J，遍历结束。4.链表中中间元素的标题描述：

　　给出顺序链表的头指针，返回链表的中间节点。

　　4.1暴力解链表的缺点是无法通过下标访问对应的元素。所以可以考虑遍历链表，把遍历的元素依次放入数组A。如果我们遍历N个元素，那么链表和数组的长度也是N，对应的中间节点是A[N/2]。

　　代码如下：

　　def middleNode(self，head: ListNode) - ListNode:

　　a=[头]

　　而A[-1]。接下来：

　　A.append(A[-1]。下一个)

　　return [len (a)//2]的复杂度分析：

　　时间复杂度：O(N)，其中NN是给定链表中的节点数。空间复杂度：O(N)，即数组a使用的空间4.2快慢指针解法解题思路：

　　我们可以使用两个指针，慢速和快速，来遍历链表。慢一步走一步，快一步走两步。那么当fast到达链表的末尾时，slow一定在中间。

　　代码如下：

　　def middleNode(self，head: ListNode) - ListNode:

　　慢=快=头

　　又快又快。下一个：

　　慢=慢。下一个

　　快速=快速.下一个.下一个

　　Return slow在上面的代码中，使用了两个同向移动的指针，这也涉及到三个一般步骤。如下所示：

　　初始化：两个指针将从相同的位置开始，即链表的开头。移动：它们会向同一个方向移动，但是第二个比第一个快。终止条件：当移动较快的指针到达链表的末尾时，遍历将停止。因为快指针的移动速度是慢指针的两倍，所以慢指针到达终点时会在中间。具体流程如下所示：

　　复杂性分析：

　　时间复杂度：O(N)，其中NN是给定链表中的节点数。空间复杂度：O(1)，只需要常量空间来存储慢速和快速指针。

　　5.总结一下，双指针技术可以帮助你减少算法的运行时间。我们可以在数组和链表中使用它。指针不一定从同一个位置开始，也不一定向同一个方向移动，需要根据搜索的内容定义停止条件。

　　嗯，就酱~

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。