python - ジグザグ配列を作成するための最小可能ステップのカウント

Question

配列が与えられた場合、ジグザグパターンを作成するために配列に加えることができる最小限の変更を見つける必要があります。

編集：変更できるもの：配列内の個々の整数は、他の負または正の整数に変更できます。各変更は 1 つの変更としてカウントされます。

私はこれをやろうとしています：

配列を Higher-Lower-Higher-Lower... パターンに従うために必要なステップ数を数えます
配列がLower-Higher....パターンに従うようにするために必要なステップ数を数えます
値が小さい方を返す

これは私が持っているものです:

def minOperations(arr):
    def first(arr): 
        count1 = 0
        i = 1
        k = len(arr)
        while i < k-1:
            if arr[i-1] < arr[i] > arr[i+1] :
                i += 2
            elif arr[i-1] > arr[i] > arr[i+1]:
                arr[i] = arr[i-1]+1
                i += 2
                count1 += 1
            elif arr[i-1] < arr[i] < arr[i+1]:
                arr[i] = arr[i+1]+1
                i+= 2
                count1 += 1
            elif arr[i-1] == arr[i]:
                arr[i] = (abs(arr[i-1])+abs(arr[i+1]))
                count1 += 1
                i += 2
            elif arr[i-1] < arr[i] == arr[i+1]:
                arr[i] = arr[i+1]+1
                count1 += 1
                i += 2
            else:
                i += 1
        return count1
    
    def second(arr):
        ij = 1
        k = len(arr)
        count2=0
        while ij < k-1:
            if arr[ij-1] > arr[ij] < arr[ij+1] :
                ij += 2
            elif arr[ij-1] > arr[ij] > arr[ij+1]:
                arr[ij] = arr[ij+1]-1
                ij += 2
                count2 += 1
            elif arr[ij-1] < arr[ij] < arr[ij+1]:
                arr[ij] = arr[ij-1]-1
                ij+= 2
                count2 += 1
            elif arr[ij-1] == arr[ij]:
                arr[ij] = -arr[ij-1]
                count2 += 1
                ij += 2
            elif arr[ij] == arr[ij+1]:
                arr[ij] = arr[ij+1]-1 - abs(arr[ij-1])
                count2 += 1
                ij += 2
            else:
                ij += 1
        return count2
        
    count1 = first(arr)
    count2 = second(arr)
    return count1 if count1<count2 else count2

編集 2: 入力は任意の整数配列です。出力は、arr[0]>arr[1]<arr[2]>arr[3]... または arr[0]<arr で始まるジグザグパターンを作成するための変更の最小数を示す整数です。 [1]>arr[2]...

外すと

def second(arr)...

ほとんどの場合、うまく機能します。

この 1000 行の入力では、正しい出力を取得するのに苦労しています (以下)。

count1 が 112 になる

正しい出力は 106 です

唯一の変更点が追加である場合、def first(arr) が問題なくダウンしたと考えています。最も効率的な出力につながる変更に減算が含まれている場合、それらがありません。

もっと簡単な解決策があると感じています。私はそれを見ていません。この問題にどのように取り組みますか?

PS: 私の最初のスタックオーバーフローの投稿に付き合ってくれてありがとう。これを整理するために詳細を提供するために最善を尽くしています。

python - ジグザグ配列を作成するための最小可能ステップのカウント

1 に答える 1

Related

Reference