目录
  1. 1. 前言
  2. 2. 贪心算法
  3. 3. 455-分发饼干
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 435-无重叠区间
    1. 4.1. 题目
    2. 4.2. 题解
  5. 5. 452-用最少数量的箭引爆气球
    1. 5.1. 题目
    2. 5.2. 题解
  6. 6. 406-根据身高重建队列
    1. 6.1. 题目
    2. 6.2. 题解
  7. 7. 121-买卖股票的最佳时机
    1. 7.1. 题目
    2. 7.2. 题解
  8. 8. 122-股票买卖的最佳时间II
    1. 8.1. 题目
    2. 8.2. 题解
  9. 9. 605-种花问题
    1. 9.1. 题目
    2. 9.2. 题解
  10. 10. 392-判断子序列
    1. 10.1. 题目
    2. 10.2. 题解
  11. 11. 665-非递减数列
    1. 11.1. 题目
    2. 11.2. 题解
  12. 12. 53-最大子序和
    1. 12.1. 题目
    2. 12.2. 题解
  13. 13. 763-划分字母区间※
    1. 13.1. 题目
    2. 13.2. 题解
leetcode-贪心

title: leetcode-贪心
date: 2020-06-27 02:05:59
categories: 刷题

前言

简单回顾贪心算法思想,并完成leetcode中几道经典的贪心算法题。

  • 455-分发饼干
  • 435-无重叠区间
  • 452-用最少数量的箭引爆气球
  • 406-根据身高重建队列
  • 121-买卖股票的最佳时机
  • 122-买卖股票的最佳时机II
  • 605-种花问题
  • 392-判断子序列
  • 665-非递减数列
  • 53-最大子序和
  • 763-划分字母区间

贪心算法

引用labuladong公众号-《运用贪心算法来做时间管理》

  • 什么是贪心算法呢?
    • 贪心算法可以认为是动态规划算法的一个特例,相比动态规划,使用贪心算法需要满足更多的条件(贪心选择性质),但是效率比动态规划要高。
    • 比如说一个算法问题使用暴力解法需要指数级时间,如果能使用动态规划消除重叠子问题,就可以降到多项式级别时间,如果满足贪心选择性质,那么可以进一步降低时间复杂度,达到线性级别的。
  • 什么是贪心选择性质?
    • 简单的说就是,每一步都做出一个局部最优选择,最终的结果就是全局最优。注意哦,这是一种特殊性质,其实只有一小部分问题拥有这个性质。

455-分发饼干

题目

  • 难度:简单

  • 题目:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

  • 注意:

    • 你可以假设胃口值为正。
    • 一个小朋友最多只能拥有一块饼干。
  • 示例:

    示例1:

    输入: [1,2,3], [1,1]

    输出: 1

    解释:
    你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
    虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
    所以你应该输出1。


    示例2:

    输入: [1,2], [1,2,3]

    输出: 2

    解释:
    你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
    你拥有的饼干数量和尺寸都足以让所有孩子满足。
    所以你应该输出2.

题解

  • 分析:
    • 给一个孩子的饼干应当尽量小并且又能满足该孩子,这样大饼干才能拿来给满足度比较大的孩子。
    • 因为满足度最小的孩子最容易得到满足,所以先满足满足度最小的孩子。
  • 证明:上述贪心策略,可以从局部最优达到全局最优
    • 反证法:假设存在一种比我们使用的贪心策略更优的最优策略。如果不存在这种最优策略,表示贪心策略就是最优策略,得到的解也就是全局最优解。
    • 证明:假设在某次选择中,贪心策略选择给当前满足度最小的孩子分配第 m 个饼干,第 m 个饼干为可以满足该孩子的最小饼干。假设存在一种最优策略,可以给该孩子分配第 n 个饼干,并且 m < n。我们可以发现,经过这一轮分配,贪心策略分配后剩下的饼干一定有一个比最优策略来得大。因此在后续的分配中,贪心策略一定能满足更多的孩子。也就是说不存在比贪心策略更优的策略,即贪心策略就是最优策略。
class Solution(object):
def findContentChildren(self, g, s):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
if not s or not g:
return 0

g.sort()
s.sort()

count = 0
i = 0
j = 0
while i < len(s) and j < len(g):
if s[i] >= g[j]: #如果最小的饼干能满足胃口最小的孩子
count += 1 #满足人数+1
i += 1 #找剩下饼干中最小的饼干
j += 1 #找剩下孩子中胃口最小的孩子
else:
i += 1 #最小饼干不满足胃口最小的孩子,从剩下饼干中找最小的饼干
return count
  • 时间复杂度:O(n),最多需要遍历s和g
  • 空间复杂度:O(1)

435-无重叠区间

题目

  • 难度:中等

  • 题目:给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

  • 注意:

    • 可以认为区间的终点总是大于它的起点。
    • 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。
  • 示例:

    示例1:

    输入: [ [1,2], [2,3], [3,4], [1,3] ]

    输出: 1

    解释: 移除 [1,3] 后,剩下的区间没有重叠。


    示例2:

    输入: [ [1,2], [1,2], [1,2] ]

    输出: 2

    解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。


    示例3:

    输入: [ [1,2], [2,3] ]

    输出: 0

    解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

题解

  • 分析:
    • 把问题转换成:最多能选取几个区间不重叠的区域
    • 那答案显然变成:总区间个数-不重叠区间个数
  • 步骤:
    1. 按照结束时间从小到大排序,然后对新列表遍历
    2. 判断当前区间是否满足:开始时间大于或等于上一次的结束时间
    3. 每次都选结束时间最早的
    4. 每选一次更新一下结束时间
    5. 返回总区间个数-不重叠区间个数
class Solution(object):
def eraseOverlapIntervals(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: int
"""
if not intervals:
return 0

intervals = sorted(intervals, key = lambda x : x[1])

ans = 0 #不重叠区域个数
end = -float('inf') #初始化结束时间无穷小

for i in intervals:
if i[0] >= end: #开始时间大于或等于上一次结束时间
ans += 1 #不重叠区域个数+1
end = i[1] #每选择一次更新一下结束时间
return len(intervals) - ans
  • 时间复杂度:O(nlogn),sorted()排序时间复杂度:O(nlogn),遍历一遍数组O(n)
  • 空间复杂度:O(1)

452-用最少数量的箭引爆气球

题目

  • 难度:中等

  • 题目:在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。由于它是水平的,所以y坐标并不重要,因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

    一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstartx_{start}xendx_{end}, 且满足 xstartxxendx_{start}≤ x ≤ x_{end},则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后,可以无限地前进。我们想找到使得所有气球全部被引爆,所需的弓箭的最小数量。

  • 示例:

    输入:
    [[10,16], [2,8], [1,6], [7,12]]

    输出:
    2

    解释:
    对于该样例,我们可以在x = 6(射爆[2,8],[1,6]两个气球)和 x = 11(射爆另外两个气球)。

题解

  • 分析:
    • 本题和435题类似,不同之处在于,本题[1,2]和[2,3]算重叠区间
    • 举例分析:
      • 假设只有1个气球,那么最少需要一支箭引爆
      • 假设有两个气球,坐标为[1,2]和[2,3],此时第二个气球的xstartx_{start}小于或等于第一个气球的xendx_{end}坐标,因此重叠,至少需要一支箭引爆气球
      • 假设有三个气球,坐标为[1,2]和[2,3]和[3,4],此时第三个气球的xstartx_{start}坐标大于前两个气球的xendx_{end}坐标的最小值,因此第三个区间不与前两个区间重叠,至少需要两支箭
  • 步骤:
    • 按照分析,如果有一个气球(区间),就至少需要一支箭,可以进行特例判断
    • 按照xendx_{end}从小到大排序,然后对新列表遍历
    • 判断当前区间是否满足:xstartx_{start}大于上一个区间xendx_{end}
    • 每次判断重叠区域都更新历史气球的最小xendx_{end}
    • 每增加一支箭就更新当前气球的xendx_{end}
class Solution(object):
def findMinArrowShots(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
n = len(points)
if n < 2:
return n

points = sorted(points, key = lambda x : x[1])

ans = 1 #只要有区间,就至少需要一支箭
end = points[0][1] #初始化end为第一个区间的x_end坐标值

for i in range(1, n):
if points[i][0] > end:
ans += 1 #箭数+1
end = points[i][1] #记录当前气球的x_end
else:
end = min(end, points[i][1]) #每次判断重叠区域都更新历史气球的最小x_end
return ans
  • 时间复杂度:O(nlogn),sorted()排序时间复杂度:O(nlogn),遍历一遍数组O(n)
  • 空间复杂度:O(1)

406-根据身高重建队列

题目

  • 难度:中等

  • 题目:假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

  • 注意:总人数少于1100人。

  • 示例:

    输入:
    [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

    输出:
    [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

题解

  • 思路:
    • 为了使插入操作不影响后续的操作,身高较高的学生应该先做插入操作,否则身高较小的学生原先正确插入的第 k 个位置可能会变成第 k+1 个位置。
    • 身高 h 降序、个数 k 值升序,然后将某个学生插入队列的第 k 个位置中。
  • 举例分析:
    • 最简单的情况,当队列所有人的(h,k)都是相同的高度h,只有k不同时,解决方案很简单:每个人在队列的索引index=k。
    • 即使不是所有人都是同一高度,这个策略也是可行的。因为个子矮的人相对于个子高的人是 “看不见” 的,所以可以先安排个子高的人。
    • 如[7,1],[6,1],[7,0],我们先安排身高为7的人,把他放在与k值相等索引上,再安排身高为6的人,同样把他放在与k值相等索引上。
    • 该策略可以递归进行:
      • 将最高的人按照 k 值升序排序,然后将它们放置到输出队列中与 k 值相等的索引位置上。
      • 按降序取下一个高度,同样按 k 值对该身高的人升序排序,然后逐个插入到输出队列中与 k 值相等的索引位置上。
      • 直到完成为止。
  • 步骤:
    • 排序:
      • 按高度h降序排序
      • 在同一高度的人中,按k值的升序排序
    • 逐个地把它们放在输出队列中,索引等于它们的 k 值。
    • 返回输出队列
class Solution(object):
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
if not people:
return None

#升高按降序,k值按升序排序
people = sorted(people, key = lambda x : (-x[0], x[1]))

output = []
for p in people:
output.insert(p[1],p)
return output
  • 时间复杂度:O(n2)O(n^2)。排序使用了O(nlogn),每个人插入输出队列需要O(k),其中k是当前输出队列的元素个数。总共的时间复杂度:k=0N1K=O(n2)\sum_{k=0}^{N-1}K=O(n^2)
  • 空间复杂度:O(1)

121-买卖股票的最佳时机

题目

  • 难度:简单

  • 题目:给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

  • 注意:你不能在买入股票前卖出股票

  • 示例:

    输入: [7,1,5,3,6,4]
    输出: 5
    解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。


    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题解

  • 第一次面试时候二面考的题~
  • 思路:
    • 记录历史购买股票的最低价,以这个价格作为买入价格。
    • 以当前的价格作为卖出价格,更新最大收益。
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0

max_value = 0
min_value = float('inf')
for price in prices:
min_value = min(min_value, price)
max_value = max(max_value, price - min_value)

return max_value
  • 时间复杂度:O(n),需要遍历一遍数组
  • 空间复杂度:O(1),常量空间

122-股票买卖的最佳时间II

题目

  • 难度:简单

  • 题目:给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

  • 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

  • 示例:

    输入: [7,1,5,3,6,4]
    输出: 7
    解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
      随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。


    输入: [1,2,3,4,5]
    输出: 4
    解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
      注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
      因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。


    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
  • 提示:

    • 1 <= prices.length <= 3 * 10 ^ 4
    • 0 <= prices[i] <= 10 ^ 4

题解

  • 思路:只要股票有涨,我们就买卖
    • 即相邻的两个数,后者减去前者如果是正数,我们就将其差值加入利润,这样遍历一遍数组,即可获得最大利润。
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) <= 1:
return 0

max_value = 0

for i in range(len(prices) - 1):
if prices[i + 1] - prices[i] > 0:
max_value += prices[i + 1] - prices[i]
return max_value
  • 时间复杂度:O(n),需要遍历一遍数组
  • 空间复杂度:O(1)

605-种花问题

题目

  • 难度:简单

  • 题目:假设你有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花卉不能种植在相邻的地块上,它们会争夺水源,两者都会死去。

    给定一个花坛(表示为一个数组包含0和1,其中0表示没种植花,1表示种植了花),和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花?能则返回True,不能则返回False。

  • 示例:

    输入: flowerbed = [1,0,0,0,1], n = 1
    输出: True

    输入: flowerbed = [1,0,0,0,1], n = 2
    输出: False
  • 注意:

    • 数组内已种好的花不会违反种植规则。
    • 输入的数组长度范围为 [1, 20000]。
    • n 是非负整数,且不会超过输入数组的大小。

题解

  • 思路:三个连续的0可以种一朵花
    • 从左到右扫描数组,如果数组有一个0,且这个0的左右两边也都是0,那么我们就可以再这个0种花,即将这个位置的值设为1,计数器count增加1。
  • **需要考虑边界情况:**数组首尾是否为0。
  • 如果可以修改原数组,我们可以在数组首尾添加0,避免边界的判断。
  • 如果不可以修改原数组,我们可以只判断一侧是否是0。
#不修改数组
class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
#初始化种花数位0
count = 0

length = len(flowerbed)

#边界:花坛的位置少于一个
if length <= 1:
return flowerbed.count(0) >= n

# 花盆,判断当前花盆的前一个花盆和后一个花盆以及当前花盆是否为空花盆,是就计数,并种上花
# 第一个和最后一个需要特殊处理

if flowerbed[0] == 0 and flowerbed[1] == 0:
count += 1
flowerbed[0] = 1

for i in range(1, length - 2):
if flowerbed[i] == 1:
continue

if flowerbed[i] == flowerbed[i - 1] == flowerbed[i + 1]:
count += 1
flowerbed[i] = 1
else:
if flowerbed[-1] == flowerbed[-2] == 0:
count += 1
return count >= n
#修改数组
class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
flowerbed = [0] + flowerbed + [0]

length = len(flowerbed)

for i in range(1, length - 1):
if flowerbed[i - 1] == flowerbed[i] == flowerbed[i + 1] == 0:
n = n - 1
flowerbed[i] = 1
return n <= 0
  • 时间复杂度:O(n),需要遍历一遍数组
  • 空间复杂度:O(1)

392-判断子序列

题目

  • 难度:简单

  • 题目:给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

    你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

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

  • 示例:

    示例 1:
    s = "abc", t = "ahbgdc"

    返回 true.

    示例 2:
    s = "axc", t = "ahbgdc"

    返回 false.

    后续挑战 :

    如果有大量输入的 S,称作S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

题解

  • 思路:双指针。设置两个指针,遍历两个字符串,判断字符串s的每个字符是否存在于t且对应顺序一致。
  • 没感觉到贪心,反而就是简单的双指针。
class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""

i = j = 0
count = 0 #已遍历s中的字符数
while i < len(s) and j < len(t):
if s[i] == t[j]:
count += 1
i += 1
j += 1
else:
j += 1
return count == len(s)
  • 时间复杂度:O(n),n为字符串t的长度,最多需要遍历整个字符串t

  • 空间复杂度:O(1)

  • 后续挑战:哈希表+二分法

  • 用哈希集合hase_set记录下t中每个字符出现过的位置,即最多有26个key

  • 对s中每个字母进行匹配,s[i]一定出现在s[i-1]之后,所以匹配s[i]的时候,应该找hash_set[s[i]]中大于s[i-1]的索引的索引值

  • 我们用匹配左边界的二分法(即匹配第一个大于等于目标值的数),找当前字母索引列表中第一个大于上一个字母索引的值

  • 如果某个匹配到的边界值等于当前字幕索引列表的长度,则表明无法匹配当前字母,返回False

  • 全部成功匹配返回True

class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""

hash_set = {}
for i, word in enumerate(t):
if word not in hash_set:
hash_set[word] = [i]
else:
hash_set[word].append(i)

# 匹配
index = -1
for word in s:
if word not in hash_set:
return False
# 字母s出现的索引 用二分法找到其中大于index的第一个
indexes = hash_set[word]
left = 0
right = len(indexes)
while left < right:
mid = left + (right - left) // 2
if indexes[mid] > index:
right = mid
else:
left = mid + 1
if left == len(indexes):
return False
index = indexes[left]

return True
  • 时间复杂度:O(nlogn),n是s的长度,二分查找O(logn)
  • 空间复杂度:O(1),最多有26个key

665-非递减数列

题目

  • 难度:简单

  • 题目:给你一个长度为 n 的整数数组,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列。

    我们是这样定义一个非递减数列的: 对于数组中所有的 i (0 <= i <= n-2),总满足 nums[i] <= nums[i + 1]。

  • 示例:

    输入: nums = [4,2,3]
    输出: true
    解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

    输入: nums = [4,2,1]
    输出: false
    解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
  • 说明:

    • 1 <= n <= 10 ^ 4
    • - 10 ^ 5 <= nums[i] <= 10 ^ 5

题解

  • 思路:遍历一遍数组,相邻的两个数,用后者减去前者得到差值,判断差值是否大于或等于0,如果不是,计数器count增加1,遍历数组时,如果count大于1,直接break,返回False。
  • **特殊情况(比较难考虑到):如[2,4,0,1]
    • 当下标 i == 2 时,nums[i] < nums[i-1],也就是 0 < 4,这时我们要保证数组非递减有两种选择
      • 选择 1:把 0 放大,并且保证 0 后面的数不能比 4 小,0 前面的数均是非递减的;nums[i + 1] > nums[i - 1]
      • 选择 2:把 4 缩小,并且保证 4 前面的数不能比 0 大,4 后面的数均是非递减的。nums[i-2]<nums[i]
    • 换言之,当 0 < 4时,如果以上两个选择中的保证同时不满足,说明该数组肯定无法通过只修改一个元素而变为非递减数组,该情况即为上述提到的 “特殊情况”。对于本例,有:当 0 < 4时,0 后面的数为 1,1 小于 4,不满足选择 1 的保证;且 4 前面的数为 2,4 后面的数为 0,0 小于 2,不满足选择 2 的保证。
class Solution(object):
def checkPossibility(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = len(nums)
if n == 1:
return True
count = 0
for i in range(1, n):
if nums[i] < nums[i - 1]:
count += 1
if i + 1 < n and i - 2 >= 0:
if nums[i + 1] < nums[i - 1] and nums[i - 2] > nums[i]:
return False
if count > 1:
return False
return True
  • 时间复杂度:O(n),遍历一遍数组,长度为n
  • 空间复杂度:O(1)

53-最大子序和

题目

  • 难度:简单

  • 题目:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

  • 示例:

    输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
  • 进阶:

    • 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

题解

  • 思路:
    • 对数组进行遍历,初始化当前最大连续子序列和cur_sum = 0,结果max_sum = nums[0]
    • 如果cur_sum > 0,则说明cur_sum对结果有增益效果,则 cur_sum 保留并加上当前遍历数字
    • 如果cur_sum < 0,则说明cur_sum对结果无增益效果,则 cur_sum 更新为当前遍历数数字
    • 每次比较cur_sum和max_sum的值,将大的赋值给max_sum
    • 返回max_sum
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

n = len(nums)
if n == 1:
return nums[0]

cur_sum = 0
max_sum = nums[0]

for num in nums:
if cur_sum > 0:
cur_sum += num
else:
cur_sum = num
max_sum = max(cur_sum, max_sum)

return max_sum

763-划分字母区间※

题目

  • 难度:中等

  • 题目:字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

  • 示例:

    输入:S = "ababcbacadefegdehijhklij"
    输出:[9,7,8]
    解释:
    划分结果为 "ababcbaca", "defegde", "hijhklij"。
    每个字母最多出现在一个片段中。
    像 "ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少。
  • 提示:

    • S的长度在[1, 500]之间。
    • S只包含小写字母 'a''z'

题解

  • 思路:
    • 策略就是不断地选择从最左边起最小的区间。可以从第一个字母开始分析,假设第一个字母是 ‘a’,那么第一个区间一定包含最后一次出现的 ‘a’。但第一个出现的 ‘a’ 和最后一个出现的 ‘a’ 之间可能还有其他字母,这些字母会让区间变大。举个例子,在 “abccaddbeffe” 字符串中,第一个最小的区间是 “abccaddb”。
    • 通过以上的分析,我们可以得出一个算法:对于遇到的每一个字母,去找这个字母最后一次出现的位置,用来更新当前的最小区间。
  • 步骤:
    • 定义数组 last[char] 来表示字符 char 最后一次出现的下标。定义 anchor 和 j 来表示当前区间的首尾。
    • 如果遇到的字符最后一出现的位置下标大于 j, 就让 j=last[c] 来拓展当前的区间。
    • 当遍历到了当前区间的末尾时(即 i==j ),把当前区间加入答案,同时将 start 设为 i+1 去找下一个区间。
class Solution(object):
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
#首先找到每个元素出现的最后位置,字典的形式,通过元素找到下标
last = {c: i for i, c in enumerate(S)}
#设置当前字符串区间
start = end = 0
#保存字符串的长度
res = []
#开始遍历元素"ababcbacadefegdehijhklij"
for i, c in enumerate(S):
#设置尾部
end = max(end, last[c])
#当区间里所有元素都遍历过
if i == end:
res.append(end - start + 1)
start = i + 1
return res
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
文章作者: Lesy
文章链接: https://lesylin.com/2020/06/27/leetcode-%E8%B4%AA%E5%BF%83/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment