HackerRank Counting Valleys

Counting Valleys

這是 Hacker Rank 上面的題目，屬於多觀察類型的題目。

題目給出一個字串包含了「U」和「D」，兩個字元，一個是往上爬，一個是往下走，我們要去走這個步道，出發地和目的地都是在海平面，求這一路上有多少的山谷。

山谷的定義一段路都是在海平面以下，這段路如果都是起起伏伏的，但是沒有高過海平面的話，都是屬於同一個山谷，我們只能算做一次，題目也可以換另一個方式考，把山谷換成山脊。

老實說題目屬於簡單，不過我還是想了很久才想到要怎麼解，我試過從我知道的演算法，二分搜索，雙指針來做，我覺得不是做不出來，不過寫下去會發現題目給的限制鬆散（山谷的定義），遇到程式碼限制鬆散的情夼，寫起程式來一直要去判斷各種 Coner cases ，反而很容易遇到錯誤。

於是我就畫圖，如果要判斷是不是山谷，很重要的一點是要找一路上海平面轉折的地方在哪裡，因為有海平面的地方，就是山谷山脊的交界處，這時候很建議可以畫張圖看看，畫完就會觀察到，從山谷的頭尾去看，山谷從海平面開始的起始點，下一個位置一定是往下走的，山谷的終點上一個位置一定是往上走的。我們要判斷的條件就只剩下上面那個條件。

所以題目就變成，我們要判斷：一路上走回海平面的位置。

我們先將 U 和 D 轉換成數字的 1 與 -1 ，並且建立一個 mountainArray ，建立的時候，我們要注意要將題目沒有提到的起點與終點加進去。mountainArray 的每個元素就是前一個位置所在的高度，加上當前往上或是往下的步伐。

path = [1 if step == 'U' else -1 for step in path]
mountainArray = [0] * (steps + 2)
for i in range(len(path)):
    mountainArray[i+1] = mountainArray[i] + path[i]

接著我們要找出返回海平面所發生的位置

seaLevls = [idx for idx, val in enumerate(mountainArray) if val == 0]

最後一步是計算出有幾個山谷，我們每次要拿出兩個海平面的位置，檢查山谷從海平面開始的起始點，下一個位置一定是往下走的，山谷的終點上一個位置一定是往上走的這個條件有沒有成立，這裡沒有加等號的原因是因為如果是等號，代表我們一直在平地上面行走。

整體的時間複雜度是 O(n)，空間複雜度也是 O(n)

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'countingValleys' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER steps
#  2. STRING path
#

def countingValleys(steps, path):
    # Write your code here
    path = [1 if step == 'U' else -1 for step in path]
    mountainArray = [0] * (steps + 2)
    for i in range(len(path)):
        mountainArray[i+1] = mountainArray[i] + path[i]
    seaLevls = [idx for idx, val in enumerate(mountainArray) if val == 0]
    valleys = 0
    for i in range(1, len(seaLevls)):
        left = seaLevls[i-1]
        right = seaLevls[i]
        if mountainArray[left + 1] < 0 and mountainArray[right - 1] < 0:
            valleys += 1
    return valleys

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    steps = int(input().strip())

    path = input()

    result = countingValleys(steps, path)

    fptr.write(str(result) + '\n')

    fptr.close()