2022-12-22:给定一个数字n,代表数组的长度, 给定一个数字m,代表数组每个位置都可以在1~m之间选择数字

2022-12-22:给定一个数字n,代表数组的长度,
给定一个数字m,代表数组每个位置都可以在1~m之间选择数字,
所有长度为n的数组中,最长递增子序列长度为3的数组,叫做达标数组。
返回达标数组的数量。
1 <= n <= 500,
1 <= m <= 10,
500 * 10 * 10 * 10,
结果对998244353取模,
实现的时候没有取模的逻辑,因为非重点。
来自微众银行。

答案2022-12-22:

参考最长递增子序列。

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

use std::iter::repeat;
fn main() {
    println!("功能测试开始");
    for n in 4..=8 {
        for m in 1..=5 {
            let ans1 = number1(n, m);
            let ans2 = number2(n, m);
            if ans1 != ans2 {
                println!("{}", ans1);
                println!("{}", ans2);
                println!("出错了!");
            }
        }
    }
    println!("功能测试结束");
}

// 暴力方法
// 为了验证
fn number1(n: i32, m: i32) -> i32 {
    let mut a: Vec<i32> = repeat(0).take(n as usize).collect();
    return process1(0, n, m, &mut a);
}

fn process1(i: i32, n: i32, m: i32, path: &mut Vec<i32>) -> i32 {
    if i == n {
        return if length_of_lis(path) == 3 { 1 } else { 0 };
    } else {
        let mut ans = 0;
        for cur in 1..=m {
            path[i as usize] = cur;
            ans += process1(i + 1, n, m, path);
        }
        return ans;
    }
}

fn length_of_lis(arr: &mut Vec<i32>) -> i32 {
    if arr.len() == 0 {
        return 0;
    }
    let mut ends: Vec<i32> = repeat(0).take(arr.len()).collect();
    ends[0] = arr[0];
    let mut right = 0;
    let mut max = 1;
    for i in 1..arr.len() as i32 {
        let mut l = 0;
        let mut r = right;
        while l <= r {
            let mut m = (l + r) / 2;
            if arr[i as usize] > ends[m as usize] {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        right = get_max(right, l);
        ends[l as usize] = arr[i as usize];
        max = get_max(max, l + 1);
    }
    return max;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}
// i : 当前来到的下标
// f、s、t : ends数组中放置的数字!
// ? == 0,没放!
// n : 一共的长度!
// m : 每一位,都可以在1~m中随意选择数字
// 返回值:i..... 有几个合法的数组!
fn zuo(i: i32, f: i32, s: i32, t: i32, n: i32, m: i32) -> i32 {
    if i == n {
        return if f != 0 && s != 0 && t != 0 { 1 } else { 0 };
    }
    // i < n
    let mut ans = 0;
    for cur in 1..=m {
        if f == 0 || f >= cur {
            ans += zuo(i + 1, cur, s, t, n, m);
        } else if s == 0 || s >= cur {
            ans += zuo(i + 1, f, cur, t, n, m);
        } else if t == 0 || t >= cur {
            ans += zuo(i + 1, f, s, cur, n, m);
        }
    }
    return ans;
}

// 正式方法
// 需要看最长递增子序列!
// 尤其是理解ends数组的意义!
fn number2(n: i32, m: i32) -> i32 {
    //repeat(vec![]).take((m+1) as usize).collect();
    let mut dp: Vec<Vec<Vec<Vec<i32>>>> = repeat(
        repeat(
            repeat(repeat(-1).take((m + 1) as usize).collect())
                .take((m + 1) as usize)
                .collect(),
        )
        .take((m + 1) as usize)
        .collect(),
    )
    .take(n as usize)
    .collect();
    return process2(0, 0, 0, 0, n, m, &mut dp);
}

fn process2(
    i: i32,
    f: i32,
    s: i32,
    t: i32,
    n: i32,
    m: i32,
    dp: &mut Vec<Vec<Vec<Vec<i32>>>>,
) -> i32 {
    if i == n {
        return if f != 0 && s != 0 && t != 0 { 1 } else { 0 };
    }
    if dp[i as usize][f as usize][s as usize][t as usize] != -1 {
        return dp[i as usize][f as usize][s as usize][t as usize];
    }
    let mut ans = 0;
    for cur in 1..=m {
        if f == 0 || cur <= f {
            ans += process2(i + 1, cur, s, t, n, m, dp);
        } else if s == 0 || cur <= s {
            ans += process2(i + 1, f, cur, t, n, m, dp);
        } else if t == 0 || cur <= t {
            ans += process2(i + 1, f, s, cur, n, m, dp);
        }
    }
    dp[i as usize][f as usize][s as usize][t as usize] = ans;
    return ans;
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!