写点什么

【LeetCode】反转字符串 IIJava 题解

用户头像
HQ数字卡
关注
发布于: 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
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】反转字符串 IIJava题解