文字列の傍受に関するテンセントの質問について
- WBOYオリジナル
- 2016-06-13 12:51:54906ブラウズ
文字列の傍受に関する Tencent の質問について
以前、Tencent に面接に行ったときに聞いた質問だったと記憶していますが、その時はペンで書くことができなかったので、簡単に話しました。今日時間があるときに書き留めましたが、完璧を達成するのはまだ非常に面倒であることがわかりました。
タイトルは:
「123907fae80ddef53131f3292ee4f81644babcd1c6776b927dc33c5d9114750b586338456907fae80ddef53131f3292ee4f81644bdefd1c6776b927dc33c5d9114750b586338789」のような文字列があるとします。文字列とインターセプトされる長さを渡すことができる関数を作成します。インターセプトした結果を返します。
要件:
1 907fae80ddef53131f3292ee4f81644b および d1c6776b927dc33c5d9114750b586338 タグは長さの計算に含まれません。
2. インターセプトされた文字列では、元の 907fae80ddef53131f3292ee4f81644b タグが保持される必要がありますが、最後のタグが閉じられていない場合、その開始タグは削除されます。
例:
質問の文字列について、長さ 5 をインターセプトしたい場合は、返される文字列は 123ab になります。長さ 8 をインターセプトしたい場合は、123907fae80ddef53131f3292ee4f81644babcd1c6776b927dc33c5d9114750b58633845 を返す必要があります。
私のアプローチの一般的な考え方は次のとおりです。
1 まず文字列を順番に読み取り、resultstr 変数を使用してすべての文字を記録します。64eb72d48e41977f2081ba33ebf8062a の形式であることが判明した場合は、それをスタックにプッシュします。このタグを格納するにはスタック構造を使用します。 9b5ccbc2fd6a71ce4fb7565d094c63f3 (html タグの終了タグ) に遭遇すると、スタックから飛び出します。
3 それ以外の場合、通常の文字の場合は長さカウンタ。インターセプトされるために渡された長さと等しくなるまで。
4 最後に、スタックが空かどうかを判断し、空の場合は、インターセプトされた文字列を直接返します。それ以外の場合は、スタック内の残りの要素を 1 つずつポップし、インターセプトされた文字列をループして、ラベル要素の最後の位置を見つけます。スタックの最上位にあるインデックスを返し、このラベルを何も置き換えません。スタック全体が空になるまで。最後に、処理された文字列が返されます。
実際、元の質問ではタグの入れ子について考慮されておらず、プログラムがより堅牢になるように入れ子になったタグを処理できるように最善を尽くしました。また、アルゴリズム自体がわかりにくくなる可能性があるため、PHP の組み込み関数はできるだけ使用しないようにしてください。たとえば、a1e388a4556c0f65e1904146cc1a846beeb2907fae80ddef53131f3292ee4f81644bc3d1c6776b927dc33c5d9114750b586338d494b3e26ee717c64999d7867364b1b4a3e5
この形式のネストされたタグ。しかし、ラベルが a1e388a4556c0f65e1904146cc1a846beeb2907fae80ddef53131f3292ee4f81644bc3d494b3e26ee717c64999d7867364b1b4a3e5 という不規則な形式の場合、プログラムに問題が発生することがわかりました。スタック全体をループで検索するのではなく、取得した終了マークとスタックの先頭の要素を比較しただけだからです。実はここで変更することができます。
他にアイデアがあるかどうかはわかりませんが、これを行うのは非常に面倒で、冗長です。これほど多くのコーディング面接中にペンで文字を書くのはクレイジーでしょう。また、時間計算量は理想的ではなく、約 O(n*(n2)) です。スペースの面でも余分なスペースを多くとります。きっととても簡単な方法があるはずだと思います。もっと簡単な方法はないか、皆さんも一緒に考えていただければと思います。
<br />
<?php<br />
function mySubstr( $str, $length ){<br />
<br />
$tagcnt = 0;<br />
$charcnt = 0;<br />
$tag = '';<br />
$maxlen = strlen( $str );<br />
$resultstr = '';<br />
$tagstack = array();<br />
<br />
for( $i = 0; $i < $length; $i++ ){<br />
if( $str[$i] == '<' ){<br />
<br />
$resultstr .= $str[$i];<br />
<br />
for( $j=$i; $str[$j]!='>'; $j++,$length++ ){<br />
$tag .= $str[$j];<br />
}<br />
$tagcnt++;<br />
$length++;<br />
$tag .= '>';<br />
<br />
//如果是开始标记，则入栈，如果是与之相对应的结束标记则出栈<br />
if( preg_match('/<([^\/]+)?>/i', $tag, $r) ){<br />
echo '入栈:',htmlspecialchars($r[1]),'<br />';<br />
array_push($tagstack, $r[1]);<br />
}<br />
elseif( preg_match( '/'.$tagstack[count($tagstack)-1].'/', $tag ) ){<br />
echo '出栈:',htmlspecialchars($tagstack[count($tagstack)-1]),'<br />';<br />
array_pop( $tagstack );<br />
}<br />
<br />
$tag = '';<br />
continue;<br />
}<br />
<br />
$charcnt++;<br />
$resultstr .= $str[$i];<br />
}<br />
<br />
<br />
echo '<hr size=1>最后结果为:';<br />
<br />
//栈是空的直接返回<br />
if(empty($tagstack)){<br />
return $resultstr;<br />
}<br />
//否则去掉没有结束标记的开始标记<br />
else{<br />
<br />
while(!empty($tagstack)){<br />
<br />
$tag = array_pop($tagstack);<br />
<br />
$index = strrpos($resultstr, $tag);<br />
<br />
for($i = $index-1; $resultstr[$i] != '>'; $i++ ){<br />
$resultstr[$i] = '';<br />
}<br />
<br />
$resultstr[$i++] = '';<br />
<br />
}<br />
<br />
return $resultstr;<br />
}<br />
<br />
}<br />
<br />
$sttime = microtime(true);<br />
<br />
$stmem = memory_get_usage();<br />
<br />
$str = "a1<body>b2<p>c3<em>d4</em>e5</p>f6</body>g7h8";<br />
<br />
echo '处理结果为:<br/><hr size=1>',htmlspecialchars( mySubstr( $str, 18 ) ),'<br />';<br />
<br />
echo "内存使用情况:",(memory_get_usage()-$stmem),'<br />';<br />
<br />
echo "算法运行时间(microtime):",(microtime(true)-$sttime),'<br/>';<br />
-----解決策--------------------------------
はは、この質問は印象的です
ぜひ貢献してください
<div class="clear"></div>