今天被滴滴面试官面试,又一个算法问题.....
问题就是找到字符串里不包括重复字符的最长子字符串。
第一种:
<?php $string = "abcdaefaedkqatlmtx"; function test($string){ $len = strlen($string); $arr = []; for ($i = 1; $i <= $len; $i++) { for($j = 1; $j<= $len; $j++) { //从第0个开始依次截取到最大长度,然后从第一个开始...依次截取 if ($tmp_str = substr($string,$i,$j)) { if (checks($tmp_str) !== false) { $arr[strlen($tmp_str)] = $tmp_str; } } } } return $arr[max(array_keys($arr))]; } //此方法用来验证是否包括重复的字符串 function checks($str){ $arr = str_split($str); $arr_len = count($arr); $tmp_len = count(array_unique($arr)); if ($arr_len == $tmp_len) { return true; } return false; } print_r(test($string)); //结果:edkqatlm ?>
第二种:
<?php $string = "abcdaefaedkqatlmtx"; $len = strlen($string); $resArr =[]; $tmp = []; $i = 0; while ($i < $len){ $char = $string{$i}; if(!array_key_exists($char, $tmp)){ $tmp[$char]= $i; $i++; if($i !== $len) continue; } //从重复值下个开始 $i = $tmp[$char]+1; if( count($tmp) > count($resArr) ){ $resArr = $tmp; } $tmp = []; } echo implode(array_keys($resArr)); //结果:edkqatlm
?>