leetcode
leetcode 151 ~ 200
反转字符串中的单词 II

反转字符串中的单词 II

难度:

标签:

题目描述

代码结果

运行时间: 29 ms, 内存: 20.5 MB

/*
 * LeetCode 题目：反转字符串中的单词 II
 * 题目思路：
 * 1. 使用Java Stream来简化操作
 * 2. 将字符串拆分为单词数组，然后反转单词数组，再将反转后的单词数组拼接回字符串
 * 例如：
 * 输入: "the sky is blue"
 * 处理过程："blue is sky the"
 */
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
 
public class ReverseWordsInStringIIStream {
    public static void main(String[] args) {
        String s = "the sky is blue";
        System.out.println(reverseWords(s));
    }
 
    public static String reverseWords(String s) {
        List<String> words = Arrays.asList(s.split(" "));
        Collections.reverse(words);
        return words.stream().collect(Collectors.joining(" "));
    }
}

解释

方法:

此题解的主要思路是先对整个字符串数组进行一次完整的反转，然后再逐个反转每个单词以恢复其原始顺序。首先，使用一个辅助函数‘reverse’来实现数组的局部反转。在第一步中，调用这个函数将整个字符串数组从头到尾反转。之后，遍历反转后的数组，每当遇到空格字符时，就反转前一个单词（即从上一个空格后到当前空格前的部分）。对于最后一个单词，因为后面没有空格，所以在循环结束后单独进行反转。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
此算法中的`reverse`函数是如何确保在反转时不会出现索引越界的问题？
▷
在`reverse`函数中，通过确保传入的`left`和`right`指针始终在有效的数组索引范围内来避免索引越界。函数设计时，调用者需传入有效的起始和结束索引，函数内部通过while循环控制`left`小于`right`条件，确保每次交换都是在合法的范围内。此外，在主函数`reverseWords`中调用`reverse`时，都是基于已确定存在的空格位置或字符串边界，进一步确保了索引的有效性。
🦆
在函数`reverseWords`中，为何选择先反转整个字符串，再逐个反转单词，这样的顺序有何优势或必要性？
▷
选择先整体反转字符串再逐个单词反转的方法，主要是为了方便和效率。整体反转后，原本位于字符串末尾的单词到了开头，但单词内字符的顺序也被反转了。这样只需再逐个反转每个单词内部的字符，就能将整个句子中单词的顺序和每个单词内的字符顺序都恢复到正确状态。这种方法避免了复杂的位置计算，只需要两次扫描：一次全字符串反转，一次遍历单词进行反转，从而提高了算法的效率。
🦆
对于字符串数组中没有空格的情况，此算法是否有特殊处理，或者说算法如何处理这种边界情况？
▷
在没有空格的情况下，即整个字符串数组被视为一个单独的单词，算法依然有效。首先，整个字符串被反转，此时由于只有一个单词，所以整个字符串即为单词本身且顺序已经反转。接着，在`reverseWords`函数中，因为找不到空格来标识单词的结束，所以整个字符串只会在最后被单独反转一次。这样，字符串中的字符顺序又被恢复到原始顺序。因此，算法不需要特殊处理这种情况，它自然地处理了只有一个单词的边界情况。

相关问题

反转字符串中的单词

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

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

 

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

 

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

 

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

 

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
最大数重复的DNA序列