客服小祥

2023-09-09 23:23 南京理工大学区块链

关注

2023 0906 华为机试学习

每天起床第一句孟晚舟保佑我能过华为机试

1

题目：每日股票价格

给定某只股票连续N天的价格列表stockPrices，其中stockPrices[i]。表示服票某天的价格，请生成一个新列表，对应位置输出为:要想等到股票价格上涨，至少需要等待的天数，如果股票价格不上涨，对应位置输出为0。

解答要求

时间限制:C/C++ 500ms其他语言: 1000ms内存限制: C/C++ 256MB,其他语言:512MB

输入描述

第一行表示第二行元素的个数N；

第二行为用空格隔开的整数，表示每天股票的价格。

其中0<N<=1000000，每天股票价格为正整数

输出描述

输出为用空格分隔的长度为N的列表，对应位置为:要想等到股票价格上涨，至少需要等待的天数

样例输入

5
33 34 14 12 16

样例输出

1 0 2 1 0

解释：

stockPrices =[33,34,14,12,16]

当i=0时，stockPrices[0] =33,下次价格上涨stockPrices[1]=34，此处输出为 1-0=1

单调栈

impl Solution {
    pub fn at_least_waiting_days(stock_prices: Vec<i32>) -> Vec<i32> {
        let mut waiting = vec![0; stock_prices.len()];
        let mut stack = Vec::new();
        stack.reserve(stock_prices.len());
        stack.push(0);

        for i in 1..stock_prices.len() {
            if stack.is_empty() {
                stack.push(i);
            }else if stock_prices[i] == stock_prices[*stack.last().unwrap()]{
                stack.pop();
                stack.push(i);
            }else if stock_prices[i] < stock_prices[*stack.last().unwrap()] {
                stack.push(i);
            }else {
                while !stack.is_empty() && stock_prices[i] > stock_prices[*stack.last().unwrap()] {
                    let prev = stack.pop().unwrap();
                    waiting[prev] = (i - prev) as i32;
                }
            }
        }

        waiting

    }
}

二

题目：中庸行者

给定一个m*n的整数阵作为地图，短阵数值为地形高度；中庸行者选择地图中的任意一点作为起点，尝试往上、下、左、右四个相邻格子移动;

移动时有如下约束:

中庸行者只能上坡或者下坡，不能走到高度相同的点；
不允许连续上坡或者连续下坡，需要交替进行;
每个位置只能经过一次，不能重复行走；

请给出中庸行者在本地图内，能连续移动的最大次数。

解答要求

时间限制: C/C++500ms,其他语言:1000ms内存限制: C/C++ 256MB,其他语言:512MB

输入描述

一个只包含整数的二维数组:

第一行两个数字，分别为行数和每行的列数

后续数据为矩阵地图内容

矩阵边长范围:[1,8];

地形高度范围:[0,100000];

输出描述

一个整数，代表中庸行者在本地图内，能连续移动的最大次数。

样例输入

2 2
1 2
4 3

样例输出

3

解释

3->4->1->2

dfs求最大深度，最难的就是visited的位置和对next visited的判断

struct Solution;
/* ------------------------------------- */
use std::collections::HashMap;

fn show_grid(grid: &Vec<Vec<i32>>, cur: usize, visited: &mut Vec<bool>) {
    let m = grid.len();
    let n = grid[0].len();
    let f = |i, j| i * m + j;
    for i in 0..m {
        for j in 0.. n {
            if f(i,j) == cur {
                print!("🟥 ");
            }else if visited[f(i,j)] {
                print!("⬛ ");
            }else {
                print!("⬜ ");
            }
        }
        println!("");
    }
    println!("----------------------------");
    
}
impl Solution {
    pub fn dfs(grid: &Vec<Vec<i32>>, cur: usize, visited: &mut Vec<bool>, should_up: bool) -> i32 {

        let m = grid.len();
        let n = grid[0].len();
        let mut ans = 0;

        if visited[cur] {return 0;}
        visited[cur] = true;

        let f = |i, j| i * m + j;
        let r = |cur| (cur / n, cur % n);
        // if visited[cur] {return 0;}
        let mv = [[0, 1], [1, 0], [0, -1], [-1, 0]];
        let (i, j) = r(cur);

        for k in 0..4 {
            let y = i as i32 + mv[k][0];
            let x = j as i32 + mv[k][1];

            if y < 0 || y >= m as i32 || x < 0 || x >= n as i32 {
                continue;
            }
            let y = y as usize;
            let x = x as usize;
            // 中庸行者只能上坡或者下坡，不能走到高度相同的点；
            if grid[y][x] == grid[i][j] {
                continue;
            }
            // 不允许连续上坡或者连续下坡，需要交替进行;
            if (should_up && grid[y][x] < grid[i][j]) || (!should_up && grid[y][x] > grid[i][j]) {
                continue;
            }
            let next = f(y, x);
            if visited[next] {// 如果next返回0 那么当前的dfs就是返回1了 但是如果当前的四周都是墙壁 就应该返回0 所以必须要判断next
                continue;
            }

            let dfs = Self::dfs(grid, next, visited, !should_up) + 1;
            ans = ans.max(dfs);

        }

        // show_grid(grid, cur, visited);

        visited[cur] = false;
        ans
    }
    pub fn zyxz(grid: &Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut ans = i32::MIN;
        let f = |i, j| i * m + j;
        let mut visited = vec![false; n * m];

        for i in 0..m {
            for j in 0..n {
                ans = ans.max(Self::dfs(grid, f(i, j), &mut visited, true))
                         .max(Self::dfs(grid, f(i, j), &mut visited, false));
            }
        }

        ans
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test1() {
        let grid = vec![
            vec![1, 2],
            vec![4, 3],
        ];
        assert_eq!(
            Solution::zyxz(&grid), 3
        )
    }
    #[test]
    fn test2() {
        let grid = vec![
            vec![3, 4, 4],
            vec![3, 2, 4],
            vec![3, 5, 1],
        ];
        assert_eq!(
            Solution::zyxz(&grid), 6
        )
    }
}
fn main() {

}

三

题目：设备配置数据排序

在现代网络通信设备中，设备的配置数据是一个队列集合。当前设备配置数据存在全局唯一序号id标志此身份，还有一个字段决定此条配置数据的位置信息position。通常,position支持如下几种格式:

1、first:队列头，编码格式:idid -1;

2、end:处于队列尾部，编码格式: id-1id;

3、before id1: 表示id应该在数据id1之前，编码格式id id id1;

4、after id1 表示id应该在数据id1之后，编码格式id id1 id

5、无特别排序指令的id数据，编码格式: $id -1-1

当存在多种排序结果均满足上述排序要求的，则按照id第一次出现在扫序指令队列的前后关系排序，以保证唯一顺序；假定你已收到设备配置数据排序指令队列，需要正确计算出符合排序指令要求的数据id序列。

解答要求

时间限制: C/C++1000ms,其他语言:2000ms 内存限制: C/C++ 256MB,其他语言:512MB

输入描述

第一行代表本次的总配置数据数量，不超过100000;

其余行对应每个具体配置数据id和排序要求。id不超过100000；

输出描述

输出按照要求排序好的数据id序列。

若当前排序指令存在问题，无法排序，则输出-1

样例输入

示例一：
5
1 -1 -1
2 -1 2
3 1 3
4 4 -1
5 4 5
示例二：
3
1 -1 -1
2 2 -1
3 -1 -1

样例输出

示例一：
4 1 3 5 2
示例二：
2 1 3

解释

1和3的position为空，且无其他指令约束，则按照输入顺序排序；

拓扑排序即可一遍秒

struct Solution;
/* ------------------------------------- */
use std::collections::{HashMap, VecDeque};
/*
1  -1  -1   1 无特别排序
2  -1   2   2 在队列尾部
3   1   3   3 在1之后
4   4  -1   4 在队列头
5   4   5   5 在4后

4 1 3 5 2

    4 <- 5

    1 <- 3
                2

 */
pub fn id_sort(id_seqs: Vec<(i32, i32, i32)>) -> Vec<usize> {
    let mut tail = Vec::new();
    let mut head = Vec::new();
    let mut arrive_time = HashMap::new();
    let mut indegree = vec![0; id_seqs.len() + 1];
    let mut adjs = vec![Vec::new(); id_seqs.len() + 1];
    let seqlen = id_seqs.len();

    for (idx, (a, b, c)) in id_seqs.into_iter().enumerate() {
        let id;
        if a == b && c == -1 {
            // 队列头
            id = a as usize;
            indegree[id] = 0;
            head.push(id);
        }else if a == c && b == -1 {
            // 队列尾部
            id = a as usize;
            tail.push(id);
        }else if a == b && a != c && b != c && c != -1 {
            // a == b 在 c之前
            id = a as usize;
            adjs[id].push(c as usize);
            indegree[c as usize] += 1;
        }else if a == c && a != b && c != b && b != -1 {
            // a == c 在b之后
            id = a as usize;
            adjs[b as usize].push(id);
            indegree[id] += 1;
        }else if b == -1 && c == -1 {
            // 无特别排序指令
            id = a as usize;
        }else {unreachable!()}

        arrive_time.insert(id, idx);
    }

    let mut fifo = Vec::new();
    let mut result = Vec::new();

    //找出无特别排序指令 按时间顺序排序
    for id in 1..=seqlen {
        if indegree[id] == 0 && !tail.contains(&id) && !head.contains(&id){
            fifo.push(id);
        }
    }

    // 在无特别排序指令前面插入头指令
    fifo.sort_by_key(|id| *arrive_time.get(id).unwrap());
    let mut tmp = Vec::new();
    tmp.append(&mut head);
    tmp.append(&mut fifo);
    let mut fifo = tmp.into_iter().collect::<VecDeque<usize>>();

    //拓扑排序
    while !fifo.is_empty() {
        let sz = fifo.len();
        let mut stash = Vec::new();

        for _ in 0..sz {
            
            let cur_id =  fifo.pop_front().unwrap();
            result.push(cur_id);
            
            for adj in adjs[cur_id].iter() {
                indegree[*adj] -= 1;
                if indegree[*adj] == 0 && !tail.contains(adj){// 尾指令最后处理
                    stash.push(*adj);
                }
            }
        }

        stash.sort_by_key(|e| *arrive_time.get(e).unwrap());
        for s in stash.into_iter() {
            fifo.push_back(s);
        }
    }

    // 最后插入尾指令
    result.append(&mut tail);
    result
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test1() {
        assert_eq!(
            id_sort(vec![
                (1 ,-1 ,-1),
                (2 ,-1 , 2),
                (3 , 1 , 3),
                (4 , 4 ,-1),
                (5 , 4 , 5),
            ]), vec![4, 1, 3, 5, 2]
        );
    }

    #[test]
    fn test2() {
        assert_eq!(
            id_sort(vec![
                (1,-1, -1),
                (2,2 ,-1),
                (3,-1, -1),
            ]), vec![2, 1, 3]
        )
    }
}
fn main() {

}