文字列の傍受に関する Tencent の質問について b2c3d4 b2c3d4
以前、Tencent に面接に行ったときに聞いた質問だったと記憶していますが、その時はペンで書くことができなかったので、簡単に話しました。今日時間があるときに書き留めましたが、完璧を達成するのはまだ非常に面倒であることがわかりました。
タイトルは:
「123abc456def789」のような文字列があるとします。文字列とインターセプトされる長さを渡すことができる関数を作成します。インターセプトした結果を返します。
要件:
1 および タグは長さの計算に含まれません。
2. インターセプトされた文字列では、元の タグが保持される必要がありますが、最後のタグが閉じられていない場合、その開始タグは削除されます。
例:
質問の文字列について、長さ 5 をインターセプトしたい場合は、返される文字列は 123ab になります。長さ 8 をインターセプトしたい場合は、123abc45 を返す必要があります。
私のアプローチの一般的な考え方は次のとおりです。
1 まず文字列を順番に読み取り、resultstr 変数を使用してすべての文字を記録します。< マークが見つかったら、タグ変数を使用して部分文字列の記録を開始します。
2. タグ変数が html タグの開始タグである
3 それ以外の場合、通常の文字の場合は長さカウンタ。インターセプトされるために渡された長さと等しくなるまで。
4 最後に、スタックが空かどうかを判断し、空の場合は、インターセプトされた文字列を直接返します。それ以外の場合は、スタック内の残りの要素を 1 つずつポップし、インターセプトされた文字列をループして、ラベル要素の最後の位置を見つけます。スタックの最上位にあるインデックスを返し、このラベルを何も置き換えません。スタック全体が空になるまで。最後に、処理された文字列が返されます。
実際、元の質問ではタグの入れ子について考慮されておらず、プログラムがより堅牢になるように入れ子になったタグを処理できるように最善を尽くしました。また、アルゴリズム自体がわかりにくくなる可能性があるため、PHP の組み込み関数はできるだけ使用しないようにしてください。たとえば、a1
この形式のネストされたタグ。しかし、ラベルが a1
他にアイデアがあるかどうかはわかりませんが、これを行うのは非常に面倒で、冗長です。これほど多くのコーディング面接中にペンで文字を書くのはクレイジーでしょう。また、時間計算量は理想的ではなく、約 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>
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
