CTF of Z2BNS
0%

仅仅反转字母

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 773 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

示例1：

1
2
输入："ab-cd"
输出："dc-ba"

示例2：

1
2
输入："a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"

示例3：

1
2
输入："Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"

提示：

  1. S.length <= 100
  2. 33 <= S[i].ASCIIcode <= 122
  3. S 中不包含 \ or "
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：双指针法，索引i从前向后查找字母，索引j从后向前查找字母，然后使用swap交换前后两个字母。

c++代码：(执行用时4ms，击败34.86%，内存消耗5.9M，击败89.58%）

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 reverseOnlyLetters(string S) {
        int tmp1=0;
        int tmp2=0;
        int j=S.length()-1;
        for(int i=0;i<j;){
            tmp1=S[i];
            tmp2=S[j];
            if(tmp1>64&&tmp1<91 || tmp1>96&&tmp1<123){
                if(tmp2>64&&tmp2<91 || tmp2>96&&tmp2<123){
                    swap(S[i],S[j]);
                    i++;
                    j--;
                }else{
                    j--;
                }
            }else{
                i++;
            }
        }
        return S;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：字母栈

想法和算法

将 s 中的所有字母单独存入栈中，所以出栈等价于对字母反序操作。（或者，可以用数组存储字母并反序数组。）

然后，遍历 s 的所有字符，如果是字母我们就选择栈顶元素输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String reverseOnlyLetters(String S) {
        Stack<Character> letters = new Stack();
        for (char c: S.toCharArray())
            if (Character.isLetter(c))
                letters.push(c);

        StringBuilder ans = new StringBuilder();
        for (char c: S.toCharArray()) {
            if (Character.isLetter(c))
                ans.append(letters.pop());
            else
                ans.append(c);
        }

        return ans.toString();
    }
}

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 是 S 的长度。
  • 空间复杂度：$O(N)$。

方法 2：反转指针

想法

一个接一个输出 s 的所有字符。当遇到一个字母时，我们希望找到逆序遍历字符串的下一个字母。

所以我们这么做：维护一个指针 j 从后往前遍历字符串，当需要字母时就使用它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String reverseOnlyLetters(String S) {
        StringBuilder ans = new StringBuilder();
        int j = S.length() - 1;
        for (int i = 0; i < S.length(); ++i) {
            if (Character.isLetter(S.charAt(i))) {
                while (!Character.isLetter(S.charAt(j)))
                    j--;
                ans.append(S.charAt(j--));
            } else {
                ans.append(S.charAt(i));
            }
        }

        return ans.toString();
    }
}

复杂度分析

  • 时间复杂度：O(N)，其中 N 是 S 的长度。
  • 空间复杂度：O(N)。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

嗯，字母栈方法也挺好的😮。

------------- THE END! THANKS! -------------