4、贪心双指针问题
4、贪心双指针问题
605. 种花问题——种花问题
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。
示例 1：
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true
示例 2：
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false
提示：
1 <= flowerbed.length <= 2 * 104flowerbed[i]为0或1flowerbed中不存在相邻的两朵花0 <= n <= flowerbed.length
我觉得这道题非常巧妙，难度也不算太大，但是思路也还是比较巧妙的，让你觉得有思路但是又有点难以下手。其实只要把条件处理清楚了也是比较好做的。
1 0 0 0 1 0 0 1
情况一：当i = 0, nums[i]==1,我们需要判断i=3的情况，
情况二：当i=3，nums[i] =0，我们有需要分两个情况：
- 情况一：nums[i+1] == 1,i = i+1+2,加一是到情况一，再加2是从情况一开始判断
- 情况二：nums[i+1] == 0,这个位置我们是可以种花的
问题一，能不能种n个花：
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
left = 0
while left < len(flowerbed) and n > 0:
if flowerbed[left] == 1:
left += 2
elif flowerbed[left] == 0:
if left + 1 == len(flowerbed) or flowerbed[left + 1] == 0:
n -= 1
left += 2
else:
left += 3
return n == 0
问题二：最多中多少个花
class Solution:
def canPlaceFlowers(self, flowerbed: List[int]) -> bool:
left = 0
result = 0
while left < len(flowerbed):
if flowerbed[left] == 1:
left += 2
elif flowerbed[left] == 0:
if left + 1 == len(flowerbed) or flowerbed[left + 1] == 0:
result += 1
left += 2
else:
left += 3
return result
问题三：返回种完花的花坛
class Solution:
def canPlaceFlowers(self, flowerbed: List[int]) -> bool:
left = 0
while left < len(flowerbed):
if flowerbed[left] == 1:
left += 2
elif flowerbed[left] == 0:
if left + 1 == len(flowerbed) or flowerbed[left + 1] == 0:
flowerbed[left] = 1
left += 2
else:
left += 3
return flowerbed
11. 盛最多水的容器
给定一个长度为 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
思路：
当前矩形的面积是多少：(right-left)*min(height[left], height[right])
只要能想到这里就很好解决了
class Solution:
def maxArea(self, height: List[int]) -> int:
result = 0
left = 0
right = len(height) - 1
while left <= right:
cur_area = min(height[left], height[right]) * (right - left )
result = max(cur_area, result)
if height[left] < height[right]:
left += 1
else:
right -= 1
return result
881. 救生艇
给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。
示例 1：
输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)
示例 2：
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：
输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)
思路：
优先让船装重量小的两个人，然后在装重量大的一个人的，那么我们需要先对重量进行排序，让重量少的尽量在一起且有序，然后使用双指针进行遍历
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
result = 0
left = 0
right = len(people) - 1
people.sort()
while left <= right:
if people[left] + people[right] > limit:
right -= 1
else:
left += 1
right -= 1
result += 1
return result
611. 有效三角形的个数
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:
输入: nums = [4,2,3,4]
输出: 4
提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
这题我一开始使用的回溯算法，因为我看到了这个是求的是组合
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
result = []
self.back_tracking(nums, [], result, 0)
print(result)
return len(result)
def check(self, path: list):
x, y, z = path
return x + y > z and x + z > y and y + z > x
def back_tracking(self, nums: list, path: list, result: list, index: int):
if len(path) == 3 and self.check(path):
result.append(path[:])
return
for i in range(index, len(nums)):
path.append(nums[i])
self.back_tracking(nums, path, result, i + 1)
path.pop()
正确思路：
三角形的定义，任意两边之和要大于第三边，因此我们需要先对数据进行排序，然后遍历数据用较短的两个边相加和第三个边进行比较，判断是否满足条件，感觉和三数之和有点相似
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
# x, y, z从小到大，一定满足x+y > z
nums.sort()
result = 0
for right in range(2, len(nums)):
left = 0
middle = right - 1
# 先确定最右边
while left < middle :
if nums[left] + nums[middle] > nums[right]:
# 这里一旦满足条件就可以证明[left, middle]之间的所有数都是可以组合为三角形的
result += middle - left
middle -= 1
else:
left += 1
return result
问题：为什么要先确定最右边，先确定最左边结果如何算，先确定中间做不到
for left in range( len(nums)-2):
middle = left + 1
right = len(nums)-1
while middle <= right:
if nums[left] + nums[middle] > nums[right]:
result += ?
524. 通过删除字母匹配到字典里最长单词
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
示例 1：
输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"
示例 2：
输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"
提示：
1 <= s.length <= 10001 <= dictionary.length <= 10001 <= dictionary[i].length <= 1000s和dictionary[i]仅由小写英文字母组成
思路：
求dictionary长度最长且字母序最小的字符串是否在s中出现
我们首先可以通过双指针判断字符串a是否存在于字符串b中，接下来就是字母序最小，长度最长，这个可以通过排序实现
dictionary = ["ale", "apple", "monkey", "plea"]
dictionary.sort(key=lambda obj: obj)
dictionary.sort(key=lambda obj: len(obj), reverse=True)
print(dictionary)
# ['monkey', 'apple', 'plea', 'ale']
这个排序有可能不熟，其实我也不熟
class Solution:
def findLongestWord(self, s: str, dictionary: List[str]) -> str:
# 排序字典序最小且长度最长
dictionary.sort(key=lambda obj: (-len(obj), obj))
s_length = len(s)
for word in dictionary:
word_index = 0
s_index = 0
word_length = len(word)
while word_index < word_length and s_index < s_length:
if word[word_index] == s[s_index]:
word_index += 1
s_index += 1
if word_index == word_length:
return word
return ""