双指针方法 — Python 代码

悠悠 2024-03-17 14:43 39阅读 0赞

双指针方法 — Python 代码

如果它们作为一个整体，两个总比一个好。

双指针算法是任何编程面试中最常见的问题之一。此方法通过利用数据的某些顺序（不一定是排序）来优化运行时。此方法通常用于搜索排序数组中的对。这种方法在恒定空间中有效。

在此技术中，指针表示索引或迭代属性，如节点的下一个。

双指针方法的步骤：

图片来源：作者 如上图所示，两指针方法有三个主要步骤：

指针初始化 — 起点。指针可以在任何地方，具体取决于我们想要实现的目标。在图片的左侧，我们有两个指针从相同的位置开始，即链表的开头。在图片的右侧，我们在极端末端有指针，一个在起始索引处，另一个在最后一个索引处。

指针移动 — 这将决定我们如何趋同于解决方案。指针可以沿同一方向移动（上图中左侧），也可以沿相反方向移动（上图中右侧）。同样在图片的左侧，我们对指针有不同的增量（顶部（慢）有 1 个单位，底部（快）有 2 个单位）。

停止条件 — 这决定了我们何时停止。在左侧部分，我们继续前进，直到到达下一个元素为 None 的节点。在正确的一个中，我们继续直到我们的开始小于结束（i <j）。

注意：滑动窗口是双指针方法的另一种变体。

让我们看看我们如何通过解决一些问题来使用上述逻辑。

问题1 就地反转阵列。

图片来源：作者 在 Python 中的实现：

def reverseArray(array):
        start, end = 0, len(array)-1
        while start< end:
            array[start], array[end] = array[end] , array[start]
            start += 1
            end -= 1
      
    array = [10, 20, 30, 40, 50]      
    reverseArray(array)
    print(array)

问题2 给定一个按非降序排序的整数数组，返回按非降序排序的每个数字的平方数组。

图片来源：作者 在 Python 中的实现：

def sortedSquares(nums):
        n = len(nums)
        start, end = 0, n-1
        res = [0]*n
        idx = n-1
        
        while end > -1 and idx >-1:
            if abs(nums[start]) > abs(nums[end]):
                res[idx] = nums[start] * nums[start]
                start +=1
            else:
                res[idx] = nums[end] * nums[end]
                end -= 1
            idx -= 1
        
        return res

问题3 链表中的查找周期：

图片来源：作者 在 Python 中的实现：

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
        
        def __repr__(self):
            return str(self.val)
    
    
    def hasCycle(head):
        
        if not head or not head.next:
            return False
        
        p1 = head
        p2 = head.next
        
        while p2:
            p2 = p2.next 
            if p2:
                p2 = p2.next 
            if not p2:
                return False
            
            p1 = p1.next
            
            if p1==p2:
                return True
    lt = [ListNode(item) for item in [3,2,0,-4]]
    head = lt[0]
    head.next = lt[1]
    lt[1].next= lt[2]
    lt[2].next = lt[3]
    lt[3].next = lt[1]
        
    print(hasCycle(head))

注意：在上述问题中，没有对节点进行排序。

问题4

给定一个字符串，找到最长子字符串的长度，不带重复字符。s

图片来源：作者 在 Python 中的实现：

def lengthOfLongestSubstring(s):
        seen, n = set(), len(s)
        right, res = -1, 0
        for left in range(n):
            print(left, right, s[left: right+1], seen)
            while right + 1 < n and s[right+1] not in seen:
                right += 1
                seen.add(s[right])
            res = max(res, right - left + 1)
            print( s[left: right+1])
            if right == n - 1:
                break
            seen.discard(s[left])
        return res
        
    print(lengthOfLongestSubstring("abcabcbb"))

问题5

给定三个大小不一定相同的排序数组 A、B 和 C。计算任何三元组 A\[i\]、B\[j\]、C\[k\] 的最大和最小数量之间的最小绝对差，使它们分别属于数组 A、B 和 C，即最小值（max（A\[i\]、B\[j\]、C\[k\]） — min（A\[i\]、B\[j\]、C\[k\]））

图片来源：作者 在 Python 中的实现：

def solve(A, B, C):
        i , j, k = 0, 0, 0
        m, n, p = len(A), len(B), len(C)
        min_diff = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]))
        while i < m and j < n and k < p:
            curr_diff = abs(max(A[i],B[j],C[k])-min(A[i],B[j],C[k]))
            if curr_diff < min_diff:
                min_diff = curr_diff
            min_term = min(A[i], B[j], C[k])
            if A[i] == min_term:
                i += 1
            elif B[j] == min_term:
                j += 1
            else:
                k += 1
        return min_diff
    A = [1,4,5,8,10]
    B = [6,9,15]
    C = [2,3,6,6]
    print(solve(A, B, C))

问题6 给定非负整数，其中每个整数表示坐标处的一个点。 绘制垂直线，使线的两个端点位于 和 处。找到两条线，它们与 x 轴一起形成一个容器，使得容器包含最多的水。na1, a2, ..., an(i, ai)ni(i, ai)(i, 0)

图片来源：作者 在 Python 中的实现：

def maxArea(height):
        l, r, max_area  = 0, len(height)-1, 0
        while l<r:
            base = r-l
            if height[r] >= height[l]:
                h = height[l]
                l+=1
            else:
                h = height[r]
                r-=1
            print(l,r)
            if h * base > max_area:
                max_area = h * base
        return max_area

注意：在最后一个问题中，数组未排序，但仍然适用双指针方法。

此技术可以扩展到两个以上的指针。

问题7 给定三个整数数组，并按严格的递增顺序排序，返回一个仅包含出现在所有三个数组中的整数的排序数组。arr1arr2arr3

我们从三分球开始，然后增加小于三个元素最大值的三分球。

def arraysIntersection(arr1, arr2, arr3):
        i, j, k = 0, 0, 0
        p, q, r = len(arr1), len(arr2), len(arr3)
        res = []
        while i < p and j < q and k < r:
            if arr1[i] == arr2[j] == arr3[k]:
                res.append(arr1[i])
                i += 1 
                j += 1
                k += 1
                continue
            min_next_possible = max(arr1[i], arr2[j], arr3[k])
            if arr1[i] < min_next_possible:
                i += 1
            if arr2[j] < min_next_possible:
                j += 1
            if arr3[k] < min_next_possible:
                k += 1
        return res

希望这有所帮助，并鼓励您尝试这种技术（如果尚未完成）。有关进一步的练习题，请参见下文：

同向运动问题：

查找任何连续子数组大小 k 的最大值 从排序数组中删除重复项 合并排序数组

相反方向运动问题：

二和二 有效 回文 移动零 删除排序数组中的重复元素

以下是找到任何长度为k的连续子数组的最大值的Python代码: python

def max_subarray_of_size_k(k, nums):
        max_sum = float('-inf')
        window_sum = 0
        
        left = 0
        right = 0
        
        while right < len(nums):
          
            window_sum += nums[right]
            
            if right - left + 1 == k:
                max_sum = max(max_sum, window_sum)
                window_sum -= nums[left]
                left += 1
                
            right += 1
                
        return max_sum

这个算法做了下列事情:

1.  维护一个大小为k的滑动窗口,记录窗口内元素和为window\_sum
2.  不断增加右边界right,计算新加入元素后的窗口和
3.  当窗口大小达到k时,更新最大和max\_sum
4.  将左边界left右移一个位置,移出窗口,并修正窗口和 window\_sum
5.  不断重复上述过程,直到右边界right遍历完数组
6.  最终返回最大和max\_sum

时间复杂度为O(n),我们只遍历了一次数组。 一个完整的用法示例: python nums = \[1,4,2,10,2,3,1,0,20\] k = 3

print(max\_subarray\_of\_size\_k(k, nums))

## 22 ##

## (10 + 2 + 3) 是大小为 3 的最大子数组和 ##

希望能清楚地解释这段代码!任何问题欢迎提出

本文由[ mdnice ][mdnice]多平台发布

[mdnice]: https://mdnice.com/?platform=4