玉溪定制网站建设,wordpress电商主题数据库,建设大马路小学网站,软件开发文档包括什么内容1. 题意
统计一个字符串的所有子串中唯一字符的数量。 例如: ABA的字串对应的唯一字符数量 “A”#xff1a; 1 “AB”#xff1a;2 “ABA”#xff1a;1 “B”#xff1a;1 “BA”#xff1a;2 “A”#xff1a;1 求和为8 统计子串中的唯一字符
2. 题解
…1. 题意
统计一个字符串的所有子串中唯一字符的数量。 例如: ABA的字串对应的唯一字符数量 “A” 1 “AB”2 “ABA”1 “B”1 “BA”2 “A”1 求和为8 统计子串中的唯一字符
2. 题解
正难则反直接枚举子串的方法复杂度最低为 O ( n 2 ) O(n^2) O(n2)。
所以不能使用我们可以考虑每一个字符对所有求和的贡献。
这里用到了基本计数原理中的乘法。
先从不重复的串说起;
对于串abcde
计算贡献时可以看成 p r e S t r C t a r g e t s u f S t r preStr C_{target} sufStr preStrCtargetsufStr;
就变成了算包含 C t a r g e t C_{target} Ctarget的组合数
当然 p r e S t r . s i z e s u f S t r . s i z e preStr.size\ sufStr.size preStr.size sufStr.size都可取0。
此时得到无重复字符时的贡献公式 ( P o s ( C t a r g e t ) 1 ) ) ∗ ( S z − P o s ( C t a r g e t ) ) (Pos_{(C_{target})} 1)) *(Sz -Pos_{(C_{target})}) (Pos(Ctarget)1))∗(Sz−Pos(Ctarget))
含有重复的字符的串我们可以通过记录每个相同字符出现的位置来转化为几段无重复字符串的问题。
假设当前字符位置为 j j j, 前一相同字符出现位置为 i i i,后一相同字符出现位置为 k k k。则在 j j j处出现
字符的贡献为 ( j − i ) ( k − j ) (j - i)(k - j) (j−i)(k−j)
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
2.1 实现 class Solution {
public:int uniqueLetterString(string s) {vectorvectorint v_arr(26, vectorint(1, -1));int sz s.size();int ans 0;for (int i 0; i sz; i) {int idx s[i] - A;v_arr[ idx ].push_back(i);}for ( auto arr:v_arr) {arr.push_back(sz);int asz arr.size();for (int i 1;i asz - 1; i){ans (arr[i 1] - arr[i]) * (arr[i] - arr[i - 1]);}}return ans;}
};2.2 空间压缩
实际上我们并不需要记录字符的所有位置只需要上两个位置即可。
class Solution {
public:int uniqueLetterString(string s) {vectorvectorint v_arr(26, vectorint(2, -1));int sz s.size();int ans 0;for (int i 0; i sz; i) {int idx s[i] - A;ans (v_arr[idx][1] - v_arr[idx][0]) * (i - v_arr[idx][1]);v_arr[idx][0] v_arr[idx][1];v_arr[idx][1] i;}for (int i 0; i 26;i) {ans (v_arr[i][1] - v_arr[i][0]) * (sz - v_arr[i][1]);}return ans;}
};
