目录
- 反转字符串中的单词
- 找出字符串中第一个匹配项的下标
- 重复的子字符串
一、反转字符串中的单词
主要思路:把整个字符串的头尾的空格先去掉,然后根据” ”来划分字符串数组,将字符串倒着放进结果中。- 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[i]);
- }else{
- sb.append(parts[i]);
- 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[]。
来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作! |