这是悦乐书的第 256 次更新, 第 269 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 123 题(顺位题号是 541). 给定一个字符串和一个整数 k, 你需要反转从字符串开头算起的每 2k 个字符的前 k 个字符. 如果剩下少于 k 个字符, 则反转所有字符. 如果小于 2k 但大于等于 k 个字符, 则反转前 k 个字符, 剩下的字符不变. 例如:
输入: s ="abcdefg",k = 2
输出:"bacdfeg"
注意:
该字符串仅包含小写的英文字母.
给定字符串的长度和 k 将在 [1,10000] 范围内.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
根据题意, 如果一个字符串的长度为 n, 每隔 k 位 (从 0 开始) 反转 k 位字符, 如当 k 等于 2 时, 0-1 位字符反转, 2-3 位不变, 4-5 位反转, 依次往后, 直到处理完所有字符. 所以可以直接使用 for 循环, 每次循环处理 2k 个字符, 借助 StringBuilder 类, 第一次截取 i 到 i+k 长度的子串, 此子串进行反转, 第二次截取 i+k 到 i+2k 长度的子串, 此子串不需要反转, 对字符串进行截取的时候, 需要判断是否超出字符串长度.
- public String reverseStr(String s, int k) {
- if (k == 1) {
- return s;
- }
- StringBuilder sb = new StringBuilder();
- for (int i=0; i<s.length(); i += 2*k) {
- StringBuilder temp = new StringBuilder();
- // 如果 i 加 k 后, 超出字符串长度, 直接反转剩下的字符即可, 否则就截取 k 长度的子串
- temp.append(s.substring(i, i+k> s.length() ? s.length() : i+k));
- temp.reverse();
- // 如果 i 加 k 小于字符串长度, 才会去继续截取后面剩下的子串
- if (i+k <s.length()) {
- temp.append(s.substring(i+k, i+2*k> s.length() ? s.length() : i+2*k));
- }
- sb.append(temp.toString());
- }
- return sb.toString();
- }
03 第二种解法
我们也可以操作字符, 不使用截取字符串的办法. 将 s 转为字符数组, 每次循环, 处理 2k 个字符, 然后对前 k 个字符进行反转(换位置), 进行字符互换的时候, 需要使用经典的三行代码:
- char temp = arr[start];
- arr[start] = arr[end];
- arr[end] = temp;
很好记住, 首尾相连即可. 同样, 此解法也需要考虑下标越界的问题, 所以 end 会在当前起始索引, 字符数组长度 (字符串长度) 之间取最小值.
- public String reverseStr2(String s, int k) {
- if (k == 1) {
- return s;
- }
- char[] arr = s.toCharArray();
- for (int i=0; i<arr.length; i += 2*k) {
- int start = i;
- int end = Math.min(start+k-1, arr.length-1);
- while (start < end) {
- char temp = arr[start];
- arr[start] = arr[end];
- arr[end] = temp;
- start++;
- end--;
- }
- }
- return new String(arr);
- }
04 小结
算法专题目前已日更超过三个月, 算法题文章 123 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/0f5136f16728