国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

代碼隨想錄字符串 Java

2年前作者：努力努力再努力@_@分類：Toy博客閱讀(24)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了代碼隨想錄字符串 Java。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

（簡單）344. 反轉(zhuǎn)字符串

代碼隨想錄字符串 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--;
        }
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(N)，其中N為字符數(shù)組的長度。一共執(zhí)行了N/2次的交換
空間復(fù)雜度：O(1)，只使用了常數(shù)空間來存放若干變量

（簡單）541. 反轉(zhuǎn)字符串||

代碼隨想錄字符串 Java
我的思路：2k個字符為一組，先將前k個字符（或者不足k個字符）添加到StringBuilder中，然后調(diào)用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轉(zhuǎn)換成字符數(shù)組，然后在字符數(shù)組中找到合適的區(qū)間進(jìn)行交換

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
其他寫法

也是模擬，反轉(zhuǎn)每個下標(biāo)從2k的倍數(shù)開始的，長度為k的子串。若該子串長度不足k，則反轉(zhuǎn)整個子串。

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
復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)，其中n是字符串s的長度
空間復(fù)雜度：O(1)和O(n)，取決于使用的語言中字符串類型的性質(zhì)。如果字符串是可修改的，可以直接在原字符串上進(jìn)行修改，空間復(fù)雜度為O(1)，否則需要使用O(n)的空間將字符串臨時(shí)轉(zhuǎn)換為可以修改的數(shù)據(jù)結(jié)構(gòu)（例如數(shù)組），空間復(fù)雜度為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個字符，使用字符數(shù)組可方便地進(jìn)行替換。建立字符數(shù)組的長度為s的長度的3倍，這樣可保證字符數(shù)組可以容納所有替換后的字符。

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. 反轉(zhuǎn)字符串中的單詞

代碼隨想錄字符串 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翻轉(zhuǎn)和join連接等方法，因此可以通過調(diào)用內(nèi)置的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);
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)，其中n為輸入字符串的長度
空間復(fù)雜度：O(n)，用來存儲字符串分割之后的結(jié)果

官方思路，方法二：自行編寫相應(yīng)的函數(shù)

在不同的編程語言中，這些函數(shù)是不一樣的，主要的差別是有些語言的字符串不可變（如Python、Java），有些語言的字符串可變（如C++）。

對于字符串不可變的語言，首先得把字符串轉(zhuǎn)化成其他可變的數(shù)據(jù)結(jié)構(gòu)，同時(shí)還需要在轉(zhuǎn)化的過程中去除空格。
代碼隨想錄字符串 Java

對于字符串可變的語言，就不需要額外開辟空間了，直接在字符串上原地實(shí)現(xiàn)。在這種情況下，反轉(zhuǎn)字符和去除空格可以一起完成。
代碼隨想錄字符串 Java

class Solution {
    public String reverseWords(String s) {
        
        //去除首部、尾部、中間多余字符
        StringBuilder sb = trimSpace(s);
        
        //反轉(zhuǎn)整個字符串
        reverse(sb, 0, sb.length() - 1);
        
        //以空格為分割，反轉(zhuǎn)每一個單詞
        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
復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)，其中n為輸入字符串的長度，因?yàn)樾枰暾闅v字符串
空間復(fù)雜度：Java和Python的方法需要O(n)的空間來存儲字符出，而C++方法只需要O(1)的額外空間來存放若干變量

官方思路，方法三：雙端隊(duì)列

由于雙端隊(duì)列支持從隊(duì)列頭部插入的方法，因此我們可以沿著字符串一個一個單詞處理，然后將單詞壓入隊(duì)列頭部，再將隊(duì)列轉(zhuǎn)成字符串即可

代碼隨想錄字符串 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
復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)，其中n為輸入字符串的長度
空間復(fù)雜度：O(n)，雙端隊(duì)列存儲單詞需要O(n)的空間。

其實(shí)這個地方的雙端隊(duì)列和棧是一個意思啊

（簡單）劍指 Offer 58 - II. 左旋轉(zhuǎn)字符串

代碼隨想錄字符串 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. 找出字符串中第一個匹配項(xiàng)的下標(biāo)

代碼隨想錄字符串 Java

最最最傳統(tǒng)的字符串匹配問題，腦海中第一反應(yīng)是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的子串均匹配一次。

為了減少不必要的匹配，我們每次匹配失敗即立刻停止當(dāng)前子串的匹配，對下一個子串進(jìn)行匹配。如果當(dāng)前字串匹配成功，就返回當(dāng)前子串開始的位置即可。如果所有子串都匹配失敗，則返回-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
復(fù)雜度分析：

時(shí)間復(fù)雜度：O(nm)，其中n是字符串haystack的長度，m是字符串needle的長度。最壞情況下需要將字符串needle與字符串haystack的所有長度為m的子串均匹配一次。
空間復(fù)雜度：O(1)，只需要常數(shù)的空間保存若干變量。

KMP算法

暴力法的時(shí)間復(fù)雜度是O(mn)，而KMP的時(shí)間復(fù)雜度是O(m+n)，是因?yàn)槠淠茉诜峭耆ヅ涞倪^程中提取到有效信息進(jìn)行復(fù)用，以減少重復(fù)匹配的消耗

暴力法匹配字符串，當(dāng)出現(xiàn)不同位置時(shí)，將原字符串的指針移動至本次起始點(diǎn)的下一個位置，匹配串的指針移動至起始位置。繼續(xù)嘗試匹配，發(fā)現(xià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. 重復(fù)的子字符串

代碼隨想錄字符串 Java

假設(shè)原字符串S是由子串s重復(fù)N次而成的，則S+S則有子串s重復(fù)2N次，那么現(xiàn)在有S=Ns，S+S=2Ns，其中N>=2。如果條件成立，掐頭去尾破壞兩個s，S+S中至少還有2(N-1)s，又因?yàn)镹>=2，因此在S+S的索引從[0,length-2]中必出現(xiàn)一次以上

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

代碼隨想錄字符串 Java 文章來源地址http://www.zghlxwxcb.cn/news/detail-456491.html

到了這里，關(guān)于代碼隨想錄字符串 Java的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

代碼隨想錄day9｜實(shí)現(xiàn)strStr()、重復(fù)的子字符串
一般的字符串匹配問題我們可以使用KMP算法來處理，當(dāng)我們搜索文本串和模式串是否匹配的時(shí)候，我們先得到模式串的一個前綴表，其中前綴表中存放的內(nèi)容是模式串的最長相等前后綴。例如文本串為：aabaabaafa，模式串為：aabaaf，那么文本串的前綴表就是010120。當(dāng)我們開始搜
2024年02月15日
瀏覽(98)
代碼隨想錄 Leetcode1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng)
? ? ? ? 時(shí)間復(fù)雜度高 ? ? ? ? 寫完代碼多思考怎么優(yōu)化
2024年01月22日
瀏覽(28)
代碼隨想錄第五十六天——兩個字符串的刪除操作，編輯距離
題目鏈接：兩個字符串的刪除操作兩個字符串可以相互刪除版本一：確定dp數(shù)組及下標(biāo)的含義 dp[i][j] ：以i-1為結(jié)尾的字符串word1，和以j-1為結(jié)尾的字符串word2，想要達(dá)到相等，所需要刪除元素的最少次數(shù) 確定遞推公式（1）當(dāng)word1[i - 1] 與 word2[j - 1]相同：（2）當(dāng)word1[i - 1] 與
2024年02月02日
瀏覽(27)
代碼隨想錄打卡第56天|583. 兩個字符串的刪除操作；72. 編輯距離
583. 兩個字符串的刪除操作關(guān)鍵點(diǎn)1：dp數(shù)組的含義 dp[i][j],使得以i-1為結(jié)尾word1 和以j-1為結(jié)尾的word2 相同所需的最小步數(shù)；關(guān)鍵點(diǎn)2：遞歸公式的推導(dǎo) if(nums1[i-1] == nums2[j-1])，則i和j同時(shí)移動，所以為i-1,j-1；dp[i][j] = dp[i-1][j-1];由于不需要進(jìn)行刪除操作，所以不需要加1 如果不相
2023年04月19日
瀏覽(34)
【代碼隨想錄 | Leetcode | 第十一天】字符串 | 反轉(zhuǎn)字符串 | 反轉(zhuǎn)字符串 II | 替換空格 | 反轉(zhuǎn)字符串中的單詞 | 左旋轉(zhuǎn)字符串
歡迎來到小K的Leetcode|代碼隨想錄|專題化專欄，今天將為大家?guī)碜址畘反轉(zhuǎn)字符串 | 反轉(zhuǎn)字符串 II | 替換空格 | 反轉(zhuǎn)字符串中的單詞 | 左旋轉(zhuǎn)字符串的分享 ? ?題目鏈接點(diǎn)這里編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 s 的形式給出。不要
2024年02月15日
瀏覽(54)
代碼隨想錄復(fù)習(xí) 151反轉(zhuǎn)字符串中的單詞242 有效的字母異位詞 0-1背包問題
代碼如下? func?reverseWords(s?string)?string?{ ?????????b?:=?[]byte(s)? ? ?????????slowindex,fastindex?:=?0,0? //設(shè)置兩個指著，快慢指針 ?????????for?len(b)??0??fastindex??len(b)??b[fastindex]?==?\\\'?\\\'{ ?????????????fastindex++? ? //這里是取出開頭的空格，邏輯是如果當(dāng)
2024年02月04日
瀏覽(19)
第8天-代碼隨想錄刷題訓(xùn)練-字符串● 344.反轉(zhuǎn)字符串 ● 541. 反轉(zhuǎn)字符串II ● 劍指Offer 05.替換空格 ● 151.翻轉(zhuǎn)字符串里的單詞 ● 劍指Offer58-II.左旋轉(zhuǎn)字符串
LeetCode鏈接編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 s 的形式給出。不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。 swap常見的兩種交換形式常見的值交換通過位運(yùn)算 LeetCode鏈接給定一個
2024年02月04日
瀏覽(23)
代碼隨想錄復(fù)習(xí) 1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng) 150 逆波蘭表達(dá)式求值 239 滑動窗口最大值
1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng) 代碼如下? func?removeDuplicates(s?string)?string?{ ????????????var??stack?[]byte? ?//結(jié)果棧數(shù)組 ????????????for?i?:=?0?;?i??len(s)?;?i++?{ ????????????????if?len(stack)??0??stack[len(stack)-1]?==?s[i]?{? //如果當(dāng)前遍歷到的元素
2024年02月05日
瀏覽(26)
代碼隨想錄第十一天 | ??????LeetCode 20. 有效的括號、??????LeetCode 1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng)、??????LeetCode 150. 逆波蘭表達(dá)式求
目錄 ??????LeetCode 20.?有效的括號文章講解：代碼隨想錄(programmercarl.com) 視頻講解：棧的拿手好戲！| LeetCode：20. 有效的括號_嗶哩嗶哩_bilibili 思路 ??????LeetCode 1047.?刪除字符串中的所有相鄰重復(fù)項(xiàng) 文章講解：代碼隨想錄(programmercarl.com) 視頻講解：棧的好戲還
2024年02月22日
瀏覽(36)
代碼隨想錄Day9 棧與隊(duì)列 LeetCodeT20 有效的括號 T1047 刪除字符串中所有相鄰重復(fù)項(xiàng) T150 逆波蘭表達(dá)式求值
題目詳細(xì)思路和解法來自于:代碼隨想錄 (programmercarl.com) 這道題分為三種情況 1.左括號多了? ? ? ? ?([{}]() 2.括號不匹配? ? ? ? ?[{(]}] 3.右括號多了? ? ? ? ?[]{}()))) 處理思路:我們在遇到左括號的時(shí)候,直接入棧其對應(yīng)的右括號即可,然后在遇到右括號的時(shí)候直接與棧頂元素比
2024年02月06日
瀏覽(780)

<var id="pum4i"><dfn id="pum4i"></dfn></var>