Python算法练习 9.11

leetcode 392 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

输入：s = "abc", t = "ahbgdc"
输出：true

class Solution(object):def isSubsequence(self, s, t):""":type s: str:type t: str:rtype: bool"""sflag = 0tflag = 0while 1:if tflag > len(t) - 1 or sflag > len(s) - 1:breakif s[sflag] == t[tflag]:sflag += 1tflag += 1else:tflag += 1if sflag == len(s):return Trueelse:return False

 

 leetcode 11 盛水最多的容器

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

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

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

说明：你不能倾斜容器。

 

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

其实就是短的那条线与两条线距离围成的长方形面积

双指针，由数组两端向中间移动

不管移动长板还是短板，宽一定减小，而高度由短板决定

所以移动短板：宽减小，高有可能增大，面积有可能增大

移动长板：宽减小，高一定减小，面积一定减小（下一个板更长，高仍然不变；下一个板更短，高就更短）

所以每次移动短板 

class Solution(object):def maxArea(self, height):""":type height: List[int]:rtype: int"""left = 0right = len(height) - 1maxArea = 0while left < right:maxArea = max(maxArea, min(height[left], height[right])*(right - left))if height[left] > height[right]:right -= 1else:left += 1return maxArea

leetcode 75 K和数对的最大数目

给你一个整数数组 nums 和一个整数 k 。

每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

输入：nums = [1,2,3,4], k = 5
输出：2
解释：开始时 nums = [1,2,3,4]：
- 移出 1 和 4 ，之后 nums = [2,3]
- 移出 2 和 3 ，之后 nums = []
不再有和为 5 的数对，因此最多执行 2 次操作。

class Solution(object):def maxOperations(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""numsSort = sorted(nums)left = 0right = len(nums) - 1maxOperations = 0while left < right:currentSum = numsSort[left]+numsSort[right]if currentSum > k:right -= 1if currentSum < k:left += 1if currentSum == k:maxOperations += 1right -= 1left += 1return maxOperations

 

 时间太久，算了就这样，摆烂了