Java C++ 算法leetcode828统计子串中唯一字符乘法原理
目录
- 题目要求
- 思路:模拟
- java
- C++
- Rust
题目要求
思路:模拟
解题的核心思想在于逆向思维,不考虑每个子数组中的唯一字符个数,转而考虑每个字符可以作为多少个子数组的唯一字符;
- 所以在计算答案时的算式和示例中给出的是不一样的;
- 在计算每个字符“贡献”【即当前向左向右分别可组成的答案个数】的时候要用到乘法原理。
对每一个字符s[i]s[i]s[i]都记录其左边和右边的第一个相同字符位置,分别记为l[i]l[i]l[i]和r[i]r[i]r[i],这两个位置中间构成的就是s[i]s[i]s[i]能够作为唯一字符的最长子串,在这个最长的子串中还有若干个较短的子串,此时s[i]s[i]s[i]的“贡献”可由到左边和到右边的距离相乘计算得出。
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]; // 左边第一个相同的字符所在位置 letters[idx] = i; // 更新当前字母最新左位置 } Arrays.fill(letters, n); for (int i = n - 1; i >= 0; i--) { int idx = cs[i] - 'A'; r[i] = letters[idx]; // 右边第一个相同的字符所在位置 letters[idx] = i; // 更新当前字母最新右位置 } for (int i = 0; i < n; i++) res += (i - l[i]) * (r[i] - i); return res; } }
- 时间复杂度:O(n)
- 空间复杂度:O(n)
C++
- 因为
memset
初始化问题,所以在构成结果的时候多一步判断。
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]; // 左边第一个相同的字符所在位置 letters[idx] = i; // 更新当前字母最新左位置 } memset(letters, -1, sizeof(letters)); for (int i = n - 1; i >= 0; i--) { int idx = s[i] - 'A'; r[i] = letters[idx]; // 右边第一个相同的字符所在位置 letters[idx] = i; // 更新当前字母最新右位置 } for (int i = 0; i < n; i++) { int ri = r[i] == -1 ? n : r[i]; res += (i - l[i]) * (ri - i); } return res; } };
- 时间复杂度:O(n)
- 空间复杂度: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>() } }
- 时间复杂度:O(n)
- 空间复杂度:O(n)
以上就是Java C++ 算法leetcode828统计子串中唯一字符乘法原理的详细内容,更多关于Java C++ 统计子串唯一字符的资料请关注我们其它相关文章!
赞 (0)