什麼是算法

Question

我試圖從codility解決問題

「即使資金」

，但我不能這樣做背後的邏輯。下面是問題。

即使總和是兩個球員的比賽。玩家獲得N個正整數序列並交替輪流。在每一回閤中，玩家選擇非空片段（連續元素的子序列），使得該片段中的值的總和爲偶數，然後移除片段並連接序列的其餘部分。無法做出合法舉動的第一位球員失去了比賽。

如果你和對手一樣玩這個遊戲，並且想知道你是否能贏，那麼假設你和你的對手都打得最好。你先行動。

寫功能：

string solution(vector< int>& A);

，鑑於一種零索引數組A由N個整數的，返回格式 「X，Y」 的一個字符串，其中X和Y分別是，該假設你有一個獲勝策略，你應該在第一步移除以取勝的第一個和最後一個位置（包含）。如果有多個獲勝切片，則該函數應該返回X值最小的切片。如果有多個切片的X值最小，則該函數應返回最短值。如果您沒有制勝策略，則該功能應返回「無解」。

例如，給定以下的數組：

A [0] = 4 A [1] = 5 A [2] = 3 A [3] = 7 A [4] = 2

函數應該返回「1,2」。從位置1到2（具有5 + 3 = 8的偶數和）中移除切片後，剩餘的陣列是[4,7,2]。然後對手將能夠移除第一個元素（偶數4）或最後一個元素（偶數2）。之後，你可以做一個讓陣列只包含[7]的動作，這樣你的對手就不會有合法的動作，並且會失敗。其中一個可能的遊戲顯示在following picture

請注意，刪除切片「2,3」（偶數和3 + 7 = 10）也是一個勝利的舉動，但切片「1,2」有一個較小的X.

的值。對於以下的數組：

A [0] = 2 A [1] = 5 A [2] = 4

函數應該返回「無解「，因爲沒有保證你贏的戰略。

假設：

N是範圍[1..100,000]內的整數;數組A的每個元素都是[1..1,000,000,000]範圍內的整數。複雜度：

預期的最壞情況時間複雜度爲O（N）;預期的最壞情況空間複雜度爲O（N），超出輸入存儲量（不包括輸入參數所需的存儲空間）。輸入數組的元素可以修改。 我在python中找到了一個在線解決方案。

def check(start, end): 
    if start>end: 
     res = 'NO SOLUTION' 
    else: 
     res = str(start) + ',' + str(end) 

    return res 

def trans(strr): 
    if strr =='NO SOLUTION': 
     return (-1, -1) 
    else: 
     a, b = strr.split(',') 
     return (int(a), int(b)) 


def solution(A): 
    # write your code in Python 2.7 

    odd_list = [ ind for ind in range(len(A)) if A[ind]%2==1 ] 

    if len(odd_list)%2==0: 
     return check(0, len(A)-1) 


    odd_list = [-1] + odd_list + [len(A)] 
    res_cand = [] 
    # the numbers at the either end of A are even 
    count = odd_list[1] 
    second_count = len(A)-1-odd_list[-2] 
    first_count = odd_list[2]-odd_list[1]-1 
    if second_count >= count: 
     res_cand.append( trans(check(odd_list[1]+1, len(A)-1-count))) 

    if first_count >= count: 
     res_cand.append( trans(check(odd_list[1]+count+1, len(A)-1))) 

    twosum = first_count + second_count 
    if second_count < count <= twosum: 
     res_cand.append( trans(check(odd_list[1]+(first_count-(count-second_count))+1, odd_list[-2]))) 

    ########################################### 
    count = len(A)-1-odd_list[-2] 
    first_count = odd_list[1] 
    second_count = odd_list[-2]-odd_list[-3]-1 
    if first_count >= count: 
     res_cand.append( trans(check(count, odd_list[-2]-1))) 

    if second_count >= count: 
     res_cand.append( trans(check(0, odd_list[-2]-count-1))) 

    twosum = first_count + second_count 
    if second_count < count <= twosum: 
     res_cand.append( trans(check(count-second_count, odd_list[-3]))) 



    res_cand = sorted(res_cand, key=lambda x: (-x[0],-x[1])) 

    cur = (-1, -2) 
    for item in res_cand: 
     if item[0]!=-1: 
      cur = item 

    return check(cur[0], cur[1]) 

此代碼的工作原理，我無法理解一個函數的代碼和流向另一個。但是我不明白算法的邏輯。它如何解決問題並解決問題。這可能是一個長期的任務，但任何人都可以請足夠小心的向我解釋算法。提前致謝。

Answer 1

到目前爲止，我發現奇數的數量對於找出結果至關重要。特別是第一個奇數和最後一個奇數的索引需要計算重要值。

現在我需要了解比較背後的邏輯，比如「if first_count> = count」以及「second_count < count < = twosum」。

更新： 嘿，我發現了我的問題的解決方案，並最終了解算法的邏輯。

這個想法存在於數組的對稱性背後。如果陣列是對稱的，我們永遠無法贏得比賽。這裏的對稱性定義爲中間只有一個奇數並且奇數兩邊的均等數量的陣列。

如果有偶數的話我們可以直接贏得比賽。

如果有奇數的機率，我們應該總是嘗試使陣列對稱。這就是該算法試圖做的事情。

現在有兩種情況。最後一個奇數將保留，否則將保留第一個奇數。如果你們不理解，我會很樂意解釋。謝謝。