一、字符串的反转

1、反转字符串(简单)

自己的想法

方法一:原地交换

  • 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:45.1 MB, 在所有 Java 提交中击败了60.21%的用户
 1class Solution {
 2    public void reverseString(char[] s) {
 3        int n = s.length - 1;
 4        for (int i = 0; i <= n / 2; i++) {
 5            char tmp = s[i];
 6            s[i] = s[n - i];
 7            s[n - i] = tmp;
 8        }
 9    }
10}

2、反转字符串 II(简单)

自己的想法

方法一:双指针(StringBuilder)

  题意如下,将字符串前 k 个字符反序存储,然后将下标为 k~2k 的字符正序存储,接着将下标为 2k~3k 的字符反序存储,依次类推。我们使用双指针计算每个 k 区间的下标,从而进行存储。

  • 执行用时:4 ms, 在所有 Java 提交中击败了15.78%的用户
  • 内存消耗:38.5 MB, 在所有 Java 提交中击败了57.22%的用户
 1class Solution {
 2    public String reverseStr(String s, int k) {
 3        StringBuilder stringBuilder = new StringBuilder();
 4        int left = 0, right = k - 1;
 5        while (right < s.length()) {
 6            int tmpRight = right;
 7            // 将前k个字符反转后存起来
 8            while (left <= tmpRight) {
 9                stringBuilder.append(s.charAt(tmpRight--));
10            }
11            // 右指针向后移动 k 个位置
12            left = right + 1;
13            right += k;
14            // 再将 k 个字符正序存起来
15            if (right >= s.length()) {
16                tmpRight = s.length() - 1;
17            } else {
18                tmpRight = right;
19            }
20            stringBuilder.append(s, left, tmpRight + 1);
21            left = right + 1;
22            right += k;
23        }
24        // 如果后面还存在字符,以反序存起来
25        if (stringBuilder.length() != s.length()) {
26            right = s.length() - 1;
27            while (left <= right) {
28                stringBuilder.append(s.charAt(right--));
29            }
30        }
31        return stringBuilder.toString();
32    }
33}

看题解后

方法二:双指针(char[])

  • 执行用时:1 ms, 在所有 Java 提交中击败了99.70%的用户
  • 内存消耗:38.4 MB, 在所有 Java 提交中击败了75.32%的用户
 1class Solution {
 2    public String reverseStr(String s, int k) {
 3        char[] array = s.toCharArray();
 4        int left, right;
 5        for (int i = 0; i < s.length(); i += 2 * k) {
 6            left = i;
 7            // 防止越界
 8            right = Math.min(i + k - 1, s.length() - 1);
 9            // 对 [left, right] 区间的字符串进行反转
10            while (left < right) {
11                char tmp = array[left];
12                array[left++] = array[right];
13                array[right--] = tmp;
14            }
15        }
16        return new String(array);
17    }
18}

3、反转字符串中的单词 III(简单)

自己的想法

方法一:双指针

  • 执行用时:7 ms, 在所有 Java 提交中击败了64.97%的用户
  • 内存消耗:39.1 MB, 在所有 Java 提交中击败了56.22%的用户
 1class Solution {
 2    public String reverseWords(String s) {
 3        char[] array = s.toCharArray();
 4        int left = 0, right;
 5        for (int i = 0; i < array.length; i++) {
 6            // 确定单词的起始下标
 7            if ((i == 0 || array[i - 1] == ' ') && array[i] != ' ') {
 8                left = i;
 9            }
10            // 确定单词的结束下标
11            if (array[i] != ' ' && (i + 1 == array.length || array[i + 1] == ' ')) {
12                right = i;
13                // 对单词进行翻转
14                while (left < right) {
15                    char tmp = array[left];
16                    array[left++] = array[right];
17                    array[right--] = tmp;
18                }
19            }
20        }
21        return new String(array);
22    }
23}

看题解后

  优化:不单独寻找单词的开始下标。

  • 执行用时:3 ms, 在所有 Java 提交中击败了99.88%的用户
  • 内存消耗:39 MB, 在所有 Java 提交中击败了75.16%的用户
 1class Solution {
 2    public String reverseWords(String s) {
 3        char[] array = s.toCharArray();
 4        int left = 0, right = 0;
 5        while (right < array.length) {
 6            // 寻找当前单词的结尾
 7            while (right < array.length && array[right] != ' '){
 8                right++;
 9            }
10            // 翻转找到的单词
11            sawp(array, left, right - 1);
12            // 指针向后移动
13            left = right + 1;
14            right = left;
15        }
16        // 翻转最后一个单词
17        sawp(array, left, right - 1);
18        return new String(array);
19    }
20
21    public void sawp (char[] array, int left, int right) {
22        char c;
23        while (left < right) {
24            c = array[left];
25            array[left++] = array[right];
26            array[right--] = c;
27        }
28    }
29}

4、翻转字符串里的单词(简单)

自己的想法

方法一:双指针(从后往前)

  使用两个指针从后往前扫描,每扫到一个单词,将其加入 StringBuilder 中。

  • 执行用时:3 ms, 在所有 Java 提交中击败了94.83%的用户
  • 内存消耗:38.4 MB, 在所有 Java 提交中击败了86.55%的用户
 1class Solution {
 2    public String reverseWords(String s) {
 3        StringBuilder stringBuilder = new StringBuilder();
 4        int left = s.length() - 1, right = s.length() - 1;
 5        // 从后往前查找单词
 6        while (left >= 0) {
 7            // 如果有空格或者越界,则表示 left+1 就是单词
 8            while (left >= 0 && s.charAt(left) != ' ') {
 9                left--;
10            }
11            if (left != right) {
12                stringBuilder.append(s, left + 1, right + 1).append(' ');
13            }
14            // 指针向前移动
15            left = left - 1;
16            right = left;
17        }
18        // 删除最后多余的空格
19        return stringBuilder.deleteCharAt(stringBuilder.length() - 1).toString();
20    }
21}

看题解后

方法二:API

  使用 Java 的语言特性,首先去掉首位空格,然后对其进行分割反序,最后以空格为分隔符生成字符串。

  • 执行用时:11 ms, 在所有 Java 提交中击败了36.34%的用户
  • 内存消耗:38.9 MB, 在所有 Java 提交中击败了21.04%的用户
 1class Solution {
 2    public String reverseWords(String s) {
 3        // 除去开头和末尾的空白字符
 4        s = s.trim();
 5        // 正则匹配连续的空白字符作为分隔符分割
 6        List<String> wordList = Arrays.asList(s.split("\\s+"));
 7        Collections.reverse(wordList);
 8        return String.join(" ", wordList);
 9    }
10}

方法三:双指针(从前往后)

  从前往后递归查找,将先查到的单词压栈,然后查找下一个单词,最后再添加。

  • 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:38.9 MB, 在所有 Java 提交中击败了22.14%的用户
 1class Solution {
 2
 3    public String reverseWords(String s) {
 4        StringBuilder stringBuilder = new StringBuilder();
 5        getReverseWords(s, stringBuilder, 0);
 6        return stringBuilder.toString().trim();
 7    }
 8
 9    public void getReverseWords(String s, StringBuilder stringBuilder, int left) {
10        // 确定单词的左边界
11        while (left < s.length() && s.charAt(left) == ' ') {
12            left++;
13        }
14        if (left == s.length()) {
15            return;
16        }
17        int right = left;
18        // 确定单词的右边界
19        while (right < s.length() && s.charAt(right) != ' ') {
20            right++;
21        }
22        // 查找下一个单词
23        getReverseWords(s, stringBuilder, right);
24        // 添加单词
25        stringBuilder.append(s, left, right).append(" ");
26    }
27}

二、单词相关操作

1、字符串中的单词数(简单)

自己的想法

方法一:统计空格个数

  首先去掉字符串的首尾空格,然后遍历字符串,每发现一段空格就将单词数加一,最后再将单词数加一。

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36 MB, 在所有 Java 提交中击败了93.77%的用户
 1class Solution {
 2    public int countSegments(String s) {
 3        // 去掉字符串的首尾空格
 4        s = s.trim();
 5        if (s.length() == 0){
 6            return 0;
 7        }
 8        int count = 0;
 9        byte[] bytes = s.getBytes();
10        for (int i = 0; i < bytes.length; i++) {
11            // 如果当前为空格则进行判断
12            if (bytes[i] == ' ') {
13                // 寻找下一个字符
14                while (i < bytes.length && bytes[i] == ' '){
15                    i++;
16                }
17                count++;
18            }
19        }
20        return count + 1;
21    }
22}

看题解后

方法二:使用内置函数

  使用 String 类的 split 方法对字符串进行分割。

  • 执行用时:3 ms, 在所有 Java 提交中击败了24.43%的用户
  • 内存消耗:36.4 MB, 在所有 Java 提交中击败了37.56%的用户
1class Solution {
2    public int countSegments(String s) {
3        String str = s.trim();
4        if (str.equals("")) {
5            return 0;
6        }
7        return str.split("\\s+").length;
8    }
9}

方法三:原地判断

  使用 charAt 方法获取字符串中的指定字符。前一个字符为空格,当前字符不是空格,则表示这是一个单词。

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:35.8 MB, 在所有 Java 提交中击败了99.18%的用户
 1class Solution {
 2    public int countSegments(String s) {
 3        int count = 0;
 4        for (int i = 0; i < s.length(); i++) {
 5            // 前一个字符为空格,当前字符不是空格,则表示这是一个单词
 6            if ((i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != ' ') {
 7                count++;
 8            }
 9        }
10        return count;
11    }
12}

2、最后一个单词的长度(简单)

自己的想法

方法一:从右向左遍历

  从右向左遍历,寻找第一个单词,并获取其长度。

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.6 MB, 在所有 Java 提交中击败了84.02%的用户
 1class Solution {
 2    public int lengthOfLastWord(String s) {
 3        int count = 0;
 4        int i = s.length() - 1;
 5        // 从右向左遍历,寻找第一个单词
 6        for (; i >= 0; i--) {
 7            if (s.charAt(i) != ' ') {
 8                break;
 9            }
10        }
11        // 获取单词的长度
12        for (; i >= 0; i--) {
13            if (s.charAt(i) == ' ') {
14                break;
15            }
16            count++;
17        }
18        return count;
19    }
20}

看题解后

  代码简化。

 1class Solution {
 2    public int lengthOfLastWord(String s) {
 3        int count = 0;
 4        // 从右向左遍历,寻找第一个单词,并获取其长度。
 5        for (int i = s.length() - 1; i >= 0; i--) {
 6            if (s.charAt(i) == ' ') {
 7                if (count == 0) {
 8                    continue;
 9                }
10                break;
11            }
12            count++;
13        }
14        return count;
15    }
16}

3、检测大写字母(简单)

方法一:记录大写字母的个数,然后进行判断

  • 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.9 MB, 在所有 Java 提交中击败了55.61%的用户
 1class Solution {
 2    public boolean detectCapitalUse(String word) {
 3        byte[] wordBytes = word.getBytes();
 4        // 记录大写字母的个数
 5        int large = 0;
 6        for (byte i : wordBytes) {
 7            if (i < 91) {
 8                large++;
 9            }
10        }
11        // 如果大写字母的个数大于一个,则所有字母都必须是大写字母
12        if (large > 1) {
13            return large == word.length();
14        } else if (large == 1) {
15            // 如果大小字母的个数为 1 个,则第一个字母必须为大写字母
16            return wordBytes[0] < 91;
17        }
18        return true;
19    }
20}

4、验证回文串(简单)

自己的想法

方法一:双指针(使用 byte[])

  使用两个指针分别指向字符串的头和尾,然后判断两个指针指向的值是否相等,不相等则返回 false。在判断前必须确保指针指向的值是合法的(数字和字母,并需将大写字母转为小写字母)。

  • 执行用时:3 ms, 在所有 Java 提交中击败了93.21%的用户
  • 内存消耗:38.6 MB, 在所有 Java 提交中击败了70.58%的用户
 1class Solution {
 2    public boolean isPalindrome(String s) {
 3        if (s.length() == 0) {
 4            return true;
 5        }
 6        byte[] bytes = s.getBytes();
 7        int left = getLeft(0, bytes);
 8        int right = getRight(s.length() - 1, bytes);
 9        while (left < right) {
10            // 如果不相等直接结束
11            if (bytes[left++] != bytes[right--]) {
12                return false;
13            }
14            left = getLeft(left, bytes);
15            right = getRight(right, bytes);
16        }
17        return true;
18    }
19
20    public byte isValid(byte value) {
21        // 如果是大写字母,则转为小写字母
22        if (value >= 'A' && value <= 'Z') {
23            return (byte) (value + 32);
24        }
25        // 如果是小写字母和数字则返回
26        if ((value >= '0' && value <= '9') || (value >= 'a' && value <= 'z')) {
27            return value;
28        }
29        return -1;
30    }
31
32    // 寻找有效的左元素
33    public int getLeft(int left, byte[] bytes) {
34        while (left < bytes.length) {
35            byte tmp = isValid(bytes[left]);
36            // 找到合法的左元素返回
37            if (tmp != -1) {
38                bytes[left] = tmp;
39                return left;
40            }
41            left++;
42        }
43        return left;
44    }
45
46    // 寻找有效的右元素
47    public int getRight(int right, byte[] bytes) {
48        while (right >= 0) {
49            byte tmp = isValid(bytes[right]);
50            // 找到合法的右元素返回
51            if (tmp != -1) {
52                bytes[right] = tmp;
53                return right;
54            }
55            right--;
56        }
57        return right;
58    }
59}

看题解后

方法二:双指针(使用 StringBuilder)

  • 执行用时:5 ms, 在所有 Java 提交中击败了49.57%的用户
  • 内存消耗:38.6 MB, 在所有 Java 提交中击败了71.57%的用户
 1class Solution {
 2    public boolean isPalindrome(String s) {
 3        StringBuilder string = new StringBuilder();
 4        // 将合法的字符添加到 string 中
 5        for (int i = 0; i < s.length(); i++) {
 6            char ch = s.charAt(i);
 7            if (Character.isLetterOrDigit(ch)) {
 8                string.append(Character.toLowerCase(ch));
 9            }
10        }
11        int left = 0, right = string.length() - 1;
12        // 使用双指针进行遍历
13        while (left < right) {
14            if (string.charAt(left++) != string.charAt(right--)) {
15                return false;
16            }
17        }
18        return true;
19    }
20}

方法三:双指针(在原字符串上判断)

  • 执行用时:3 ms, 在所有 Java 提交中击败了93.21%的用户
  • 内存消耗:38.4 MB, 在所有 Java 提交中击败了84.85%的用户
 1class Solution {
 2    public boolean isPalindrome(String s) {
 3        int n = s.length();
 4        int left = 0, right = n - 1;
 5        while (left < right) {
 6            // 将指针移动到合法的位置
 7            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
 8                left++;
 9            }
10            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
11                right--;
12            }
13            if (left < right) {
14                if (Character.toLowerCase(s.charAt(left++)) != Character.toLowerCase(s.charAt(right--))) {
15                    return false;
16                }
17            }
18        }
19        return true;
20    }
21}

方法四:筛选 + 反转

  首先对字符串进行筛选,找出合法的字符组成字符串,然后将字符串进行反转比较。

  • 执行用时:6 ms, 在所有 Java 提交中击败了35.53%的用户
  • 内存消耗:38.6 MB, 在所有 Java 提交中击败了61.76%的用户
 1class Solution {
 2    public boolean isPalindrome(String s) {
 3        StringBuilder string = new StringBuilder();
 4        int length = s.length();
 5        for (int i = 0; i < length; i++) {
 6            char ch = s.charAt(i);
 7            // 判断指定的字符是否是字母或数字。
 8            if (Character.isLetterOrDigit(ch)) {
 9                // 将大写字母转为小写字母
10                string.append(Character.toLowerCase(ch));
11            }
12        }
13        // 对字符串进行翻转
14        StringBuilder stringReverse = new StringBuilder(string).reverse();
15        return string.toString().equals(stringReverse.toString());
16    }
17}

标题:字符串的反转和单词相关操作——LeetCode
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2021/04/04/1617544219911.html
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!