esc to dismiss
x
Home / week-83 / 828

信息

题解

按照题意, 很容易写入如下枚举的方式, 时间复杂度 \(O(n^3 + c \times n^2)\)
枚举边界 \(n^2\), 内层统计个数 \(n + C\)
最后超时 

pub fn unique_letter_string(s: String) -> i32 {
    fn count_unique_chars(s: &str) -> usize {
        use std::collections::HashMap;
        let mut counter = HashMap::new();
        for chr in s.chars() {
            *counter.entry(chr).or_insert(0) += 1;
        }
        counter.into_iter().filter(|(_, v)| *v == 1).count()
    }
    let mut cnt = 0;
    for i in 0..s.len() {
        for j in i..s.len() {
            cnt += count_unique_chars(s.get(i..=j).unwrap());
        }
    }
    cnt as i32
}

优化方向: 将内层的遍历换成类似"滑动窗口", 不做重复统计
时间复杂度 \(O(n^2 + c \times n^2)\), 仍然超时 

pub fn unique_letter_string(s: String) -> i32 {
    use std::collections::HashMap;
    let s = s.as_bytes();
    let mut cnt = 0;
    for i in 0..s.len() {
        let mut counter = HashMap::new();
        for j in i..s.len() {
            {
                *counter.entry(s[j]).or_insert(0) += 1;
            }
            cnt += counter.iter().filter(|(_, &v)| v == 1).count();
        }
    }
    cnt as i32
}

其他思路:
对于字串 BCADEF, 假定其前后都是A, 即(A)BCADEF(A), 含统计字符A的唯一串有
BCA, BCAD, BCADE, BCADEF, CA, CAD, CADE, CADEF, A, AD, ADE, ADEF

  • 站在BC的角度看, 后面有4种选择, (), D, DE, DEF
  • 站在DEF的角度看, 前面有3种选择, BC, C, ()

所以这个段内, 含统计A字符的唯一串有 3 * 4 = 12, 即 (2+1) * (3+1),
2为当前A到前一个A之间字符个数, 3为当前A到后一个A之间字符个数

基于此, 可以对任意一个(A)..A..(A)进行计算, 最终加和即为结果

边界情况: 字符只出现一次

时间复杂度\(O(n)\) 

pub fn unique_letter_string(s: String) -> i32 {
    let s = s.as_bytes();

    let mut last_pos = vec![-1; 26];
    let mut curr_pos = vec![-1; 26];

    let mut ans = 0;

    for (pos, &b) in s.iter().enumerate() {
        let i = (b - b'A') as usize;
        let pos = pos as i32;
        if curr_pos[i] > -1 {
            // 这个字符之前出现过, 这时的pos对应上述推导中的后一个
            ans = ans + (pos - curr_pos[i]) * (curr_pos[i] - last_pos[i]);
        }
        last_pos[i] = curr_pos[i];
        curr_pos[i] = pos;
    }
    // 对于只出现过一次的字符, 上面循环统计不到, 即等效 后一个 的位置为字符结尾
    for (last, curr) in last_pos.into_iter().zip(curr_pos.into_iter()) {
        if curr > -1 {
            ans = ans + (curr - last) * (s.len() as i32 - curr);
        }
    }
    ans
}

Backlinks

Tags

x