Problem 4：替換空格（字符串）

wenyiweb 發(fā)布于2019-08-16 15:04 / 3438人閱讀

摘要：注用替換的原因，空格在碼中的序號為，用十六進制表示為。在第一個空格處，空格替換為，空格之后的字符全部右移三個位置。同理，第一次移動后，向后遍歷，在第二個空格處繼續(xù)將后邊字符移動。因此后者應舍去，否則會不通過牛客測試。

一、題目描述

請實現(xiàn)一個函數(shù)，將一個字符串中的每個空格替換成“%20”。例如，當字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
注：用%20替換的原因，空格在ASCII碼中的序號為32，用十六進制表示為0x20。

二、思路分析

參考劍指offer上的說明，需要考慮操作是原地（in place）操作還是新建字符串操作。以原地操作為例，首先考慮最直觀的方法-從前往后依次替換。在第一個空格處，空格替換為%20，空格之后的字符全部右移三個位置。同理，第一次移動后，向后遍歷，在第二個空格處繼續(xù)將后邊字符移動。

從算法角度分析，設輸入規(guī)模為n，我們需要循環(huán)遍歷字符串中空格（循環(huán)中，判斷是否為空的操作執(zhí)行n次），在每個空格處，進行字符移動操作，每個字符的移動又相當于一次循環(huán)。因此，總的運行效率為

$$ O（n^2） $$

直接遍歷移動的方法效率太低，因此，考慮其他方法。
方法1：
考慮比Sting高效的字符串操作工具-StringBuffer，同樣使用之前的直接遍歷的方法，但是對比發(fā)現(xiàn)，不需要重復移動，每次判斷執(zhí)行一次操作，共執(zhí)行n此判斷，效率為O(n)
方法2：
不使用StringBuffer，參考劍指offer書上的方法，在原字符串上進行操作，利用兩條指針進行數(shù)據(jù)移動的思路，具體見方法2代碼。（注意倒序復制提高效率的思路）

三、Java實現(xiàn)

方法1源程序：

package jz_offer;

public class problem04 {
    public static String spaceReplace(String str) {
        StringBuffer newStr=new StringBuffer();
        int length=str.length();
        //特殊情況，
        if(str==null)
            return null;
        
        for(int i=0;i
（2019/2/17 增加）注：特殊情況下原條件為str==null||length==0，后者為空字符串，輸出應仍為空字符。因此后者應舍去，否則OJ會不通過（牛客測試）。
方法2部分程序：
//2、使用臨時字符數(shù)組
public static String spaceReplace2(String str) {
    int length=str.length();    
    int spaceCount=0;
    for(int i=0;i=0;i--) {
        if(str.charAt(i)==" ") {
            newStrArray[j]="0";
            newStrArray[j-1]="2";
            newStrArray[j-2]="%";
            j=j-3;
        }                
        else {
            newStrArray[j]=str.charAt(i);
            j--;
        }
    }
    return new String(newStrArray);
            
}

GPU云服務器云服務器 php替換多個空格 js用空格替換- js如何替換空格符刪除字符串空格

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/73257.html

JavaScript 編程精解中文第三版九、正則表達式

摘要：使用構造器時，需要將模式書寫成普通的字符串，因此反斜杠的使用規(guī)則與往常相同。構造器的后四個參數(shù)小時分鐘秒毫秒是可選的，如果用戶沒有指定這些參數(shù)，則參數(shù)的值默認為。來源：ApacheCN『JavaScript 編程精解中文第三版』翻譯項目原文：Regular Expressions 譯者：飛龍協(xié)議：CC BY-NC-SA 4.0 自豪地采用谷歌翻譯部分參考了《JavaScript...

Pluser 2019-08-23 18:18 評論0 收藏0
【劍指offer】2.替換空格

摘要：例如，當字符串為則經(jīng)過替換之后的字符串為。題目說的不太嚴謹能不能允許連續(xù)出現(xiàn)多個空格若有可能連續(xù)多個空格，用多個還是單個進行替換分三種情況解答不會出現(xiàn)連續(xù)多個空格直接用空格將字符串切割成數(shù)組，在用進行連接。題目描述請實現(xiàn)一個函數(shù)，將一個字符串中的每個空格替換成%20。例如，當字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。題目說的不太嚴...

Leo_chen 2019-08-23 14:34 評論0 收藏0
ES6 系列之模板字符串

摘要：最終的代碼如下第二版假設有這樣一段為了保持可讀性，我希望最終輸入的樣式為其實就是匹配每行前面的空格，然后將其替換為空字符串。基礎用法 let message = `Hello World`; console.log(message); 如果你碰巧要在字符串中使用反撇號，你可以使用反斜杠轉(zhuǎn)義： let message = `Hello ` World`; console.log(mes...

Travis 2019-08-26 11:55 評論0 收藏0