java给定一个由英文小写字母组成的字符串。请将此字符串拆分成最少数量的子字符串,以使每个子字符串的字母都不会出现多次。
时间: 2023-12-14 14:35:43 浏览: 65
这个问题可以使用贪心算法来解决。我们可以遍历整个字符串,对于每个字符,我们尝试将其作为一个子字符串的起点,并向后扫描,直到找到一个字符在之前已经出现过的位置。在此期间,我们可以通过哈希表或者数组来记录当前子字符串中的字符是否出现过。一旦我们找到了一个字符在之前已经出现过的位置,我们就将该位置作为新的起点,继续向后扫描。
以下是 Java 代码实现:
```java
public static int minSplit(String s) {
int n = s.length();
int[] last = new int[26];
Arrays.fill(last, -1);
int res = 0, start = 0;
for (int i = 0; i < n; i++) {
int index = s.charAt(i) - 'a';
if (last[index] >= start) {
res++;
start = i;
}
last[index] = i;
}
return res + 1;
}
```
时间复杂度为 $O(n)$,其中 $n$ 是字符串的长度。
相关问题
java字符串常用方法
Java 字符串类 String 提供了很多常用的方法,以下是一些常用的方法:
1. char charAt(int index):返回指定索引处的字符。
2. int length():返回字符串的长度。
3. boolean equals(Object anObject):将此字符串与指定对象进行比较。
4. boolean isEmpty():当且仅当 length() 为 0 时返回 true。
5. String substring(int beginIndex):返回一个新的字符串,它是此字符串从 beginIndex 开始截取后的子字符串。
6. String substring(int beginIndex, int endIndex):返回一个新字符串,它是此字符串从 beginIndex 开始截取到 endIndex-1 位置的子字符串。
7. boolean contains(CharSequence s):当且仅当此字符串包含指定的 char 值序列时,返回 true。
8. String replace(CharSequence target, CharSequence replacement):返回一个新的字符串,它是通过用 replacement 替换此字符串中出现的所有 target 。
9. String[] split(String regex):根据给定的正则表达式来拆分此字符串。
10. String toLowerCase():使用默认语言环境的规则将此 String 中的所有字符都转换为小写。
11. String toUpperCase():使用默认语言环境的规则将此 String 中的所有字符都转换为大写。
12. boolean startsWith(String prefix):测试此字符串是否以指定的前缀开头。
13. boolean endsWith(String suffix):测试此字符串是否以指定的后缀结尾。
14. int indexOf(int ch):返回指定字符在此字符串中第一次出现处的索引。
15. int indexOf(int ch, int fromIndex):返回在此字符串中第一次出现指定字符处的索引,从指定的索引开始搜索。
16. int indexOf(String str):返回指定子字符串在此字符串中第一次出现处的索引。
17. int indexOf(String str, int fromIndex):返回指定子字符串在此字符串中第一次出现处的索引,从指定的索引开始。
18. String trim():返回字符串的副本,忽略前导空白和尾部空白。
19. static String valueOf(char[] data):返回 char 数组参数的字符串表示形式。
20. static String valueOf(int i):返回 int 参数的字符串表示形式。
以上是一些常用的字符串方法,还有很多其他方法可以参考 Java 文档。
利用指针任意给定一个字符串s(长度小于100),其中只包含大写字母“A—Z”和小写字母“a—z”。你的任务是把s中大写字母和小写字母分开,并分别存到指定的字符数组中。拆分后原字母顺序保持不变。本题要求用函数实现。
以下是一个实现该功能的函数示例:
```c
void splitString(char* s, char* upperCase, char* lowerCase) {
int i = 0, j = 0, k = 0;
while (s[i] != '\0') {
if (s[i] >= 'A' && s[i] <= 'Z') {
upperCase[j] = s[i];
j++;
} else if (s[i] >= 'a' && s[i] <= 'z') {
lowerCase[k] = s[i];
k++;
}
i++;
}
upperCase[j] = '\0';
lowerCase[k] = '\0';
}
```
该函数接受一个字符串指针 `s`,以及两个字符数组指针 `upperCase` 和 `lowerCase`,分别用于存放大写字母和小写字母。在函数内部,使用循环遍历字符串 `s` 中的每个字符,判断其是否为大写或小写字母,并将其分别存放到 `upperCase` 和 `lowerCase` 中。最后,在两个数组的末尾添加字符串终止符 `\0`,以保证字符串的正确性。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)