🚀 算法题 🚀 |
---|
🚀 算法题 🚀 |
---|
给定一个字符串 S,返回 “反转后的” 字符串,其中不是字母的字符都保留在原地,而所有字母的位置发生反转。
示例1:
输入:"ab-cd"
输出:"dc-ba"
示例2:
输入:"a-bC-dEf-ghIj"
输出:"j-Ih-gfE-dCba"
示例3:
输入:"Test1ng-Leet=code-Q!"
输出:"Qedo1ct-eeLg=ntse-T!"
提示:
两次循环,一次添加字母,一次添加其他
代码:
public class Solution
{
public string ReverseOnlyLetters(string s)
{
string result = "";
int n = s.Length;
for (int i = n - 1; i >= 0; i--)
{
if (char.IsLetter(s[i])) result += s[i];
}
for (int i = 0; i < n; i++)
{
if (!char.IsLetter(s[i]))
result = result.Insert(i, s[i].ToString());
}
return result;
}
}
执行结果
通过
执行用时:88 ms,在所有 C# 提交中击败了47.14%的用户
内存消耗:35.9 MB,在所有 C# 提交中击败了8.70%的用户
思路解析 将 s 中的所有字母单独存入栈中,所以出栈等价于对字母反序操作。(或者,可以用数组存储字母并反序数组。)
然后,遍历 s 的所有字符,如果是字母我们就选择栈顶元素输出。
代码:
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();
}
}
执行结果
通过
执行用时:1 ms,在所有 Java 提交中击败了48.41%的用户
内存消耗:36.4 MB,在所有 Java 提交中击败了6.53%的用户
复杂度分析
时间复杂度:O( n ),其中 N 是 S 的长度。
空间复杂度:O(n)
C#
和 Java
两种编程语言进行解题发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/183760.html原文链接:https://javaforall.cn