Day07

今日任务：

• 344 反转字符串
• 541 反转字符串Ⅱ
• 剑指offer 05 替换空格
• 151 翻转字符串里的单词
• 剑指offer 58 左旋转字符串

---

344?反转字符串

题目链接：https://leetcode.cn/problems/reverse-string/description/

关键： 双指针的运用

思路：

1. 在原数组上修改，定义两个指针，从左右两端向中间移动
2. 移动的时候进行元素值互换

代码：

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

---

541 反转字符串Ⅱ

题目链接：https://leetcode.cn/problems/reverse-string-ii/description/

两个题目类似，主要是修改了 i 是如何变化的，每次要增长的是 2k，但是在是否全部反转的判断上使用的是 k

代码：

class Solution {
    public String reverseStr(String s, int k) {
        char[] c = s.toCharArray();
        for(int i = 0; i < s.length(); i +=(2*k)) {
            if(i + k <= s.length()) {
                reversePart(c,i,i+k-1);
            }else {
                reversePart(c,i,s.length()-1);
            }
        }
        return new String(c);
    }
    public void reversePart(char[] c, int begin, int end) {
        while(begin < end ) {
            char tmp = c[begin];
            c[begin] = c[end];
            c[end] = tmp;
            begin++;
            end--;
        }
    }
}

---

剑指offer 05 替换空格

题目：

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"

输入描述：

输入一个字符串 s,s 仅包含小写字母和数字字符。

输出描述

打印一个新的字符串，其中每个数字字符都被替换为了number

?方法一：创建新的字符数组，然后遍历 s，不断向里添加

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(replaceNumber(s));
        sc.close();
    }
    public static String replaceNumber(String s) {
        char[] arr = s.toCharArray();
        StringBuffer res = new StringBuffer();
        for(int i = 0; i < s.length(); i++) {
            if(arr[i] >= 97 && arr[i] <= 122) {
                res.append(arr[i]);
            }else {
                res.append("number");
            }
        }
        return res.toString();
    }
}

方法二：可以免除进行数组扩容带来的性能损失

思路：

1. 先统计字符串上多少数字，然后给数组进行扩容
2. 然后从后往前进行操作

其实很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作

代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        char[] sin = s.toCharArray();
        //用于统计有多少数字
        int count = 0;
        int size1 = sin.length;
        for(int i = 0; i < size1; i++) {
            if(sin[i] >= '0' && sin[i] <= '9') {
                count++;
            }
        }
        int size2 = size1 + count * 5;
        char[] res = new char[size2];
        for(int i = size2 - 1, j = size1 - 1; i >= 0; i--, j--) {
            if (sin[j] > '9' || sin[j] < '0'){
                res[i] = sin[j];
            }else {
                res[i--] = 'r';
                res[i--] = 'e';
                res[i--] = 'b';
                res[i--] = 'm';
                res[i--] = 'u';
                res[i] = 'n';
            }
        }
        String ans = new String(res);
        System.out.println(ans);
    }
}

---

151 翻转字符串里的单词

题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/description/

思路：

1. 先将字符串两端的空格去掉
2. 然后两个指针都指向最后一位 i，j
3. i 指针向前移动，直到找到 空格 的时候停下，这个时候截取字符的 [i+1, j+1) 就是一个单词，这个区间是满足 substring 方法的
4. 然后 i 指针继续向前移动，直到找到一个 不是空格 的地方
5. 两个指针指向同一个地方，重复3-4步
6. 直到 i 指针走到左边的尽头

代码：

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        int j = s.length()-1;
        int i = j;
        StringBuilder ans = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--;
            ans.append(s.substring(i+1, j+1) + " ");
            while(i >= 0 && s.charAt(i) == ' ') i--;
            j = i;
        }
        return ans.toString().trim();
    }
}

进阶做法：空间复杂度为O(1)

思路：

1. 删除多余空格，两端的空格及连续的空格只保留一个
2. 反转整个字符串
3. 再反转每个单词

class Solution {
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }
    /**
     * 去除多余空格
     */
    private StringBuilder removeSpace(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while(start <= end) {
            char c = s.charAt(start);
            //这个判断很关键，要么这个元素不是 空格
            //要么 这个空格前的元素不是空格
            if(c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        return sb;
    }
    /**
     * 反转字符串指定区间[start, end]的字符
     */
    public void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

---

剑指offer 58 左旋转字符串

题目：

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。?

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

输入描述：

?输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出描述：

?输出共一行，为进行了右旋转操作后的字符串

?注意 k 是 可以进行 求余计算的

代码：

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        sc.nextLine();
        String s = new String(sc.nextLine());
        int slen = s.length();
        k %= slen;
        k = slen - k;
        System.out.print(s.substring(k));
        System.out.println(s.substring(0,k));
    }
}