Java C++ 算法leetcode828统计子串中唯一字符乘法原理
作者:AnjaVon 时间:2022-05-09 11:19:18
题目要求
思路:模拟
解题的核心思想在于逆向思维,不考虑每个子数组中的唯一字符个数,转而考虑每个字符可以作为多少个子数组的唯一字符;
所以在计算答案时的算式和示例中给出的是不一样的;
在计算每个字符“贡献”【即当前向左向右分别可组成的答案个数】的时候要用到乘法原理。
对每一个字符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)
来源:https://juejin.cn/post/7140264367676719117
标签:Java,C++,算法,子串唯一字符,乘法原理
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java利用三目运算符比较三个数字的大小
2023-04-18 01:20:19
java异常与错误处理基本知识
2023-11-25 10:44:59
c# 在windows中操作IIS设置FTP服务器的示例
2023-07-18 06:13:01
![](https://img.aspxhome.com/file/2023/6/66116_0s.jpg)
Java读取json数据并存入数据库的操作代码
2023-09-23 06:00:57
Java异常处理try catch的基本使用
2023-11-24 05:04:38
使用Java和WebSocket实现网页聊天室实例代码
2023-11-26 00:16:02
![](https://img.aspxhome.com/file/2023/5/60395_0s.png)
java实现哈弗曼编码与反编码实例分享(哈弗曼算法)
2023-11-25 04:54:05
Java利用移位运算将int型分解成四个byte型的方法
2023-11-09 08:25:00
![](https://img.aspxhome.com/file/2023/4/59334_0s.png)
elasticsearch分布式及数据的功能源码分析
2023-08-11 06:31:26
![](https://img.aspxhome.com/file/2023/7/58087_0s.png)
Java基于Javafaker生成测试数据
2023-11-23 09:36:16
![](https://img.aspxhome.com/file/2023/5/58895_0s.png)
Swagger及knife4j的基本使用详解
2023-02-13 09:34:00
Android自定义带圆点的半圆形进度条
2023-08-05 07:47:15
![](https://img.aspxhome.com/file/2023/0/86750_0s.png)
教你怎么用SpringBoot+Mybati-Plus快速搭建代码
2023-08-07 12:42:10
![](https://img.aspxhome.com/file/2023/1/58081_0s.png)
详解Java注解知识点
2021-06-24 18:39:12
![](https://img.aspxhome.com/file/2023/5/60905_0s.png)
java 读取excel文件转换成json格式的实例代码
2023-09-11 13:07:28
使用flutter创建可移动的stack小部件功能
2023-06-21 12:28:25
![](https://img.aspxhome.com/file/2023/0/57150_0s.gif)
java开发之读写txt文件操作的实现
2023-11-17 06:00:23
![](https://img.aspxhome.com/file/2023/3/59553_0s.png)
JAVA的反射机制你了解多少
2023-11-29 16:46:38
![](https://img.aspxhome.com/file/2023/9/60609_0s.jpg)
Java实现AWT四大事件的详细过程
2023-11-28 18:39:52
![](https://img.aspxhome.com/file/2023/6/60076_0s.png)
IDEA解决springboot热部署失效问题(推荐)
2023-08-12 10:40:49
![](https://img.aspxhome.com/file/2023/8/58148_0s.png)