2

给定一个层次结构（如大纲），其中每个级别都由一个整数表示（例如，第一级是 0，第二级是 1，并且在任何时候你都可以在更早的级别开始一个新点），我想重新分配整数，以便不跳过数字，但同时尊重原始关系。我将输入表示为一个数组：

$stuff = array(0,1,2,2,4,1,9,9,10,3,8,4);

所需的输出（当表示为数组时）是：

$stuff = array(0,1,2,2,3,1,2,2,3,2,3,3);

规则是：

  • 如果给定值与最近的先验值相同，则输出值应与最近的先验输出值相同
  • 如果给定值比最近的先验值更高（即更深），则输出值应该比最近的先验值大一
  • 如果给定值低于（即，更浅）最近的先验值，则找到小于给定值的最近的先验值，并且输出值应该比该值大一。

我认为这样做的唯一方法是通过递归。除了前面提到的输入数组中的最后一种情况外，我可以让它适用于所有情况。如果我将输入数组中的最后一个案例更改为“5”而不是“4”，那么它可以工作。

这是我正在尝试的：

<?php

$input = array(0,1,2,2,4,1,9,9,10,3,8,4);
$debug = false;
for ($i =0; $i < count($input); $i++) {
    if ($debug) {
        echo '<hr />Old level: '.$input[$i];
        $newLevel = newLevel($input,$i,$input[$i],$debug);
        echo '<br />New level: '.$newLevel.'<br /><br /><br /><hr />';
    }
    else {
        echo 'Old level: '.$input[$i].'; New level: '.newLevel($input,$i,$input[$i],$debug).'<br />';
    }
}

function newLevel($input, $index,$origValue,$debug) {
    if ($index == 0) return 0;
    else {
        if ($input[$index] > $input[$index-1]) {
            if ($debug) echo '<br />Orig value: '.$origValue.' in else/if';
            return newLevel($input,$index-1,$origValue,$debug)+1;
        }
        elseif ($input[$index] == $input[$index-1]) {
            if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif1';
            return newLevel($input,$index-1,$origValue,$debug);
        }
        elseif ($input[$index] < $input[$index-1]) {
            for ($i = $index-2; $i >= 0; $i--) {
                if ($input[$index] == $input[$i]) {
                    if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif2/for/if';
                    return newLevel($input,$i,$origValue,$debug);
                }
                elseif ($input[$index] == ($input[$i] + 1)) {
                    if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif2/for/elseif';
                    return newLevel($input,$i,$origValue,$debug);
                }
            }
                die ("Error with going to outer level -- should never hit this.");
        }
    }
}

?>

这是我想要的输出：

Old level: 0; New level: 0
Old level: 1; New level: 1
Old level: 2; New level: 2
Old level: 2; New level: 2
Old level: 4; New level: 3
Old level: 1; New level: 1
Old level: 9; New level: 2
Old level: 9; New level: 2
Old level: 10; New level: 3
Old level: 3; New level: 2
Old level: 8; New level: 3
Old level: 4; New level: 3

但是我得到的输出对于最后一行的新级别有一个“2”。非常感谢任何帮助。

4

1 回答 1

3

实际上，您根本不需要递归。您在不使用递归的情况下很好地解释了您的算法，因此您的代码也不需要它。

这是我的算法版本，没有递归。

$original = array(0,1,2,2,4,1,9,9,10,3,8,4);
$revised = array();

foreach($original as $index=>$value) {
    $output = 0;
    $previous = false;

    if ($index > 0)
        $previous = $original[$index-1];

    if ($previous === false) 
        $output = 0;
    else if ($value == $previous)
        $output = $revised[$index-1];
    else if ($value > $previous)
        $output = $revised[$index-1] + 1;
    else {
        $output = 1; // worst case scenario
        for($rindex = $index-1; $rindex >= 0; $rindex--) {
            if ($value > $original[$rindex]) {
                $output = $revised[$rindex]+1;
                break;
            }
        }
    }

    $revised[] = $output;
}

echo "\n";
print_r($original);
print_r($revised);
于 2013-05-17T23:30:27.563 回答