0

だから私は面接の練習問題をやっていて、これに出くわしました: 文字列 str と、文字列内のどのインデックスを交換できるかを示すペアの配列が与えられた場合、許可された交換を行った結果、辞書編集的に最大の文字列を返します。インデックスは何度でも交換できます。

例

str = "abdc" およびpairs = [[1, 4], [3, 4]] の場合、出力は swapLexOrder(str,pairs) = "dbca" になります。

指定されたインデックスを交換すると、文字列 "cbda"、"cbad"、"dbac"、"dbca" が得られます。このリストで辞書順で最大の文字列は「dbca」です。

組合を見つけることに関する実用的な答えがありますが、私の答えは遅すぎます:

[time limit] 4000ms (js)
0 ≤ pairs.length ≤ 5000,
pairs[i].length = 2.
1 ≤ str.length ≤ 10^4

誰かが私のコードを微調整して速度を上げるのを手伝ってくれませんか? 私が持っているコードは次のとおりです。

  function swapLexOrder(str, pairs) {
    if (!pairs.length){
        return str
    }

    answerHash = {}
    unmoved = findUnmoved(pairs, str.length)
    unionsArr = findUnions(pairs)


    for (i in unmoved){
        answerHash[unmoved[i]] = str[(unmoved[i]-1)]
    }

    unionsArr.forEach(function(union){
        letters = []
        for (i in union){
            letters.push(str[(union[i]-1)])
        }

        letters.sort()
        union.sort(function(a,b){
            return b-a
        })

        for (j in union){
            answerHash[union[j]] = letters[j]
        }
     })

    string = []
    for (keys in answerHash){
        string.push(answerHash[keys])
    }
    return string.join('')
}



//if two pairs share a number they belong in the same array
findUnions = function(pairs, unions){
   if (!unions){
       unions = [pairs[0]];
       pairs.shift();
   }else{
       if(pairs.length){
           unions.push(pairs[0])
           pairs.shift()
       }
   }

    if (!pairs.length){
        return unions
    }

    unite = true
    while (unite && pairs.length){
        unite = false
        loop1:
        for (i in unions){
            loop2:
            for (j in pairs){
                if (unions[i].includes(pairs[j][0])){
                    unions[i].push(pairs[j][1])
                    pairs.splice(j, 1)
                    unite = true
                    break loop1
                }else if (unions[i].includes(pairs[j][1])){
                    unions[i].push(pairs[j][0])
                    pairs.splice(j, 1)
                    unite = true
                    break loop1
                }
            }
        }
    }
    return findUnions(pairs, unions)
}


findUnmoved = function(pairs, length){
    range = []
    for (var i=1;i<length+1;i++){
        range.push(i);
    }
    allNum = [].concat.apply([], pairs)
    range = range.filter(function(x){
        return (!allNum.includes(x))
    })
    return range
}

おそらくユニオンを見つけるために使用している関数ですが、ハッシュを作成せずにそれを行うことができるのではないかと考えていましたか? また、問題を解決するためのより良い方法を知っている場合は、常に何か新しいことを学びたいと思っています. ありがとう！

4

1 に答える 1