942. 增减字符串匹配

【题意】

        是有点难懂了,给出一个字符串S,S全部由‘D’和‘I’组成,然后现在需要解出一个数组,而这个数组需要和S相匹配。假设S的长度为N,那么这个数组的长度是N+1,并且值是集合{0...N}的任意排列。给出一个例子,假设有字符串S1 = "DIDID",那么S1的长度为5,那么答案就必须是集合{0,1,2,3,4,5}的一个排序,可能是{5,4,3,2,1,0},也可能是{0,1,3,5,2,4}等等。

        而这个排序必须是与字符串S相匹配的。这里上题目的example:

“IDID”

[0,4,1,3,2]

题目的意思是,将字符串与数组一一对应,因为数组多一位,不考虑这一位。剩下的位置,如果字符串写的是‘I’,那么该位置上的数应该比右边所有的数都小。而如果是‘D’,则是比右边的都大。现在需要找到其中任意一组。
---------------------
作者:iwts_poi
来源:CSDN
原文:https://blog.csdn.net/iwts_24/article/details/84436773
版权声明:本文为博主原创文章,转载请附上博文链接!

【我的思路】

S="IDID"

A=[0,1,2,3,4]

1.迭代S

2.碰到“I”就找A里面的最小值,然后把这个最小值放到ret数组里面并移出A。

3.碰到“D”就找A里面的最大值,然后把这个最大值放到ret数组里面并移出A。

4.最后因为A比S长度大1,所以迭代完后A里面还会剩一个元素,把这个元素放进ret

5.ret就是最后的结果数组

ret=[0,4,1,3,2]

class Solution:
    def diStringMatch(self, S):
        """
        因为是递增的A,所以列表头永远指向最小,列表尾永远指向最大
        通过出队和出栈的方法实现
        """
        A=list(range(len(S)+1))
        ret=[]
        for x in range(len(S)):
            if S[x]=="I" :
                ret.append(A.pop(0))
            else:
                ret.append(A.pop())
        ret.append(A[0])
        #print(ret)
        return ret
原文地址:https://www.cnblogs.com/remly/p/10093645.html