T942 增减字符串匹配

桌桌 2022-8-12 57 8/12

题目描述如下:

T942 增减字符串匹配

解题思路:

选取一个中间数,如果是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

结果如下:

T942 增减字符串匹配

把没用到的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

结果如下:

T942 增减字符串匹配

- THE END -

桌桌

8月16日01:10

最后修改:2022年8月16日
0

非特殊说明,本博所有文章均为博主原创。