[数据结构与算法]代码随想录算法训练营第七天

字符串

反转字符串

题目：LeetCode.344

class Solution {
    public void reverseString(char[] s) {
        int i = 0;
        int j = s.length - 1;
        while (i < j){
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
            i++;
            j--;
        }
    }
}

反转字符串Ⅱ

题目：LeetCode.541

String常用API：

• length()：返回长度
• split(String regex)：分割字符串
• toCharArray()：字符串转换成字符数组
• append：添加字符串
• reverse()：翻转字符串
• indexOf(char c)、indexOf(String str)：查找，找不到返回-1
• equals()：判断两个字符串是否相等，注意不能直接用==
• compareTo()：判断两个字符串的字典序大小，负数表示小于，0表示相等，正数表示大于
• startsWith()：判断是否以某个前缀开头
• endsWith()：判断是否以某个后缀结尾
• trim()：去掉首尾的空白字符
• toLowerCase()：全部用小写字符
• toUpperCase()：全部用大写字符
• replace(char oldChar, char newChar)：替换字符
• replace(String oldRegex, String newRegex)：替换字符串
• substring(int beginIndex, int endIndex)：返回[beginIndex, endIndex)中的子串

StringBuffer

• append：添加字符串
• reverse()：翻转字符串
• insert()：插入
• delete()：删除

写法一：转换成字符数组

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i += 2 * k){
            int start = i;
            //这里是判断尾数够不够k个来取决end指针的位置
            int end = Math.min(ch.length - 1, start + k - 1);
            //用异或运算反转 
            while(start < end){
                char tmp = ch[start];
                ch[start] = ch[end];
                ch[end] = tmp;
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}

写法二：StringBuffer

class Solution {
    public String reverseStr(String s, int k) {
        StringBuffer res = new StringBuffer();
        int length = s.length();
        int i = 0;
        while (i < length){
            int firstK = (i + k > length) ? length : i + k;
            int secondK = (i + (2 * k) > length) ? length : i + (2 * k);
            StringBuffer tmp = new StringBuffer();
            tmp.append(s.substring(i, firstK));//将前k个字符反转
            res.append(tmp.reverse());//反转后的前k个字符加入
            if (firstK < secondK) { //此时剩余长度一定大于k。
                res.append(s.substring(firstK, secondK));
            }
            i += (2 * k);
        }
        return res.toString();
    }
}

替换空格

题目：剑指offer.05

charAt()

class Solution {
    public String replaceSpace(String s) {
        if(s == null) return null;
        StringBuffer str = new StringBuffer();
        for(int i = 0 ; i < s.length() ; i++){
            if(s.charAt(i) == ' ') str.append("%20");
            else str.append(s.charAt(i));
        }
        return str.toString();
    }
}

反转字符串里的单词

题目：LeetCode.151

解题步骤：

1. 去除多余的空格，先去除首尾全部空格，再去除单词间多余的空格。
2. 定义部分反转函数
3. 应用反转函数，先将整体反转，再将单词反转。遍历单词时采用双指针的想法start指向首字母，end向后遍历至空格处，以此时的start和end为参数反转，之后start移动end+1的位置，end++，到达最后一个单词的末尾时start==n，跳出while。

class Solution {
    public String reverseWords(String s) {
        StringBuilder res = new StringBuilder();//去除多余的空格
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        for(int i = start ; i <= end ; i++){
            if (s.charAt(i) == ' ' && s.charAt(i + 1) == ' ') continue;
            else res.append(s.charAt(i));

        }
        reverse(res, 0, res.length() - 1);// 翻转字符串
        reverseEachWord(res);// 翻转每个单词
        return res.toString();
    }


     public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }

    
    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0, end = 0;

        while (start < n) {
            // 循环至单词的末尾
            while (end < n && sb.charAt(end) != ' ') {
                ++end;
            }
            // 翻转单词
            reverse(sb, start, end - 1);
            // 更新start，去找下一个单词
            start = end + 1;
            end++;
        }
    }

}

左旋转字符串

题目：剑指offer.58

将上题中的局部反转的代码应用一下，先反转前n个，再反转后面剩余部分，最后整体反转，就可得到最终结果。

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder(s);
        reverse(res, 0, n - 1);
        reverse(res, n, s.length() - 1);
        reverse(res, 0, s.length() - 1);
        return res.toString();
    }
    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }
}