第62题-立方数排列

问题描述

第62题图

翻译为中文就是：

立方数，41063625(345^3)经过排列后得到另外2个立方数:56623104(384^3)和66430125(405^3)，事实上41063625是最小的排列之后仅能得到另外2个立方数的数

求解：找到最小的立方数，经过排列后还能得到4个立方数

解题思路

一个范围内的立方数应该不会很多，因为增长得太快了，所以可以尝试暴力破解的办法，先得到一串立方数，然后从里面寻找哪5个数字是排列之后生成的（姑且先称呼这样的数字为转置数吧）

rust语言描述

p62.rs

pub fn solution_of_p62() -> usize {
    let cbrt_arr = gen_cubic_arr(1_00_000_000_000, 1_000_000_000_000);
    // let cbrt_arr = vec![41063625, 56623104, 66430125];
    let l = cbrt_arr.len();
    for i in 0..l {
        let mut perm_num = 0;
        for j in i + 1..l {
            if is_permutate(cbrt_arr[i], cbrt_arr[j]) {
                perm_num += 1;
            }
        }
        if perm_num == 4 {
            return cbrt_arr[i];
        }
    }
    return 1;
}

fn gen_cubic_arr(start: usize, end: usize) -> Vec<usize> {
    let mut n = (start as f64).cbrt() as usize;
    let mut arr = vec![];
    loop {
        let c = n * n * n;
        if c < end {
            arr.push(c);
            n += 1;
        } else {
            return arr;
        }
    }
}

fn is_permutate(a: usize, b: usize) -> bool {
    let mut astr: Vec<char> = a.to_string().chars().collect();
    astr.sort();
    let mut bstr: Vec<char> = b.to_string().chars().collect();
    bstr.sort();
    if astr != bstr {
        return false;
    }
    return true;
}

上面这段代码很简单，先是生成一个1_00_000_000_000到1_000_000_000_000之间的立方数组（就1万多个），然后分2次迭代，找到每个数对应转置数的个数，如果是4那就终止

按理来说应该很快，因为要处理的数据集就是一个1万多个元素的数组，但是因为有2重循环，最坏时间复杂度是O(n^2)性能还是有点慢，在我的笔记本上大概要20秒才能算出结果

做完之后看了一下论坛上其他人的做法，有人提出了O(n)时间复杂度的算法，在寻找转置数个数处做了优化，代码如下：

p62_1.rs

use std::collections::HashMap;

pub fn solution_of_p62() -> usize {
    let cbrt_arr = gen_cubic_arr(1_00_000_000_000, 1_000_000_000_000);
    // let cbrt_arr = vec![41063625, 56623104, 66430125];
    let mut h: HashMap<String, Vec<usize>> = HashMap::new();
    let l = cbrt_arr.len();
    for i in 0..l {
        let mut kv: Vec<char> = cbrt_arr[i].to_string().chars().collect();
        kv.sort();
        let key: String = kv.into_iter().collect();
        match h.get_mut(&key) {
            Some(v) => {
                let mut new_v: Vec<usize> = v.clone();
                new_v.push(cbrt_arr[i]);
                *v = new_v;
            }
            None => {
                let new_v = vec![cbrt_arr[i]];
                h.insert(key, new_v);
            }
        }
    }
    for (_k, v) in h.iter() {
        if v.len() == 5 {
            return v[0];
        }
    }
    return 1;
}

fn gen_cubic_arr(start: usize, end: usize) -> Vec<usize> {
    let mut n = (start as f64).cbrt() as usize;
    let mut arr = vec![];
    loop {
        let c = n * n * n;
        if c < end {
            arr.push(c);
            n += 1;
        } else {
            return arr;
        }
    }
}

关键之处是定义了一个字典用来存放每个key及对应的转置数数组，当这个key对应的转置数数组长度为5的时候就说明得到了结果。rust因为类型系统和所有权的原因，在字符串处理和hash上提供的几个api似乎不够简洁优雅，比如说用了个 get_mut 方法才能修改key本身