【题目描述】
给定只含 "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]
思路:
题意意思是 给你一个只包含I和D的字符串,然后返回同时满足一下条件的数组
如果 S[i] == "I",那么 A[i] < A[i+1]
如果 S[i] == "D",那么 A[i] > A[i+1]
- 当字符为 I 时,返回所对应的数字是递增的;
- 当字符为 D 时,返回所对应的数字是递减的;
- 返回的数字区间是 0-S.length
- 所以定义两个变量min(对应I) 和 max(对应D),min从0开始 来记录 I 所对应的数字,每碰到一个 I ,min++,max从S.length开始,每碰到一个D,max--
- 时间复杂度为字符串的遍历 O(n)
- 空间复杂度为O(n)
代码实现:
func diStringMatch(_ S: String) -> [Int] {
var result = [Int]()
var min = 0
var max = S.count
for cha in S {
if cha == "I" {
result.append(min)
min+=1
} else {
result.append(max)
max-=1
}
}
result.append(min)
return result
}
网友评论