剑指offer(2)——字符串（共9道题目）

参考资料：

剑指offer题目汇总

字符串（共9道题目）：

模板：

　　题目描述：

　　解题思路：

　　注意问题：

　　补充知识点：

---

2、替换空格（08.31）

27、字符串的排列（09.01）

34、第一个只出现一次的字符（09.02）

43、左旋转字符串（09.03）

44、反转单词序列（09.04）

49、把字符串转换成整数（09.05）（多种情况讨论，重点在于对目标的分析和归纳）

52、正则表达式匹配（09.06）（多种情况讨论，重点在于对目标的分析和归纳）

53、表示数值的字符串（09.07）（多种情况讨论，重点在于对目标的分析和归纳）

54、字符流中第一个不重复的字符（09.08）

---

2、替换空格

　　题目描述：
  请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

　　解题思路：把从前往后一次遍历处理的方法（时间复杂度：O(n^2)）转化为两次遍历处理（第一次：统计空格数量，确定替换之后的总长度，第二次：从后往前设立两个指针处理，每次时间复杂度均为：O(n)）;

　　注意问题：

　　1.for (i=0;i<2*j;i++) str.append(" ");要先把不足的空间用append方法开辟出来，否则会报错。具体原因请参考StringBuffer类的charAt函数的写法，其中变量count的定义为：public synchronized int length() {return count;},即length方法的返回值；

public synchronized char charAt(int index) {
    if ((index < 0) || (index >= count))
        throw new StringIndexOutOfBoundsException(index);
    return value[index];
}

　　2.比较当前位置的字符是否是空格的时候，不能用str.charAt(k)==" "。因为charAt方法的返回值是char类型，而" "是字符串类型。Java的字符类型必须是单引号，字符串类型必须是严格的双引号（与python不同之处）；所以可以采取使用单引号（str.charAt(k)==' '）和定义一个字符类型变量（char c=' '）两种方法；

　　2.题目中要求的返回类型是String，所以需要调用toString方法，把StringBuffer类数据类型转化为String类型（String类型也是类类型的数据类型）；

　　补充知识点：java字符串

#python

//java
public class Solution {
    public String replaceSpace(StringBuffer str) {
        int len=str.length();
        int i;
        int j=0;
        for (i=0;i<len;i++)
            if (str.charAt(i)==' ')
               j++;
        int k=len-1;
        int l=len+2*j-1;
        for (i=0;i<2*j;i++)
            str.append(" ");//没有这一步会报错
        while (k>=0)
        {
            if (str.charAt(k)==' ')
            {
                k--;
                str.replace(l-2,l+1,"%20");
                l=l-3;
            }
            else
            {
                str.setCharAt(l,str.charAt(k));
                k--;
                l--;
            }
        }
        return str.toString();//必须转化为String类型，否则会报错。
    }
}

27、字符串的排列

　　题目描述：

  输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

　　解题思路：由于字符长度不确定，所以不能通过设置多重循环来穷举。这是典型的递归例题。

——字符串（共9道题目）/1.png)

　　注意问题：

　　1.加入链表之前需要判断是否有重复元素if (!res.contains(String.valueOf(a)))，因为测试用例里面有重复字符，如："aa"；

　　2.全部加入链表之后要对链表中的字符串按字典序排序；关于java的排序方法详见：java的排序方法；

　　3.字符数组转化为字符串：String s=String.valueOf(a) / String s=new String(a)；字符串转化为字符数组：char []a=str.toCharArray(); ；

　　补充知识点：

#python

//java
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;//不加会报错
public class Solution {
    ArrayList <String> res =new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        if (str==null || str.length()==0)
            return res;
        char []a=str.toCharArray();
        Arrays.sort(a);//字符数组排序
        Permutation(a,0);
        Collections.sort(res);//链表排序
        return res;
    }
    public void Permutation(char []a,int begin)
    {
        int i;
        if (begin==a.length-1)
        {
            if (!res.contains(String.valueOf(a)))
                res.add(String.valueOf(a));
        }
        else
        {
            for (i=begin;i<a.length;i++)
            {
                swap(a,i,begin);
                Permutation(a,begin+1);
                swap(a,i,begin);//交换完之后一定要再交换回来，否则会影响后续的排序
            }
        }
    }
    public void swap(char []a,int i,int begin)
    {
        char t;
        t=a[i];
        a[i]=a[begin];
        a[begin]=t;
    }
}

34、第一个只出现一次的字符

　　题目描述：

  在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。

　　解题思路：桶排序；

　　注意问题：

　　1.A-Z对应的ASCII码为65-90，a-z对应的ASCII码值为97-122；

　　2.java 获取字符串指定下标位置的值的方法：public char charAt(int index)；

　　3.关于字符类型和ASCII表（java实际上是Unicode表）的使用：(int)'a'：观察字符 ‘a’ 的ASCII值（在表中的位置），(char)97：在表97的位置对应的字符。但本题中a[str.charAt(i)-'A']++;也可以（我认为应该是：a[(int)str.charAt(i)-'A']++;，感觉可以理解为：'a'-'A'和97-65的结果都是：32，如果把'a'-'A'换成char c='a'; c-'A'结果是等价的）；

　　4.最后统计数组a中为1的项时，是依次拿这字符串中的每一个字符，判断其在数组中对应位置的值是否为1，这样可以保证如果值为1，则必定是第一个只出现一次的字符。如果遍历数组，找到第一个为1的项目，再去找其对应的字符和该字符对应的位置，则不能保证必定是第一个只出现一次的字符。此处是个易错点。

　　补充知识点：java字符类型和Unicode表的转换、字母对应的Unicode值；

//java
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if (str==null || str.length()==0)
            return -1;
        int []a=new int[122-65+1];
        int i;
        int t=-1;
        for (i=0;i<str.length();i++)
            a[str.charAt(i)-'A']++;
        for (i=0;i<str.length();i++)//此处决定能否找到第一个只出现一次的字符
            if (a[str.charAt(i)-'A']==1)
                return i;
        return -1;
    }
}

43、左旋转字符串

　　题目描述：

  汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

　　解题思路：三次反转算法（妙哉！）

　　注意问题：

　　1.在对c[n，str.length()-1]进行反转时，极易出错；

　　2.数组反转方法：for（i=begin；i<=(end-begin)/2；i++）（i可以取到end）；

　　3.注意数组的length是属性后面没有括号，字符串的length（）是方法，后面有括号；

　　4.注意对字符串为空和长度为零的判断和对n为0和str.length()两种极端情况的判断。因为这四个判断，多提交了三次；

　　补充知识点：

//java
public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str==null || str.length()==0)
            return "";
        if(n==0 || n==str.length())
            return str;
        int i;
        char []c=str.toCharArray();
        char t;
        for (i=0;i<=(n-1)/2;i++)
        {
            t=c[i];
            c[i]=c[n-1-i];
            c[n-1-i]=t;
        }
        for (i=n;i<=(str.length()-1-n)/2+n;i++)//极易出错
        {
            t=c[i];
            c[i]=c[str.length()-1-i+n];
            c[str.length()-1-i+n]=t;
        }
        for (i=0;i<=(str.length()-1)/2;i++)
        {
            t=c[i];
            c[i]=c[str.length()-1-i];
            c[str.length()-1-i]=t;
        }
        return String.valueOf(c);
    }
}

44、反转单词序列

　　题目描述：

  牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

　　解题思路：

  第一步：反转整个序列中所有的字符，这时会发现不但反转了单词的顺序，单词中的字母顺序也被反转，因此需要第二步的调整。

  第二步：以空格为分隔，依次反转每个单词，即让每个单词会到原来的正常顺序。

　　注意问题：

　　1.反转函数：数列思想；

for(i=begin;i<=(end-begin)/2+begin;i++)//写成：i<=(end+begin)/2完全可行。因为i的最后位置为end和begin的等差中项
{
    t=array[i];
    array[i]=array[end+begin-i];//根据等差数列：end+begin==i+x，此处x代表和array[i]进行交换的数组元素
    array[end+begin-i]=t;
}

　　2.String str=null与String str=“”的区别：String str1= null; str1引用为空，String str2= “”; str2引用一个空字符串。即：””分配了内存；null没有分配内存，因此str1还不是一个实例化的对象，而str2已经实例化；

　　3.注意考虑特殊情况：输入的字符串只包含多了空格：if (strArr[i]==' ' && strArr[i+1]!=' ')；

　　补充知识点：

//java
public class Solution {
    public String ReverseSentence(String str) {
        if (str==null)//1注意
            return null;
        if(str.length()==0)//2注意：注意区分1和2的区别
            return "";
        int i;
        int j;
        char []strArr=str.toCharArray();
        char t;
        for (i=0;i<=(str.length()-1)/2;i++)
        {
            t=strArr[i];
            strArr[i]=strArr[str.length()-1-i];
            strArr[str.length()-1-i]=t;
        }
        int begin=0;
        for (i=0;i<str.length()-1;i++)
        {
            if (strArr[i]==' ' && strArr[i+1]!=' ')
            {
                for (j=begin;j<=(i-1-begin)/2+begin;j++)
                {
                    t=strArr[j];
                    strArr[j]=strArr[i-1-j+begin];
                    strArr[i-1-j+begin]=t;
                }
                begin=i+1;
            }
        }
        for (j=begin;j<=(str.length()-1-begin)/2+begin;j++)
        {
            t=strArr[j];
            strArr[j]=strArr[str.length()-1+begin-j];//等差数列的思想
            strArr[str.length()-1+begin-j]=t;
        }
        return String.valueOf(strArr);
    }
}

49、把字符串转换成整数

　　题目描述：

  将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

　　解题思路：第一位情况较多，所以第一位要分多种情况讨论（+、-、数字、其他），第2—str.length()-1位只有两种情况（是数字，不是数字），所以先讨论第2—str.length()-1位，再讨论第一位。当第一位为+、-、数字，后面全为数字时，他们的核心问题是一样的：把一串数字字符串转化为整数。而解决该问题的关键在于找到第一位非零数字。

　　注意问题：

　　1.if (str==null || str.length()==0)，该问题已强调多次；

　　2.public String substring(int startpoint)获得当前字符串的子串，该字串是从当前字符串的startpoint处截取到最后所得到的字符串；

　　3.找第一位非零数字时，用了设标志位的方法，比较巧妙，属于自创；

　　4.(int)str.charAt(i)-48;数字字符转数字，因为 ‘0’ 对应的ASCII值是48；’

　　补充知识点：String类的常用方法

　　备注：通过这道题我就感觉，没什么问题是我想不明白的。

//java
public class Solution {
    public int StrToInt(String str) {
        int i;
        int sum;
        if (str==null || str.length()==0)
            return 0;
        for (i=1;i<str.length();i++)
            if (str.charAt(i)<'0' || str.charAt(i)>'9')
                return 0;
        if (str.charAt(0)=='+')
            return fun(str.substring(1));
        if (str.charAt(0)=='-')
            return -1*fun(str.substring(1));
        if (str.charAt(0)>='0' && str.charAt(0)<='9' )
            return fun(str);
        return 0;
    }
    public int fun(String str)
    {
        int i=0;
        int len=str.length();
        int sum=0;
        int f=0;
        for (i=0;i<len;i++)
        {
            if (str.charAt(i)!='0')//找第一个非0数字，比较巧妙。
                f=1;
            if (f==1)
            {
                sum*=10;
                sum+=(int)str.charAt(i)-48;//数字字符转数字
            }

        }
        return sum;
    }
}

52、正则表达式匹配

　　题目描述：

  请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a“和”ab*ac*a“匹配，但是与”aa.a“和”ab*a“均不匹配。

　　解题思路：核心在于分类和各种情况的讨论。对于分类找到找到了一条清晰的主线：同时结束，都未结束，一个结束；对于都未结束的情况又需要分成多种情况（3种以上），这种分法虽然大体上清晰，但情况太多，容易漏掉，建议采用参考资料上的方法。（标准代码：把所有false的情况列出来）

　　注意问题：

　　1.涉及到i+1或j+1时，必须先判断是否超出界限；

　　2.最后一个return false;确实起作用，具体见代码注释；

　　补充知识点：

//java
public class Solution {
    public boolean match(char[] str, char[] pattern){
        /*
        思路：比较前两个字符，递归比较
        */
        if(str==null || pattern==null)
            return false;
        return match(str,0,pattern,0);
    }
    public boolean match(char[] str,int i,char[] pattern,int j){
        if(i==str.length && j==pattern.length)//都为空
            return true;
        if(i<str.length && j==pattern.length)//模式串为空
            return false;
        if (i==str.length && j<pattern.length)//匹配串为空
            if (j+1 == pattern.length-1 && pattern[j+1]=='*')//匹配串为空，模式串不为空时，也可能匹配得上：'.','*'
                return true;
            else 
                return false;
        if (i<str.length && j<pattern.length)//都不空分两种情况（这两种情况考虑并不完整）
        {
            if (i==str.length-1 && j==pattern.length-1)//1.当匹配串和模式串都进行到最后一个字符时的情况要单独列出，因为情况二要求匹配串至少剩余一个字符。
                if(str[i]==pattern[j] || pattern[j]=='.')
                    return match(str,i+1,pattern,j+1);
            if(i<str.length && j+1<pattern.length)//2.模式串至少剩余一个字符，因为要考虑'*'的情况。
            {
                if(pattern[j+1]=='*'){ //第二个字符是*
                    if(str[i]==pattern[j] || pattern[j]=='.' ) //第一个字符相等，有三种情况
                        return match(str,i,pattern,j+2) || match(str,i+1,pattern,j+2) || match(str,i+1,pattern,j);
                        //分别代表匹配0个，1个和多个：匹配串为：'a'，模式串为：'a*a'/'a*b'/分别表示匹配0个或一个。匹配串为：'aa',模式串为:'a*b'表示匹配多个。
                    else //第一个字符不等
                        return match(str,i,pattern,j+2);//只能匹配0个。
                }
                else{     //第二个字符不是*
                    if(str[i]==pattern[j] || pattern[j]=='.')
                        return match(str,i+1,pattern,j+1);
                    else
                        return false;
                }
            }
        }

        return false;//本以为上述四个if已经把所有的情况列出来了，该return只是为了不报错。改成：return true;也没问题，事实证明，还有未考虑到的情况：匹配串为：'aa'，模式串为：'.';此时就会走最后一个return
    }
}

53、表示数值的字符串

　　题目描述：

  请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”, “5e2”, “-123”,” 3.1416” 和 “-1E-16” 都表示数值。 但是 “12e”, “1a3.14”, “1.2.3”, “+-5” 和 “12e+4.3” 都不是。

　　解题思路：主要还是对各种情况的分类讨论。把所有的false的情况都单列出来，最后留下的情况就是true。所以最后一句是return true；对数字特征的分析和归纳是关键。

　　注意问题：

　　补充知识点：

//java
public class Solution {
    /*
        思路：表示数字的字符串遵循模式：A[.[B]][e|EC]或者.B[e|EC]
        A为整数部分，B为小数部分，C为指数部分
        开头可能有正负号
        两种方法：逐位判断、正则表达式
     */
    public boolean isNumeric(char[] str) {
        //方法一：逐位判断，把所有的false情况列出来。
        if(str==null)
            return false;
        boolean sign=false,decimal=false,hasE=false; //标记符号、小数点、指数符号E是否出现过
        for(int i=0;i<str.length;i++){
            if(str[i]=='e'||str[i]=='E'){ //有E或者e出现
                if(i==str.length-1) //E不能是最后一位，后面必须跟指数
                    return false;
                if(hasE) return false; //E只能出现一次
                hasE=true;
            }else if(str[i]=='.'){
                if(hasE||decimal) //指数不能有（hasE表示i之前已经出现过E了，如果str[i]=='.'，那这个点必定是在指数位置。并且：小数点只能出现一次，所以有两个条件。 
                    return false;
                decimal=true;
            }else if(str[i]=='+'||str[i]=='-'){
                //第一次出现，开头或者e之后，!sign表示第一次出现
                if(!sign && i!=0 && str[i-1]!='e' && str[i-1]!='E') //不在开头也不在e之后
                    return false;
                //第二次出现，E之后
                if(sign && str[i-1]!='E' && str[i-1]!='e')
                    return false;
                sign=true;
            }else if(str[i]>'9'||str[i]<'0') //不合法字符
                return false;
        }
        return true;
    }
    
    //方法二：正则表达式
    //+代表出现一次或多次，*代表出现0次或多次，？代表出现0次或者一次
     public boolean isNumeric(char[] str) {
        String string = String.valueOf(str);
        return string.matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
         /*
         为什么是两个反斜杠
         首先字符串中的\\被编译器解释为\ -------》  第一步，编译器将字符串转变为“正则表达式”
		然后作为正则表达式，\.又被正则表达式引擎解释为.   ----------------> 第二步，才开始把第一步的结果当做是正则表达式，开始进行匹配！
		如果在字符串里只写\.的话，第一步就被直接解释为.，之后作为正则表达式被解释时就变成匹配任意字符了
         */
    }
}

54、字符流中第一个不重复的字符

　　题目描述：

  请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

　　解题思路：

　　注意问题：

　　补充知识点：

//java