LeetCode第111场周赛题解

2019-05-03 本文已影响0人独孤岳

941. 有效的山脉数组

题目难度Easy

给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

A.length >= 3
在 0 < i < A.length - 1条件下，存在 i使得：
- A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[B.length - 1]

示例 1：

输入：[2,1]
输出：false

示例 2：

输入：[3,5,5]
输出：false

示例 3：

输入：[0,3,2,1]
输出：true

提示：

0 <= A.length <= 10000
0 <= A[i] <= 10000

思路：

直接一遍遍历即可，数组长度小于3的直接返回False，如果大于3，先寻找山顶，山顶前的元素都是严格递增的，如果到了山顶数组结束了，那么返回False，如果没有结束，那么检查山顶后的元素是否都是严格递减的。

时间复杂度 $O(N)$

空间复杂度 $O(1)$

代码：

class Solution:
    def validMountainArray(self, A: List[int]) -> bool:
        l = len(A)
        if l < 3:
            return False
        i = 0
        while i < l - 1 and A[i] < A[i + 1]:
            i += 1
        if i == l - 1 or i == 0:
            return False
        while i < l - 1 and A[i] > A[i + 1]:
            i += 1
        if i == l - 1:
            return True
        return False

944. 删列造序

题目难度Easy

给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。

选取一个删除索引序列，对于 A 中的每个字符串，删除对应每个索引处的字符。所余下的字符串行从上往下读形成列。

比如，有 A = ["abcdef", "uvwxyz"]，删除索引序列 {0, 2, 3}，删除后 A 为["bef", "vyz"]， A 的列分别为["b","v"], ["e","y"], ["f","z"]。（形式上，第 n 列为 [A[0][n], A[1][n], ..., A[A.length-1][n]]）。

假设，我们选择了一组删除索引 D，那么在执行删除操作之后，A 中所剩余的每一列都必须是 非降序 排列的，然后请你返回 D.length 的最小可能值。

示例 1：

输入：["cba", "daf", "ghi"]
输出：1
解释：
当选择 D = {1}，删除后 A 的列为：["c","d","g"] 和 ["a","f","i"]，均为非降序排列。
若选择 D = {}，那么 A 的列 ["b","a","h"] 就不是非降序排列了。

示例 2：

输入：["a", "b"]
输出：0
解释：D = {}

示例 3：

输入：["zyx", "wvu", "tsr"]
输出：3
解释：D = {0, 1, 2}

提示：

1 <= A.length <= 100
1 <= A[i].length <= 1000

思路：

遍历每列，只要出现逆序就需要删除。

时间复杂度 $O(NM)$

空间复杂度 $O(1)$

代码：

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        ans = 0
        for i in range(len(A[0])):
            for j in range(len(A) - 1):
                if A[j][i] > A[j + 1][i]:
                    ans += 1
                    break
        return ans

一行代码写法

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        return sum([sorted(z) != list(z) for z in zip(*A)])

942. 增减字符串匹配

题目难度Easy

给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。

返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：

如果 S[i] == "I"，那么 A[i] < A[i+1]
如果 S[i] == "D"，那么 A[i] > A[i+1]

示例 1：

输出："IDID"
输出：[0,4,1,3,2]

示例 2：

输出："III"
输出：[0,1,2,3]

示例 3：

输出："DDI"
输出：[3,2,0,1]

提示：

1 <= S.length <= 1000
S 只包含字符 "I" 或 "D"。

思路：

贪心构造。对于一个长度为N的ID序列，可对应多个长度为N+1的数组A，我们可以这样构造一个符合条件的数组A，双指针一个（下限指针）指向数组A的最小值0，另一个（上限指针）指向数组A的最大值，如果序列中出现I那么我们就将最小值加入数组，下限加1，因为加入的是后面所有数中的最小值，所以无论后面再加入什么数字，都会符合I的要求；如果序列中出现D，那么我们就将最大值加入数组，上限减1，同理，因为加入的是后面所有数字的最大值，所以无论后面再加入什么数，都会符合D的要求。

时间复杂度 $O(N)$

空间复杂度 $O(N)$

代码：

解法1

class Solution:
    def diStringMatch(self, S: str) -> List[int]:
        n = len(S)
        ub = n
        lb = 0
        ans = []
        for c in S:
            if c == 'I':
                ans.append(lb)
                lb += 1
            else:
                ans.append(ub)
                ub -= 1
        return ans + [lb]

943. 最短超级串

题目难度Hard

给定一个字符串数组 A，找到以 A 中每个字符串作为子字符串的最短字符串。

我们可以假设 A 中没有字符串是 A 中另一个字符串的子字符串。

示例 1：

输入：["alex","loves","leetcode"]
输出："alexlovesleetcode"
解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。

示例 2：

输入：["catg","ctaagt","gcta","ttca","atgcatc"]
输出："gctaagttcatgcatc"

提示：

1 <= A.length <= 12
1 <= A[i].length <= 20

思路：

状态压缩动态规划：用dp[s][i]表示使用了集合s中的字符串并以全集中第i个字符串作为结尾的超级串最短长度，则状态转移方程为dp[s + j][j] = min(dp[s][i] + overlap(i, j)) for i in s，所以需要预处理每有序两个字符串对(i, j)之间的最大重叠长度，方法可以用KMP算法，也可以直接枚举子串。初始状态是把每个字符串单独看成一个集合，最小长度就是当前字符串的长度，返回结果的长度是S为全集，遍历i结尾的最小值，所以还需要一个pre数组来记录转移过程，最后通过pre数组往回查找结果。

时间复杂度 $O(2^NN^2)$

空间复杂度 $O(2^NN)$

代码：

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        # 求next数组
        def cal_next(s):
            l = len(s)
            if l == 1:
                return [0]
            next = [0, 0]
            for i in range(1, l):
                j = next[i]
                while j and s[i] != s[j]:
                    j = next[j]
                next.append(j + 1) if s[i] == s[j] else next.append(0)
            return next

        # kmp算法求后缀前缀最大重合
        def kmp(s, p):
            next = cal_next(p)
            j = 0
            for i in range(len(s)):
                while j and p[j] != s[i]:
                    j = next[j]
                if p[j] == s[i]:
                    j += 1
            return j
        
        n = len(A)
        # 记录后缀前缀最大重合
        pstr = dict()
        for i in range(n - 1):
            for j in range(i + 1, n):
                pstr[(i, j)] = kmp(A[i], A[j])
                pstr[(j, i)] = kmp(A[j], A[i])
        
        dp = [[1000 for _ in range(n)] for _ in range(1 << n)]
        pre = [[-1 for _ in range(n)] for _ in range(1 << n)]
        
        for i in range(n):
            dp[1 << i][i] = len(A[i])
        
        for s in range(1 << n):
            for i in range(n):
                if s & (1 << i):
                    for j in range(n):
                        if not s & (1 << j):
                            if dp[s][i] + len(A[j]) - pstr[i, j] < dp[s | (1 << j)][j]:
                                dp[s | (1 << j)][j] = dp[s][i] + len(A[j]) - pstr[i, j]
                                pre[s | (1 << j)][j] = i
        
        shortest = 1000
        last = -1
        for i, m in enumerate(dp[(1 << n) - 1]):
            if m < shortest:
                shortest = m
                last = i
        
        ans = [A[last]]
        s = (1 << n) - 1
        for i in range(n - 1):
            p = pre[s][last]
            ans.insert(0, A[p][:len(A[p]) - pstr[p, last]])
            s = s - (1 << last)
            last = p
            
        return ''.join(ans)

LeetCode第111场周赛题解

941. 有效的山脉数组

944. 删列造序

942. 增减字符串匹配

943. 最短超级串

猜你喜欢

热点阅读