我的面试准备过程---字符串相关(更新中)

摘要：字符串简介内置类型，不可理性，要更改的话考虑转，之类对来说，一个的范围，位面试题总体分析和数组相关，内容广泛概念理解字典序，哪个排在字典前面，哪个字典序就小简单操作插入删除字符，旋转规则判断罗马数字转换，是否是合法的整数浮点数数字运算套数加

String 内置类型，不可理性，要更改的话考虑转StringBuffer,StringBuilder，char[]之类

对java来说，一个char的范围 [0,65535]，16位

和数组相关，内容广泛

概念理解：字典序，哪个排在字典前面，哪个字典序就小

简单操作： 插入、删除字符，旋转

规则判断 罗马数字转换，是否是合法的整数、浮点数

数字运算（套数加法、二进制加法）

排序、交换（partition过程）

字符计数(hash)： 变位词

匹配(正则表达式、全串匹配、KMP、周期判断)

动态规划(LCS、编辑距离、最长回文子串)

搜索(单词变换、排列组合)

思路：快排partition 最左边0和最右边的1都可以不管

    public int exchangeTimes(String s){
        int answer = 0;
        for(int i = 0, j = s.length() - 1; i < j; i++, j--){
            for(; i < j && s.charAt(i) == "0"; i++);
            for(; i < j && s.charAt(j) == "1"; j--);
            if(i < j) answer++;
        }
        return answer;
    }

    public void solve(char[] chars){
        //先删除a,可以利用原来字符串的空间,过程类似插入排序
        int n = 0;//删除a后的字符数组长度
        int bCount = 0;
        for(int i = 0; s[i] != ""; i++){
            if(chars[i] == "a"){
                chars[n++] = chars[i];
            }
            if(chars[i] == "b"){
                bCount++;
            }
        }
        //从后往前复制
        //步骤1. 遍历计算新串长度,b出现的次数2. 从后往前遍历 3.旧串复制,如果遇到b,复制两遍
        int newLength = n + bCount;
        chars[newLength] = "";
      for(int i = n, j = newLength - 1; i >= 0; i--){
            chars[j--] = chars[i];
            if(chars[i] == "b"){
                chars[j--] = "b"; 
        }
    }

    public void replaceSpace(char[] chars){
        int length = 0;
        int spaceCount = 0;
        for(int i = 0; chars[i] != ""; i++){
            length++;
            if(chars[i] == " "){
                spaceCount++;
            }
        }

        int newLength = length + 2 * spaceCount;
        chars[newLength] = "";
        for(int i = newLength - 1, j = length; j >= 0; j--){
            if(chars[j] == " "){
                char[i] = "0";
                char[--i] = "2";
                char[--i] = "%"; 
            }else{
                char[i--] = char[j];
            }
        }
    }

方法1 快排partition,因为过程不稳定,所以数字相对顺序会变化

    public void sortStar(char[] chars){
        for(int i = 0 , j = 0; j < a.length; j++){
            if(chars[i] == "*"){
                swap(a[i++], a[j])
            }
        }
    }

    private void swap(char[] chars, int i, int j){
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

方法2 倒着处理

     public void sortStar(char[] chars){
        int length = chars.length;
        int i = length - 1;
        for(int j = length - 1; j >= 0; j--){
            if(chars[j] != "*"){
                chars[i--] = chars[j];
            }
        }
        while(i >= 0){
            chars[i--] = "*";
        }
    }

注意:以上两种解法的异同,方法1,用到交换和快排partition思想,但是无法保证数字的顺序;方法2,使用倒着向前处理的思想,如果必须用交换,只能采用方法1

翻转句子中全部的单词，单词内容不变，例如I"m a student. 变为student. a I"m
思路：in-place翻转 字符串第i位到第j位

    while(i < j) swap(s[i++], s[j--]);

1. 翻转整个句子：.tneduts a m"I
2. 每个单词多带带翻转: students. a I"m

这段代码写得非常丑陋

    public void revertStr(char[] chars){
    int length = chars.length;
    //翻转整个句子
    revertInPlace(chars, 0, length - 1);
    //翻转每个单词
    String str = new String(chars);
    String[] strs = str.split(" ");
    int wordCounts = strs.length;
    int[] eachLength = new int[wordCounts];
    int i = 0;
    for(String s : strs){
        eachLength[i++] = s.length();
    }
    int start = 0;
    for(int j = 0; j < wordCounts; j++){
        revertInPlace(chars, start, start + eachLength[j] - 1);
        start += eachLength[j] + 1;
    }
}
private void revertInPlace(char[] chars, int i, int j){
    while(i < j){
        swap(chars, i++, j--);
    }
}
private void swap(char[] chars, int i, int j){
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
}

abcd 移动1次为bcda,移动两次为cdab,移动三次为dabc
结论：长度为n，移动m次，相当于移动m%n次
    - 前m%n位翻转，后n-m%n位翻转
    - 总体再翻转一次

public void circularMove(char[] chars, int m){
    int n = chars.length;
    revertInPlace(chars, 0, m % n - 1);
    revertInPlace(chars, m % n, n - 1);
    revertInPlace(chars, 0, n - 1);
}
private void revertInPlace(char[] chars, int i, int j){
    while(i < j){
        swap(chars, i++, j--);
    }
}
private void swap(char[] chars, int i, int j){
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
}

in-place(原地)理解

本身为O(1)空间

递归，堆栈空间可以不考虑

原地相关的问题

字符串循环左移、右移

快排partition相关

滑动窗口

能达到O(n)的时间复杂度

O(1)的空间复杂度

规则相关---细致

匹配(暴力):KMP比较少见

Manacher----要求比较高的笔试