Leetcode第272场周赛write up

发表于

找出数组中的第一个回文字符串

1
2
给你一个字符串数组 words ，找出并返回数组中的 第一个回文字符串 。如果不存在满足要求的字符串，返回一个 空字符串 "" 。
回文字符串 的定义为：如果一个字符串正着读和反着读一样，那么该字符串就是一个 回文字符串 。
1
2
3
4
输入：words = ["abc","car","ada","racecar","cool"]
输出："ada"
解释：第一个回文字符串是 "ada" 。
注意，"racecar" 也是回文字符串，但它不是第一个。
1
2
3
输入：words = ["notapalindrome","racecar"]
输出："racecar"
解释：第一个也是唯一一个回文字符串是 "racecar" 。
1
2
3
输入：words = ["def","ghi"]
输出：""
解释：不存在回文字符串，所以返回一个空字符串。

这道没什么说的，依次遍历每一个字符串取反后进行比较，如果相等直接返回

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def firstPalindrome(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        for word in words:
            r_word = word[::-1]
            if r_word == word:
                return word
        return ""

向字符串添加空格

1
2
3
4
给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces。
数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值之前。
例如，s = "EnjoyYourCoffee" 且 spaces = [5, 9] ，那么我们需要在 'Y' 和 'C' 之前添加空格，这两个字符分别位于下标 5 和下标 9 。因此，最终得到 "Enjoy Your Coffee" 。
请你添加空格，并返回修改后的字符串。
1
2
3
4
5
输入：s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
输出："Leetcode Helps Me Learn"
解释：
下标 8、13 和 15 对应 "LeetcodeHelpsMeLearn" 中加粗斜体字符。
接着在这些字符前添加空格。
1
2
3
4
5
输入：s = "icodeinpython", spaces = [1,5,7,9]
输出："i code in py thon"
解释：
下标 1、5、7 和 9 对应 "icodeinpython" 中加粗斜体字符。
接着在这些字符前添加空格。
1
2
3
4
输入：s = "spacing", spaces = [0,1,2,3,4,5,6]
输出：" s p a c i n g"
解释：
字符串的第一个字符前可以添加空格。

这道题的思路是：根据要插入空格的地方将字符串进行拆分，将拆分后的字符串通过空格连接即可。这里要注意spaces第一个位置和最后一个位置的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def addSpaces(self, s, spaces):
        """
        :type s: str
        :type spaces: List[int]
        :rtype: str
        """
        res = []
        for i in range(len(spaces)):
          //处理spaces第一个位置
            if i == 0:
                res.append(s[0:spaces[0]])
            else:
                res.append(s[spaces[i-1]:spaces[i]])
        //处理spaces最后一个位置
        if spaces[-1]<len(s):
            res.append(s[spaces[-1]:])
        return " ".join(res)

股票平滑下跌阶段的数目

1
2
3
给你一个整数数组 prices ，表示一支股票的历史每日股价，其中 prices[i] 是这支股票第 i 天的价格。
一个 平滑下降的阶段 定义为：对于 连续一天或者多天 ，每日股价都比 前一日股价恰好少 1 ，这个阶段第一天的股价没有限制。
请你返回 平滑下降阶段 的数目。
1
2
3
4
5
输入：prices = [3,2,1,4]
输出：7
解释：总共有 7 个平滑下降阶段：
[3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1]
注意，仅一天按照定义也是平滑下降阶段。
1
2
3
4
输入：prices = [8,6,7,7]
输出：4
解释：总共有 4 个连续平滑下降阶段：[8], [6], [7] 和 [7]
由于 8 - 6 ≠ 1 ，所以 [8,6] 不是平滑下降阶段。
1
2
3
输入：prices = [1]
输出：1
解释：总共有 1 个平滑下降阶段：[1]

这道题思路也比较简单，首先我们考虑一下，对于连续1天，则可以得到平滑下降的阶段是1个，对于连续2天，则可以得到平滑下降的阶段是3个，假如prices=[2,1]，则阶段值为[2],[1],[2,1]，对于连续3天，则可以得到平滑下降的阶段是6个，假如prices=[3,2,1]，则阶段值为[3],[2],[1],[3,2],[2,1],[3,2,1]，这样我们就可以找到规律，对于连续n天，平滑下降的阶段是1+2+...+n的值。

所以我们可以依次遍历prices中的值，找到每一个连续平滑阶段，并根据每一个阶段中的值计算数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution(object):
    def getDescentPeriods(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 1:
            return 1
        res = []
        tmp=[]
        result = 0
        i=1
        while i < len(prices):
          //如果前一个比后一个多1，则他们属于一个平滑阶段
            if prices[i-1]-prices[i] == 1:
                tmp.append(prices[i-1])
                i+=1
            else:
              //这里因为前一个值还没有加入到tmp中，因此先添加前一个值
                tmp.append(prices[i-1])
                ////先把之前的平滑阶段保存起来
                res.append(tmp)
                //判断后续的平滑阶段，因此tmp置为空
                tmp=[]
                i+=1
        if tmp:
          //如果tmp中有值，那说明最后一段没有加入到res中
            res.append(tmp)
        //如果prices中最后一个值比倒数第二个值小1，则最后一个值属于倒数第二个tmp平滑阶段
        if prices[-2] - prices[-1] == 1:
            res[-1].append(prices[-1])
        else:
          //否则的话最后一个值单独组成一个平滑阶段
            res.append([prices[-1]])
        for r in res:
          //计算累加和
          result += (1+len(r))*len(r)/2
        return result

做最后这道题之前，我们先做一下Leetcode第300题，最长递增子序列。

最长递增子序列

1
2
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
1
2
输入：nums = [0,1,0,3,2,3]
输出：4
1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1

这道题要找的是严格递增的子序列，我们首先来根据动态规划的思路走一遍。

如果nums的长度是1，那么不用考虑，直接返回1即可。

  • 从nums的长度大于等于2开始，首先我们要初始化一个dp数组。这个数组的初值可以全部设置为1，因为最短的子序列长度也是1。
  • 从第2个值开始遍历，依次比较当前值之前的所有值，从而更新当前值之前的最长子序列长度，更新到dp[i]中
  • 设置一个全局的值，用来保存最长子序列的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #动态规划
        if len(nums) <= 1:
            return len(nums)
        #初始化dp数组，其中dp[i]表示i之前包含i的最长上升子序列的长度
        dp = [1 for i in range(len(nums))]
        #用来保存最大值
        res = 0
        for i in range(1,len(nums)):
            for j in range(i):
                #如果当前i的值大于i之前的值
                if nums[i] > nums[j]:
                    #则对当前dp[i]中的值进行更新
                    dp[i] = max(dp[i],dp[j]+1)
            #如果当前dp[i]的值大于res的值，则更新res
            if dp[i] > res:
                res = dp[i]
        return res

另一种做法，通过bisect模块实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = []
        for x in nums:
          #因为要求得是严格递增的，因此这里遇到重复的值直接跳过
            if x in dp:
                continue
            #找到当前值在dp中应该插入的位置
            pos = bisect.bisect(dp, x)
            #这里会有两种情况，一种是dp为空，一种是pos应该插入到dp中最后一个位置
            if pos == len(dp):
                dp.append(x)
            else:
              #这种情况说明pos应该插入到dp中间位置。
                dp[pos] = x
        return len(dp)

使数组 K 递增的最少操作次数

1
2
3
4
5
6
7
8
9
10
给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。
如果对于每个满足 k <= i <= n-1 的下标 i ，都有 arr[i-k] <= arr[i] ，那么我们称 arr 是 K 递增 的。
比方说，arr = [4, 1, 5, 2, 6, 2] 对于 k = 2 是 K 递增的，因为：
arr[0] <= arr[2] (4 <= 5)
arr[1] <= arr[3] (1 <= 2)
arr[2] <= arr[4] (5 <= 6)
arr[3] <= arr[5] (2 <= 2)
但是，相同的数组 arr 对于 k = 1 不是 K 递增的（因为 arr[0] > arr[1]），对于 k = 3 也不是 K 递增的（因为 arr[0] > arr[3] ）。
每一次 操作 中，你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。
请你返回对于给定的 k ，使数组变成 K 递增的 最少操作次数 。
1
2
3
4
5
6
7
输入：arr = [5,4,3,2,1], k = 1
输出：4
解释：
对于 k = 1 ，数组最终必须变成非递减的。
可行的 K 递增结果数组为 [5,6,7,8,9]，[1,1,1,1,1]，[2,2,3,4,4] 。它们都需要 4 次操作。
次优解是将数组变成比方说 [6,7,8,9,10] ，因为需要 5 次操作。
显然我们无法使用少于 4 次操作将数组变成 K 递增的。
1
2
3
4
5
6
输入：arr = [4,1,5,2,6,2], k = 2
输出：0
解释：
这是题目描述中的例子。
对于每个满足 2 <= i <= 5 的下标 i ，有 arr[i-2] <= arr[i] 。
由于给定数组已经是 K 递增的，我们不需要进行任何操作。
1
2
3
4
5
6
7
输入：arr = [4,1,5,2,6,2], k = 3
输出：2
解释：
下标 3 和 5 是仅有的 3 <= i <= 5 且不满足 arr[i-3] <= arr[i] 的下标。
将数组变成 K 递增的方法之一是将 arr[3] 变为 4 ，且将 arr[5] 变成 5 。
数组变为 [4,1,5,4,6,5] 。
可能有其他方法将数组变为 K 递增的，但没有任何一种方法需要的操作次数小于 2 次。

这道题和Leetcode第300题有些类似，只不过这里面加了一个K递增的概念。而且要注意的是，这里面没有要求严格递增。所以这道题我们可以分三步走

  • 首先将数组分为k组
  • 对k组中的每个数组遍历，求解每个数组的最长子序列
  • 这k组中的每个数组长度减去每个数组的最长子序列就可以得到每个数组需要修改的最少操作数

最终将k组中每个数组变为非递减需要的最少操作数相加即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
    def kIncreasing(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        nums = [[] for i in range(k)]
        #将数组分成k个字数组
        for index,v in enumerate(arr):
            nums[index % k].append(v)
        res = 0
        #print(nums)
        #分别对每一个子数组求需要修改的最少操作次数
        for num in nums:
            res += self.lengthOfLIS(num)
        return res
    
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #动态规划
        if len(nums) <= 1:
            return 0
        #初始化dp数组，其中dp[i]表示i之前包含i的最长上升子序列的长度
        dp = [1 for i in range(len(nums))]
        #用来保存最大值
        res = 0
        for i in range(1,len(nums)):
            for j in range(i):
                #如果当前i的值大于i之前的值
                if nums[i] >= nums[j]:
                    #则对当前dp[i]中的值进行更新
                    dp[i] = max(dp[i],dp[j]+1)
            #如果当前dp[i]的值大于res的值，则更新res
            if dp[i] > res:
                res = dp[i]
        #res是最长递增子序列，长度减去之后就是需要修改的个数
        return len(nums) - res

超时了。。。。😭

另外一种做法，没超时🐶，基本思路还是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def kIncreasing(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        nums = [[] for i in range(k)]
        #将数组分成k个字数组
        for index,v in enumerate(arr):
            nums[index % k].append(v)
        res = 0
        #print(nums)
        #分别对每一个子数组求需要修改的最少操作次数
        for num in nums:
            res += self.lengthOfLIS(num)
        return res
    
    def lengthOfLIS(self,nums):
            dp = []
            for x in nums:
                pos = bisect_right(dp, x)
                if pos == len(dp):
                    dp.append(x)
                else:
                    dp[pos] = x
            return len(nums) - len(dp)