java 程序员面试金典 6（字符串）

1. 请编写一个方法，将字符串中的空格全部替换为“%20”。假定该字符串有足够的空间存放新增的字符，并且知道字符串的真实长度(小于等于1000)，同时保证字符串由大小写的英文字母组成。

给定一个string iniString 为原始的串，以及串的长度 int len, 返回替换后的string。

//我的想法  
import java.util.*;
public class Replacement{
    public String repalceSpace(String iniString,int length){
         String str2="";
         for(int i=0;i<length;i++){
             if(iniString.charAt(i)==' '){   //之前编译出错，空格的表示是'  ',而不是''。
                  str2=str2+"%20";
             }else{
                  str2=str2+iniString.charAt(i);   //这块应该是有类型自动提升的，char-->string
             }
         }
         return  str2;
      }
}

//最简便的方法：利用String自带的replaceAll方法
import java.util.*;
public class Replacement{
    public String repalceSpace(String iniString,int length){
return iniString.replaceAll(" ","%20");
 }
}

//借助于StringBuffer
import java.util.*;
public class Replacement{
    public String repalceSpace(String iniString,int length){
        if(iniString==null || length<=0)
            return iniString;
        StringBuffer sb=new StringBuffer();
        for(int i=0; i<length;i++){
           char c=iniString.charAt(i);
           if(c==' ')
              sb.append("%20");
           else
              sb.append(c);
        }
        return sb.toString(); // StringBuffer--->String
   }
}

//剑指offer的解法 
//如果不允许额外开辟空间，如果采取每遇到一个空格就把空格后的字符往后挪，算法复杂度无疑太高。
//剑指offer中提供的思路是先计算出字符串的总长度，遍历一遍得到空格数，得到替换后的字符串长度，
//然后用两个指针分别指向原始字符串的末尾位置和目标字符串的末尾位置（同在这个字符数组中），
//由后往前进行复制和替换。这样做的好处是所有字符都只复制一次。算法复杂度为O(n)。
import java.util.*;
public class Replacement{
    public String repalceSpace(String iniString,int length){
         char[] charArr=iniString.toCharArray();
         int originalLength=charArr.length; 
         int numberOfBlank=0; //计算空格的数量
         for(char item:charArr)
             if(item==' ')
                numberOfBlank++;
         int newLength=originalLength+numberOfBlank*2; //计算新的字符串长度
         char [] newCharArr=new char[newLength];
         int indexOfOriginal=originalLength-1;
         int indexOfNeew =newLength-1;
         while(indexOfOriginal>=0){
            if(charArr[ indexOfOriginal]==' '){
                newcharArr[indexOfNew--]='0';
                newcharArr[indexOfNew--]='2';
                newcharArr[indexOfNew--]='%';
                indexOfOriginal--;
            }else{
                newcharArr[indexOfNew--]=charArr[indexOfOriginal--];
            } 
        }
        return String.valueOf(newcharArr);
     }
}

2 利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。给定一个string iniString为待压缩的串(长度小于等于10000)，保证串内字符均由大小写英文字母组成，返回一个string，为所求的压缩后或未变化的串。

//我的有部分实例没有通过  是错误方法！！
import java.util.*;
public class Zipper{
   public String  zipString(String iniString){
       StringBuffer sb=new StringBuffer();
       int i=0;
       while(i<iniString.length()){
           char tmp=iniString.charAt(i);
           int num=1;
           while(tmp==iniString.charAt(++i){
               num++;
           }
           sb.append(tmp).append(num);
       }
       if(sb.length()>=iniString.length())
           return iniString;
       return sb.toString();
    }
}

//正确的方法：
import java.util.*;
public class Zipper{
   public String  zipString(String iniString){
       StringBuffer sb=new StringBuffer();
       int k=1;
       for(int i=0; i<iniString.length()-1;i++){
          if(iniString.charAt(i)==iniString.charAt(i+1))
              k++;
          else{
              sb.append(iniString.charAt(i));
              sb.append(k);
              k=1;
          }
        }
       sb.append(iniString.charAt(iniString.length()-1));
       sb.append(k);
       if(sb.length()>=iniString.length())
          return iniString;
       return sb.toString();
     }
}