건물을 선택하는 방법의 수

1851 단어 theabbieleetcodedsa
거리를 따라 있는 건물의 유형을 나타내는 0-인덱스 이진 문자열s이 제공됩니다.
  • s[i] = '0'ith 건물이 사무실임을 나타내고
  • s[i] = '1'ith 건물이 레스토랑임을 나타냅니다.

  • 시 공무원으로서 임의 검사를 위해 3개의 건물을 선택하려고 합니다. 그러나 다양성을 보장하기 위해 선택한 건물 중 두 개의 연속 건물이 같은 유형일 수 없습니다.
  • 예를 들어, 주어진 s = "0**0**1**1**0**1**" 에서 1st , 3rd5th 건물을 선택할 수 없습니다. 이는 동일한 유형의 두 개의 연속 건물로 인해 허용되지 않는 "0**11**" 건물입니다.

  • 3개의 건물을 선택하는 유효한 방법의 수를 반환합니다.

    예 1:

    입력: s = "001101"
    출력: 6
    설명:
    선택한 다음 인덱스 세트가 유효합니다.
  • [0,2,4] "00*110*1"에서 "010"을 형성
  • [0,3,4] "001*10*1"에서 "010"을 형성합니다
  • [1,2,4] "0*0110*1"에서 "010"을 형성
  • [1,3,4] "0*0110*1"에서 "010"을 형성합니다
  • [2,4,5] "00*1101*"에서 "101"을 형성합니다
  • [3,4,5] "001*101*"에서 "101"을 형성
    다른 선택은 유효하지 않습니다. 따라서 총 6가지 방법이 있습니다.

  • 예 2:

    입력: s = "11100"
    출력: 0
    설명: 유효한 선택 항목이 없다고 표시될 수 있습니다.

    제약:
  • 3 <= s.length <= 105
  • s[i]'0' 또는 '1' 입니다.

  • 해결책:

    class Solution:
        def numberOfWays(self, s: str) -> int:
            n = len(s)
            z = 0
            o = 0
            zeroes = [z]
            ones = [o]
            for c in s:
                if c == '0':
                    z += 1
                if c == '1':
                    o += 1
                zeroes.append(z)
                ones.append(o)
            ways = 0
            for i in range(n):
                if s[i] == '0':
                    ways += (ones[i] - ones[0]) * (ones[-1] - ones[i + 1])
                elif s[i] == '1':
                    ways += (zeroes[i] - zeroes[0]) * (zeroes[-1] - zeroes[i + 1])
            return ways
    

    좋은 웹페이지 즐겨찾기