2

私はこのような配列を持っています:

["one", "foo", "two", "baz", "two", "one", "three", "lulz", "wtf", "three"]
   1             2             2      1       3                       3

各文字列は、オブジェクト リテラルにアクセスするためのキーです。私がやりたいことは、この場合one、two、 、およびthree. これは期待される結果です:

[
  'one', 'one.foo', 'one.two', 'one.two.baz', 'one.two', 'one',
  'three', 'three.lulz', 'three.wtf', 'three'
]

過去数時間、ループを使用して最初に重複したアイテムを抽出し、次に特定の開始点と終了点で配列をスライスしようとしました。それから、可能かどうかを確認するために正規表現を試してみましたが、JS は正規表現の再帰を処理せず、非常に複雑になり、おそらく不要になりました。私は欲求不満になり、何も機能していないところにいます。今どこに行けばいいのかわからない。私は立ち往生しています。

編集：より単純に見えたので、しばらくの間上記を試してきましたが、理想的には、終了「タグ」のないキーのチェーンだけを抽出したいだけです。

[
  'one', 'one.foo', 'one.two', 'one.two.baz',
  'three', 'three.lulz', 'three.wtf'
]

誰かがここで私を啓発できますか？

4

3 に答える 3

2

再帰がなければ、次のように解決できます。共通のプレフィックスを保持し、反復ごとに左右両方をスキャンして同一のアイテムを見つけます。

左に同一のアイテムがある場合は、プレフィックスを減らします (発行する前に)。右側に項目がある場合は、プレフィックスを増やします (発行後)。

var a = ["one", "foo", "two", "baz", "two", "one", "three", "lulz", "wtf", "three"];

var prefix = '',
    keys = [];

for (var i = 0, len = a.length; i < len; ++i) {
  var left = a.indexOf(a[i]),
      right = a.indexOf(a[i], i + 1);

  if (left >= 0 && left < i) {
    prefix = prefix.substr(0, prefix.lastIndexOf(a[i]));
  }
  keys.push(prefix + a[i]);
  if (right !== -1) {
    prefix = prefix + a[i] + '.';
  }
}

console.log(keys);

デモ

于 2013-02-06T08:24:44.747 に答える
1

ここで再帰を避けることができます。配列を歩くだけです。現在の配列要素を、蓄積している文字列と比較します。新しい「メイン」要素を初めて見たときは、それを構築中の文字列に追加します。これまでに取得した文字列のサフィックスと一致するメイン要素の終了インスタンスが表示されたら、それをポップします。歩きながら結果の配列を構築します。

たとえば、与えられた

["one", "foo", "two", "baz", "two", "one", "three", "lulz", "wtf", "three"]

最初に「one」が表示されるので、それを発します

result = ["one"]
working = "one"

それからあなたはそう見ますが、比較する文字列として"foo"のみ保持します。"one"

result = ["one", "one.foo"]
working = "one"

次に、あなたは"two"とても放出して保持してい"one.two"ます。 

result = ["one", "one.foo", "one.two"]
working = "one.two"

次は"baz"emit but do not keepです。

result = ["one", "one.foo", "one.two", "one.two.baz"]
working = "one.two"

次は"two"ポッポできるように！

result = ["one", "one.foo", "one.two", "one.two.baz"]
working = "one"

次に、"one"またポップ！

result = ["one", "one.foo", "one.two", "one.two.baz"]
working = ""

メインのタグである 3 つなので、発行して保持します。

result = ["one", "one.foo", "one.two", "one.two.baz", "three"]
working = "three"

簡単です！ここから取れると思います。派手な再帰は必要ありません。もちろん、ネスティングとバランシングのエラーをチェックする必要があるかもしれません。

于 2013-02-06T08:05:58.093 に答える
1

これが再帰的な解決策です。この関数は、現在のプレフィックスと操作対象の配列を受け取ります。配列が空の場合はキーの空の配列を返します。それ以外の場合は、配列の先頭からアイテムをシフトすることにより、現在のプレフィックスでキーを構築します。そのプロセス中に配列の最後に到達するか、配列の後半にある要素に到達すると、新しいキーの構築を停止して再帰します。

再帰は、繰り返しが見つかった要素の次の出現で配列を分割することによって機能します。現在のキーは、一方の呼び出しでは左側のサブ配列とともにプレフィックスとして使用され、もう一方の呼び出しでは空白のプレフィックスが右側のサブ配列とともに使用されます。この関数は、見つかったキーと、2 つの再帰呼び出しで見つかったキーを返します。

最も効率的なソリューションではありません。その点では反復的なソリューションの方が優れていますが、興味のある人のために再帰的なソリューションを投稿すると思いました。

function foldKeys(prefix, arr) {
    var keys = [],
        key,
        i;

    if (arr.length == 0) {
        return keys;
    }

    do {
        next = arr.shift();
        key = prefix + (prefix == '' ?  next : ('.' + next));
        keys.push(key);
    } while (arr.length && (i = arr.indexOf(next)) === -1);

    return keys
        .concat(foldKeys(key, arr.slice(0, i)))
        .concat(foldKeys('', arr.slice(i + 1)));
}

var arr = ["one", "foo", "two", "baz", "two", "one", "three", "lulz", "wtf", "three"];
var keys = foldKeys('', arr);
console.log(keys.toString());
于 2013-02-06T10:39:14.410 に答える