构造DI字符串的最小数字

<?php
/**
 * @param String $pattern
 * @return String
 */
function smallestNumber($pattern) {
    $n = strlen($pattern);
    $nums = range(1, $n);
    $i = 0;
    while ($i < $n) {
        if ($pattern[$i] == 'd') {
            $j = $i;
            while ($j < $n && $pattern[$j] == 'd') {
                $j++;
            }
            reverseSubarray($nums, $i, $j -1);
            $i = $j;
        } else {
            $i++;
        }
    }
    return implode("", $nums);
}

/**
 * @param $arr
 * @param $start
 * @param $end
 * @return void
 */
function reverseSubarray(&$arr, $start, $end) {
    while ($start < $end) {
        $temp = $arr[$start];
        $arr[$start] = $arr[$end];
        $arr[$end] = $temp;
        $start++;
        $end--;
    }
}

// Example cases
echo smallestNumber("iiididdd") . "\n"; // Output: "123549876"
echo smallestNumber("ddd") . "\n";       // Output: "4321"
?>

2375. 从DI字符串构造最小数字

难度：中等

主题：字符串，回溯，堆栈，贪婪

给定一个长度为 n 的字符串 pattern，由字符 'i' 和 'd' 组成，其中 'i' 表示递增，'d' 表示递减。构造一个由数字 '1' 到 '9' 组成的长度为 n+1 的数字字符串 num，满足以下条件：

• 如果 pattern[i] == 'i'，则 num[i]
• 如果 pattern[i] == 'd'，则 num[i] > num[i+1]。

返回字典序最小的可能字符串 num。

示例 1：

输入：pattern = "iiididdd" 输出："123549876" 说明：在索引 0、1、2 和 4 处，我们必须有 num[i] num[i+1]。num 的一些可能值是 "245639871"、"135749862" 和 "123849765"。可以证明 "123549876" 是符合条件的最小数字。请注意，"123414321" 是不可能的，因为数字 '1' 被多次使用。

示例 2：

输入：pattern = "ddd" 输出："4321" 说明：num 的一些可能值是 "9876"、"7321" 和 "8742"。可以证明 "4321" 是符合条件的最小可能的数字。

约束：

• pattern 仅由字母 'i' 和 'd' 组成。

提示：

• 有约束条件，我们可以生成所有可能的字符串吗？是的，我们可以。现在，我们只需要检查字符串是否符合所有条件。

解决方案：

我们需要根据给定的 'i'（递增）和 'd'（递减）字符的模式来构造字典序最小的数字字符串。该解决方案必须确保每位数字从 1 到 9 的精确使用一次，并且该序列遵守给定的模式。

方法的关键见解是认识到模式中的连续 'd' 字符需要递减的数字序列。每当遇到一组连续的 'd' 时，我们可以有效地生成所需的序列，从而反转最初递增数字序列的段。这种方法通过利用反转段来处理递减序列的特性来确保我们产生字典序最小的序列。

这段代码实现了上述算法，并包含了示例用例。 reverseSubarray 函数用于反转数组的子数组。 smallestNumber 函数则处理模式字符串，并根据模式构造最小数字字符串。 代码简洁高效，直接明了。

以上就是构造DI字符串的最小数字的详细内容，更多请关注php中文网其它相关文章！