算法day08-字符串篇（2）
目录[*]反转字符串中的单词
[*]找出字符串中第一个匹配项的下标
[*]重复的子字符串
一、反转字符串中的单词
主要思路：把整个字符串的头尾的空格先去掉，然后根据” ”来划分字符串数组，将字符串倒着放进结果中。
class Solution {
public String reverseWords(String s) {
String[] parts = s.trim().split("\\s+"); //去掉首尾空格
StringBuilder sb = new StringBuilder();
for(int i = parts.length-1; i>=0; i--){
if(i == 0){
sb.append(parts);
}else{
sb.append(parts);
sb.append(" ");
}
}
return sb.toString();
}
}
//时间复杂度：O(n)
//空间复杂度：O(n)
二、右旋转字符串
class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
String s = in.nextLine();
int p1 = s.length() - n; //要右旋的起点
int p2 = 0;
StringBuilder sb = new StringBuilder();
while(p1 < s.length()){
sb.append(s.charAt(p1));
p1++;
}
while(p2 < s.length() - n){
sb.append(s.charAt(p2));
p2++;
}
System.out.print(sb);
}
}
//时间复杂度：O(N)
//空间复杂度：O(N)
三、找出字符串中第一个匹配项的下标
主要思路：在原字符串的每一个位置都截取一段子字符串来判断是否和needle相等。
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length()==0){
return 0;
}
if(needle.length() > haystack.length()){
return -1;
}
for(int i=0; i<=haystack.length() - needle.length(); i++){
if(haystack.substring(i, i+needle.length()).equals(needle)){
return i;
}
}
return -1;
}
}
//时间复杂度：O((n-m+1)*m)
//空间复杂度：O(1)// 时间复杂度：O(n)，其中 n 是字符串的长度，KMP 构造 next 数组只需要一次线性扫描。
// 空间复杂度：O(n)，用于存储前缀表 next[]。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]