search
HomeBackend DevelopmentPHP Tutorial 关于腾讯的那谈题截取字符串的题

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


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

要求:
标记不得计算在长度之内。
2 截取后的字符串,要保留原有标签,不过如果最后有一个标签没有闭合,则去掉其开始标签。

示例:
题中的字符串,要截取长度5,则返回的字符串应该为:123ab,要截取长度8,应返回123abc45。



我的做法大概思路是:
1 首先顺序读取字符串,并用一个resultstr变量来记录所有字符,当发现 2 如果发现tag变量形式为也就是html标签的开始标记),就将其入栈。用栈结构来存储这个标记。若遇到(html标签的结束标记),就出栈。

3 否则如果是常规字符的话,长度计数器++。直到与传入的要截取长度相等。

4 最后判断栈是否为空,如果为空,直接返回截取后的字符串,否则,将栈中剩余元素一个个出栈,循环从截取后的字符串中查找栈顶标签元素最后一次出现的位置,返回索引,将这个标签替换为空。直到整个栈为空为止。最后返回处理后的字符串。



原题其实是没有考虑标签嵌套的情况的,我尽量的让程序可以处理嵌套标签,使其更健壮。并且尽量少的去用php的内置函数,因为那样可能会掩盖算法本身。如可以处理a1

b2c3d4

e5
这种形式的嵌套标签。但我发现如果标签是这种不规则形式a1

b2c3d4

e5的话,程序就会出问题了。因为我只将取到的结束标记与栈顶的元素相比较,而没有去循环搜索整个栈。这里要改一下其实也可以。


不知大家还有没有其他思路,我感觉我这么做实在是太麻烦了,罗罗嗦嗦一大堆。这么多代码面试时拿笔写非得疯了不可。而且这个时间复杂度不理想,大概为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>

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
What are some common problems that can cause PHP sessions to fail?What are some common problems that can cause PHP sessions to fail?Apr 25, 2025 am 12:16 AM

Reasons for PHPSession failure include configuration errors, cookie issues, and session expiration. 1. Configuration error: Check and set the correct session.save_path. 2.Cookie problem: Make sure the cookie is set correctly. 3.Session expires: Adjust session.gc_maxlifetime value to extend session time.

How do you debug session-related issues in PHP?How do you debug session-related issues in PHP?Apr 25, 2025 am 12:12 AM

Methods to debug session problems in PHP include: 1. Check whether the session is started correctly; 2. Verify the delivery of the session ID; 3. Check the storage and reading of session data; 4. Check the server configuration. By outputting session ID and data, viewing session file content, etc., you can effectively diagnose and solve session-related problems.

What happens if session_start() is called multiple times?What happens if session_start() is called multiple times?Apr 25, 2025 am 12:06 AM

Multiple calls to session_start() will result in warning messages and possible data overwrites. 1) PHP will issue a warning, prompting that the session has been started. 2) It may cause unexpected overwriting of session data. 3) Use session_status() to check the session status to avoid repeated calls.

How do you configure the session lifetime in PHP?How do you configure the session lifetime in PHP?Apr 25, 2025 am 12:05 AM

Configuring the session lifecycle in PHP can be achieved by setting session.gc_maxlifetime and session.cookie_lifetime. 1) session.gc_maxlifetime controls the survival time of server-side session data, 2) session.cookie_lifetime controls the life cycle of client cookies. When set to 0, the cookie expires when the browser is closed.

What are the advantages of using a database to store sessions?What are the advantages of using a database to store sessions?Apr 24, 2025 am 12:16 AM

The main advantages of using database storage sessions include persistence, scalability, and security. 1. Persistence: Even if the server restarts, the session data can remain unchanged. 2. Scalability: Applicable to distributed systems, ensuring that session data is synchronized between multiple servers. 3. Security: The database provides encrypted storage to protect sensitive information.

How do you implement custom session handling in PHP?How do you implement custom session handling in PHP?Apr 24, 2025 am 12:16 AM

Implementing custom session processing in PHP can be done by implementing the SessionHandlerInterface interface. The specific steps include: 1) Creating a class that implements SessionHandlerInterface, such as CustomSessionHandler; 2) Rewriting methods in the interface (such as open, close, read, write, destroy, gc) to define the life cycle and storage method of session data; 3) Register a custom session processor in a PHP script and start the session. This allows data to be stored in media such as MySQL and Redis to improve performance, security and scalability.

What is a session ID?What is a session ID?Apr 24, 2025 am 12:13 AM

SessionID is a mechanism used in web applications to track user session status. 1. It is a randomly generated string used to maintain user's identity information during multiple interactions between the user and the server. 2. The server generates and sends it to the client through cookies or URL parameters to help identify and associate these requests in multiple requests of the user. 3. Generation usually uses random algorithms to ensure uniqueness and unpredictability. 4. In actual development, in-memory databases such as Redis can be used to store session data to improve performance and security.

How do you handle sessions in a stateless environment (e.g., API)?How do you handle sessions in a stateless environment (e.g., API)?Apr 24, 2025 am 12:12 AM

Managing sessions in stateless environments such as APIs can be achieved by using JWT or cookies. 1. JWT is suitable for statelessness and scalability, but it is large in size when it comes to big data. 2.Cookies are more traditional and easy to implement, but they need to be configured with caution to ensure security.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function