代码随想录算法训练营day8_算法随想录网站

代码随想录算法训练营day7

反转字符串

https://leetcode.cn/problems/reverse-string/

题目

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

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

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：
输入：[“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

示例 2：
输入：[“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]

思路

本质上字符串也是一个数组，使用双指针就可以进行翻转

代码

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

class Solution {
    public void reverseString(char[] s) {
        if (s.length < 2) return;
        int left = 0, right = s.length - 1;
        while(left < right){
            s[left] ^= s[right]; //构造 a ^ b 的结果，并放在 a 中
            s[right] ^= s[left]; //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
            s[left] ^= s[right]; //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
            left++;
            right--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

反转字符串II

https://leetcode.cn/problems/reverse-string-ii/

题目

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

如果剩余字符少于 k 个，则将剩余字符全部反转。

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

示例:

输入: s = “abcdefg”, k = 2
输出: “bacdfeg”

思路

• 在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

需要翻转的区间：

• 尾数够不够k个取决end指针的位置 尾长len < k
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

代码

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        int len = ch.length - 1 > k ? k : ch.length - 1;
        int left = 0, right = len - 1;
        while(left < right){
            char tmp = ch[left];
            ch[left] = ch[right];
            ch[right] = tmp;
            left++;
            right--;
        }
        return new String(ch);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

替换空格

https://leetcode.cn/problems/ti-huan-kong-ge-lcof/

题目

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

示例 1： 输入：s = “We are happy.”
输出：“We%20are%20happy.”

思路

• 暴力破解，遇到空字符串进行替换
• 双指针法，先提前开辟空间
  • 这么做有两个好处：
    • 不用申请新数组。
    • 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

代码

双指针

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        for(int i = 0; i < len; i++){
            if(s.charAt(i) == ' '){
                //扩充空间，空格数量2倍
                sb.append("  ");
            }
        }
        //若是没有空格直接返回
        if(sb.length() == 0){
            return s;
        }
        int slow = len - 1;
        s += sb.toString();
        int fast = s.length() - 1;
        char ch[] = s.toCharArray();
        while(slow >= 0){
            if(ch[slow] == ' '){
                ch[fast--] = '0';
                ch[fast--] = '2';
                ch[fast] = '%';
            }else{
                ch[fast] = ch[slow];
            }
            fast--;
            slow--;
        }
        return new String(ch);
    }
}
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

字符串替换

class Solution {
    public String replaceSpace(String s) {
        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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

翻转字符串里的单词

https://leetcode.cn/problems/reverse-words-in-a-string/

题目

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

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

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

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

示例 1：

输入：s = “the sky is blue”
输出：“blue is sky the”

思路

本题的难度：不要使用辅助空间，空间复杂度要求为O(1)。

不能使用辅助空间之后，那么只能在原字符串上下功夫了。

想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。

所以解题思路如下：

移除多余空格
将整个字符串反转
将每个单词反转

举个例子，源字符串为："the sky is blue "

移除多余空格 : “the sky is blue”
字符串反转：“eulb si yks eht”
单词反转：“blue is sky the”

移除多余空格

使用双指针法来去移除空格，最后resize（重新设置）一下字符串的大小，就可以做到O(n)的时间复杂度。

代码

解法一

不使用Java内置方法实现
1.去除首尾以及中间多余空格
2.反转整个字符串
3.反转各个单词

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = removeSpace(s);
        reverseStr(sb, 0, sb.length() - 1);
        reverseEachWord(sb);
        return sb.toString();
    }

    public StringBuilder removeSpace(String s){
        int start = 0, 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);
            // sb.charAt(sb.length() - 1) != ' ' 判断有没多余的空格
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

    public void reverseStr(StringBuilder sb, int start, int end){
        while(start < end){
            char ch = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, ch);
            start++;
            end--;
        }
    }

    public void reverseEachWord(StringBuilder sb){
        int start = 0;
        int end = 1;
        int len = sb.length();
        while(start < len){
            while(end < len && sb.charAt(end) != ' ') end++;
            reverseStr(sb, start, end - 1);
            start = end + 1;
            end = end + 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

解法二(双指针去重多余空格和翻转单词)

网站内代码

/*
 * 解法四：时间复杂度 O(n)
 * 参考卡哥 c++ 代码的三步骤：先移除多余空格，再将整个字符串反转，最后把单词逐个反转
 * 有别于解法一 ：没有用 StringBuilder  实现，而是对 String 的 char[] 数组操作来实现以上三个步骤
 */
class Solution {
    //用 char[] 来实现 String 的 removeExtraSpaces，reverse 操作
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        //1.去除首尾以及中间多余空格
        chars = removeExtraSpaces(chars);
        //2.整个字符串反转
        reverse(chars, 0, chars.length - 1);
        //3.单词反转
        reverseEachWord(chars);
        return new String(chars);
    }

    //1.用 快慢指针 去除首尾以及中间多余空格，可参考数组元素移除的题解
    public char[] removeExtraSpaces(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            //先用 fast 移除所有空格
            if (chars[fast] != ' ') {
                //在用 slow 加空格。 除第一个单词外，单词末尾要加空格
                if (slow != 0)
                    chars[slow++] = ' ';
                //fast 遇到空格或遍历到字符串末尾，就证明遍历完一个单词了
                while (fast < chars.length && chars[fast] != ' ')
                    chars[slow++] = chars[fast++];
            }
        }
        //相当于 c++ 里的 resize()
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow); 
        return newChars;
    }

    //双指针实现指定范围内字符串反转，可参考字符串反转题解
    public void reverse(char[] chars, int left, int right) {
        if (right >= chars.length) {
            System.out.println("set a wrong right");
            return;
        }
        while (left < right) {
            chars[left] ^= chars[right];
            chars[right] ^= chars[left];
            chars[left] ^= chars[right];
            left++;
            right--;
        }
    }

    //3.单词反转
    public void reverseEachWord(char[] chars) {
        int start = 0;
        //end <= s.length() 这里的 = ，是为了让 end 永远指向单词末尾后一个位置，这样 reverse 的实参更好设置
        for (int end = 0; end <= chars.length; end++) {
            // end 每次到单词末尾后的空格或串尾,开始反转单词
            if (end == chars.length || chars[end] == ' ') {
                reverse(chars, start, end - 1);
                start = end + 1;
            }
        }
    }
}
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
58
59
60
61
62
63
64
65
66

左旋转字符串

题目

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

示例 1：
输入: s = “abcdefg”, k = 2
输出: “cdefgab”

示例 2：
输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

限制：
1 <= k < s.length <= 10000

思路

提升一下本题难度：不能申请额外空间，只能在本串上操作。

具体步骤为：

• 反转区间为前n的子串
• 反转区间为n到末尾的子串
• 反转整个字符串

最终得到左旋2个单元的字符串：cdefgab

代码

class Solution {
    public String reverseLeftWords(String s, int n) {
        int len=s.length();
        StringBuilder sb=new StringBuilder(s);
        reverse(sb, 0, n - 1);
        reverse(sb, n, len - 1);
        reverse(sb, 0, len - 1);
        return sb.toString();
    }

    private void reverse(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--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

先整个字符串反转，再反转前面的，最后反转后面 n 个

//解法二：空间复杂度：O(1)。用原始数组来进行反转操作
class Solution {
    public String reverseLeftWords(String s, int n) {
        char[] chars = s.toCharArray();
        reverse(chars, 0, chars.length - 1);
        reverse(chars, 0, chars.length - 1 - n);
        reverse(chars, chars.length - n, chars.length - 1);
        return new String(chars);
    }

    public void reverse(char[] chars, int left, int right) {
        while (left < right) {
            chars[left] ^= chars[right];
            chars[right] ^= chars[left];
            chars[left] ^= chars[right];
            left++;
            right--;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19