2022-11-26：给定一个字符串s，只含有0~9这些字符你可以使用来自s中的数字，目的是拼出一个最大的回

moonfdd 的个人博客 / 11 / 0 / 创建于 1年前

2022-11-26：给定一个字符串s，只含有0~9这些字符
你可以使用来自s中的数字，目的是拼出一个最大的回文数
使用数字的个数，不能超过s里含有的个数
比如 :
39878，能拼出的最大回文数是 : 898
00900，能拼出的最大回文数是 : 9
54321，能拼出的最大回文数是 : 5
最终的结果以字符串形式返回。
str的长度为N，1 <= N <= 100000。
来自微软。

答案2022-11-26：

力扣2384。统计词频，先从大网校填写一对一对的数据，然后填写剩下的最大的数据，最后组合就是需要的返回值。注意取一对数的时候刚开始不能取0，因为起始为0的数不是回文数。

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

use std::{cmp::Ordering, collections::HashMap};

impl Solution {
    pub fn largest_palindromic(s: String) -> String {
        if s == "" {
            return String::from("");
        }
        let mut map: HashMap<i32, i32> = HashMap::new();
        let n = s.len() as i32;
        let sc: Vec<char> = s.chars().collect();
        for i in 0..n {
            let number = sc[i as usize] as i32 - '0' as i32;
            map.insert(
                number,
                if map.contains_key(&number) {
                    map.get(&number).unwrap() + 1
                } else {
                    1
                },
            );
        }
        let mut heap: Vec<Record> = vec![];
        for (k, v) in map.iter() {
            heap.push(Record::new(*k, *v));
        }
        heap.sort_by(compare);
        let mut top = heap.remove(0);
        if top.times == 1 {
            return format!("{}", top.number);
        } else if top.number == 0 {
            heap.sort_by(compare);
            return format!("{}", if heap.len() == 0 { 0 } else { heap[0].number });
        } else {
            let mut left = String::new();
            left.push_str(&format!("{}", top.number));
            top.times -= 2;
            if top.times > 0 {
                heap.push(top);
            }
            heap.sort_by(compare);
            while heap.len() > 0 && heap[0].times > 1 {
                top = heap.remove(0);
                left.push_str(&format!("{}", top.number));
                top.times -= 2;
                if top.times > 0 {
                    heap.push(top);
                }
                heap.sort_by(compare);
            }
            let mut ans = String::new();
            ans.push_str(&left);
            if heap.len() > 0 {
                heap.sort_by(compare);
                ans.push_str(&format!("{}", heap[0].number));
            }
            let lc: Vec<char> = left.chars().collect();
            let mut i = left.len() as i32 - 1;
            while i >= 0 {
                ans.push(lc[i as usize]);
                i -= 1;
            }
            return ans;
        }
    }
}

fn compare(o1: &Record, o2: &Record) -> Ordering {
    let l1 = Ordering::Greater;
    let l2 = Ordering::Less;

    if o1.times == 1 && o2.times > 1 {
        return l1;
    }
    if o1.times > 1 && o2.times == 1 {
        return l2;
    }
    if o2.number - o1.number > 0 {
        return l1;
    } else if o2.number - o1.number < 0 {
        return l2;
    } else {
        return Ordering::Equal;
    }
}

struct Record {
    number: i32,
    times: i32,
}

impl Record {
    fn new(n: i32, t: i32) -> Self {
        Self {
            number: n,
            times: t,
        }
    }
}

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

struct Solution {}