文字列の傍受に関する Tencent の質問について、どうすれば解決できますか?

文字列の傍受に関する Tencent の質問について
以前、Tencent に面接に行ったときに聞いた質問だったと記憶していますが、その時はペンで書くことができなかったので、簡単に話しました。今日時間があるときに書き留めましたが、完璧を達成するのはまだ非常に面倒であることがわかりました。


問題は次のとおりです。
「123abc456def789」のような文字列があるとします。文字列と切り捨てられる長さで渡されます。インターセプトした結果を返します。

要件:
1 タグと タグは長さにカウントされません。
2 インターセプトされた文字列では、元の タグが保持される必要がありますが、最後のタグが閉じられていない場合、その開始タグは削除されます。

例:
長さ 5 の質問内の文字列をインターセプトする場合、返される文字列は次のようになります: 123ab 長さ 8 をインターセプトする場合は、123abc45.



私のアプローチの一般的な考え方は次のとおりです。
1 まず文字列を順番に読み取り、2 タグ変数が html タグの開始タグである の形式であることが判明した場合は、それをスタックにプッシュします。このタグを格納するにはスタック構造を使用します。 +> (html タグの終了タグ) に遭遇すると、スタックから飛び出します。

3 それ以外の場合、通常の文字の場合は長さ counter++。インターセプトするために渡された長さと等しくなるまで。

4 最後に、スタックが空かどうかを判断し、空の場合は、インターセプトされた文字列を直接返します。それ以外の場合は、スタック内の残りの要素を 1 つずつポップし、スタックの最上位ラベルを見つけます。インターセプトされた文字列から要素が最後に出現した位置を取得し、インデックスを返し、このタグを何も置き換えません。スタック全体が空になるまで。最後に、処理された文字列が返されます。



元の質問では、実際にはタグのネストを考慮していませんでした。プログラムがネストされたタグをより堅牢にするために最善を尽くしました。また、アルゴリズム自体がわかりにくくなる可能性があるため、PHP の組み込み関数はできるだけ使用しないようにしてください。たとえば、a1

b2c3d4

e5
の形式のネストされたタグを処理できます。しかし、ラベルが a1

b2c3d4

e5 という不規則な形式の場合、プログラムに問題が発生することがわかりました。スタック全体をループで検索するのではなく、取得した終了マークとスタックの先頭の要素を比較しただけだからです。実はここで変更することができます。


他にアイデアがあるかどうかはわかりませんが、これを行うのは面倒で、冗長です。これほど多くのコーディング面接中にペンで文字を書くのはクレイジーでしょう。また、時間計算量は理想的ではなく、約 O(n*(n2)) です。スペースの面でも余分なスペースを多くとります。きっととても簡単な方法があるはずだと思います。もっと簡単な方法はないか、皆さんも一緒に考えていただければと思います。

PHP コード

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->
<?php function mySubstr( $str, $length ){
    
    $tagcnt = 0;
    $charcnt = 0;
    $tag = '';
    $maxlen = strlen( $str );
    $resultstr = '';
    $tagstack = array();

    for( $i = 0; $i < $length; $i++ ){
        if( $str[$i] == '<' ){

            $resultstr .= $str[$i];

            for( $j=$i; $str[$j]!='>'; $j++,$length++ ){
                $tag .= $str[$j];
            }
            $tagcnt++;
            $length++;
            $tag .= '>';
            
            //如果是开始标记，则入栈，如果是与之相对应的结束标记则出栈
            if( preg_match('//i', $tag, $r) ){
                echo '入栈:',htmlspecialchars($r[1]),'<br>';
                array_push($tagstack, $r[1]);
            }
            elseif( preg_match( '/'.$tagstack[count($tagstack)-1].'/', $tag ) ){
                echo '出栈:',htmlspecialchars($tagstack[count($tagstack)-1]),'<br>';
                array_pop( $tagstack );
            }

            $tag = '';
            continue;
        }

        $charcnt++;
        $resultstr .= $str[$i];
    }

    
    echo '<hr size="1">最后结果为:';

    //栈是空的直接返回
    if(empty($tagstack)){
        return $resultstr;
    }
    //否则去掉没有结束标记的开始标记
    else{
        
        while(!empty($tagstack)){

            $tag = array_pop($tagstack);

            $index = strrpos($resultstr, $tag);

            for($i = $index-1; $resultstr[$i] != '>'; $i++ ){
                $resultstr[$i] = '';
            }

            $resultstr[$i++] = '';
        
        }

        return $resultstr;
    }
    
}

$sttime = microtime(true);

$stmem = memory_get_usage();

$str = "a1b2<p>c3<em>d4</em>e5</p>f6g7h8";

echo '处理结果为:<br><hr size="1">',htmlspecialchars( mySubstr( $str, 18 ) ),'<br>';

echo "内存使用情况:",(memory_get_usage()-$stmem),'<br>';

echo "算法运行时间(microtime):",(microtime(true)-$sttime),'<br>';

-----解決策---------- - --------
はは、この質問は印象的です

。

PHP コード

 を提供してください

$str = "a1b2<p>c3<em>d4</em>e5</p>f6g7h8";
$arr = preg_split('/(]*>)/', $str, -1, PREG_SPLIT_OFFSET_CAPTURE);
foreach($arr AS $k => $v)
{
    if(isset($arr[$k+1]))
    {
        $temp = $arr[$k][1] + strlen($arr[$k][0]);
        $arr[$k][2] = substr($str, $temp, $arr[$k+1][1] - $temp);
    }
}

print_r($arr);
/*
この処理を行うと、文字列はhtmlタグ＋このタグの前の文字を要素とした配列となります。 。次のように
配列
(
    [0] => 配列
        (
            [0] => a1
            [1] => 0
            [2] =>
        )
 …
*/
 <div class="clear"></div>