Java C++ 算法leetcode828統(tǒng)計(jì)子串中唯一字符乘法原理

更新時(shí)間：2022年09月14日 09:51:11 作者：AnjaVon

這篇文章主要為大家介紹了Java C++ 算法leetcode828統(tǒng)計(jì)子串中唯一字符乘法原理詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路：模擬

解題的核心思想在于逆向思維，不考慮每個(gè)子數(shù)組中的唯一字符個(gè)數(shù)，轉(zhuǎn)而考慮每個(gè)字符可以作為多少個(gè)子數(shù)組的唯一字符；

所以在計(jì)算答案時(shí)的算式和示例中給出的是不一樣的；
在計(jì)算每個(gè)字符“貢獻(xiàn)”【即當(dāng)前向左向右分別可組成的答案個(gè)數(shù)】的時(shí)候要用到乘法原理。

對(duì)每一個(gè)字符s[i]s[i]s[i]都記錄其左邊和右邊的第一個(gè)相同字符位置，分別記為l[i]l[i]l[i]和r[i]r[i]r[i]，這兩個(gè)位置中間構(gòu)成的就是s[i]s[i]s[i]能夠作為唯一字符的最長子串，在這個(gè)最長的子串中還有若干個(gè)較短的子串，此時(shí)s[i]s[i]s[i]的“貢獻(xiàn)”可由到左邊和到右邊的距離相乘計(jì)算得出。

java

class Solution {
    public int uniqueLetterString(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length, res = 0;
        int[] l = new int[n], r = new int[n];
        int[] letters = new int[26];
        Arrays.fill(letters, -1);
        for (int i = 0; i < n; i++) {
            int idx = cs[i] - 'A';
            l[i] = letters[idx]; // 左邊第一個(gè)相同的字符所在位置
            letters[idx] = i; // 更新當(dāng)前字母最新左位置
        }
        Arrays.fill(letters, n);
        for (int i = n - 1; i >= 0; i--) {
            int idx = cs[i] - 'A';
            r[i] = letters[idx]; // 右邊第一個(gè)相同的字符所在位置
            letters[idx] = i; // 更新當(dāng)前字母最新右位置
        }
        for (int i = 0; i < n; i++)
            res += (i - l[i]) * (r[i] - i);
        return res;
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

C++

因?yàn)?code>memset初始化問題，所以在構(gòu)成結(jié)果的時(shí)候多一步判斷。

class Solution {
public:
    int uniqueLetterString(string s) {
        int n = s.size(), res = 0;
        cout << n << endl;
        int l[n], r[n];
        int letters[26];
        memset(letters, -1, sizeof(letters));
        for (int i = 0; i < n; i++) {
            int idx = s[i] - 'A';
            l[i] = letters[idx]; // 左邊第一個(gè)相同的字符所在位置
            letters[idx] = i; // 更新當(dāng)前字母最新左位置
        }
        memset(letters, -1, sizeof(letters));
        for (int i = n - 1; i >= 0; i--) {
            int idx = s[i] - 'A';
            r[i] = letters[idx]; // 右邊第一個(gè)相同的字符所在位置
            letters[idx] = i; // 更新當(dāng)前字母最新右位置
        }
        for (int i = 0; i < n; i++) {
            int ri = r[i] == -1 ? n : r[i];
            res += (i - l[i]) * (ri - i);
        }
        return res;
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

Rust

用Rust的遍歷稍微改一下，思路一樣……

impl Solution {
    pub fn unique_letter_string(s: String) -> i32 {
        let cs = s.as_bytes();
        (0..s.len()).into_iter().map(|i| {
            let (mut l, mut r) = (i - 1, i + 1);
            while l < s.len() && cs[l] != cs[i] {
                l -= 1;
            }
            while r < s.len() && cs[r] != cs[i] {
                r += 1;
            }
            ((i - l) * (r - i)) as i32
        }).sum::<i32>()
    }
}