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 <= 100000 <= A[i] <= 10000
思路：
直接一遍遍历即可，数组长度小于3的直接返回False，如果大于3，先寻找山顶，山顶前的元素都是严格递增的，如果到了山顶数组结束了，那么返回False，如果没有结束，那么检查山顶后的元素是否都是严格递减的。
时间复杂度
空间复杂度
代码：
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 <= 1001 <= A[i].length <= 1000
思路：
遍历每列，只要出现逆序就需要删除。
时间复杂度
空间复杂度
代码：
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的要求。
时间复杂度
空间复杂度
代码：
解法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 <= 121 <= 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数组往回查找结果。
时间复杂度
空间复杂度
代码：
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)
