算法训练营（day08）

344.反转字符串

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

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

解题思路

解题过程：

  1. 使用双指针的思路，依次将首尾字符调换即可

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while(left < right){
            s[left] ^= s[right];
            s[right] ^= s[left];
            s[left] ^= s[right];

            left++;
            right--;
        }
    }
}

541.反转字符串II

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

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

解题思路

解题过程：

  1. 沿用 344.反转字符串 的方法，本题实际需要考虑的是 如何拼接字符串

  2. 使用 char 存储字符串字符

  3. 2k 字符中的前 k 个字符的 首字符下标定义为 left ，末字符下标定义为 right

    • left = left + 2 * k
    • right = left + k - 1

  4. 当取到字符串尾部时，考虑剩余字符的数量，需要将 right = cs.length纳入考虑

  5. 返回 string 数组

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String reverseStr(String s, int k) {
        char[] cs = s.toCharArray();
        int len = cs.length;

        for(int left = 0; left < len; left = left + 2 * k){
            int right = left + k - 1;
            swap(cs, left, Math.min(right, len - 1));
        }
        return String.valueOf(cs);
    }

    public void swap(char[] s, int left, int right) {
        while(left < right){
            s[left] ^= s[right];
            s[right] ^= s[left];
            s[left] ^= s[right];

            left++;
            right--;
        }
    }
}

剑指Offer 05.替换空格

题目链接：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/description/

请实现一个函数，把字符串 s 中的每个空格替换成“%20”。

解题思路

解题过程：

  1. 定义一个新字符集 char 或者 一个字符串变量 StringBuilder
  2. 遍历字符串字符
    • 如果当前字符为空格，则将 %20 添加到新字符集中
    • 否则将字符添加到新字符集中

详细代码

解法一：使用 char 字符集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String replaceSpace(String s) {
        int len = s.length();
        char[] array = new char[len*3];

        int size = 0;
        for (int i=0;i<len;i++){
            char c = s.charAt(i);
            if (c == ' '){
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            }else {
                array[size++] = c;
            }
        }
        String newStr = new String(array,0,size);
        return newStr;
    }
}

解法二：使用 StringBuilder 字符串变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String replaceSpace(String s) {
        if(s == null){
            return null;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == ' '){
                sb.append("%20");
            }else{
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

151.翻转字符串里的单词

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

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

解题思路

解题过程：

  1. 根据题意，需要反转字符串中的 单词，有两种解决思路

    • 先反转整个字符串，再根据单词进行反转
    • 直接界定字符串的每个单词，再直接对单词进行反转

  2. 题意还对字符串空格作了具体要求

    • 前后空格要略去
    • 单词间空格有且仅有一个

详细代码

解法一：库函数快速解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0){
            return "";
        }

        String[] arr = s.trim().split(" ");
        StringBuilder sb = new StringBuilder();

        int len = arr.length;
        for (int i = len - 1; i >= 0; i--){
            if (arr[i].equals("")){
                continue;
            }
            if (i == 0){
                sb.append(arr[i]);
            }else {
                sb.append(arr[i]).append(" ");
            }
        }

        return sb.toString();
    }
}

解法二：使用 StringBuilder 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    //主函数
    public String reverseWords(String s) {
        StringBuilder sb = removeSpace(s);
        reverseString(sb, 0, sb.length() - 1);
        reverseEachWords(sb);
        return sb.toString();
    }

    //空格格式化
    public 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 cs = s.charAt(start);
            if(cs != ' ' || sb.charAt(sb.length() - 1) != ' '){
                sb.append(cs);
            }
            start++;
        }
        return sb;
    }

    //反转字符
    public void reverseString(StringBuilder sb, int start, int end){
        while(start < end){
            char tmp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, tmp);
            start++;
            end--;
        }
    }

    //反转单词
    public void reverseEachWords(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;
        }
    }
}

解法三：创建新字符数组填充，时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public String reverseWords(String s) {
        //源字符数组
        char[] arr = s.toCharArray();
        //新字符数组
        char[] newArr = new char[arr.length + 1];	//最终末尾的空格不会返回
        int index = 0;
        int len = arr.length - 1;					//len进行整体对 源字符数组 从后往前遍历

        while(len >= 0){
            while(len >= 0 && arr[len] == ' '){		//跳过空格
                len--;
            }
            int right = len;						//此时len位置是边界或!=空格，记录当前索引
            
            while(len >= 0 && arr[len] != ' '){		//确定单词的首字母的位置
                len--;
            }
            
        //指定区间单词取出(由于len为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格
            for(int left = len + 1; left <= right; left++){
                newArr[index++] = arr[left];
                if(left == right){
                    newArr[index++] = ' ';			//
                }
            }
        }
		//若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)
        if(index == 0){
            return "";
        }else{
            return new String(newArr, 0, index - 1);
        }
    }
}

剑指Offer58-II.左旋转字符串

题目链接：https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/description/

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串 abcdefg 和数字2，该函数将返回左旋转两位得到的结果 cdefgab。

解题思路

解题过程：

  1. 使用字符数组 char 存储字符串

  2. 仍是调用 反转字符串 的方法，判断反转方式

    1. 反转整个数组
    2. 反转前 cs.length - 1 - n 个字符
    3. 再单独反转尾部的n个字符

  3. 返回string格式

详细代码

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] cs = s.toCharArray();
        reverse(cs, 0, s.length() - 1);
        reverse(cs, 0, s.length() - n - 1);
        reverse(cs,s.length() - n, s.length() - 1);
        return new String(cs);
    }
    public void reverse(char[] cs, int start, int end){
        while(start < end){
            cs[start] ^= cs[end];
            cs[end] ^= cs[start];
            cs[start] ^= cs[end];

            start++;
            end--;
        }
    }
}

解法二：库函数快速解法

1
2
3
4
5
class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n,s.length()) + s.substring(0,n);
    }
}