剑指offer刷题总结(三)字符串

发表于 | Edited on | 分类于 | Comments： | Views： ℃

1. 第一个只出现一次的字符

题目描述：

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

代码实现：

/**
 * @ClassName problem1
 * @Description TODO  第一个只出现一次的字符
 * @Author niran
 * @Date 2019/8/3 8:28
 * Version 1.0
 **/
public class problem1 {

    public static void main(String [] args){
        FirstNotRepeatingChar2("google");
    }

    /**
     * HashMap实现
     * @param str
     * @return
     */
    public int FirstNotRepeatingChar(String str) {
        Map<Character,Integer> hashmap=new HashMap<>();
        for(int i=0;i<str.length();i++){
            if(hashmap.containsKey(str.charAt(i))){
                hashmap.put(str.charAt(i),hashmap.get(str.charAt(i)));
            }else{
                hashmap.put(str.charAt(i),1);
            }
        }
        for(int i=0;i<str.length();i++){
            if(hashmap.get(str.charAt(i))==1)
                return i;
        }
        return -1;
    }


    /**
     * 双重循环实现
     * @param str
     * @return
     */
    public static int FirstNotRepeatingChar2(String str) {
        for(int i=0;i<str.length();i++){
            int j=0;
            for(j=0;j<str.length();j++){
                if(str.charAt(i)==str.charAt(j)&&i!=j){
                    break;
                }
            }
            if(j==str.length()-1)
                return i;
        }
        return -1;
    }
}

2. 字符流中第一个不重复的字符

题目描述:

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

代码实现：
解法一：

/**
 * @ClassName problem2
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 9:12
 * Version 1.0
 **/
public class problem2 {

    private List<Character> list=new ArrayList<>();
    private HashMap<Character,Integer> hashMap=new HashMap<>();
    //Insert one char from stringstream

    /**
     * 用list保存获取的字符，用hashmap记录自负出现的次数
     * @param ch
     */
    public void Insert(char ch)
    {
        if(hashMap.containsKey(ch)){
            hashMap.put(ch,hashMap.get(ch)+1);
        }else{
            hashMap.put(ch,1);
        }
        list.add(ch);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(char ch:list){
            if(hashMap.get(ch)==1)
                return ch;
        }
        return '#';
    }
}

解法二：

/**
 * @ClassName problem2
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 9:12
 * Version 1.0
 **/
public class problem2 {
    char [] chars = new char[256];//ascii字符共128，其他字符非中文认为256个，
    //为每个字符预留空间。默认每个存的ascii值为0 
    StringBuffer sb = new StringBuffer();//记录当前的所有字符
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        sb.append(ch);
        chars[ch]++;//如果字符是1，那么就是在字符1对应的下标的地方
        //也就是49的下标处，ascii加1.此时如果输出chars[ch],里面存ascii值
        //为1，所以是一个不可显示的字符。
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        char [] str = sb.toString().toCharArray();
        for(char c:str) {
            if(chars[c] == 1)//判断这个字符数组中在这个字符下标处值是否为1.
                return c;
        }
        return '#';
    }
}

3. 翻转字符串

题目描述:

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

代码实现：

/**
 * @ClassName problem3
 * @Description TODO 单词反转
 * @Author niran
 * @Date 2019/8/3 9:39
 * Version 1.0
 **/
public class problem3 {

    public String ReverseSentence(String str) {
        if (str == null || str.trim().length() == 0) {
            return str;
        }
        String[] arr=str.split(" ");
        String result="";
        for(String string:arr){
            result=" "+string+result;
        }
        result=result.trim();
        return result;
    }
}

4. 左旋转字符串

题目描述：

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

思路：
（1）先将左边 K个字符串进行翻转：abcXYZdef –> cbaXYZdef 原来—->–>
（2）再将右边剩余字符串进行翻转：cbaXYZdef –> cbafedZYX 将—->–>变成<—-<–
（3）最后将整个字符串进行翻转： cbafedZYX –> XYZdefabc 变成–>—->
代码实现：

package Str;

/**
 * @ClassName problem4
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 10:12
 * Version 1.0
 **/
public class problem4 {

    public static void main(String[] args){
        System.out.println(LeftRotateString("123456",2));
    }
    public static String LeftRotateString(String str,int n) {
        if(n>str.length())
            return "";
        //分别翻转前n个字符和剩下的字符
        str=reverse(str.substring(0,n))+reverse(str.substring(n,str.length()));
        //翻转整个字符串
        str=reverse(str);
        return str;

    }

    /**
     * 翻转字符串
     * @param str
     * @return
     */
    private static String reverse(String str){
        StringBuffer stringBuffer=new StringBuffer();
        for(int i=str.length()-1;i>=0;i--){
            stringBuffer.append(str.charAt(i));
        }
        return String.valueOf(stringBuffer);
    }
}

5. 把字符串转换为整数

题目描述:

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

输入描述:

输入一个字符串,包括数字字母符号,可以为空

输出描述:

如果是合法的数值表达则返回该数字，否则返回0

示例

输入
+2147483647
输出
2147483647
输入
1a33
输出
0

代码实现：

package Str;

/**
 * @ClassName problem5
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 10:45
 * Version 1.0
 **/
public class problem5 {

    public static void main(String[] args){
        int a=1+'1';
        System.out.println(1+'1');
    }
    public int StrToInt(String str) {
        if(str.equals(""))
            return 0;
        int negtive=1;//标志是否为负数
        int start=0;  //标志循环开始位置
        int result=0;
        if(str.charAt(start)=='-') { 
            negtive=-1;
            start++;
        }else if(str.charAt(start)=='+'){
            start++;
        }

        for(;start<str.length();start++){
            if(str.charAt(start)<48||str.charAt(start)>57){
                return 0;
            }
            result=result*10+str.charAt(start)-48;
        }
        return result*negtive;
    }
}
-------------本文结束感谢您的阅读-------------