【LeetCode】反转字符串 IIJava 题解

关注

发布于: 2 小时前

题目描述

给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。

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

示例 1：
输入：s = "abcdefg", k = 2输出："bacdfeg"示例 2：
输入：s = "abcd", k = 2输出："bacd"
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-string-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的每日一题是字符串反转题目，题干容易理解，反转的函数就是常用的 swap 函数增加指针的移动。
按照题意，可以首先写出朴素代码，经过测试，朴素代码可以通过测试。
朴素代码通过之后，翻看题解，一看到官方题解，瞬间感觉到自己还有很大的提升空间。反转每个下标从 2k 的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串。
这里的理解很厉害，比题干优化了很多，根据这个理解，可以写出优化的代码。

通过代码

朴素代码

public String reverseStr(String s, int k) {        int i = 0;        int idx = 0;        char[] charArray = s.toCharArray();        int n = charArray.length;        for (int j = 0; j < n; j++) {            i++;            if (i == 2 * k) {                swap(idx, idx + k - 1, charArray);                idx = j + 1;                i = 0;            }        }        if (i > 0 && i < k) {            swap(idx, idx + i - 1, charArray);        } else if (i > 0 && i < 2 * k) {            int end = Math.min(idx + k - 1, n - 1);            swap(idx, end, charArray);        }                return new String(charArray);    }
    public void swap(int left ,int right, char[] arr) {        while (left < right) {            char temp = arr[left];            arr[left] = arr[right];            arr[right] = temp;            left++;            right--;        }    }

复制代码

优化代码

    public String reverseStr(String s, int k) {        char[] charArray = s.toCharArray();        int n = charArray.length;        for (int i = 0; i < n; i += 2 * k) {            int end = Math.min(i + k, n) - 1;            swap(i, end, charArray);        }                return new String(charArray);    }
    public void swap(int left ,int right, char[] arr) {        while (left < right) {            char temp = arr[left];            arr[left] = arr[right];            arr[right] = temp;            left++;            right--;        }    }

复制代码

总结

上述代码的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持算法每日一题，加油！在算法学习过程中，每次提交通过之后，还要学习优秀的代码的解决方案，进而转换成为自己的解法，提升能力！

发布于: 2 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/afdb0c140a9487f57c4957924】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】反转字符串 IIJava 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论