【LeetCode】541. 反转字符串 II

in #programming15 days ago

1 题目描述

541. 反转字符串 II给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。如果剩余字符少于 k 个,则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。

2 解题思路

  1. 转换为字符数组:首先将字符串转换为字符数组,方便进行字符的交换。
  2. 循环遍历并反转:使用一个指针 i 从字符串的开头开始,每次增加 2k 个位置,确定需要反转的子串范围,并执行反转操作。
  3. 反转操作:对于每个子串,定义两个指针 leftright 分别指向子串的开始和结束位置,然后交换这两个位置上的字符,直到 left 不再小于 right

3 Java 代码实现

public class Solution {
    public String reverseStr(String s, int k) {
        // 将字符串转换为字符数组
        char[] ch = s.toCharArray();

        // 每隔 2k 个字符进行反转操作
        for (int i = 0; i < ch.length; i += 2 * k) {
            // 计算反转区间的左右边界
            int left = i;
            int right = Math.min(ch.length - 1, i + k - 1);

            // 执行反转操作
            while (left < right) {
                char temp = ch[left];
                ch[left] = ch[right];
                ch[right] = temp;
                left++;
                right--;
            }
        }

        // 将字符数组转换回字符串并返回
        return new String(ch);
    }
}
  • 时间复杂度: O(n),其中 n 是字符串的长度。、
  • 空间复杂度: O(n),需要额外的字符数组来存储字符。

4 注意事项

  • 字符数组转换:首先将字符串转换为字符数组 ch,便于进行字符的交换操作。
  • 循环步长:每次循环步长为 2k,这是因为我们要处理每 2k 个字符中的前 k 个字符。
  • 反转区间:反转区间的左端点为 left,右端点为 right,其中 right 需要考虑字符串的实际长度,不能超过。
  • 反转操作:使用临时变量 temp 进行字符的交换操作。
  • 返回结果:最后将字符数组转换回字符串返回。

Coin Marketplace

STEEM 0.19
TRX 0.18
JST 0.033
BTC 88172.86
ETH 3116.36
USDT 1.00
SBD 2.77