2022-08-28:把字符串 s 看作 “abcdefghijklmnopqrstuvwxyz“ 的无限环绕字符串

2022-08-28:把字符串 s 看作 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串,
所以 s 看起来是这样的:
…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….
现在给定另一个字符串 p 。返回 s 中 不同 的 p 的 非空子串 的数量。
输入: p = “zab”。
输出: 6。

答案2022-08-28:

统计从以a结尾的最长字符的长度,从以b结尾的最长字符的长度,……,从以z结尾的最长字符的长度。最后全部累加就是需要的返回值。
时间复杂度:O(N)。

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

fn main() {
    let s = "zab";
    let ans = find_substring_in_wrapround_string(s);
    println!("ans = {}", ans);
}

fn find_substring_in_wrapround_string(s: &str) -> i32 {
    let str = s.as_bytes();
    let n = str.len() as i32;
    let mut ans = 0;
    let mut len = 1;
    // 256 0~255
    let mut max: [i32; 256] = [0; 256];
    max[str[0] as usize] += 1;
    for i in 1..n {
        let cur = str[i as usize];
        let pre = str[(i - 1) as usize];
        if (pre == 'z' as u8 && cur == 'a' as u8) || pre + 1 == cur {
            len += 1;
        } else {
            len = 1;
        }
        max[cur as usize] = get_max(max[cur as usize], len);
    }
    for i in 0..256 {
        ans += max[i as usize];
    }
    return ans;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

执行结果如下:

在这里插入图片描述


左神java代码

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

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