解题思路:
选取一个中间数,如果是I就选一个大于该中间数并比当前所有数大1的数字,小于就选一个比该中间数小且比当前出现过的最小数小1的数。可以发现,字母D的数量就是我们要找的中间数,因为D的数量,是前一个数字比后一个数字大的数量,也就是该处的数字应该比我们的中间数要小的可能的数字的数量。
按照实例3,我们D的数量是2,所以从2开始,遇到第一个D,选取1,遇到第二个D,选取0,遇到I,选取3,最终为[2,1,0,3],对于每一个这样的字母序列,我们就找出了一个排序序列
代码如下:
class Solution:
def diStringMatch(self, s: str) -> List[int]:
inum = 0
dnum = 0
result = []
for item in s:
if item == "I":
inum += 1
else:
dnum += 1
result = [dnum]
psmallnum = dnum
pbignum = dnum
for item in s:
if item == "I":
pbignum += 1
result.append(pbignum)
else:
psmallnum -= 1
result.append(psmallnum)
return result
结果如下:
把没用到的inum计算和用不到的判断语句删除了,代码如下:
class Solution:
def diStringMatch(self, s: str) -> List[int]:
dnum = 0
result = []
for item in s:
if item == "D":
dnum += 1
result = [dnum]
psmallnum = dnum
pbignum = dnum
for item in s:
if item == "I":
pbignum += 1
result.append(pbignum)
else:
psmallnum -= 1
result.append(psmallnum)
return result
结果如下:
- THE END -
最后修改:2022年8月16日
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:https://wangyuanzhuo.top/t942-%e5%a2%9e%e5%87%8f%e5%ad%97%e7%ac%a6%e4%b8%b2%e5%8c%b9%e9%85%8d/