【算法千题案例】每日LeetCode打卡——84.反转字符串中的单词 III

​​​​

  • ​​????原题样例:反转字符串中的单词 III​​
    • ​​????C#方法:使用额外空间​​
    • ​​????Java 方法:使用额外空间​​
  • linux操作系统基础知识​????总结​​

????字符前言系统运维工作内容

???? 算法题 ????

???? 算法题 ????


????原题样例:反转字符串中的单词 III

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

示例1:

输入:"Let's take LeetCode contest"
输出:"s'teL ekat edoCteeL tsetnoc"

提示:

  • 在字符串中,每个单词由单个空格分隔,并且字符串中不会有任何额外的空格。

????C#方法:使用额外空间

  • 开辟一个新字符串。然后算法是什么从头到尾贪心算法背包问题遍历原字符串,直到找到空格为止,此时找到了一个单词,并能得到单词的起止位置
  • 随后,根据单词的起算法的三种基本结构止位置,可以将该单词逆序放到新字符串当中。如此循环多次,直到遍历完原字符串,就能得到翻转后的结果。

代码

public class Solution {
public string ReverseWords(string str) {
string[] arrStr = str.Split(' ');
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < arrStr.Length; i++)
{
for (int j = arrStr[i].Length - 1; j >= 0; j--)
{
stringBuilder.Append(arrStr[i][j]);
}
stringBuilder.Append(" ");
}
stringBuilder.Remove(str.Length, 1);
return stringBuilder.ToString();
}
}

执行结果

通过
执行用时:96 ms,在所有 C# 提交中击败了49.50%的用户
内存消耗43.4 MB,在所有 C# 提交中击败了31.90%的用户

????Java 方法:使用额外空间

思路解析

  • 开辟一个新字符串。然后从头到尾遍历原字符串,直到找到空格为止,此时找到了一个单词,并能得到单词的起止位置
  • 随后,根据单词的起止位置,可以将该单词逆序放到新字符串当中。如此循环多次,直到遍历完原字符串leetcode是什么,就能得到翻转后的结果。

代码

class Solution {
public String reverseWords(String s) {
StringBuffer ret = new StringBuffer();
int length = s.length();
int i = 0;
while (i < length) {
int start = i;
while (i < length &amp;&amp; s.charAt(i) != ' ') {
i++;
}
for (int p = start; p < i; p++) {
ret.append(s.charAt(start + i - 1 - p));
}
while (i < length && s.charAt(i) == ' ') {
i++;
ret.append(' ');
}
}
return ret.toString();
}
}

结果

通过
执行用时:7 ms,在所有 Java 提交中击败了38.76%的用户
内存消耗:38.9 MB,在所有 Java 提交中击败了74.40%的用户

复杂度分析

时间复杂度:O( n )
空间复杂度:O(n)