Skip to content

Latest commit

 

History

History
387 lines (317 loc) · 11.9 KB

2_字符串.md

File metadata and controls

387 lines (317 loc) · 11.9 KB
Raw

字符串

1、替换空格

替换空格

public String replaceSpace(StringBuffer str) {
    int n = str.length(); // str 的 初始长度

    //遍历该字符串，遇到空格就添加 2 个空格
    //因为要将 " " -> "%20",1 个字符替换成 3 个字符，则需要额外的两个字符
    for(int i=0;i<n;i++){
        if(str.charAt(i)==' '){
            str.append(" ").append(" ");
        }
    }


    int p1 = n-1;//p1 指向字符串最后一位
    int p2 = str.length()-1;//p2 指向新字符串最后一位
    //从后向前遍是为了在改变 p2 所指向的内容时，不会影响到 p1 遍历原来字符串的内容。
    while(p1>=0 && p2>p1){ // p1==p2 则前面的元素就不需要遍历了，是存在空格的
        char ch = str.charAt(p1--);
        if(ch==' '){ //" " -> "%20" ,由于是从后向前的，所以要倒序填充
            str.setCharAt(p2--,'0');
            str.setCharAt(p2--,'2');
            str.setCharAt(p2--,'%');
        }else{
            str.setCharAt(p2--,ch);
        }
    }
    return str.toString();
}

*2、正则表达式匹配

正则表达式匹配

//思路：
// 当模式中的第二个字符不是“*”时：
// 1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
// 2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
// 
// 当模式中的第二个字符是“*”时：
// 如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
// 如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
// 1、模式后移2字符，相当于x*被忽略；
// 2、字符串后移1字符，模式后移2字符；(匹配一位)
// 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；

public boolean match(char[] str, char[] pattern) {
    if(str==null || pattern==null){
        return false;
    }
    return match(str,0,pattern,0);
}

private boolean match(char[] str,int strIndex,char[] pattern,int patternIndex){
    if(strIndex==str.length && patternIndex==pattern.length){
        // str 和 pattern 都到达了末尾，则返回 true
        return true;
    }
    if(patternIndex==pattern.length && strIndex!=str.length){
        //pattern 先到达了末尾，则返回 false
        return false;
    }

    //当模式中的第二个字符不是“*”时：
    if(patternIndex+1<pattern.length && pattern[patternIndex+1]=='*'){
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) ||
            (strIndex != str.length && pattern[patternIndex] == '.')){
            return match(str,strIndex,pattern,patternIndex+2) ||  
                //1、模式后移2字符，相当于x*被忽略；
                match(str,strIndex+1,pattern,patternIndex+2) || 
                // 2、字符串后移1字符，模式后移2字符；(匹配一位)
                match(str,strIndex+1,pattern,patternIndex); 
            // 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位
        }else{ // 前一个元素既不相等，也不是"*",模式后移 2 字符，相当于 x* 被忽略。
            return match(str,strIndex,pattern,patternIndex+2);
        }
    }else{
        // 如果字符串第一个字符和模式中的第一个字符相匹配，
        // 那么字符串和模式都后移一个字符，然后匹配剩余的。
        if((strIndex != str.length && pattern[patternIndex] == str[strIndex]) ||
           (pattern[patternIndex] == '.' && strIndex != str.length)){
            return match(str,strIndex+1,pattern,patternIndex+1);
        }else{
            return false;
        }
    }
}

3、表示数值的字符串

表示数值的字符串

常用的正则表达式:

[]  ： 字符集合
()  ： 分组
?   ： 重复 0 ~ 1 次
+   ： 重复 1 ~ n 次
*   ： 重复 0 ~ n 次
.   ： 任意字符
\\. ： 转义后的 .
\\d ： 数字
public boolean isNumeric(char[] str) {
    if(str==null || str.length==0){
        return false;
    }
    //字符开始时 + 或 - 出现 0 次或者 1 次
    //() 表示分组
    //小数分组组 (\.\d+)?
    //指数分组([eE]+[+-]?\d+)?
    return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
    //注意这里使用 \\d*，因为 "-.123" 也是正确的
}

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

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

//思路一：暴力解法
//先将所有数据插入，再进行统计

private StringBuffer buffer=new StringBuffer();
//Insert one char from stringstream
public void Insert(char ch)
{
    buffer.append(ch);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
    int[] freq = new int[256];

    for(int i=0;i<buffer.length();i++){
        char ch = buffer.charAt(i);
        freq[ch]++;
    }

    for(int i=0;i<buffer.length();i++){
        char ch = buffer.charAt(i);
        if(freq[ch]==1){
            return ch;
        }
    }
    return '#';
}
//思路二：
//利用队列先进先出的特性

//统计字符出现的次数
private int[] freq = new int[256];
//队列中值存储出现一次的字符，并且出队顺序就是入队顺序一致
private Queue<Character> queue = new LinkedList<>();
//Insert one char from stringstream
public void Insert(char ch) {
    freq[ch]++;
    queue.offer(ch);
    while (!queue.isEmpty() && freq[queue.peek()]>1){
        queue.poll();
    }
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
    return queue.isEmpty()? '#':queue.peek();
}

*5、字符串的排列

字符串的排列

private ArrayList<String> res;
private boolean[] visited;

public ArrayList<String> Permutation(String str) {
    res = new ArrayList<>();
    if(str==null || str.length()==0){
        return res;
    }
    char[] chs = str.toCharArray();
    Arrays.sort(chs); //方便后面的去重处理
    visited = new boolean[str.length()];
    permute(chs,0,new StringBuilder());
    return res;
}

//产生排列
//p中保存一个存在index个元素的排列
//向这个排列的末尾添加第(index+1)个元素，获得包含(index+1)个元素的排列
private void permute(char[] chs,int index,StringBuilder p){
    if(index==chs.length){
        res.add(p.toString());
        return;
    }
    for(int i=0;i<chs.length;i++){
        //需要进行去重处理
        if(i>0 && chs[i-1]==chs[i] && !visited[i-1]){
            continue;
        }
        if(!visited[i]){
            p.append(chs[i]);
            visited[i] = true;
            permute(chs,index+1,p);
            p.deleteCharAt(p.length()-1);
            visited[i] = false;
        }
    }
}

6、把数组排成最小的数

把数组排成最小的数

//思路：
//可以看成是一个排序问题，在比较两个字符串 S1 和 S2 的大小时，
//应该比较的是 S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，
//那么应该把 S1 排在前面，否则应该把 S2 排在前面。

import java.util.Arrays;
import java.util.Comparator;

//把数组排成最小的数
public String PrintMinNumber(int [] numbers) {
    StringBuilder res = new StringBuilder();
    if(numbers==null || numbers.length==0){
        return res.toString();
    }
    int n = numbers.length;
    String[] nums = new String[n];
    for(int i=0;i<n;i++){
        nums[i]=numbers[i]+"";
    }

    //TODO:定义排序规则
    Arrays.sort(nums, new Comparator<String>() {
        @Override
        public int compare(String s1, String s2) {
            //如果 s1+s2 < s2+s1，则 s1 排在前面（默认是按照升序排列的）
            return (s1+s2).compareTo(s2+s1);
        }
    });

    for(String num:nums){
        res.append(num);
    }
    return res.toString();
}

7、把字符串转换成整数

把字符串转换成整数

public int StrToInt(String str) {
    if(str==null || str.length()==0){
        return 0;
    }
    //判断是否是负数
    boolean isNegative = str.charAt(0)=='-';

    int res=0;
    for(int i=0;i<str.length();i++){
        char ch = str.charAt(i);
        if(i==0 && (ch=='+' || ch=='-')){ //第一位有可能是符号位
            continue;
        }
        if(ch<'0' || ch>'9'){ //字符不是数字
            return 0;
        }
        res = res*10+(ch-'0');
    }
    //注意：当 str = "-2147483648" 时，res = 2147483640 + 8 = -2147483648
    //由于 int 范围限制，则 -(-2147483648) = -2147483648
    return isNegative?-res:res;
}

8、左旋转字符串

左旋转字符串

public String LeftRotateString(String str,int n) {
    if(str==null || str.length()==0){
        return "";
    }
    char[] chs = str.toCharArray();
    if(n>chs.length){
        return str;
    }
    reverse(chs,0,chs.length-1);
    reverse(chs,0,chs.length-n-1);
    reverse(chs,chs.length-n,chs.length-1);
    return new String(chs);
}

//将[start,end] 之间的字符串反转
private void reverse(char[] chs,int start,int end){
    while (start<end){
        char tmp = chs[start];
        chs[start] = chs[end];
        chs[end] = tmp;
        start++;
        end--;
    }
}

9、翻转单词顺序列

翻转单词顺序列

//注意：
// 题目应该有一个隐含条件，就是不能用额外的空间。
// 虽然 Java 的题目输入参数为 String 类型，需要先创建一个字符数组使得空间复杂度为 O(N)，
// 但是正确的参数类型应该和原书一样，为字符数组，并且只能使用该字符数组的空间。
// 任何使用了额外空间的解法在面试时都会大打折扣

//思路：先旋转每个单词，在旋转整个字符数组
public String ReverseSentence(String str) {
    char[] chs = str.toCharArray();
    int N = chs.length;

    //先翻转每个单词
    int start=0;
    int end=0;
    while(end<=N){
        if(end==N || chs[end]==' '){
            reverse(chs,start,end-1);
            start = end+1;
        }
        end++;
    }

    //再翻转整个字符串
    reverse(chs,0,N-1);
    return new String(chs);
}

private void reverse(char[] chs,int start,int end){
    while (start<end){
        char tmp = chs[start];
        chs[start] = chs[end];
        chs[end] = tmp;
        start++;
        end--;
    }
}