leetcode
leetcode 501 ~ 550
反转字符串 II

反转字符串 II

难度:

标签:

题目描述

给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个,则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。

 

示例 1:

输入:s = "abcdefg", k = 2
输出:"bacdfeg"

示例 2:

输入:s = "abcd", k = 2
输出:"bacd"

 

提示:

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104

代码结果

运行时间: 19 ms, 内存: 16.0 MB


/*
 * 题目思路:
 * 使用 Java Stream 实现类似的反转逻辑。我们仍然需要按照每 2k 个字符进行操作,
 * 并对前 k 个字符进行反转。
 */
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
    public String reverseStr(String s, int k) {
        return IntStream.range(0, s.length())
            .mapToObj(i -> new AbstractMap.SimpleEntry<>(i, s.charAt(i)))
            .collect(Collectors.groupingBy(e -> e.getKey() / (2 * k)))
            .values().stream()
            .flatMap(group -> {
                List<Map.Entry<Integer, Character>> subList = new ArrayList<>(group);
                int limit = Math.min(k, subList.size());
                IntStream.range(0, limit / 2).forEach(j -> {
                    Collections.swap(subList, j, limit - j - 1);
                });
                return subList.stream();
            })
            .sorted(Map.Entry.comparingByKey())
            .map(Map.Entry::getValue)
            .map(String::valueOf)
            .collect(Collectors.joining());
    }
}

解释

方法:

该题解采用遍历字符串的方式,每次步进2k个字符,处理每个分段。对每个分段的前k个字符进行反转,并将反转后的字符串与该分段的后k个字符(如果存在)相连,累加到结果字符串中。这样可以确保每次处理都符合题目的要求,即每2k个字符中的前k个字符被反转,后k个字符保持不变。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在遍历的过程中,如何确保代码正确处理字符串最后的字符,特别是当字符串长度不是2k的倍数时?
在Python中,字符串切片操作s[i:j]会在索引i到j-1的范围内提取字符。如果j超出了字符串的实际长度,切片操作会自动停止在字符串的末尾,不会引起错误。因此,通过在每次循环中尝试取i到i+k和i+k到i+2k的切片,代码自动适应了字符串长度不是2k倍数的情况。对于最后一个分段,如果长度小于k,会反转整个分段;如果长度在k和2k之间,只有前k个字符被反转,剩余的字符保持原样。
🦆
对于长度极小或极大的k值(接近1或104),有没有可能导致性能问题?如果有,如何优化?
当k值非常小(如1)时,每次反转仅涉及一个字符,这在性能上不是问题。但当k值非常大时,反转操作可能涉及大量字符,这可能导致显著的性能下降,尤其是在字符串本身长度也很大的情况下。为了优化,可以考虑使用更高效的数据结构,如列表(数组),因为列表的元素更新比字符串(不可变)更高效。将字符串转换为列表,进行反转操作后,再将列表转换回字符串可以提高性能。
🦆
在实际的字符串操作中,是否考虑了Python字符串的不可变特性对性能的影响?如果考虑了,是如何优化的?
Python中的字符串是不可变的,这意味着每次修改字符串实际上都会创建一个新的字符串对象。这在反复操作大型字符串时可能导致性能问题。在题解中,通过构建一个新的字符串并累加结果来避免反复修改原始字符串。此外,可以进一步优化性能,通过使用列表来存储各个部分的字符串,最后使用join方法将它们合并成一个字符串,这样可以减少创建不必要的中间字符串。
🦆
代码中对于`i + k`和`i + 2 * k`范围超出字符串长度的情况有没有做特殊处理?如果没有,Python是如何处理这种情况的?
代码中没有特别处理`i + k`和`i + 2 * k`范围超出字符串长度的情况,因为Python的切片操作自然地处理了这种情况。如果切片的结束索引超出了字符串的长度,Python将只返回从开始索引到字符串末尾的子字符串。这种行为确保了即使在字符串的末尾也不会产生错误或需要额外的逻辑来处理边界条件。

相关问题

反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

 

示例 1:

输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例 2:

输入:s = ["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

 

提示:

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符

反转字符串中的单词 III

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

 

示例 1:

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

示例 2:

输入: s = "Mr Ding"
输出:"rM gniD"

 

提示:

  • 1 <= s.length <= 5 * 104
  • s 包含可打印的 ASCII 字符。
  • s 不包含任何开头或结尾空格。
  • s 里 至少 有一个词。
  • s 中的所有单词都用一个空格隔开。