CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法训练营第八天｜344-541-剑指05-151-剑指58

Posted on

今天的主题是字符串：

LeetCode 344.反转字符串

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

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

示例 1：

1
2
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

1
2
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 
 a simple simulation of the swap behavior using dual pointer 
 pointing to the first and last element, then step by step swap 
 two pointed elements and swap them 
 until the two pointer pointing to the same element
*/
class Solution {
    public void reverseString(char[] s) {

        int left = 0;
        int right = s.length - 1;
        char temp;

        while (left < right) {
            //swap the pointed two elements 
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left++;
            right--;
        }
    }
}

LeetCode 541.反转字符串II

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

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

示例 1：

1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

1
2
输入：s = "abcd", k = 2
输出："bacd"

提示：

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104
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
class Solution {
    public String reverseStr(String s, int k) {
        int quotient, remiander;
        quotient = s.length() / (2 * k);
        remiander = s.length() % (2 * k);

        char[] str = s.toCharArray();

        // for (int i = 0; i < quotient; i++) {
        //     reverseFromTo(str, i * 2 * k, i * 2 * k + k - 1);
        // }

        // if ( remiander / k == 0){
        //     reverseFromTo(str, quotient * 2 * k, str.length - 1);
        // }else if (remiander / k >= 1) {
        //     reverseFromTo(str, quotient * 2 * k, quotient * 2 * k - 1 + k);
        // }

        for (int i = 0; i < str.length; i += 2 * k) {
            reverseFromTo(str, i, Math.min(i+k, str.length) - 1);
        }

        return new String(str);

    }

    private void reverseFromTo (char[] chars, int startIndex, int endIndex) {
        
        char temp;
        while (startIndex < endIndex) {
            //swap the pointed two elements 
            temp = chars[startIndex];
            chars[startIndex] = chars[endIndex];
            chars[endIndex] = temp;

            startIndex++;
            endIndex--;
        }
    }
}

这道题的核心思路很简单，其实就是不停的找到下一个需要反转的子串，反转之，然后重复，直到到达输入字符串的末尾，一开始我写了一个相对复杂的版本，试图通过商和余数去判断。后来看了题解发现其实可以直接通过一个for循环更改序号，并通过对i+k和length-1的最小值进行判断从而将边界case纳入一个循环，挺巧妙的，值得学习。

剑指offer 05.替换空格

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

示例 1：

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

限制：

1
0 <= s 的长度 <= 10000
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
public class Solution {
    public String replaceSpace(String s) {
        int cnt = 0;
        char[] str = s.toCharArray();
      	
      	// count the numer of space first to decide the length of the new array
        for (int i = 0; i < str.length; i++) {
            char c = str[i];
            if (c == ' '){
                cnt ++;
            }
        }
      	
      	// actually, there is no need for this counting, we can directly claim 
      	// a new array, whose size is triple the previous one which is definitly
      	// enough for our use
        char[] ans = new char[str.length + 2 * cnt];
				
        for (int i = 0, j = 0; i < str.length; i++) {
            if (str[i] != ' '){
                ans[j++] = str[i];
            }else{
                ans[j++] = '%';
                ans[j++] = '2';
                ans[j++] = '0';
            }
        }

        return String.valueOf(ans);
    }
}

另一种方式是使用双指针从后向前遍历，虽然没有本质的区别，但是这里记录一下这种数组填充元素的双指针从后遍历填充方法：

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
//方式二：双指针法
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);
}

LeetCode 151.反转字符串里的单词

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

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

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

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

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(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
class Solution {

    public String reverseWords(String s) {
        List<String> list = new ArrayList<>();

        int left = 0;

        // step 1: use space dividing the string s into words
        while (left < s.length()) {
            char c = s.charAt(left);

            if ( c == ' ') {
                left++;
            }else {
                int right = left;
                while(right < s.length() && s.charAt(right) != ' '){
                    right++;
                }
                list.add(s.substring(left, right));
                left = right;
            }
        }

        // setp 2: swap the words in the list
        int leftIndex = 0; int rightIndex = list.size() - 1;

        while ( leftIndex < rightIndex) {
            swap(list, leftIndex, rightIndex);
            leftIndex++;
            rightIndex--;
        }

        // step 3: add sapce as divider between the revered words
        StringBuffer sb = new StringBuffer();

        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
            if(i != list.size() - 1){
                sb.append(' ');
            }
        }

        // step4: return the reversed words string
        return sb.toString();
    }

    private void swap (List<String> list, int left, int right) {
        String temp = list.get(left);
        list.set(left,list.get(right));
        list.set(right,temp);
    }
}

如注释所示，把整体任务分解成如上的几步，整体并不复杂，有不同复杂度的各种解法，待后续补充。

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

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

示例 1：

1
2
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

1
2
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制：

  • 1 <= k < s.length <= 10000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {

    // 0 1 2 3 4 5 6, size = 7
    public String reverseLeftWords(String s, int n) {
        char[] input = s.toCharArray();
        int size = input.length;

        char[] output = new char[size];

        for (int i = 0; i < size; i++) {
            output[(i + size - n) % size] = input[i];
        }
      
        return new String(output);
    }
}

计算一下可知，原来的i位置的元素要到 (i + size - n) % size的位置，知道了坐标关系后就可以很方便的进行计算。

除此之外，还可以先反转前n个元素，然后反转后size - n个元素，然后反转整个字符串即可。