python---双指针

验证回文串（p125）

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串s，如果它是回文串，返回true；否则，返回false。

示例 1：

输入:s = "A man, a plan, a canal: Panama"输出：true解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"输出：false解释："raceacar" 不是回文串。

示例 3：

输入：s = " "输出：true解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。 由于空字符串正着反着读都一样，所以是回文串。

实现代码：

import re class Solution: def isPalindrome(self, s: str) -> bool: #正则表达式匹配非字母数字字符 pattern=r'[^A-Za-z0-9]' s = re.sub(pattern, '', s) s=s.lower() left=0 right=len(s)-1 while left<right: if s[left]!=s[right]: return False left+=1 right-=1 return True

盛最多的水

给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。

找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]输出：49解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]输出：1

实现代码：

class Solution: def maxArea(self, height: List[int]) -> int: left,right=0,len(height)-1 max_capacity=0 while left < right: capacity=height[right]*(right-left) if height[right]<height[left] else height[left]*(right-left) max_capacity=max_capacity if max_capacity>capacity else capacity if height[left]<=height[right]: left+=1 else: right-=1 return max_capacity