LeetCode解題筆記#4 -Advantage Shuffle

Advantage Shuffle 這題我認為難的地方是在於想出如何解題,而不是寫程式的過程,當然我在解這題的過程中,看到別人的程式碼也看到了更簡潔的處理資料的方式,以下我都會進行講解,那就開始吧!

Advantage Shuffle 題目詳解

Advantage Shuffle 老樣子中翻英的話,就是希望你能夠排兩個陣列的對陣表,在B陣列不會動的前提下,將A陣列排序到能夠以陣列內的元素為單位贏下最多的場次就是最好的排列,像是[2,7,11,15]對戰[1,10,4,11] 原本只有贏三個元素,但在改動排列成[2,11,7,15]時就變成贏四場了,那就會是最佳的排列,這個問題最難的在於,如果讓你們自己去排的話,你可能都無法很直覺的說清楚你排序的邏輯是什麼,所以這個題目想出在你的腦袋裡,你是怎麼排序的會是很重要的!那以下就來看看實際的邏輯會是什麼吧!

1.我希望能夠用最弱的選手去迎戰對面最弱的選手

2.假設我們自己最弱的選手連對面最弱的選手都贏不過,那就派他去和對面最強的選手打消耗戰

只要你能想出以上兩個邏輯,那基本上這題對你來說就沒什麼問題了,我們開始來看程式碼吧

A = sorted(A,reverse=True) 
B = sorted((b, i,) for i, b in enumerate(B))
B = sorted(B,reverse=True)

首先如果我們要做到以上兩點邏輯,還是需要對於資料做一些處理的,我們希望能夠用自己最弱去迎戰對面最弱,代表需要先將整個陣列做sorted,這樣才能夠去排出誰是最弱的,再來是,我們還必須要在做sorted的同時將B陣列原本數字的位置都保留下來,才能在決定對陣表的時候將元素排列到正確的位置,至於這邊可能會好奇為什麼要倒著排,這邊會跟後續會產生的小Bug有關係,因為這邊對於資料的處理方式最好的其實還是使用Deque的形式來處理,在後續才能夠寫出更簡短的程式碼,但我實際寫的時候根本沒想到,可能是功力也還不到吧XD

answer_list = []
for x in range(len(A)-1,-1,-1):
    if A[x]>B[x][0]: #如果A最弱大於B最弱 則將答案列B的位置放A,然後將A.B都pop掉
        answer_list[B[x][1]] = A[x]
        A.pop(x)
        B.pop(x)
    else: #A最弱沒有贏過B最弱,則將A最弱放大B最強的位置去抵銷,然後pop掉A和B最強
        answer_list[B[0][1]] = A[x]
        A.pop(x)
        B.pop(0)
return answer_list

在這邊我們只需要使用單迴圈就可以進行比較了,這邊使用遞減的原因就是前面要倒著排的關係,因為for迴圈開始的時候陣列是最長的,如果我們使用遞增的話,就會在pop的時候,導致陣列越來越小,但是x會越來越大,最後會導致list index out of range這項錯誤,所以我的解決方式就是倒著排,這樣x就會跟著陣列一起縮小,就不會超出範圍了,之後如註解寫的一樣,如果A最弱大於B最弱 則將答案列B的位置放A,然後將A.B都pop掉,pop掉就可以確定下一次比的數字不會涵蓋進已經被排好的數字,至於else的話也跟if的邏輯是一樣的,最後再將儲存對陣表的陣列回傳就可以了!

一樣附上整個程式讓同學們做參考,那今天的講解就到這邊了喔!

class Solution:
    def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
        #先sort之後 要紀錄B原本的位置
        A = sorted(A,reverse=True) 
        B = sorted((b, i,) for i, b in enumerate(B))
        B = sorted(B,reverse=True)
        answer_list = ['*']*len(A) #宣告空list用來放答案
        #用A最弱的和B最弱的比 如果比過就放過去,如果比輸就去跟最尾巴比
        for x in range(len(A)-1,-1,-1):
            if A[x]>B[x][0]: #如果A最弱大於B最弱 則將答案列B的位置放A,然後將A.B都pop掉
                answer_list[B[x][1]] = A[x]
                A.pop(x)
                B.pop(x)
            else: #A最弱沒有贏過B最弱,則將A最弱放大B最強的位置去抵銷,然後pop掉A和B最強
                answer_list[B[0][1]] = A[x]
                A.pop(x)
                B.pop(0)
        return answer_list


發佈留言

發佈留言必須填寫的電子郵件地址不會公開。