2023-04-11：给你下标从 0 开始、长度为 n 的字符串 pattern ， 它包含两种字符，‘I‘ 表示 上升

2023-04-11：给你下标从 0 开始、长度为 n 的字符串 pattern ，
它包含两种字符，’I’ 表示 上升 ，’D’ 表示 下降 。
你需要构造一个下标从 0 开始长度为 n + 1 的字符串，且它要满足以下条件：
num 包含数字 ‘1’ 到 ‘9’ ，其中每个数字 至多 使用一次。
如果 pattern[i] == ‘I’ ，那么 num[i] < num[i + 1] 。
如果 pattern[i] == ‘D’ ，那么 num[i] > num[i + 1] 。
请你返回满足上述条件字典序 最小 的字符串 num。
输入：pattern = “IIIDIDDD”，
输出：”123549876”。

答案2023-04-11：

解题思路

这是一道比较有趣的贪心题目。我们可以根据给定的 pattern 字符串来决定数字串中相邻两个数的关系。

步骤1：定义 next 函数

首先，我们需要定义一个函数 next(status, num)，用来查找在状态 status 中没有使用过的最小数字（大于 num）。该函数通过遍历数字 1 到 9，判断哪些数字在 status 中未被使用，且大于 num，然后返回其中最小的数字。

fn next(status: usize, num: u8) -> Option<u8> {
    for i in (num + 1)..=9 {
        if (status & (1 << i)) == 0 {
            return Some(i as u8);
        }
    }
    None
}

步骤2：定义 create 函数

接着，我们需要定义另一个函数 create(pattern, index, status, number)，用来递归生成数字串，并判断是否符合要求。在递归过程中，我们需要判断当前位应该填入哪个数字，并根据数字的大小关系更新 status、number 和 index 的值。如果生成的数字串不符合要求，则需要回溯并重新选择数字。

fn create(pattern: &[char], index: usize, status: &mut usize, number: &mut u32) -> bool {
    if index == pattern.len() + 1 {
        return true;
    }

    let mut cur = 0;
    while let Some(next_cur) = next(*status, cur) {
        cur = next_cur;

        // cur == 0 , 当前位，1 X
        // cur == 1 , 当前位，2 X
        // cur == 2,  当前位，4
        // pattern I D >
        //         0 1 2 3
        //         ? ? ? ?
        //         D
        //         0 1
        //         5 ?
        if index == 0
            || (pattern[index - 1] == 'I' && *number % 10 < cur as u32)
            || (pattern[index - 1] == 'D' && *number % 10 > cur as u32)
        {
            *status |= 1 << cur;
            *number = *number * 10 + cur as u32;

            if create(pattern, index + 1, status, number) {
                return true;
            }

            *number /= 10;
            *status &= !(1 << cur);
        }
    }

    false
}

步骤3：定义 smallest_number 函数

最后，我们需要定义 smallest_number 函数，调用 create 函数来生成数字串，并将其转化为字符串类型返回。

fn smallest_number(pattern: &str) -> String {
    let chars = pattern.chars().collect::<Vec<_>>();
    let mut status = 0usize;
    let mut number = 0;

    create(&chars, 0, &mut status, &mut number);

    number.to_string()
}

时间复杂度

对于这个解法，最坏情况下需要枚举所有可能的数字串，因此时间复杂度为 O(n * 9!)，其中 n 是 pattern 字符串的长度。在实际测试中，由于存在大量剪枝操作，实际运行时间要比这个上界要小得多。

空间复杂度

主要的存储空间是用来记录数字是否被使用过的 status 变量和已经生成的数字串 number 变量，以及递归调用栈所占用的空间。其中，status 和 number 变量的大小均为常数级别，因此空间复杂度为 O(1)。递归调用栈的深度最多为 n + 1，因此空间复杂度为 O(n)。

rust完整代码如下：

fn smallest_number(pattern: &str) -> String {
    let chars = pattern.chars().collect::<Vec<_>>();
    let mut status = 0usize;
    let mut number = 0;

    create(&chars, 0, &mut status, &mut number);

    number.to_string()
}

/// 返回 i... 所有数字都决定了，并且不破坏pattern，
/// 并且1~9每个数字最多用一次能出来的最小值是啥，返回
fn create(pattern: &[char], index: usize, status: &mut usize, number: &mut u32) -> bool {
    if index == pattern.len() + 1 {
        return true;
    }

    let mut cur = 0;
    while let Some(next_cur) = next(*status, cur) {
        cur = next_cur;

        // cur == 0 , 当前位，1 X
        // cur == 1 , 当前位，2 X
        // cur == 2,  当前位，4
        // pattern I D >
        //         0 1 2 3
        //         ? ? ? ?
        //         D
        //         0 1
        //         5 ?
        if index == 0
            || (pattern[index - 1] == 'I' && *number % 10 < cur as u32)
            || (pattern[index - 1] == 'D' && *number % 10 > cur as u32)
        {
            *status |= 1 << cur;
            *number = *number * 10 + cur as u32;

            if create(pattern, index + 1, status, number) {
                return true;
            }

            *number /= 10;
            *status &= !(1 << cur);
        }
    }

    false
}

/// 返回没有使用，且 > num, 最小的数字
fn next(status: usize, num: u8) -> Option<u8> {
    for i in (num + 1)..=9 {
        if (status & (1 << i)) == 0 {
            return Some(i as u8);
        }
    }
    None
}

fn main() {
    let pattern = "IIIDIDDD";
    let result = smallest_number(pattern);
    println!("{}", result); // 输出：123549876
}

本作品采用《CC 协议》，转载必须注明作者和本文链接