目次
ディスカッションへの返信 (解決策)
ホームページ バックエンド開発 PHPチュートリアル 文字列の傍受に関するテンセントの質問について

文字列の傍受に関するテンセントの質問について

Jun 23, 2016 pm 02:03 PM

これは以前、テンセントの面接で私が尋ねた質問だったと記憶していますが、その時はペンで書くことができなかったので、今日は少し時間があったので、自分の考えをざっとまとめました。それを書き留めてみましたが、それを完璧に行うのはまだ非常に面倒であることがわかりました。


質問は次のとおりです:
"123abc456def789" のような文字列があると仮定して、文字列と長さをインターセプトする を渡すことができる関数を作成します。 。インターセプトした結果を返します。

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

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



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

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

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



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

b2c3d4

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

b2c3d4

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


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



<?phpfunction 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 = "a1<body>b2<p>c3<em>d4</em>e5</p>f6</body>g7h8";echo '处理结果为:<br/><hr size=1>',htmlspecialchars( mySubstr( $str, 18 ) ),'<br />';echo "内存使用情况:",(memory_get_usage()-$stmem),'<br />';echo "算法运行时间(microtime):",(microtime(true)-$sttime),'<br/>';
ログイン後にコピー


ディスカッションへの返信 (解決策)

投稿者のコードはすでに非常に優れていると言うべきです

まずいくつか意見を述べさせてください
1. テスト問題として、試験官はあらかじめ決められた答えを持っています。 任意のトピックについての詳細な分析は不必要であると考えられるかもしれません。フォーラムのトップページにこんな苦情投稿がありました
2. トピックから開始してHTMLタグを探しながらカウントします(元の投稿者もこれを行いました) 終了条件に達したら、キャッシュされたHTMLタグを確認して処理します。ネストは考慮されていないため、偶数にすることができ、最終的に戻り文字列が生成されます。この種のコードはコード量が少なく、コンピューター上でデバッグできなくてもエラーの確率が小さくなります
3. 実用的な機能としては、もっと考慮するのが自然です。投稿者のコードは一般的なタグの組み合わせのみを考慮していますが、独立したタグ



、自己終了タグ
などは HTML 内に表示できることを無視しています。

タグのネストのレベルがいくつであっても、一致するかどうかに関係なく、ブラウザーでのパフォーマンスは同じです

はは、この質問は印象的です

ぜひ投稿してください

$str = "a1<body>b2<p>c3<em>d4</em>e5</p>f6</body>g7h8";$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标签 + 这个标签之前的字符 组成的元素 组成的数组。。如下Array(    [0] => Array        (            [0] => a1            [1] => 0            [2] => <body>         ) ……*/
ログイン後にコピー


次に、トラバースします要素を 1 つに結合します 希望の文字列だけです

同時に、少し処理を行い、 を記録し、+1、-1 を使用します。 。 。 <0's
の場合、文字列は追加されません。 。最終結果が > 0 の場合は、 を後ろから前に数回置き換えます


ただし、まだ問題があります。 。 。 。 。 。 。 の状況は考慮されません

実際、この場合、コメントも考慮されます

$arr	= preg_split('/(<\!--.*-->|<[^>]*>)/s', $str, -1, PREG_SPLIT_OFFSET_CAPTURE);
ログイン後にコピー

前回この質問をテストしました
簡単ではありませんでした

PHP 手持ちのタグが一致しない場合に自動的にコードを完成させます
Tencent の人々が答えを持っていなくても、それは十分であると推定されています数日

実際のアプリケーションでは、Dr. Wang の Web ページの選択や保存など、一部のプログラムにこの機能があります

タグの混合ネストは xhtml 標準に準拠していませんが、単一タグのクロージャーは許可されています



この質問:

"123<" のみが考慮される場合 ;em>abc
456def789" この文字列
はもっと単純になります。


これは単にアルゴリズムをテストするためのものです

ただし、実際的な意味がある場合は、ラベルに制限はありません

< のような単一のラベルの場合。 ;br/> 初めて一致したときに対応する開始タグがスタックに見つからない場合、スタックにプッシュされないため、影響を受けません。ただし、
のような単一タグでは実際に問題が発生します。

はは、この質問は印象的です

ぜひ投稿してください

PHP コード

$str = "a1b2

c3d4e5

f6 $arr = preg_split('/(<[^>]*>)/', $str, -1, PREG_SPLIT_OFFSET_CAPTURE);
foreach($arr AS $k => $v)
{
i...

兄さん、あなたのコードがよくわかりません。 最後の配列では、配列の各要素に文字が単独で存在しません。インターセプトしたい長さはどのように計算すればよいでしょうか。長さに関しては?

知りたい結果は
配列 'a'、
1 => 文字列 ' であると理解しています。 ; string 'b',
4 => string '2',
...


この形式では、インターセプトされた文字列を取得するために各要素を接続できます。

呵呵,打印一下数组结构
比如
$str = "a1b2

c3d4e5

f6g7h8
";
…………

结果如下,,遍历下数组,拼接字符串,应该就可以了。$arr[$i][1]是字符串开始位置,到这一步可以不用理会了
Array
(
[0] => Array
(
[0] => a1
[1] => 0
[2] =>
)

[1] => Array
(
[0] => b2
[1] => 8
[2] =>


)

[2] => Array
(
[0] => c
[1] => 13
[2] =>
)

[3] => Array
(
[0] => 3
[1] => 33
[2] =>
)
……
……

引用 2 楼 amani11 的回复:
呵呵,这题有印象

来添砖加瓦

PHP code

$str = "a1b2

c3d4e5

f6g7h8";
$arr = preg_split('/(<[^>]*>)/', $str, -1, PREG_SPLIT_OFFSET_CAPTURE);
foreach($arr ……
那你理解错了,你最好先看看preg_split
结果是个二维的数组

这样不是更直观些?

$str = "a1<body>b2<p>c<!--</em>123<em>-->3<em>d4</em>e5</p>f6</body>g7h8<br />";$arr    = preg_split("/(<\!--.*-->|<[^>]*>)/s", $str, -1, PREG_SPLIT_DELIM_CAPTURE);print_r($arr);
ログイン後にコピー

Array
(
[0] => a1
[1] =>
[2] => b2
[3] =>


[4] => c
[5] =>
[6] => 3
[7] =>
[8] => d4
[9] =>

[10] => e5
[11] =>


[12] => f6
[13] =>
[14] => g7h8
[15] =>

[16] =>
)

引用 9 楼 shadowsniper 的回复:

引用 2 楼 amani11 的回复:
呵呵,这题有印象

来添砖加瓦

PHP code

$str = "a1b2

c3d4e5

f6g7h8";
$arr = preg_split('/(<[^>]*>)/', $str, -1, PREG_SPLIT_OFFSET_……

明白了,如果是这样就可以将二维数组的元素连接起来了。不过最后还是要处理掉不匹配的标签。

写了个简单的,欢迎拍砖

/** * 函数名 html_substr * 功能 从html串中截取指定长度的字串,html标记不计算在内 * 参数 *  $str 要截取的串 *  $len 要截取的长度 *  $mode 不匹配的标记的处理方式 0 删去(默认),1 补齐 * 返回 截取到的串 * 说明 *  未考虑多字节字符,仅已字节做计数单位 *  未考虑可单独存在的标记 **/function html_substr($str, $len, $mode=0) {  $ar= preg_split('/(<\!--.*-->|<[^>]*>)/s', $str, -1, PREG_SPLIT_DELIM_CAPTURE);  foreach($ar AS $k => $v) {    if($v{0} != '<') {      $len = $len - strlen($v);      if($len < 0) $ar[$k] = substr($v, 0, $len);    }else $ar[$k] = strtolower($v);    if($len <= 0) break;  }  $ar = array_slice($ar, 0, $k+1);  $len = count($ar);  foreach($ar as $k=>$v) {    if($v{0} == '<' && $v[1] != '/') {      $ch = str_replace('<', '</', $v);      for($i=$k+1; $i<$len && $ar[$i]!=$ch; $i++);      if($i == $len)        if($mode)          $ar[$len] = $ch . $ar[$len];        else          $ar[$k] = '';    }  }  return join('', $ar);}$str = "123<em>abc</em>456<em>def</em>789";echo '<xmp>';echo html_substr($str, 5) . PHP_EOL;echo html_substr($str, 5, 1);
ログイン後にコピー

123ab
123ab

学习了,高手都在啊。

唠叨老大写的这个很简洁,满足题意是绝对没问题了。但是如果再多考虑一些。假如这个字符串很长,1000个字节。而我只截取10个字符。

用preg_split将整个字符串按标签分组的话,正则解析器会搜索整个字符串。做了很多多余的搜索。

$str = "a1<body>b2c3<p><em>d4</em>e</p>5f6</body>g7h8";$gn  = 7;$i   = $j = $k = 0;while( ($c = $str[$i++]) && $j < $gn ) {	if( $c == '<')	{		$tag = 1;	}	elseif($c == '>')	{		if(trim($tg,'/') == 'em')		{			$tgs[$j-1] = '<'.$tg.'>';		}		else 		{			if($tgs[$j-1]) $ogs[$j-1] = '1|'.'<'.$tg.'>';			else $ogs[$j-1] 		  = '0|'.'<'.$tg.'>';		}		$tag = 0;		$tg  = '';	}	elseif($tag == 1)	{		$tg .= $c;	}	else	{		$tmp[] = $c;		$j++;	}}$ts = count($tgs);if($ts % 2) array_pop($tgs);foreach($tmp as $k=>$v){   $ba = explode('|',$ogs[$k],2);   if( $tgs[$k] && $ogs[$k])   {		if($ba[0])		{			$s .= $v.$tgs[$k].$ba[1];		}			else $s .= $v.$ba[1].$tgs[$k];   }   else $s .= $v.$tgs[$k].$ba[1];}echo htmlspecialchars($s);
ログイン後にコピー

不会做了。123abc456def789
一定要做的话,只会:
对标签作为分割符,对其视而不见,将第一段字符存贮为$a1;即$a1=123;第二断为$a2,$a2=abc;一直到$a.$i;
总之就是一段一段的
$a1.$2.$a3.$a4.……
然后算字符,当第一段字符不够,接着取下一段。一直到够为止。

最后写条件加标签。
123奇abc偶456奇def偶789,$a1奇$a2偶$a3奇$a4偶$a5
奇偶条件。截取的如果奇偶对满,加标签,如果不满,就不加。

我做题的思路和楼主不太一样。
首先楼主直接把这个问题中的标签由 em 升级到通用性的 html 标签了,我觉得这种抽象的思维是一种好习惯,但针对如题的面试,我会就按如题所说,只对em 进行解析,完成第一版的原型,复杂的事情,以后时间多了慢慢的思考。

也写点代码,
我的思路是希望通过数据结构来处理这个问题,少依赖正则表达式。
例如
123abc456def789
的数据结构为
tagInfo =>array(
1 start 3, end 6
2 start 9, end 12
) 用于记录标签的位置
和stripStr = "123abc456def789"; 用来存取相应的去掉标签的字符串
这样一来,得到目标字符串,就成了在这个数据结构上去merge 最终字符串的一种算法了。
代码可以使用,在此我更多的是想表达一种思路,代码中有很多需要完善的地方,感谢大家指正,

$str = "123<em>abc</em>456<em>def</em>789";$str1 = mysub($str,5);/************************the result is 123bc************************/$str2 = mysub($str,10);/************************the result is 123<em>abc</em>456d************************//** * * * * @param string $str * @param int $len * @return str 目标字符串 */function mysub($str,$len = 8){	$str = "123<em>abc</em>456<em>def</em>789";	$parseStr = getTag($str,"em");  //将字符串中的em 进行解析,得到所在的开始位置和结束位置.		//得到当前指定位置所在的游标.	$cur = -1;	foreach($parseStr as $key=>$val)	{		if($len >= $val["end"])		{			$cur = $key;		}	}	$dest_str = substr(strip_tags($str),0,$len);	    $dest_str = merge_str($dest_str,$cur,$parseStr);  //得到拼接出来的目标字符串        return $dest_str; }//生成最终数据function merge_str($dest_str,$cur,$parseStr){  for($i=0;$i<strlen($dest_str);$i++)  {  	$str_arr[$i] =substr($dest_str,$i,1);  }  foreach($parseStr as $key=>$val)  {  	if($cur >= $key)  	{  		echo $val["start"];  		$str_arr[ $val["start"] ] = "<em>".$str_arr[ $val["start"] ];  		$str_arr[ $val["end"]-1 ] .= "</em>";  		  	}  }     $str_out= implode("",$str_arr);   echo $str_out;  	}/** * 解析字符串中em 的 start end 位置. * */function getTag($str,$tagName = "em"){	preg_match_all("/<$tagName>(.*)<\/$tagName>/iU",$str,$matches);	$tagArr = $matches[1];  //将em 标签的内容放入tagArr数组。		//获取相应的起始位置.	foreach ($tagArr as $key=>$val)	{		$resultArr[$key]["val"] = $val;		$resultArr[$key]["start"] = handel_getstart($str,$val,$key);		$resultArr[$key]["end"] = handel_getend($str,$val,$key);	}	return $resultArr;	}//获取开始位置function handel_getstart($str,$val,$key){	return strripos($str,$val)- $key*9-4;    //这里写得比较随意,可能问题很多,todo : 要防止重复字符串时取位错误.}//获取结束位置function handel_getend($str,$val,$key){	return handel_getstart($str,$val,$key)+strlen($val);}
ログイン後にコピー

唠叨老大写的这个很简洁,满足题意是绝对没问题了。但是如果再多考虑一些。假如这个字符串很长,1000个字节。而我只截取10个字符。

用preg_split将整个字符串按标签分组的话,正则解析器会搜索整个字符串。做了很多多余的搜索。
的确如此!
不过可以考虑只取一部分(比如待截取的长度*5)来做分析

是否使用正则表达式去分割字符串,是可商榷的。这取决于 memory_limit 的值
早期的php默认 memory_limit = 8M
这样的话,用正则表达式切割字符串远没有自己写一个函数来的快
现在的php默认 memory_limit = 128M
我测试了一下,还是正则来的快,所以就用了正则。毕竟看起来简洁多了

唠叨老大写的这个很简洁,满足题意是绝对没问题了。但是如果再多考虑一些。假如这个字符串很长,1000个字节。而我只截取10个字符。

用preg_split将整个字符串按标签分组的话,正则解析器会搜索整个字符串。做了很多多余的搜索。

我觉得在不考虑递归的情况下。
取字符串时可以预处理一下。
例如取前10 个,
最极端的情况下,字符串长度为
1234567890
那么先把字段直接取前100个,使用唠叨老大的代码处理。。。

有点错,更正一下

为了便于测试,我仿你的思路写了个测试函数

/** * 函数名 check_speed * 功能 统计运行时间和内存使用情况 * 参数 $num 大于0 开始计时,等于0或缺省 停止计时并输出结果 * 说明 本函数可以以 check_speed(运行次数, 函数名, 参数列表); *      方式调用。输出的结果是平均每次的耗时 **/function check_speed($num=0) {  static $time;  static $memo;  $argc = func_num_args();  $param = func_get_args();  switch($argc) {    case 1:      $time = microtime(true);      $memo = memory_get_usage();      break;    default:      $time = microtime(true);      $memo = memory_get_usage();      $len = array_shift($param);      $func = array_shift($param);      for($i = 0; $i<$len; $i++)        call_user_func_array($func, $param);      echo '<br />' . PHP_EOL . $func;    case 0:      $len or $len = 1;      echo '<br />' . PHP_EOL;      printf("时间: %s 微秒<br />%s", number_format((microtime(true) - $time)*1000000/$len), PHP_EOL);      printf("内存: %d<br />%s", memory_get_usage()-$memo, PHP_EOL);  }}
ログイン後にコピー


对你我的代码做了一下测试
check_speed(100, 'html_substr', $str, 5);
check_speed(100, 'mySubstr', $str, 5); //注:已注释掉影响速度的 echo 语句

结果如下:

html_substr
时间: 42 微秒
内存: 3416

mySubstr
时间: 85 微秒
内存: 3864

学习了!

记得是前阵子去腾讯面试时的那道题,当时用笔我没写出来,就大概说了下思路,今天有空,就写了一下,发现要做到完美还是很麻烦的。


题目是:
假设有"123abc456def789"这么一个字符串,写一个函数,可以传入一个字符串,和一个要截取的长度。返回截取后的结果。

要求:
1 标记不得计算在长度之内。
2 截取后的字符串,要……
楼主的思路很对呢。。只是特殊情况应该就不是他们面试的目的

我这里有啊....


http://hi.baidu.com/lael80/blog/item/669ebe1e50f635134134172c.html


//tags : 字符串可能包含的HTML标签//zhfw : 用来修正中英字宽参数function wsubstr($str, $length = 0, $suffixStr = "...", $start = 0, $tags = "div|span|p", $zhfw = 0.9, $charset = "utf-8"){//author: lael//blog: http://hi.baidu.com/lael80$re['utf-8']   = "/[\x01-\x7f]|[\xc2-\xdf][\x80-\xbf]|[\xe0-\xef][\x80-\xbf]{2}|[\xf0-\xff][\x80-\xbf]{3}/";$re['gb2312'] = "/[\x01-\x7f]|[\xb0-\xf7][\xa0-\xfe]/";$re['gbk']    = "/[\x01-\x7f]|[\x81-\xfe][\x40-\xfe]/";$re['big5']   = "/[\x01-\x7f]|[\x81-\xfe]([\x40-\x7e]|\xa1-\xfe])/";$zhre['utf-8']   = "/[\xc2-\xdf][\x80-\xbf]|[\xe0-\xef][\x80-\xbf]{2}|[\xf0-\xff][\x80-\xbf]{3}/";$zhre['gb2312'] = "/[\xb0-\xf7][\xa0-\xfe]/";$zhre['gbk']    = "/[\x81-\xfe][\x40-\xfe]/";$zhre['big5']   = "/[\x81-\xfe]([\x40-\x7e]|\xa1-\xfe])/";//下面代码还可以应用到关键字加亮、加链接等,可以避免截断HTML标签发生//得到标签位置$tpos = array();preg_match_all("/<(".$tags.")([\s\S]*?)>|<\/(".$tags.")>/ism", $str, $match);$mpos = 0;for($j = 0; $j < count($match[0]); $j ++){$mpos = strpos($str, $match[0][$j], $mpos);$tpos[$mpos] = $match[0][$j];$mpos += strlen($match[0][$j]);}ksort($tpos);//根据标签位置解析整个字符$sarr = array();$bpos = 0;$epos = 0;foreach($tpos as $k => $v){$temp = substr($str, $bpos, $k - $epos);if(!empty($temp))array_push($sarr, $temp);array_push($sarr, $v);$bpos = ($k + strlen($v));$epos = $k + strlen($v);}$temp = substr($str, $bpos);if(!empty($temp))array_push($sarr, $temp);//忽略标签截取字符串$bpos = $start;$epos = $length;for($i = 0; $i < count($sarr); $i ++){if(preg_match("/^<([\s\S]*?)>$/i", $sarr[$i]))continue;//忽略标签preg_match_all($re[$charset], $sarr[$i], $match);for($j = $bpos; $j < min($epos, count($match[0])); $j ++){if(preg_match($zhre[$charset], $match[0][$j]))$epos -= $zhfw;//计算中文字符}$sarr[$i] = "";for($j = $bpos; $j < min($epos, count($match[0])); $j ++){//截取字符$sarr[$i] .= $match[0][$j];}$bpos -= count($match[0]);$bpos = max(0, $bpos);$epos -= count($match[0]);$epos = round($epos);}//返回结果$slice = join("", $sarr);//自己可以加个清除空html标签的东东if($slice != $str)return $slice.$suffixStr;return $slice;}
ログイン後にコピー



preg_split 原来有这函数...

腾讯居然这么干啊,真是服了

看看!

路过,路过,学习

#25 代码有误,已更正

good thing

全是高手啊、

用数据结构来考虑这道题
struct Node_t
{
    char *pdata;//动态申请内存保存字符串,也可以直接指向源字符串地址,不包含<>
    int nLen;//字符串长度,不包含<>
}

struct Node
{
    int flag;//统计不匹配情况,为0时表示完全匹配,开始下一个layer
    Node_t *p_next;//下一个嵌套节点
    Node *p_next_layer;//下一个完整节点开始
}

如上结构,如果遇到不匹配的情况,flag++,同时开始新的嵌套节点,当flag为0时,开始新的node。到达指定长度后,根据节点重构字符串,如果该node的flag为0,每个node_t的字符串都要加上<>,如果不为0,则都不加上。

重构步骤,根据实际需求确定。

要把各种情况都考虑到就比较困难。

每天回帖即可获得10分可用分! 

如果原串符合xml标准,根本不用考虑标签里的内容是什么,只要用栈进去就可以了,2n的时间复杂度

我只会用c c++做这个

世界性难题啊

元の文字列が XML 標準に準拠している場合、タグの内容を考慮する必要はまったくありません。スタックを使用して入力するだけです。時間計算量は 2n です
元の文字列タグが標準化されていない場合、主なコストはタグ文字列のマッチングにあり、その場合、最悪の時間計算量は 2n+2*ラベル長 L*ラベル数 C に達する可能性があります。この種のプログラムはより複雑で、一度に解決することはできません。私は HTML 解析の初期バージョンを作成しましたが、その後、断片的なデバッグを行った後でバグを修正する時間がほとんどありました。考慮していませんでした。

学びましょう。 。 。

チェックしてください!

学びましょう。 。 。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

JSON Web Tokens(JWT)とPHP APIでのユースケースを説明してください。 JSON Web Tokens(JWT)とPHP APIでのユースケースを説明してください。 Apr 05, 2025 am 12:04 AM

JWTは、JSONに基づくオープン標準であり、主にアイデンティティ認証と情報交換のために、当事者間で情報を安全に送信するために使用されます。 1。JWTは、ヘッダー、ペイロード、署名の3つの部分で構成されています。 2。JWTの実用的な原則には、JWTの生成、JWTの検証、ペイロードの解析という3つのステップが含まれます。 3. PHPでの認証にJWTを使用する場合、JWTを生成および検証でき、ユーザーの役割と許可情報を高度な使用に含めることができます。 4.一般的なエラーには、署名検証障害、トークンの有効期限、およびペイロードが大きくなります。デバッグスキルには、デバッグツールの使用とロギングが含まれます。 5.パフォーマンスの最適化とベストプラクティスには、適切な署名アルゴリズムの使用、有効期間を合理的に設定することが含まれます。

確固たる原則と、それらがPHP開発にどのように適用されるかを説明してください。 確固たる原則と、それらがPHP開発にどのように適用されるかを説明してください。 Apr 03, 2025 am 12:04 AM

PHP開発における固体原理の適用には、次のものが含まれます。1。単一責任原則(SRP):各クラスは1つの機能のみを担当します。 2。オープンおよびクローズ原理(OCP):変更は、変更ではなく拡張によって達成されます。 3。Lischの代替原則(LSP):サブクラスは、プログラムの精度に影響を与えることなく、基本クラスを置き換えることができます。 4。インターフェイス分離原理(ISP):依存関係や未使用の方法を避けるために、細粒インターフェイスを使用します。 5。依存関係の反転原理(DIP):高レベルのモジュールと低レベルのモジュールは抽象化に依存し、依存関係噴射を通じて実装されます。

PHPにおける後期静的結合の概念を説明します。 PHPにおける後期静的結合の概念を説明します。 Mar 21, 2025 pm 01:33 PM

記事では、PHP 5.3で導入されたPHPの後期静的結合(LSB)について説明し、より柔軟な継承を求める静的メソッドコールのランタイム解像度を可能にします。 LSBの実用的なアプリケーションと潜在的なパフォーマ

システムの再起動後にUnixSocketの権限を自動的に設定する方法は? システムの再起動後にUnixSocketの権限を自動的に設定する方法は? Mar 31, 2025 pm 11:54 PM

システムが再起動した後、UnixSocketの権限を自動的に設定する方法。システムが再起動するたびに、UnixSocketの許可を変更するために次のコマンドを実行する必要があります:sudo ...

PHPのCurlライブラリを使用してJSONデータを含むPOSTリクエストを送信する方法は? PHPのCurlライブラリを使用してJSONデータを含むPOSTリクエストを送信する方法は? Apr 01, 2025 pm 03:12 PM

PHP開発でPHPのCurlライブラリを使用してJSONデータを送信すると、外部APIと対話する必要があることがよくあります。一般的な方法の1つは、Curlライブラリを使用して投稿を送信することです。

フレームワークセキュリティ機能:脆弱性から保護します。 フレームワークセキュリティ機能:脆弱性から保護します。 Mar 28, 2025 pm 05:11 PM

記事では、入力検証、認証、定期的な更新など、脆弱性から保護するためのフレームワークの重要なセキュリティ機能について説明します。

フレームワークのカスタマイズ/拡張:カスタム機能を追加する方法。 フレームワークのカスタマイズ/拡張:カスタム機能を追加する方法。 Mar 28, 2025 pm 05:12 PM

この記事では、フレームワークにカスタム機能を追加し、アーキテクチャの理解、拡張ポイントの識別、統合とデバッグのベストプラクティスに焦点を当てています。

See all articles