代码随想录 字符串 Java

这篇具有很好参考价值的文章主要介绍了代码随想录 字符串 Java。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


(简单)344. 反转字符串

代码随想录 字符串 Java

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }
}

复杂度分析:

  • 时间复杂度:O(N),其中N为字符数组的长度。一共执行了N/2次的交换
  • 空间复杂度:O(1),只使用了常数空间来存放若干变量

(简单)541. 反转字符串||

代码随想录 字符串 Java
我的思路:2k个字符为一组,先将前k个字符(或者不足k个字符)添加到StringBuilder中,然后调用reverse()方法,然后再将后k个字符(或者不足2k个字符)添加到StringBuilder中,最后在将这一组作为一个整体,添加到答案中

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        int i = 0;
        StringBuilder stringBuilder = new StringBuilder();
        while (i < n) {
            StringBuilder strk = new StringBuilder();
            while (i < n && strk.length() < k) {
                strk.append(s.charAt(i));
                i++;
            }
            strk.reverse();
            while (i < n && strk.length() >= k && strk.length() < 2 * k) {
                strk.append(s.charAt(i));
                i++;
            }
            stringBuilder.append(strk);
        }
        return stringBuilder.toString();
    }
}

代码随想录 字符串 Java
我的另一种思路:将字符串s转换成字符数组,然后在字符数组中找到合适的区间进行交换

import java.util.regex.Pattern;

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] charArray = s.toCharArray();
        boolean flag = true;
        int i = 0;
        while (i < n) {
            if (flag) {
                int left = i;
                int right = i + k > n ? n - 1 : i + k - 1;
                while (left < right) {
                    char tmp = charArray[left];
                    charArray[left] = charArray[right];
                    charArray[right] = tmp;
                    left++;
                    right--;
                }
                i = i + k;
                flag = false;
            } else {
                if (i + k >= n) {
                    break;
                } else {
                    i += k;
                    flag = true;
                }
            }
        }
        return new String(charArray);
    }
}

代码随想录 字符串 Java
其他写法

也是模拟,反转每个下标从2k的倍数开始的,长度为k的子串。若该子串长度不足k,则反转整个子串。

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] charArray = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(charArray, i, Math.min(i + k, n) - 1);
        }
        return new String(charArray);
    }

    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }
}

代码随想录 字符串 Java
复杂度分析:

  • 时间复杂度:O(n),其中n是字符串s的长度
  • 空间复杂度:O(1)和O(n),取决于使用的语言中字符串类型的性质。如果字符串是可修改的,可以直接在原字符串上进行修改,空间复杂度为O(1),否则需要使用O(n)的空间将字符串临时转换为可以修改的数据结构(例如数组),空间复杂度为O(n)。

(简单)剑指Offer 05. 替换空格

代码随想录 字符串 Java

方法一

class Solution {
    public String replaceSpace(String s) {
        return s.replaceAll(" ", "%20");
    }
}

代码随想录 字符串 Java
方法二

class Solution {
    public String replaceSpace(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                stringBuilder.append("%20");
            } else {
                stringBuilder.append(c);
            }
        }
        return stringBuilder.toString();
    }
}

代码随想录 字符串 Java
其他思路

由于每次替换从1个字符变成3个字符,使用字符数组可方便地进行替换。建立字符数组的长度为s的长度的3倍,这样可保证字符数组可以容纳所有替换后的字符。

class Solution {
    public String replaceSpace(String s) {
        int n = s.length();
        char[] array = new char[n * 3];
        int index = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[index++] = '%';
                array[index++] = '2';
                array[index++] = '0';
            } else {
                array[index++] = c;
            }
        }
        return new String(array, 0, index);
    }
}

代码随想录 字符串 Java

(中等)151. 反转字符串中的单词

代码随想录 字符串 Java

class Solution {
    public String reverseWords(String s) {
    	//使用trim()去掉首尾的空格,在使用split()按照" "分割
        String[] splits = s.trim().split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = splits.length - 1; i >= 0; i--) {
			//但单词间会有多个空格,遇到splits[i].length==0的直接跳过
            if (splits[i].length() == 0) {
                continue;
            }

            stringBuilder.append(splits[i]);

            if (i != 0) {
                stringBuilder.append(" ");
            }
        }
        return stringBuilder.toString();
    }
}

代码随想录 字符串 Java
官方思路,方案一:使用语言特性

很多语言对字符串提供了split拆分、reverse翻转和join连接等方法,因此可以通过调用内置的API完成操作
代码随想录 字符串 Java

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

复杂度分析:

  • 时间复杂度:O(n),其中n为输入字符串的长度
  • 空间复杂度:O(n),用来存储字符串分割之后的结果

官方思路,方法二:自行编写相应的函数

在不同的编程语言中,这些函数是不一样的,主要的差别是有些语言的字符串不可变(如Python、Java),有些语言的字符串可变(如C++)。

对于字符串不可变的语言,首先得把字符串转化成其他可变的数据结构,同时还需要在转化的过程中去除空格。
代码随想录 字符串 Java

对于字符串可变的语言,就不需要额外开辟空间了,直接在字符串上原地实现。在这种情况下,反转字符和去除空格可以一起完成。
代码随想录 字符串 Java

class Solution {
    public String reverseWords(String s) {
        
        //去除首部、尾部、中间多余字符
        StringBuilder sb = trimSpace(s);
        
        //反转整个字符串
        reverse(sb, 0, sb.length() - 1);
        
        //以空格为分割,反转每一个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 0;
        int n = sb.length();
        while (end < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverse(sb, start, end - 1);
            start = end + 1;
            end++;
        }
    }

    private void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left, sb.charAt(right));
            sb.setCharAt(right, tmp);
            left++;
            right--;
        }
    }

    private StringBuilder trimSpace(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left <= right) {

            //去除字符串开头的空白字符串
            while (left <= right && s.charAt(left) == ' ') {
                left++;
            }

            //去除字符串末尾的空白字符串
            while (left <= right && s.charAt(right) == ' ') {
                right--;
            }

            StringBuilder stringBuilder = new StringBuilder();
            while (left <= right) {
                char c = s.charAt(left);
                if (c != ' ') {
                    stringBuilder.append(c);
                } else if (stringBuilder.charAt(stringBuilder.length() - 1) != ' ') {
                    stringBuilder.append(c);
                }
                left++;
            }
            return stringBuilder;
        }
        return null;
    }
}

代码随想录 字符串 Java
复杂度分析:

  • 时间复杂度:O(n),其中n为输入字符串的长度,因为需要完整遍历字符串
  • 空间复杂度:Java和Python的方法需要O(n)的空间来存储字符出,而C++方法只需要O(1)的额外空间来存放若干变量

官方思路,方法三:双端队列

由于双端队列支持从队列头部插入的方法,因此我们可以沿着字符串一个一个单词处理,然后将单词压入队列头部,再将队列转成字符串即可

代码随想录 字符串 Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public String reverseWords(String s) {
        int n = s.length();
        int left = 0;
        int right = s.length() - 1;

        //去除字符串开头的空白字符串
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        //去除字符串末尾的空白字符串
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        Deque<String> deque = new ArrayDeque<>();
        StringBuilder word = new StringBuilder();

        while (left <= right) {
            char c = s.charAt(left);
            if (word.length() != 0 && c == ' ') {
                deque.offerFirst(word.toString());
                word.setLength(0);
            } else if (c != ' ') {
                word.append(c);
            }
            ++left;
        }
        deque.offerFirst(word.toString());

        return String.join(" ", deque);
    }
}

代码随想录 字符串 Java
复杂度分析:

  • 时间复杂度:O(n),其中n为输入字符串的长度
  • 空间复杂度:O(n),双端队列存储单词需要O(n)的空间。

其实这个地方的双端队列和栈是一个意思啊

(简单)剑指 Offer 58 - II. 左旋转字符串

代码随想录 字符串 Java
简单来说,就是把字符串截成两段,把这两段交换一下位置,拼接成一个新的字符串返回

class Solution {
    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        char[] chars = new char[len];
        int index = 0;
        for (int i = n; i < len; i++) {
            chars[index++] = s.charAt(i);
        }
        for (int i = 0; i < n; i++) {
            chars[index++] = s.charAt(i);
        }
        return new String(chars);

    }
}

代码随想录 字符串 Java

class Solution {
    public String reverseLeftWords(String s, int n) {

        int len = s.length();

        StringBuilder stringBuilder = new StringBuilder(len);

        for (int i = n; i < len; i++) {
            stringBuilder.append(s.charAt(i));
        }
        for (int i = 0; i < n; i++) {
            stringBuilder.append(s.charAt(i));
        }

        return stringBuilder.toString();

    }
}

代码随想录 字符串 Java

(*中等 - KMP算法)28. 找出字符串中第一个匹配项的下标

代码随想录 字符串 Java

最最最传统的字符串匹配问题,脑海中第一反应是KMP算法,但是不记得思路是啥了,所以写了暴力匹配法

class Solution {
    public int strStr(String haystack, String needle) {

        int n = needle.length();
        int h = haystack.length();

        if (n > h) {
            return -1;
        }

        int i = 0;
        int j;
        while (i < h) {
            if (haystack.charAt(i) != needle.charAt(0)) {
                i++;
            } else {
                int k = i + 1;
                j = 1;
                while (k < h && k < i + n && haystack.charAt(k) == needle.charAt(j)) {
                    k++;
                    j++;
                }
                if (k == i + n) {
                    return i;
                } else {
                    i++;
                }
            }
        }
        return -1;
    }
}

代码随想录 字符串 Java

暴力法,就是让字符串needle与字符串haystack的所有长度为m的子串均匹配一次。

为了减少不必要的匹配,我们每次匹配失败即立刻停止当前子串的匹配,对下一个子串进行匹配。如果当前字串匹配成功,就返回当前子串开始的位置即可。如果所有子串都匹配失败,则返回-1

class Solution {
    public int strStr(String haystack, String needle) {

        int m = needle.length();//短的
        int n = haystack.length();//长的

        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}

代码随想录 字符串 Java
复杂度分析:

  • 时间复杂度:O(nm),其中n是字符串haystack的长度,m是字符串needle的长度。最坏情况下需要将字符串needle与字符串haystack的所有长度为m的子串均匹配一次。
  • 空间复杂度:O(1),只需要常数的空间保存若干变量。

KMP算法

暴力法的时间复杂度是O(mn),而KMP的时间复杂度是O(m+n),是因为其能在非完全匹配的过程中提取到有效信息进行复用,以减少重复匹配的消耗

暴力法匹配字符串,当出现不同位置时,将原字符串的指针移动至本次起始点的下一个位置,匹配串的指针移动至起始位置。继续尝试匹配,发现对不上,原串的指针会一直往后移动,知道能够与匹配串对上位置。

import java.util.Arrays;

class Solution {
    public int strStr(String haystack, String needle) {

        int haystackLength = haystack.length();
        int needleLen = needle.length();

        if(needleLen > haystackLength){
            return -1;
        }

        char[] haystackArr = haystack.toCharArray();
        char[] needleArr = needle.toCharArray();
        int[] next = new int[needleLen];
        getNext(next, needle.toCharArray());
        int i = 0;
        int j = 0;
        while (i < haystackLength) {
            if (haystackArr[i] != needleArr[j]) {
                while (j != 0 && haystackArr[i] != needleArr[j]) {
                    j = next[j - 1];
                }
                if (j == 0 && haystackArr[i] != needleArr[j]) {
                    i++;
                }
            } else {
                i++;
                j++;
            }

            if (j == needleLen) {
                return i - j;
            }
        }
        return -1;
    }

    private void getNext(int[] next, char[] arr) {
        int len = arr.length;
        int j = 0;
        int i = 1;
        while (i < len) {
            if (arr[i] == arr[j]) {
                next[i] = j + 1;
                i++;
                j++;
            } else {
                while (j > 0 && arr[i] != arr[j]) {
                    j = next[j - 1];
                }
                if (j == 0 && arr[i] != arr[j]) {
                    next[i] = 0;
                    i++;
                }
            }
        }
    }
}

代码随想录 字符串 Java

(*简单 - KMP算法)459. 重复的子字符串

代码随想录 字符串 Java

假设原字符串S是由子串s重复N次而成的,则S+S则有子串s重复2N次,那么现在有S=Ns,S+S=2Ns,其中N>=2。如果条件成立,掐头去尾破坏两个s,S+S中至少还有2(N-1)s,又因为N>=2,因此在S+S的索引从[0,length-2]中必出现一次以上

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return (s + s).substring(1, (s + s).length() - 1).contains(s);
    }
}

代码随想录 字符串 Java文章来源地址https://www.toymoban.com/news/detail-456491.html

到了这里,关于代码随想录 字符串 Java的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包