LeetCode算法题-Reverse String II(Java实现)
这是悦乐书的第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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Reverse String II(Java实现)