2022-10-17：特殊的二进制序列是具有以下两个性质的二进制序列： 0 的数量与 1 的数量相等。二进制序列的每一个前缀码中 1 的数量要大于等于 0 的

原创

福大大架构师每日一题

发布于 2022-10-17 23:12:26

3110

发布于 2022-10-17 23:12:26

文章被收录于专栏：福大大架构师每日一题

2022-10-17：特殊的二进制序列是具有以下两个性质的二进制序列：

0 的数量与 1 的数量相等。

二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制序列 S，以字符串形式表示。

定义一个操作为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。

(两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符)

在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？

输入: S = "11011000"。

输出: "11100100"。

答案2022-10-17：

1认为是左括号，0认为是右括号。嵌套递归模型。两两交换，其本质是冒泡排序。

力扣761。经测试，rust和go的速度最快，go的内存占用最低。

代码用rust编写。代码如下：

impl Solution {
    pub fn make_largest_special(s: String) -> String {
        let mut arr: Vec<String> = vec![];
        // 主！
        let mut index = 0;
        while index < s.len() as i32 {
            let info = Solution::process(&s, index + 1);
            arr.push(info.ans);
            index = info.end + 1;
        }
        let mut builder = String::from("");
        arr.sort_by(|a, b| b.cmp(a));
        for cur in arr.iter() {
            builder.push_str(cur);
        }
        return builder;
    }
    // process(i)
    fn process(s: &str, mut index: i32) -> Info {
        let mut arr: Vec<String> = vec![];
        // index 不能是 ) -> 0
        let bytes = s.as_bytes();

        while bytes[index as usize] != '0' as u8 {
            // index ( -> 1
            let info = Solution::process(s, index + 1);
            arr.push(info.ans);
            index = info.end + 1;
        }
        let mut builder = String::from("");
        arr.sort_by(|a, b| b.cmp(a));
        for cur in arr.iter() {
            builder.push_str(cur);
        }
        return Info::new(&(String::from("") + "1" + &builder + "0"), index);
    }
}

struct Info {
    ans: String,
    end: i32,
}

impl Info {
    fn new(a: &str, e: i32) -> Self {
        Self {
            ans: String::from(a),
            end: e,
        }
    }
}

fn main() {
    let ans = Solution::make_largest_special(String::from("11011000"));
    println!("ans = {:?}", ans);
}

struct Solution {}

执行结果如下：