LEETCODE 541. Reverse String II 解题思路分析

题目大意:

反转字符串 II

给定一个字符串和一个整数 k,你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符,则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符,则反转前 k 个字符,并将剩余的字符保持原样。

示例:

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

要求:

  1. 该字符串只包含小写的英文字母。
  2. 给定字符串的长度和 k 在[1, 10000]范围内。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=541

解题思路分析:

本题是LEETCODE 344. Reverse String 解题思路分析的续集,相比于上一集,本题是将字符串分成了n等份,每份长度为k*2,然后我们将每一份的前k个字符进行翻转,后k个字符保持不变。

解题时,我们定义一个变量start,来记录我们当前所在的区间,该区间内的翻转范围左端是start,右端是start+k-1,即翻转区间长度为k,另外需要注意一点,如果右端大于等于字符串长度时,说明右端越界,右端应设为字符串末尾位置。定义好翻转区间后,我们利用上一篇的方式对区间内字符进行翻转。操作结束之后,我们将当前区间向后移动k*2个位置,即start变为 start + k*2;

实现代码:

public String reverseStr(String s, int k) {
    char[] arr = s.toCharArray();
    int start=0;
    while(start<arr.length){
        int l=start, r=start+k-1;
        if(r>=arr.length){
            r=arr.length-1;
        }
        while(l<r){
            arr[l]^=arr[r];
            arr[r]^=arr[l];
            arr[l]^=arr[r];
            l++;
            r--;
        }
        start+=2*k;
    }
    return new String(arr);
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 79.20% of Java online submissions for Reverse String II.

Memory Usage: 39.5 MB, less than 7.41% of Java online submissions for Reverse String II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-541-reverse-string-ii-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。