找回密码
 立即注册
首页 业界区 科技 算法day08-字符串篇(2)

算法day08-字符串篇(2)

枢覆引 3 天前
目录


  • 反转字符串中的单词
  • 找出字符串中第一个匹配项的下标
  • 重复的子字符串
一、反转字符串中的单词

1.png

   主要思路:把整个字符串的头尾的空格先去掉,然后根据” ”来划分字符串数组,将字符串倒着放进结果中。
  1. class Solution {
  2.     public String reverseWords(String s) {
  3.         String[] parts = s.trim().split("\\s+");        //去掉首尾空格
  4.         StringBuilder sb = new StringBuilder();
  5.         for(int i = parts.length-1; i>=0; i--){
  6.             if(i == 0){
  7.                 sb.append(parts[i]);
  8.             }else{
  9.                 sb.append(parts[i]);
  10.                 sb.append(" ");
  11.             }
  12.         }
  13.         return sb.toString();
  14.     }
  15. }
  16. //时间复杂度:O(n)
  17. //空间复杂度:O(n)
复制代码
 
二、右旋转字符串

2.png

 
  1. class Main{
  2.     public static void main(String[] args){
  3.         Scanner in = new Scanner(System.in);
  4.         int n = in.nextInt();
  5.         in.nextLine();
  6.         String s = in.nextLine();
  7.         int p1 = s.length() - n;        //要右旋的起点
  8.         int p2 = 0;
  9.         StringBuilder sb = new StringBuilder();
  10.         while(p1 < s.length()){
  11.             sb.append(s.charAt(p1));
  12.             p1++;
  13.         }
  14.         while(p2 < s.length() - n){
  15.             sb.append(s.charAt(p2));
  16.             p2++;
  17.         }
  18.         System.out.print(sb);
  19.     }
  20. }
  21. //时间复杂度:O(N)
  22. //空间复杂度:O(N)
复制代码
 
三、找出字符串中第一个匹配项的下标

3.png

   主要思路:在原字符串的每一个位置都截取一段子字符串来判断是否和needle相等。
  1. class Solution {
  2.     public int strStr(String haystack, String needle) {
  3.         if(needle.length()==0){
  4.             return 0;
  5.         }
  6.         if(needle.length() > haystack.length()){
  7.             return -1;
  8.         }
  9.         for(int i=0; i<=haystack.length() - needle.length(); i++){
  10.             if(haystack.substring(i, i+needle.length()).equals(needle)){
  11.                 return i;
  12.             }
  13.         }
  14.         return -1;
  15.     }
  16. }
  17. //时间复杂度:O((n-m+1)*m)
  18. //空间复杂度:O(1)
复制代码
// 时间复杂度:O(n),其中 n 是字符串的长度,KMP 构造 next 数组只需要一次线性扫描。
// 空间复杂度:O(n),用于存储前缀表 next[]。
 

来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
您需要登录后才可以回帖 登录 | 立即注册