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
输入描述
一个只包含整数的二维数组:
3 3 4 7 8 8 6 6 2 6 4
第一行两个数字，分别为行数和每行的列数
后续数据为矩阵地图内容
矩阵边长范围:[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() {
}
美的集团公司福利 836人发布
查看3道真题和解析