पायथन में खाली और भरी सीटों के बीच अधिकतम दूरी ढूंढने का प्रोग्राम

मान लीजिए हमारे पास seats नामक एक सूची है जिसमें केवल 0s और 1s हैं। जहां seats[i] एक सीट दर्शाता है। जब यह 1 होता है, तो यह भरा हुआ है, अन्यथा खाली। कम से कम एक खाली सीट और कम से कम एक भरी सीट है, हमें खाली सीट से निकटतम भरी सीट तक की अधिकतम दूरी ढूंढनी है।

तो, यदि इनपुट seats = [1, 0, 1, 0, 0, 0, 1] है, तो आउटपुट 2 होगा, क्योंकि हम seats[4] पर कब्जा कर सकते हैं, तब दूरी 2 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• res := 0

• last := -1

• n := seats का आकार

• i के लिए 0 से n - 1 तक की रेंज में, करें

  • यदि seats[i] 1 है, तो

    • res := res और (i यदि last < 0 अन्यथा (i-last)/2 का फ्लोर) का अधिकतम

    • last := i

• res और (n-last-1) का अधिकतम लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें

def solve(seats):
    res, last, n = 0, -1, len(seats)
    for i in range(n):
        if seats[i]:
            res = max(res, i if last < 0 else (i - last) // 2)
            last = i
    return max(res, n - last - 1)

seats = [1, 0, 1, 0, 0, 0, 1]
print(solve(seats))

इनपुट

[1, 0, 1, 0, 0, 0, 1]

आउटपुट

2