Login light

leetcode/816迭代消除.md

<?php
/**
给定一串数字,迭代消除其中的连续的816
【输入描述】    
比如: 818816168166  消除后是空
比如: 81818166  消除后是81
81818166
【输出描述】
要求: 写出完整的代码实现,对足够极端的情况考虑尽可能优化的算法处理
 */

define('PATTERN','816');

//递归+替换函数
function fun1($input){
    $ret = str_replace(PATTERN, '', $input);
    if($ret === $input){
        return $ret;
    }else{
        return fun1($ret);
    }
}
//不使用替换函数 后到前
function fun_back2front($input){
    $len = strlen($input);
    for($index = $len - 1; $index >= 0; $index--){
        if(PATTERN === substr($input, $index - 2, 3)){
            $input = substr($input, 0, $index - 2).substr($input, $index + 1);

            //$index += 2;

            //如果前一位的值为目标值的末尾,且目标值每一位不重复
            if(substr(PATTERN, -1) != substr($input, $index - 3, 1)){
                $index += 2;
            }else{
                $index -= 2;
            }
        }
    }
    return $input;
}
//不使用替换函数 前到后
function fun_front2back($input){
    for($index = 0; $index < strlen($input); $index++){
        //找到匹配项
        if(PATTERN === substr($input, $index, 3)){
            $input = substr($input, 0, $index).substr($input, $index + 3);
            $index = max(-1, $index - 3);
        }
    }
    return $input;
}

$str = str_repeat('818166',100);
echo 'fun1:'.fun1($str)."\n";
echo 'fun_back2front:'.fun_back2front($str)."\n";
echo 'fun_front2back:'.fun_front2back($str)."\n";