2022-09-17：一个字符串s，表示仓库的墙与货物，其中‘|‘表示墙,‘*‘表示货物。给定一个起始下标start和一个终止下标end，找出子串中被

原创

福大大架构师每日一题

发布于 2022-09-17 23:00:15

5370

发布于 2022-09-17 23:00:15

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-09-17：一个字符串s，表示仓库的墙与货物，其中'|'表示墙,'*'表示货物。

给定一个起始下标start和一个终止下标end，

找出子串中被墙包裹的货物数量。

比如：

s = "|||*"，

start = 1, end = 7，

start和end截出的子串是 "||*"，

被 '|'包裹的 '*' 有两个，所以返回2，

现在给定一系列的start，startIndices[]，和对应一系列的end ,endIndices[]。

返回每一对start,end的截出来的货物数量。

数据规模：

字符串s长度<=10^5，

startIndices长度 == endIndices长度 <=10^5。

亚马逊的货物和墙的问题。

答案2022-09-17：

前缀和。

时间复杂度：O(N)。

空间复杂度：O(N)。

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

fn main() {
    let s = "|**|**|*";
    let mut a = vec![0, 1, 3, 4];
    let mut b = vec![7, 7, 6, 5];
    let ans = number(s, &mut a, &mut b);
    println!("ans = {:?}", ans);
}

fn number(s: &str, starts: &mut Vec<i32>, ends: &mut Vec<i32>) -> Vec<i32> {
    let str = s.as_bytes();
    let n = str.len() as i32;
    let mut left: Vec<i32> = vec![];
    let mut right: Vec<i32> = vec![];
    let mut sum: Vec<i32> = vec![];
    for _ in 0..n {
        left.push(0);
        right.push(0);
        sum.push(0);
    }

    let mut pre = -1;
    let mut num = 0;
    for i in 0..n {
        pre = if str[i as usize] == '|' as u8 { i } else { pre };
        num += if str[i as usize] == '*' as u8 { 1 } else { 0 };
        left[i as usize] = pre;
        sum[i as usize] = num;
    }
    pre = -1;
    let mut i = n - 1;
    while i >= 0 {
        pre = if str[i as usize] == '|' as u8 { i } else { pre };
        right[i as usize] = pre;
        i -= 1;
    }

    let m = starts.len() as i32;
    let mut ans: Vec<i32> = vec![];
    for _ in 0..m {
        ans.push(0);
    }
    for i in 0..m {
        ans[i as usize] = stars(
            starts[i as usize],
            ends[i as usize],
            &mut left,
            &mut right,
            &mut sum,
        );
    }
    return ans;
}

fn stars(start: i32, end: i32, l: &mut Vec<i32>, r: &mut Vec<i32>, s: &mut Vec<i32>) -> i32 {
    let left = r[start as usize];
    let right = l[end as usize];
    if left == -1 || right == -1 || (left >= right) {
        return 0;
    }
    return if left == 0 {
        s[right as usize]
    } else {
        s[right as usize] - s[(left - 1) as usize]
    };
}

执行结果如下：

左神java代码

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

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

编程算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

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

编程算法

登录后参与评论

0 条评论

热度