344.反转字符串

文章：代码随想录 (programmercarl.com)

题目：字符串基础操作！ | LeetCode：344.反转字符串_哔哩哔哩_bilibili

视频：344. 反转字符串

【思路】

方法：双指针法

如果题目的实现逻辑为库函数的话，尽量手写。

swap函数的实现逻辑：

​ swap可以有两种实现。

​ 一种就是常见的交换数值：

1
2
3
int tmp = s[i];
s[i] = s[j];
s[j] = tmp;

​ 一种就是通过位运算：

1
2
3
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
  • Java实现
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public void reverseString(char[] s) {
        int j = s.length-1;
        for(int i = 0 ; i < s.length/2;i++){
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
            j--;
        }
    }
}
  • Go实现
1
2
3
4
5
6
7
func reverseString(s []byte)  {
    j := len(s)-1
    for i:=0;i<len(s)/2;i++{
        s[i] , s[j] = s[j],s[i]
        j--
    }
}

541.反转字符串II

文章：2. 反转字符串II

题目：541. 反转字符串 II - 力扣（LeetCode）

视频：字符串操作进阶！ | LeetCode：541. 反转字符串II_哔哩哔哩_bilibili

​ 需要注意for循环的临界条件！

​ 需要注意题目要求的是反转2k段中的前k段，这样可能会面临k >s.length的问题，因此我们选取右指针时需要取s.length()-1, l+k-1的最小值。

  • Java实现（一）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String reverseStr(String s, int k) {
        char[]c = s.toCharArray();
        for(int i = 0 ; i < c.length;i +=2*k){
            int l = i;
            int r = Math.min(c.length-1,l+k-1);
            while(l < r){
                c[l] ^= c[r];
                c[r] ^= c[l];
                c[l] ^= c[r];
                l++;
                r--;
            }
        }
        return new String(c);
    }
}
  • Java实现（二）：使用StringBuffer

划分区间，左指针到 k 段的值翻转后加入res，k 到 2k 段的值直接加入res，然后移动指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String reverseStr(String s, int k) {
        StringBuffer res = new StringBuffer();
        int length = s.length();
        int start = 0;
        while( start < length){
            StringBuffer temp = new StringBuffer();
            int firstK = (start+k > length)?length:start+k;
            int secondK = (start + 2*k > length)? length:start+(2*k);
            temp.append(s.substring(start,firstK));
            res.append(temp.reverse());

            if(firstK < secondK){
                res.append(s.substring(firstK,secondK));
            }
            start += 2*k;
        }
        return res.toString();
    }
}
  • Go实现

使用 if 语句来判断 右指针的边界值是否会大于字符串的长度：如果小于等于则切片范围正常取i+k，大于则切片范围取字符串的最大长度length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func reverseStr(s string, k int) string {
    ss:=[]byte(s)
    length := len(s)
    for i := 0 ; i < len(s);i+=2*k{
        if i+k <= length{
            reverse(ss[i:i+k])
        }else{
            reverse(ss[i:length])
        }
    }
    return string(ss)
}
func reverse(b []byte){
    left := 0
    right := len(b)-1
    for left < right {
        b[left],b[right] = b[right],b[left]
        left++
        right--
    }
}

剑指Offer 05.替换空格

文章：3. 替换空格

题目：已经被替换了

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

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

【思路】

如果想把这道题目做到极致，就不要只用额外的辅助空间了！

首先扩充数组到每个空格替换成”%20”之后的大小。

然后从后向前替换空格，也就是双指针法，过程如下：

i指向新长度的末尾，j指向旧长度的末尾。

有同学问了，为什么要从后向前填充，从前向后填充不行么？

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。

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

这么做有两个好处：

  1. 不用申请新数组。
  2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

时间复杂度，空间复杂度均超过100%的用户。

Java：

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
//使用一个新的对象，复制 str，复制的过程对其判断，是空格则替换，否则直接复制，类似于数组复制
public static String replaceSpace(String s) {
        if (s == null) {
            return null;
        }
        //选用 StringBuilder 单线程使用，比较快，选不选都行
        StringBuilder sb = new StringBuilder();
        //使用 sb 逐个复制 s ，碰到空格则替换，否则直接复制
        for (int i = 0; i < s.length(); i++) {
            //s.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
            //if (" ".equals(String.valueOf(s.charAt(i)))){}
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

//方式二：双指针法
public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}

#Go：

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
// 遍历添加
func replaceSpace(s string) string {
    b := []byte(s)
    result := make([]byte, 0)
    for i := 0; i < len(b); i++ {
        if b[i] == ' ' {
            result = append(result, []byte("%20")...)
        } else {
            result = append(result, b[i])
        }
    }
    return string(result)
}

// 原地修改
func replaceSpace(s string) string {
    b := []byte(s)
    length := len(b)
    spaceCount := 0
    // 计算空格数量
    for _, v := range b {
        if v == ' ' {
            spaceCount++
        }
    }
    // 扩展原有切片
    resizeCount := spaceCount * 2
    tmp := make([]byte, resizeCount)
    b = append(b, tmp...)
    i := length - 1
    j := len(b) - 1
    for i >= 0 {
        if b[i] != ' ' {
            b[j] = b[i]
            i--
            j--
        } else {
            b[j] = '0'
            b[j-1] = '2'
            b[j-2] = '%'
            i--
            j = j - 3
        }
    }
    return string(b)
}

151.反转字符串里的单词

文章：4. 翻转字符串里的单词

题目：151. 反转字符串中的单词

视频：字符串复杂操作拿捏了！ | LeetCode:151.翻转字符串里的单词_哔哩哔哩_bilibili

【思路】

先反转整个字符串，这时每个单词的位置以及字母顺序都进行了反转，和目标字符串的区别在于每个单词的字母顺序不一样，然后再将每一个单词的字母顺序进行反转即可。

不要使用辅助空间，空间复杂度要求为O(1)。

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

  • Java实现
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) {
        //1.去除首位以及中间多余空格
        StringBuilder sb = removeSpace(s);
        //2.反转整个字符串
        reverseString(sb,0,sb.length()-1);
        //3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();

    }
    //去除多余的空格
    private StringBuilder removeSpace(String s){
        StringBuilder sb = new StringBuilder();
        int start = 0;
        int end = s.length()-1;
        //去除首尾的空格
        while(s.charAt(start) == ' ')start++;
        while(s.charAt(end)==' ')end--;

        while(start <= end){
            char c = s.charAt(start);
            //c不是空格 || 前一位是字母 即可添加 c || ' '
            if(c !=' ' || sb.charAt(sb.length()-1) != ' '){
                sb.append(c);
            }
            start++;
        }
        return sb;
    }
    //反转指定区间（单个单词）字符串
    private 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 len = sb.length();
        while(start < len){
            //查找第一个空格，找到说明到达了单词的结尾
            while(end < len && sb.charAt(end) != ' '){
                end++;
            }
            //此时 end = ' ',因此我们需要将end-1
            reverseString(sb,start,end-1);
            start = end +1;
            end = start+1;
        }
    }
}
  • Go实现
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
func reverseWords(s string) string {
    b :=[]byte(s)
    slow := 0
    //移除前中后多余的空格
    for i :=0 ;i < len(s);i++{
        if b[i]!=' '{
            //说明前面有单词，现在应该加空格。
            if slow != 0{
                b[slow] = ' '
                slow++
            }
            for i<len(b) && b[i]!=' '{
                b[slow]=b[i]
                slow++
                i++
            }
        }
    }
    b =b[0:slow]
    //反转字符串
    reverse(b)
    //反转单词
    last:=0
    for i :=0;i<=len(b);i++{
        if i == len(b)|| b[i] ==' '{
            reverse(b[last:i]) //左闭右开区间
            last=i+1
        }
    }
    return string(b)
}

func reverse(b []byte){
    left :=0
    right := len(b)-1
    for left<right{
        b[left],b[right] = b[right],b[left]
        left++
        right--
    }
}

Offer58-II.左旋转字符串

文章：5. 左旋转字符串

题目：LCR 182. 动态口令

【思路】

不申请额外空间、只能在本串上操作。

这样的话我们可以使用整体反转+局部反转实现左旋转的目的。

1、反转前n位子串

2、反转n到末尾的子串

3、反转整个字符串

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String dynamicPassword(String password, int target) {
        //先反转前n位
        //然后反转n到末尾
        //最后整个反转
        StringBuilder sb = new StringBuilder(password);
        reverse(sb,0,target-1);
        reverse(sb,target,password.length()-1);
        reverse(sb,0,password.length()-1);
        return sb.toString();
    }
    private void reverse(StringBuilder sb,int start,int end){
        while(start < end){
            char c = sb.charAt(start);
            sb.setCharAt(start,sb.charAt(end));
            sb.setCharAt(end,c);
            start++;
            end--;
        }
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func dynamicPassword(password string, target int) string {
    b := []byte(password)
    reverseString(b,0,target-1)
    reverseString(b,target,len(b)-1)
    reverseString(b,0,len(b)-1)
    return string(b)
}

func reverseString(b []byte,start int, end int){
    for start < end{
        b[start],b[end] = b[end],b[start]
        start++
        end--
    }
}

【算法总结】

  • 反转字符串的题目使用双指针法对字符串进行操作即可、以及使用的数据类型为StringBuilder。
  • 反转字符串里的单词需要我们先去除字符串里面多余的空格，然后反转整个字符串，最后再反转每个单词（依靠空格划分）->反转[start,end]范围内的字符串
  • 左旋转字符和反转字符串里的单词类似，都是对某一段的字符串进行多次反转操作，即可得出题解。
  • 字符串的题目要留意**for循环的边界条件**，很容易犯错。

【语法总结】

  • Java：

字符串交换：

一种就是常见的交换数值：

1
2
3
int tmp = s[i];
s[i] = s[j];
s[j] = tmp;

​ 一种就是通过位运算：

1
2
3
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

我们可以将String类型的字符串转化为StringBuffer或StringBuilder的形式对字符串进行操作。

1
2
StringBuilder sb = new Stringbuilder(s)
sb.toString();
  • Go：

将string类型的字符串转化为[]byte数组进行操作。

1
2
b :=[]byte(s)
string(b)