区块链技术博客
www.b2bchain.cn

leetcode双周赛第31场,如何把做过的题做多的讲解

这篇文章主要介绍了leetcode双周赛第31场,如何把做过的题做多的讲解,通过具体代码讲解7909并且分析了leetcode双周赛第31场,如何把做过的题做多的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了leetcode双周赛第31场,如何把做过的题做多的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7909.html。具体如下:

leetcode双周赛第31场,如何把做过的题做多

      • 前两题的链接。
      • 题目三:字符串的好分割数目(题号:5458)
        • python代码
      • 题目四:形成目标数组的子数组最少增加次数(题号:5459)
        • 暴力法
          • python代码
        • 分治算法
          • python代码
        • 一次遍历

  因为写的较为细致,所以竟然把四道题分两次写了,希望大家看的时候能多多包涵。前两题的链接。

前两题的链接。

题目三:字符串的好分割数目(题号:5458)

给你一个字符串 s ,一个分割被称为 「好分割」 当它满足:将 s 分割成 2 个字符串 p 和 q ,它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。

请你返回 s 中好分割的数目。

 

示例 1:

输入:s = "aacaba" 输出:2 解释:总共有 5 种分割字符串"aacaba" 的方法,其中 2 种是好分割。 ("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。 ("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。 ("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。 ("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。 ("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。 

示例 2:

输入:s = "abcd" 输出:1 解释:好分割为将字符串分割成 ("ab", "cd") 。 

示例 3:

输入:s = "aaaaa" 输出:4 解释:所有分割都是好分割。

示例 4:

输入:s = "acbadbaada" 输出:2 

 

提示:

  • s 只包含小写英文字母。
  • 1 <= s.length <= 10^5

  这道题说白了就是一个字典,从左右两边分别前进,统计到每一个位置分割之后,左右两边不相同字符的个数,如果左边等于右边,则计入答案。
  核心的地方在于统计左右两边不相同字符的个数,这里需要使用哈希表来统计,一个哈希表从左往右扫描,一个哈希表从右往左扫描。直接看代码。

python代码

class Solution:     def numSplits(self, s: str) -> int:         diffl = set()         diffr = set()         res = 0         l, r = [0], [0]         for i in range(len(s)):             diffl.add(s[i])             l.append(len(diffl))             diffr.add(s[-1 - i])             r.append(len(diffr))         for i, j in zip(l, reversed(r)):             if i == j:                 res += 1         return res 

  哈希表的长度就是不相同字符的个数,一个从左往右,一个从右往左,对一个反向之后,就能把两个list对齐。
  这里时间复杂度和空间复杂度比较难以优化了。最终的时间复杂度是

O(n)O(n)

,空间复杂度

O(n)O(n)

题目四:形成目标数组的子数组最少增加次数(题号:5459)

给你一个整数数组 target 和一个数组 initial ,initial 数组与 target  数组有同样的维度,且一开始全部为 0 。

请你返回从 initial 得到  target 的最少操作次数,每次操作需遵循以下规则:

  • initial 中选择 任意 子数组,并将子数组中每个元素增加 1 。

答案保证在 32 位有符号整数以内。

 

示例 1:

输入:target = [1,2,3,2,1] 输出:3 解释:我们需要至少 3 次操作从 intial 数组得到 target 数组。 [0,0,0,0,0] 将下标为 0 到 4 的元素(包含二者)加 1 。 [1,1,1,1,1] 将下标为 1 到 3 的元素(包含二者)加 1 。 [1,2,2,2,1] 将下表为 2 的元素增加 1 。 [1,2,3,2,1] 得到了目标数组。 

示例 2:

输入:target = [3,1,1,2] 输出:4 解释:(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。 

示例 3:

输入:target = [3,1,5,4,2] 输出:7 解释:(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]                                    -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。 

示例 4:

输入:target = [1,1,1,1] 输出:1 

 

提示:

  • 1 <= target.length <= 10^5
  • 1 <= target[i] <= 10^5

  不知道这个题目为什么难度算是leetcode的hard。题不难,但是为了体现出hard的意义,我决定多用几种方法,把题做多。

暴力法

  直奔主题,既然要从全0变到target,那么可以考虑从target变到全0,每次对其中的数减1,如果前一个数减1了,那么后面的数如果不为0,则也可以跟着减1。可以只做一次变换。
  但是如果前面的数已经减到0了呢,显然当前数不为0,需要减一,但是这个时候,就得多一次变换了。需要使用一个标志来记录前面的数字是否减过1。

python代码
class Solution:     def minNumberOperations(self, target: List[int]) -> int:         res = min(target)         for i in range(len(target)):target[i]-=res         for j in range(max(target)+1):             flag = False             for i in range(len(target)):                 if target[i]>0:                     if not flag:                         res += 1                         flag = True                     target[i]-=1                 else:                     flag = False         return res 

  这里的代码做了一个小小的优化,如果最小的数都很大,那么可以直接按照最小的数做变换,可以节省一定的复杂度。最终的时间复杂度就是

O(nk)O(n*k)

,k代表最大的数减最小的数再+1。

分治算法

  我们上面的分析得出,显然一个列表的变换次数,取决于最小的数,直接做最小的数次数的变换之后,最小的数归0了,这个时候两边的区间就不能继续一起做变换了,这个时候,就可以用最小的数把两边分段,然后两边继续做变换。
  使用最小的数分段的时候,如果最小的数存在多个,这个时候可以把数组分成两段也可以分成多段。如果分成两段,后面的这个数还是最小的数,会继续对数组分段。但是分两段和多段的复杂度是一致的。
  显然这个思路,和快排很像,找一个分割点,把数组分成两段,分段的时候要逐个比较这个数是否是最小的数。而快排是遍历,然后比较。所以这个算法的时间复杂度也是

O(nlgn)O(nlgn)

python代码
class Solution:     def minNumberOperations(self, target: List[int]) -> int:         def core(start, end, base):             if start >= end:                 return 0             mins = min(target[start:end])             res = mins - base             for i in range(start, end):                 if target[i] == mins:                     res += core(start, i, mins)                     start = i + 1             return res + core(start, end, mins)          return core(0, len(target), 0)  

一次遍历

  其实这个方法并不难想到,但是确实是最优的。如果前一个数大,比当前的数小,那么当前的数肯定可以和前一个数一起变换。
  但是如果当前的数比前一个数大,那么至少可以和前一个数一起变换一些次数,这个次数就是前一个数的值。剩下的路只能当前的数自己去走。走的次数就是当前数-前一个数的次数。
  思路比较简单,直接上代码。

class Solution:     def minNumberOperations(self, target: List[int]) -> int:         res = pre = 0         for i in target:             res += max(i - pre, 0)             pre = i         return res 

  这个题用了多种解法,其实最希望掌握的还是分治,分治是一种思维方式,是一种套路,即使找不到巧妙解法的时候,也能突显出一个算法工程师的功底。
  这个题蛮有意思的,当你足够强大,就能为后面的挡风挡雨,当你不够强大,只能让后面的人自己去承担。

本文地址https://www.b2bchain.cn/7909.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » leetcode双周赛第31场,如何把做过的题做多的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们