前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-05-18:假设数组a和数组b为两组信号:1) length(b) <= length(a);2) 对于任意0<=i<

2022-05-18:假设数组a和数组b为两组信号:1) length(b) <= length(a);2) 对于任意0<=i<

作者头像
福大大架构师每日一题
发布2022-06-04 11:00:05
2150
发布2022-06-04 11:00:05
举报

2022-05-18:假设数组a和数组b为两组信号:

1) length(b) <= length(a);

2) 对于任意0<=i<length(b), 有b[i+1] - b[i] == a[i+1] - a[i]。

那么就称信号b和信号a一致,记为b==a,

给你好多b数组,假设有m个: b0数组、b1数组...

给你好多a数组,假设有n个: a0数组、a1数组...

返回一个长度为m的结果数组ans,ans[i]表示 : bi数组和多少个a数组一致。

来自字节飞书团队。

答案2022-05-18:

前缀树。

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

代码语言:javascript
复制
use std::collections::HashMap;
use std::sync::Arc;
use std::sync::Mutex;

fn main() {
    let mut bs: Vec<Vec<isize>> = vec![vec![1, 7, 5], vec![2, 8, 6, 24]];
    let mut as0: Vec<Vec<isize>> = vec![vec![1, 7, 5], vec![2, 8, 6, 24]];
    let ans = same_teams_array(&mut bs, &mut as0);
    println!("ans = {:?}", ans);
}

fn same_teams_array(bs: &mut Vec<Vec<isize>>, as0: &mut Vec<Vec<isize>>) -> Vec<isize> {
    let m = bs.len() as isize;
    let mut root = Arc::new(Mutex::new(TrieNode::new()));
    let mut cur = Arc::clone(&mut root);
    let mut cur2 = Arc::clone(&mut cur);
    for i in 0..m {
        let k = bs[i as usize].len() as isize;
        cur = Arc::clone(&mut root);
        for j in 1..k {
            let diff = bs[i as usize][j as usize] - bs[i as usize][(j - 1) as usize];
            if !cur.lock().unwrap().nexts.contains_key(&diff) {
                cur.lock()
                    .unwrap()
                    .nexts
                    .insert(diff, Arc::new(Mutex::new(TrieNode::new())));
            }
            let c2 = Arc::clone(&mut cur.lock().unwrap().nexts.get(&diff).unwrap());
            cur = c2;
        }
        cur.lock().unwrap().indices.push(i);
    }
    let mut ans: Vec<isize> = vec![];
    for _i in 0..m {
        ans.push(0);
    }
    let n = as0.len() as isize;
    for i in 0..n {
        let k = as0[i as usize].len() as isize;
        cur = Arc::clone(&mut root);
        for j in 1..k {
            let diff = as0[i as usize][j as usize] - as0[i as usize][(j - 1) as usize];
            if !cur.lock().unwrap().nexts.contains_key(&diff) {
                break;
            }
            let c2 = Arc::clone(&mut cur.lock().unwrap().nexts.get(&diff).unwrap());
            cur = c2;
            for index in &cur.lock().unwrap().indices {
                ans[(*index) as usize] += 1;
            }
        }
    }
    return ans;
}

pub struct TrieNode {
    pub indices: Vec<isize>,
    pub nexts: HashMap<isize, Arc<Mutex<TrieNode>>>,
}

impl TrieNode {
    pub fn new() -> Self {
        Self {
            indices: vec![],
            nexts: HashMap::new(),
        }
    }
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_03_2_week/Code04_SameTeams.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档