目录题目要求思路:模拟javac++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]的“贡献”可由到左边和到右边的距离相乘计算得出。
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;
}
}
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;
}
};
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>()
}
}
以上就是Java C++ 算法LeetCode828统计子串中唯一字符乘法原理的详细内容,更多关于Java C++ 统计子串唯一字符的资料请关注编程网其它相关文章!
--结束END--
本文标题: JavaC++算法leetcode828统计子串中唯一字符乘法原理
本文链接: https://www.lsjlt.com/news/167481.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0