[数据结构与算法] Leetcode双指针刷题日记（python）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Leetcode双指针刷题日记（python） -> 正文阅读

[数据结构与算法]Leetcode双指针刷题日记（python）

数组拆分 I

示例 1：

输入：nums = [1,4,3,2] 输出：4 解释：所有可能的分法（忽略元素顺序）为：

(1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
(1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
(1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 所以最大总和为 4

思路：两两拆分，返回最小，实际上就是将排序之后的偶数项相加：

class Solution(object):
 ? ?def arrayPairSum(self, nums):
 ? ? ? ?"""
 ? ? ?  :type nums: List[int]
 ? ? ?  :rtype: int
 ? ? ?  """
 ? ? ? ?l = len(nums) ? ?#法1
 ? ? ? ?nums.sort()
 ? ? ? ?res = 0
 ? ? ? ?for i in range(l):
 ? ? ? ? ? ?if i%2 == 0:
 ? ? ? ? ? ? ? ?res += nums[i]
 ? ? ? ?return res
 ? ?
 ? ?return sum(sorted(nums)[::2]) ?#法2，原理差不多
 ? ?

两数之和 II - 输入有序数组

示例 1：

输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

思路：采用二分法，从两端的和开始判断，如果小于目标值，左边的向右移动，反之右边的向左边移

class Solution(object):
 ? ?def twoSum(self, numbers, target):
 ? ? ? ?l = len(numbers)
 ? ? ? ?l2 = l//2
 ? ? ? ?for i in range(l):
 ? ? ? ? ? ?for m in range(l):
 ? ? ? ? ? ? ? ?if numbers[i]+ numbers[m] == target and i != m:
 ? ? ? ? ? ? ? ? ? ?return [i+1,m+1] ? ?#暴力法，超时了。。。
 ?#优化 
class Solution(object):
 ? ?def twoSum(self, numbers, target):
 ? ? ? ?m = len(numbers)-1
 ? ? ? ?i = 0 
 ? ? ? ?while i< m: ? #i一定在m的左边
 ? ? ? ? ? ? ? ?if numbers[i]+numbers[m] < target:
 ? ? ? ? ? ? ? ? ? ?i += 1
 ? ? ? ? ? ? ? ?elif numbers[i]+numbers[m] > target:
 ? ? ? ? ? ? ? ? ? ?m -=1
 ? ? ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ? ? ?return [i+1,m+1]
 ? ? ? ?return -1
?

移除元素

示例 1：

输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

思路：主要是使用双指针，快指针和慢指针，当块指针不等于val的时候，将该数赋值给慢指针，也就是说快指针用于查找不等于val的数并将它赋值给慢指针，最后返回慢指针即达到移除元素：

class Solution(object):
 ? ?def removeElement(self, nums, val):
 ? ? ? ?"""
 ? ? ?  :type nums: List[int]
 ? ? ?  :type val: int
 ? ? ?  :rtype: int
 ? ? ?  """
 ? ? ? ?l = len(nums)
 ? ? ? ?m = 0
 ? ? ? ?for i in range(l):
 ? ? ? ? ? ?if nums[i] != val: ? ? #当快指针找到不等于val的数
 ? ? ? ? ? ? ? ?nums[m]= nums[i] ? ?#将它赋值给慢指针m ，m并向后移动以便接下来进行下一个数的存储
 ? ? ? ? ? ? ? ?m += 1
 ? ? ? ?return m

最大连续1的个数

示例 1：

输入：nums = [1,1,0,1,1,1] 输出：3 解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

思路：遍历nums,将1的个数存下来，并对保存下来的个数进行比较，返回最大值。

class Solution(object):
 ? ?def findMaxConsecutiveOnes(self, nums):
 ? ? ? ?res = 0
 ? ? ? ?count = 0
 ? ? ? ?l = len(nums)
 ? ? ? ?for i in range(l):
 ? ? ? ? ? ?if nums[i] == 1:
 ? ? ? ? ? ? ? ?count +=1 ? ? # count用于计数1出现的个数
 ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ?count = 0 ? ? # 当出现非1，则将count清零
 ? ? ? ? ? ?res = max(count,res) ?#对count的计数和res取最大值
 ? ? ? ?return res